Obliczenia kwantowe - związek między modelem Hamiltonian a modelem Unitary

16

Podczas opracowywania algorytmów obliczeń kwantowych zauważyłem, że istnieją dwa podstawowe modele, w których odbywa się to. Niektóre algorytmy - takie jak problem drzewa Hamiltonian NAND (Farhi, Goldstone, Guttman) - działają poprzez zaprojektowanie stanu hamiltonowskiego i pewnego stanu początkowego, a następnie umożliwienie ewolucji systemu zgodnie z równaniem Schrödingera przez pewien czas przed wykonaniem pomiaru.t

Inne algorytmy - takie jak Algorytm Shora dla faktoringu - działają poprzez zaprojektowanie sekwencji transformacji Unitary (analogicznie do bramek) i zastosowanie tych transformacji pojedynczo do pewnego stanu początkowego przed wykonaniem pomiaru.

Moje pytanie, jako nowicjusz w dziedzinie obliczeń kwantowych, jaki jest związek między modelem hamiltonowskim a modelem transformacji Unitary? Niektóre algorytmy, jak na przykład problem drzewa NAND, zostały odtąd przystosowane do pracy z sekwencją transformacji Unitary (Childs, Cleve, Jordan, Yonge-Mallo). Czy każdy algorytm w jednym modelu można przekształcić w odpowiedni algorytm w drugim? Na przykład, biorąc pod uwagę sekwencję transformacji Unitary, aby rozwiązać konkretny problem, czy można zaprojektować hamiltonian i rozwiązać problem w tym modelu? Co z innym kierunkiem? Jeśli tak, jaki jest związek między czasem ewolucji systemu a liczbą przekształceń jednostkowych (bramek) wymaganych do rozwiązania problemu?

Znalazłem kilka innych problemów, w przypadku których wydaje się, że tak jest, ale nie ma jednoznacznego argumentu ani dowodu wskazującego, że jest to zawsze możliwe, a nawet prawdziwe. Może dlatego, że nie wiem, jak nazywa się ten problem, więc nie jestem pewien, czego szukać.

algorithms quantum-computing computation-models użytkownik340082710
źródło
3
Każdy algorytm wielomianowy w jednym odpowiada algorytmowi wielomianowemu w drugim, ale nie jest jasne, czy stopień wielomianu będzie taki sam. Mam nadzieję, że ktoś wymyśli referencje. Wyniki te zostały udowodnione we wczesnych dniach obliczeń kwantowych i teraz powinny istnieć lepsze dowody na te twierdzenia.
Peter Shor,
czy odnosi się to do tak zwanego obrazu QM Heisenberga vs Schroedingera, który dotyczy sposobu definiowania operatorów? także jeśli nie jest objęty Nielsen & Chuang , wydaje się to poważnym niedopatrzeniem! w drzewie drzewa NAND użyto „wyroczni hamiltonowskich”, które wydają się być wprowadzone przez Farhi / Gutmann 1998. tutaj znajduje się ładny artykuł ankietowy na temat wyroczni hamiltonowskich autorstwa Mochona 2007
2014
Link do książki, który podałeś, jest w rzeczywistości podręcznikiem, z którego korzystaliśmy na studiach licencjackich w zakresie przetwarzania informacji kwantowej. Książka jest naprawdę nastawiona na podejście Unitarne (również w kontekście wyroczni), ale nie tak bardzo w kontekście hamiltonianów. Mój kurs licencjacki koncentrował się z perspektywy cs, a nie fizyki, dlatego najbardziej znam model Unitary.
user340082710
Artykuł, który dostarczyłeś, jest ogólnie dobrym odniesieniem, ale nie sądzę, że odnosi się również do mojego pytania. Na koniec rzuciłem okiem na zdjęcie QM Heisenberga vs Schroedingera i wygląda na powiązane, ale wierzę, że moje pytanie jest inne (chociaż mogę się mylić - trudno było śledzić wpisy w Wikipedii).
user340082710
Myślę, że istnieją różne sposoby interpretacji twojego pytania i zamiast odpowiadać na wszystkie interpretacje, chciałbym zadać Ci następujące pytania: Czy mógłbyś być bardziej precyzyjny na temat wersji modelu Hamiltona, którą masz na myśli? Jaka jest miara złożoności w tym modelu? (tzn. co liczy się, jak trudno jest rozwiązać problem w modelu hamiltonowskim?) W jaki sposób podano wkład w problem? Czy zostało to podane wprost, czy musisz zapytać o dane wejściowe za pośrednictwem wyroczni?
Robin Kothari,

Odpowiedzi:

10

Aby pokazać, że ewolucja hamiltonowska może symulować model obwodu, można skorzystać z papierowego Obliczenia uniwersalnego za pomocą wielocząsteczkowego spaceru kwantowego , który pokazuje, że bardzo specyficzny rodzaj ewolucji hamiltonowskiej (wielocząsteczkowe spacery kwantowe) jest zakończony BQP, a zatem może symulować model obwodu.

Oto artykuł z ankiety na temat symulacji ewolucji kwantowej na komputerze kwantowym. Można wykorzystać techniki opisane w tym artykule do symulacji modelu ewolucji hamiltonowskiej komputerów kwantowych. Aby to zrobić, należy użyć „Trotterization”, co znacznie zmniejsza efektywność symulacji (chociaż wprowadza ona tylko wielomianowy wzrost w czasie obliczeń).

Peter Shor
źródło
Dzięki! Te referencje wyglądają całkiem dobrze i powinny dać mi wyobrażenie o tym, jak to się robi.
user340082710,