Jakie problemy statystyczne prawdopodobnie skorzystają na obliczeniach kwantowych?

14

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.)

Alexis
źródło
6
+1 Myślę, że to dobre i interesujące pytanie. Ponieważ zachęca do wielu (i potencjalnie spekulacyjnych) odpowiedzi, graniczy z tym, jakie pytanie tutaj działa. Dzieli tę granicę z niektórymi z naszych najpopularniejszych i najtrwalszych wątków i, podobnie jak te, zasługuje na status CW.
whuber
7
Ponieważ uczenie maszynowe jest swego rodzaju subdyscypliną statystyki, może okazać się interesujące algorytmy kwantowe do nadzorowanego i nienadzorowanego uczenia maszynowego .
Jakub Bartczuk,
2
Szybsze obliczenia są zawsze cenne, ale obecnie obliczenia kwantowe są w fazie początkowej i nie mają jeszcze szans na pokonanie obliczeń klasycznych. Doceniam to pytanie, ponieważ skłoniło mnie to do nauczenia się czegoś na ten temat. Jak dotąd trudno mi to zrozumieć.
Michael R. Chernick
1
Czy to ważne, że obliczenia kwantowe są jeszcze w powijakach? Działa i pokonuje klasyczne obliczenia, gdy był dzieckiem. Przyspieszenie może być również wykładnicze w przypadku takich problemów, jak rozwiązywanie równań macierzy lub znajdowanie odwrotności funkcji i czarnych skrzynek. Teraz musimy tylko dorosnąć. Algorytmy, które mogą działać na takich przyszłych komputerach, są już opracowywane od dziesięcioleci. Opracowanie aplikacji do statystyki jest proste (choć bardzo szerokie, wystarczy pomyśleć o równaniach macierzowych).
Sextus Empiricus
1
Myślę, że pierwszą i najważniejszą kwestią jest to, że obliczenia kwantowe mogą teoretycznie znacznie przyspieszyć arytmetykę. Czy to jest poprawne? Jeśli tak, to wszystkie procedury algebry liniowej już przynoszą korzyści.
AdamO

Odpowiedzi:

1

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ę.

Carl
źródło
+1 Dziękuję. Czy powiedziałbyś, że metody Monte Carlo, metody ładowania i inne podejścia ilościowe do rozwiązań pasują do etykiety „brutalna siła”?
Alexis
1
Potencjalnie mogą, ale nie w taki sam sposób jak programowanie liniowe. Na przykład Ulam zastosował metodę Metropolis i Ulama (symulacja Monte Carlo) do obliczenia masy krytycznej bomby atomowej. Przy prawdziwym obliczeniu kwantowym symulowana bomba albo ulegnie symulacji wybuchu, albo nie, z taką samą prędkością jak prawdziwa eksplozja. BTW, poznałem Ulama w 1964 roku, byłem wtedy młodym facetem.
Carl
1
Dziękuję, ten punkt dotyczący „symulowanej eksplozji” naprawdę pomaga i myślę, że buduję intuicję na ten temat. Także:: D Wow!
Alexis
1

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.

eSurfsnake
źródło
Masz rację, wywołując szum i podoba mi się twoja historyczna perspektywa eSurfsnake. Dorastałem w hrabstwie Santa Clara, gdy stało się Doliną Krzemową ... Od dawna głęboko doceniam uniwersalne obliczenia. Jednym z powodów, dla których porusza mnie statystyka, jest to, że prawdopodobieństwo - prawdziwa losowość - jest poza dziedziną obliczeń. Możemy to zasymulować ... bardzo dobrze do wielu celów, ale wydaje się, że istnieją aspekty natury, które nie są obliczeniami. Wydaje się, że obliczenia kwantowe oferują elementarne operacje, które również nie są obliczeniami Turinga ... więc chcę zrozumieć, co mogą oznaczać takie narzędzia.
Alexis
@Alexis W rzeczywistości komputery kwantowe nie mają żadnych zdolności super-Turinga. Każdy problem, który można obliczyć za pomocą komputera kwantowego, można również obliczyć za pomocą komputera klasycznego, co wynika z faktu, że komputery klasyczne mogą symulować komputery kwantowe. Istnieje jednak kilka znanych problemów, które można skutecznie rozwiązać za pomocą komputerów kwantowych.
user20160,
@ user20160 Prawdziwa losowość to zdolność super-Turinga. Superpozycja to zdolność super-Turinga. Symulacja nie jest samą rzeczą.
Alexis
@Alexis Nie jestem pewien, czy mówimy o tym samym, ale rozumiem przez super-Turinga zdolność do obliczenia funkcji, której maszyna Turinga nie jest w stanie. Co ciekawe, prawdziwa losowość nie daje możliwości obliczenia żadnej funkcji, której nie można by obliczyć deterministycznie. Całkowicie się zgadzam, że symulacja nie jest samą rzeczą, ale leży w samym sercu równoważności obliczeniowej (gdzie odejmujemy samą rzecz). Jeśli maszyna A może symulować maszynę B, to A może obliczyć dowolną funkcję, którą B może. Więcej w Nielsen i Chuang. Obliczenia kwantowe i informacje kwantowe
20160
0

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.

Rob
źródło
Nie jestem pewien, czy zgadzam się co do „prawdziwej marnotrawstwa zasobów” dla niezawodnego prawdziwego RNG. Po pierwsze, pseudo-RNG wymaga czasu, który szybko się sumuje w pracach symulacyjnych na dużą skalę. Po drugie, RNG zajmuje pamięć , podobnie jak w przypadku symulacji na dużą skalę. Posiadanie szybkiego gwarantowanego źródła prawdziwej przypadkowości ze znanej dystrybucji nie wydaje się tak marnotrawstwem. Ponadto inne rozwiązania prawdziwego RNG nie wykluczają, że komputery kwantowe również zapewniają takie rozwiązanie.
Alexis