Komputer kwantowy może skutecznie rozwiązywać problemy leżące w klasie złożoności BQP . Widziałem twierdzenie, które może (potencjalnie, ponieważ nie wiemy, czy BQP jest właściwym podzbiorem, czy jest równe PP) zwiększyć wydajność komputera kwantowego poprzez zastosowanie postselekcji i że klasa efektywnie rozwiązywanych problemów staje się teraz postBQP = PP .
Co oznacza tutaj postselekcja ?
Odpowiedzi:
„Postselekcja” odnosi się do procesu warunkowania wyniku pomiaru na innym kubicie. (Jest to coś, o czym można pomyśleć również w przypadku klasycznych rozkładów prawdopodobieństwa i analizy statystycznej: nie jest to koncepcja specjalna dla obliczeń kwantowych.)
Postselekcja występowała dość często (do tego momentu) w eksperymentach mechaniki kwantowej, ponieważ - w przypadku eksperymentów na bardzo małych układach, z udziałem niezbyt wielu cząstek - jest to stosunkowo łatwy sposób symulowania dobrej kontroli kwantowej lub sprzężenia zwrotnego. Nie jest to jednak praktyczny sposób realizacji obliczeń, ponieważ należy uzależnić wynik jednego lub więcej pomiarów, które mogą wystąpić z bardzo małym prawdopodobieństwem.
Rezultat, że postselekcja „zwiększa” (jak mówisz) moc obliczeń kwantowych z błędem ograniczonym z BQP do PP, jest bardzo popularnym wynikiem w teorii obliczeń kwantowych, nie dlatego, że jest praktyczny , ale dlatego, że jest prosty i wyraźny wynik, który jest rzadki w złożoności obliczeniowej i jest użyteczny do informowania intuicji o obliczeniach kwantowych - doprowadził do pomysłów na eksperymenty z „supremacją kwantową”, na przykład. Ale nie jest to coś, o czym powinieneś myśleć jako o operacji, która jest swobodnie dostępna dla komputerów kwantowych jako praktyczna technika, chyba że możesz wykazać, że wyniki, które próbujesz wybrać później, są wystarczająco małe i mają wysokie prawdopodobieństwo (lub, tak jak w przypadku obliczeń opartych na pomiarach, że można zasymulować „pożądany” wynik przez odpowiednie dostosowanie procedury, jeśli uzyska się jeden z „niepożądanych” wyników.
Jak przekazano inną odpowiedź (do której staram się jedynie wyjaśnić), po selekcji chodzi tylko o przyjrzenie się podzestawowi możliwych wyników pomiaru. Moim zdaniem dotyczy to dwóch różnych przypadków, jak poniżej. Tak, są to różne aspekty tej samej rzeczy, ale są używane w różny sposób przez dwie różne społeczności.
Przeprowadzasz pewne eksperymenty, ale gromadzisz dane tylko wtedy, gdy spełnione są określone warunki. Zasadniczo służy do kompensacji zwiastunów niedoskonałości eksperymentalnych (tzn. Uruchamiane jest coś, co mówi nam, że uzyskaliśmy niepożądany wynik przed przystąpieniem do kolejnej części eksperymentu). Na przykład możesz używać pary fotonów jako nośników informacji lub splątania, ale czasami te fotony gubią się po drodze. Jeśli robisz rzeczy tylko po wykryciu obu fotonów, wybierasz po ich pomyślnym przybyciu.
Jest to myślowy eksperyment „ o ile potężniejszy mógłby być mój komputer, gdybym mógł wybrać wyniki pomiarów? ” I nie jest praktyczną propozycją.
Jako prosty przykład pomyśl o teleportacji kwantowej. W normalnym scenariuszu Alice i Bob dzielą parę Bell, a Alice ma kubit w nieznanym stanie, który chce się teleportować do Boba. Wykonuje pomiar dzwonka na swoich dwóch kubitach i przesyła wynik pomiaru do Boba. Jeśli Bob jest daleko od Alicji, informacja o wyniku pomiaru zajmuje skończony czas i po tym czasie można go uznać za otrzymanego kubit (ponieważ musi zrekompensować efekty różnych wyników) na kubicie, który trzyma).
Jeśli jednak Alice może wybrać wynik pomiaru jako zawsze będący jednym konkretnym wynikiem, a Bob wie, że wybierze ten wynik, Alice nie musi wysyłać wyniku pomiaru do Boba. Może natychmiast użyć kubit, który trzyma. Jeszcze silniejszy, może go użyć, zanim Alice dokona pomiaru, mając pewność, że zrobi to! Zatem nie tylko osiągasz szybszą niż światło komunikacja, ale tak naprawdę komunikujesz się wstecz! Możesz zacząć wyobrażać sobie, jak potężny może być dla komputera (obliczyć przez dowolnie długi czas, a następnie przesłać odpowiedź z powrotem do momentu, w którym pytanie zostało zadane).