Jakie problemy statystyczne prawdopodobnie skorzystają na obliczeniach kwantowych?

Jesteśmy nadejściem obliczeń kwantowych , a języki kwantowe przewidują sprzętowe komputery kwantowe dostępne teraz na wysokim i niskim poziomie dla symulowanych komputerów kwantowych. Obliczenia kwantowe wprowadzają nowe elementarne funkcje, takie jak splątanie i teleportacja kubitów, pomiar kubitów i nakładanie superpozycji na kubity.

Jakie problemy statystyczne prawdopodobnie skorzystają na obliczeniach kwantowych?

Na przykład, czy komputery kwantowe zapewniają bardziej wszechstronne generowanie liczb losowych? A co z tanim obliczeniowo generowaniem liczb pseudolosowych? Czy obliczenia kwantowe pomogą przyspieszyć konwergencję MCMC, czy zapewnią górne granice czasu konwergencji? Czy będą istnieć algorytmy kwantowe dla innych estymatorów opartych na próbkowaniu?

To szerokie pytanie, a akceptowalne odpowiedzi będą również szerokie, ale uznanie, jeśli różnicują obliczenia kwantowe i klasyczne. (Jeśli jest to zbyt ogólne pytanie, pomóż mi uczynić je lepszym.)

Metody wykorzystujące siłę brutalną najprawdopodobniej skorzystają na tym, czym jest przetwarzanie kwantowe. Dlaczego? Jednym z możliwych fizycznych wyjaśnień ścieżki boiska baseballowego jest to, że wszystkie możliwe ścieżki kwantowe są automatycznie badane, a ścieżka najmniejszego wydatku energetycznego, tj. Ścieżka najmniejszego dostępnego oporu, jest wybierana i wszystko to odbywa się bez konieczności budowania kalkulatora ; obliczenia są niewysłowione. Uogólniające; naturę można postrzegać jako kalkulator kwantowy. Tak więc te problemy, które są podobne, optymalizujące, takie jak minimalizacja regresji jednego kryterium, takie jak dobro dopasowania lub inne (dobro dopasowania, w niektórych przypadkach źle postawione), będą tymi, które skorzystają.

BTW, etapy pośrednie; iteracje, w optymalizacji, nie byłyby obliczane, tylko wynik końcowy, tak jak w przypadku boiska do baseballu. Oznacza to, że występuje tylko rzeczywista ścieżka baseballu, alternatywne ścieżki są automatycznie wykluczane. Jedną różnicą między implementacją statystyczną a zdarzeniem fizycznym jest jednak to, że błąd obliczenia statystycznego może być tak mały, jak to pożądane, poprzez dowolne zwiększenie precyzji (np. Do 65 miejsc po przecinku), i nie jest to zazwyczaj fizycznie możliwe do osiągnięcia . Na przykład nawet maszyna do rzucania nie rzuci baseballu w dokładnie powieloną ścieżkę.

Podobała mi się powyższa odpowiedź na temat baseballu. Byłbym jednak ostrożny w kwestii tego, co komputer kwantowy może zrobić dobrze.

Wygląda na to, że radzi sobie bardzo dobrze w takich sprawach, jak łamanie schematów kryptograficznych i tym podobne: możliwość nałożenia wszystkich rozwiązań, a następnie upadku na rzeczywiste, może pójść dość szybko.

Ale w latach 80. - bardzo dawno temu - istniała bardzo znana firma o nazwie Thinking Machines. Zobacz ten artykuł: https://en.wikipedia.org/wiki/Thinking_Machines_Corporation

Cały pomysł miał powiew informatyki kwantowej. Wykorzystano n-wymiarowy układ hipersześcianu. Wyobraź sobie, jeśli chcesz, cztery (bardzo proste) mikroprocesory połączone w kwadrat. Każdy może wykonać obliczenia, a następnie udostępnić wynik procesorowi przed nim (przeciwnie do ruchu wskazówek zegara), po nim (zgodnie z ruchem wskazówek zegara) lub przeciwnie (przeciwnie). Następnie wyobraź sobie 8 procesorów w sześcianie, które mogą rozwinąć tę koncepcję do trzech wymiarów (każdy procesor może teraz dzielić swoją moc wyjściową z jednym lub więcej z 7 innych: 3 wzdłuż wierzchołka sześcianu; trzy wzdłuż powierzchni kwadratu procesor był częścią i jedna przekątna w 3-spacji).

Teraz weźmy to, może do 64 procesorów w 6-wymiarowej hipersześcianie.

Był to jeden z najgorętszych pomysłów tamtych czasów (wraz z dedykowaną 34-bitową maszyną Lisp, którą wypuściła Symbolics, i nieco dziwny system pamięci podręcznej wydany przez Kendall Square Research - obie mają strony z Wikipedii, które warto przeczytać).

Problem polegał na tym, że istniał dokładnie jeden i tylko jeden algorytm, który faktycznie działał dobrze w architekturze TM: szybka transformacja Fouriera przy użyciu tak zwanego „algorytmu doskonałego losowania”. Był to genialny wgląd w to, jak stosować technikę maski binarnej, specjalnie opracowany algorytm i architekturę do równoległego przetwarzania FFT w genialnie sprytny i szybki sposób. Ale nie sądzę, żeby kiedykolwiek znaleźli do tego kolejny cel. (patrz to powiązane pytanie: /cs/10572/perfect-shuffle-in-parallel-processing )

