Jaki poziom „pewności” wyniku z komputera kwantowego jest możliwy?

Na bardzo podstawowym poziomie czytanie lub pomiar kubita zmusza go do znalezienia się w jednym lub drugim stanie, więc działanie komputera kwantowego w celu uzyskania wyniku powoduje stan jednej z wielu możliwości.

Ponieważ jednak stan każdego kubita jest probabilistyczny, z pewnością oznacza to, że wynikiem może być dowolna z tych możliwości, o różnym prawdopodobieństwie. Jeśli ponownie uruchomię program - czy powinienem oczekiwać innych wyników?

Jak mogę się upewnić, że mam „najlepszy” wynik? Co zapewnia to zaufanie? Zakładam, że nie mogą to być pomiary przejściowe, jak opisano w tym pytaniu, ponieważ nie powodują one zwinięcia wyniku.

Większość użytecznych / względnie wydajnych algorytmów ¹ dla komputerów kwantowych należy do klasy złożoności „kwantowego wielomianowego czasu kwantowego błędu” (BQP) . Zgodnie z tą definicją chcesz, aby „współczynnik awaryjności” dowolnego algorytmu kwantowego wynosił lubP(sukces)≥$\leq\frac{1}{3}$ , chociaż wynik może nadal zawierać się w niewielkim błędzie. Algorytm nieprobabilistyczny (który może działać w czasie wielomianowym) nadal będzie należał do tej klasy złożoności, z tą różnicą, żezawszezwraca poprawny wynik²$\mathbb{P}\left(\text{success}\right) \geq \frac{2}{3}$ .

Ponieważ jednak algorytm można uruchomić dowolną liczbę razy, jest to równoważne prawdopodobieństwu sukcesu co najmniej dla wejścia o długościni dowolnej dodatniej stałejc.$\frac{1}{2} + n^{-c}$$n$$c$

Tak więc „poprawny” wynik to taki, który pojawia się co najmniej dwie trzecie czasu, chyba że chcesz obliczenia „jednorazowego”, na przykład jeśli chcesz wygenerować liczby losowe lub jeśli chcesz zrobić coś takiego jak test porównawczy chip kwantowy, w którym statystyki mają znaczenie i są częścią „wyniku”.

Oprócz tych (lub innych algorytmów, które nie mają ani jednego „poprawnego wyniku”), jeśli znajdziesz algorytm ze wskaźnikiem powodzenia poniżej połowy, nie jest to już „błąd związany” i może nie być możliwe dla użytkownika znać poprawny wynik - odpowiedź może być po prostu błędna z większym prawdopodobieństwem wystąpienia niż poprawna.

Tak, za każdym razem, gdy wykonujesz obliczenia, możesz zobaczyć inny wynik. Zaufanie do wyniku zapewniają:

1. Sam algorytm kwantowy zapewniający, że poprawny wynik nastąpi z dużym prawdopodobieństwem;
2. Powtarzanie algorytmu kilka razy w celu znalezienia najbardziej prawdopodobnego wyniku.

^{1 W tym przypadku algorytmy, które można obliczyć w czasie wielomianowym w celu uzyskania rozwiązania o „wysokim prawdopodobieństwie”, chociaż dla celów tej odpowiedzi złożoność czasu ma mniejsze znaczenie}

^{2 Cóż, przynajmniej idealistycznie}

Opracowując nieco Mithrandir24601odpowiedzi -

Martwisz się, że komputer kwantowy może uzyskać inną odpowiedź przy następnym uruchomieniu obliczeń, jest to także funkcja obliczeń losowych. Pod pewnymi względami dobrze jest móc powtarzalnie uzyskać jedną odpowiedź, ale w końcu wystarczy uzyskać poprawną odpowiedź z wystarczającą pewnością. Podobnie jak w przypadku algorytmu losowego ważne jest, aby mieć pewność, że uzyskasz poprawną odpowiedź w dowolnym przebiegu obliczeń.

Na przykład, twój komputer kwantowy może dać ci poprawną odpowiedź na pytanie TAK / NIE dwa razy na trzy. Może to wydawać się słabą wydajnością, ale oznacza to, że jeśli uruchomisz ją wiele razy, możesz po prostu wziąć odpowiedź większościową i być bardzo pewnym, że reguła większości daje poprawną odpowiedź. (To samo dotyczy normalnego obliczenia losowego.) Sposób, w jaki pewność rośnie wraz z liczbą run, oznacza, że ​​o ile jeden przebieg daje odpowiedź, która ma znacznie więcej niż 50% szansy na poprawność, możesz zwiększyć swoją pewność siebie tak, jak chcesz, wykonując skromną liczbę powtórzeń (chociaż wymaganych jest więcej przebiegów, tym mniejsze szanse na poprawną odpowiedź w jednym przebiegu wynoszą 50%).

$\mathrm{poly}(n)$$n$ łańcucha bitowych, gdzie odpowiedź brzmi popraw z prawdopodobieństwem co najmniej 2/3; w powyższym argumencie podano ten sam zestaw problemów, jeśli żądasz, aby odpowiedź była prawidłowa z prawdopodobieństwem 999/1000 lub (1 - 1e-8).

W przypadku problemów, które mają bardziej szczegółowe odpowiedzi niż pytania TAK / NIE, niekoniecznie musimy zakładać, że ta sama odpowiedź zostanie udzielona więcej niż jeden raz, abyśmy mogli głosować większością głosów. (Jeśli używasz komputera kwantowego do pobierania próbek z wykładniczej liczby wyników, możliwe jest, że istnieje kilka mniejszych, ale wciąż wykładniczo wielu odpowiedzi, które są poprawne i przydatne!) Załóżmy, że próbujesz rozwiązać problem optymalizacji: może nie być łatwo zweryfikować, czy znalazłeś optymalne rozwiązanie lub prawie optymalne rozwiązanie - lub że otrzymana odpowiedź jest nawet najlepsza, co komputer kwantowy może zrobić (co jeśli następne uruchomienie da ci lepsza odpowiedź przez przypadek?). W takim przypadku ważne jest ustalenie, co wiesz o problemie,NP , co oznacza, że ​​możesz w zasadzie skutecznie sprawdzić każdą otrzymaną odpowiedź?) Oraz z jaką jakością rozwiązania byłbyś zadowolony.

Ponownie, dotyczy to również algorytmów losowych - różnica polega na tym, że oczekujemy, że komputery kwantowe będą w stanie rozwiązać problemy, których sam komputer losowy nie byłby w stanie łatwo rozwiązać.

$15$$3\times5$ ”.

To dobra linia, zwłaszcza w taktowanym rytmie Aaronsona, a publiczność zawsze wydawała się chichotać przynajmniej trochę, ale oczywiście wszyscy wiemy, że to niewielkie uproszczenie probabilistycznej natury algorytmu Shora.

$15$$3$$15$$5$$15=3\times 5$

$\mathsf{FACTORING}$$\mathrm{BQP}\cap\mathrm{NP}$$\mathrm{BQP}$ w generowaniu rozwiązań kandydujących, ale zawsze możemy klasycznie sprawdzić, czy domniemane rozwiązania komputera kwantowego są poprawne.

$\mathrm{BQP}$$\mathrm{NP}$

(Wiem, że są już dwie świetne odpowiedzi; jednak pytanie to pozwala na wyjaśnienie / wyjaśnienie cytatu / anegdoty Aaronsona).