Byłem wystarczająco długo, aby zdać sobie sprawę, że technologie, które wydają się genialne i wydajne, często nie rozwiązują problemu (lub wystarczającej liczby problemów), aby były użyteczne.

W tym czasie było wiele genialnych pomysłów: TM, Symbolics, KSR, a także Tandem (odszedł) i Stratus (zadziwiająco, wciąż żywy). Wszyscy myśleli, że te firmy - przynajmniej niektóre - przejmą świat i zrewolucjonizują informatykę.

Ale zamiast tego mamy FaceBook.

Jakie problemy statystyczne prawdopodobnie skorzystają na obliczeniach kwantowych?

Na stronie 645 „ Chemii fizycznej: pojęcia i teoria ” Kenneth S. Schmitz wyjaśnia:

Efekty kwantowe stają się ważne, gdy długość fali de Broglie'a staje się porównywalna lub większa niż wymiary cząstki. Gdy to nastąpi, funkcje falowe mogą się nakładać, dając różne właściwości systemu.

Układy makroskopowe można analizować metodami klasycznymi, jak wyjaśnia strona Wikipedii:

Bardziej wyrafinowane rozważanie rozróżnia mechanikę klasyczną i kwantową na podstawie tego, że mechanika klasyczna nie rozpoznaje, że materii i energii nie można podzielić na nieskończenie małe działki, tak że ostatecznie dokładny podział ujawnia nieredukowalnie ziarniste cechy. Kryterium dokładności jest to, czy interakcje są opisane w kategoriach stałej Plancka. Z grubsza mówiąc, mechanika klasyczna uważa cząstki w matematycznie wyidealizowanych terminach nawet za cienkie jak punkty geometryczne bez wielkości, wciąż mające swoje skończone masy. Mechanika klasyczna uważa również matematycznie wyidealizowane materiały rozszerzone za geometrycznie stale istotne. Takie idealizacje są przydatne w większości codziennych obliczeń, ale mogą zawieść całkowicie w przypadku cząsteczek, atomów, fotonów i innych cząstek elementarnych. Na wiele sposobów, mechanikę klasyczną można uznać za głównie teorię makroskopową. W znacznie mniejszej skali atomów i cząsteczek mechanika klasyczna może zawieść, a interakcje cząstek są następnie opisywane przez mechanikę kwantową.

Na przykład, czy komputery kwantowe zapewniają bardziej wszechstronne generowanie liczb losowych?

Nie. Nie potrzebujesz komputera, aby wygenerować prawdziwą liczbę losową, a użycie do tego komputera kwantowego byłoby ogromnym marnotrawstwem zasobów bez poprawy losowości.

ID Quantique ma w sprzedaży karty SoC, samodzielne i PCIe w cenie od 1200 do 3500 USD . To trochę więcej niż fotony podróżujące przez półprzezroczyste lustro, ale ma wystarczające kwantowe właściwości losowe, aby przejść przez AIS 31 („Klasy funkcjonalności i metodologia oceny dla generatora liczb rzeczywistych (fizycznych) - wersja 3.1 29 września 2001 r.” .PDF ). Oto jak opisują swoją metodę:

Quantis to fizyczny generator liczb losowych wykorzystujący elementarny proces optyki kwantowej. Fotony - lekkie cząstki - są wysyłane jeden po drugim na półprzezroczyste lustro i wykrywane. Te zdarzenia wyłączne (odbicie - transmisja) są powiązane z wartościami bitów „0” - „1”. To pozwala nam zagwarantować naprawdę bezstronny i nieprzewidywalny system.

System QuintessenceLabs oferuje szybszy (1 Gbit / s) system . Ich kwantowy generator liczb losowych „qStream” jest zgodny z NIST SP 800-90A i spełnia wymagania projektu NIST SP 800 90B i C. Wykorzystuje diody tunelowe Esaki . Ich produkty są nowe, a ceny nie są jeszcze publicznie dostępne.

Dostępne są również systemy Comscire za kilkaset do kilku tysięcy dolarów. Ich metody i patenty PCQNG oraz post kwantowe RNG są wyjaśnione na ich stronie internetowej.

Firma Quantum Numbers Corp. opracowała urządzenie wielkości chipa, aby szybko (1 Gbit / s) wytwarzać losowe liczby kwantowe, które, jak twierdzą, będą wkrótce dostępne.

A co z tanim obliczeniowo generowaniem liczb pseudolosowych?

Jeśli masz na myśli „tanie obliczeniowo” jak w kilku instrukcjach i szybkie wykonanie = tak.

Jeśli masz na myśli, że dowolny komputer jest niedrogim sposobem generowania prawdziwych liczb losowych = nie.

Żadna zaimplementowana właściwość QRNG nie będzie generować pseudolosowych liczb.

Czy obliczenia kwantowe pomogą przyspieszyć konwergencję Markova Chain Monte Carlo (MCMC) , czy też zapewnią górne granice czasu konwergencji?

Na razie pozwolę, żeby ktoś inny się tym zajął.

Czy będą istnieć algorytmy kwantowe dla innych estymatorów opartych na próbkowaniu?

Prawdopodobnie.

Edytuj i popraw tę odpowiedź Wiki.