Wiele prac twierdzi, że symulacja Hamiltona jest kompletna pod względem BQP (np. Symulacja Hamiltona z prawie optymalną zależnością od wszystkich parametrów i symulacja Hamiltona przez Qubitization ).

Łatwo zauważyć, że symulacja Hamiltona jest trudna dla BQP, ponieważ każdy algorytm kwantowy można zredukować do symulacji Hamiltona, ale jak symulacja Hamiltona w BQP?

tj. czym dokładnie jest problem decyzyjny symulacji Hamiltona w BQP i pod jakimi warunkami w Hamiltonian?

— groupsgroupsgroups
źródło

Istnieje wiele różnych wariantów, szczególnie w odniesieniu do warunków na Hamiltonian. Jest to na przykład gra polegająca na znalezieniu najprostszej możliwej klasy hamiltonianów, dla których symulacja jest wciąż kompletna pod względem BQP.

Instrukcja będzie w przybliżeniu podobna do: let $|\psi\rangle$ być (znormalizowane) stan produktu, $H$ być Hamiltona z jakiejś konkretnej klasy (na przykład składające się wyłącznie sprzęgieł najbliższego sąsiada w jednowymiarowej $\hat O$ zauważalny zawierający produkt tensor operatorów jednoczęściową takie, że $\|\hat O\|\leq 1$ i $t$ jest czasem. Biorąc pod uwagę obietnicę, że jest albo większy niż lub mniejszy niż dla niektórych (np. $\langle\psi|e^{iHt}\hat O e^{-iHt}|\psi\rangle$ $\frac12+a$ $\frac12-a$ $a$ $a=\frac16$ ), zdecyduj, która jest sytuacja.

Dalsze szczegóły

Symulacja Hamiltona jest trudna do BQP

Podstawowa konstrukcja (pierwotnie z powodu Feynmana, tutaj nieco poprawiona) w zasadzie pokazuje, w jaki sposób można zaprojektować hamiltonian, który implementuje dowolne obliczenia kwantowe, w tym dowolne obliczenie BQP. Obserwowalny, który mierzyłbyś, to po prostu na konkretnym kubicie wyjściowym, przy czym dwa wyniki pomiaru odpowiadają „tak” i „nie”. $Z$

Najprostszym rodzajem hamiltonianu, jaki możesz sobie wyobrazić, jest rozważenie obliczenia sekwencyjnych jednostek unitarnych działających na kubitów, zaczynając od stanu . Następnie możesz wprowadzić dodatkowe kubitów i podać Hamiltonian Jeśli przygotujesz stan początkowy jako to po pewnym czasie , będzie on w stan gdzie $N-1$ $U_n$ $M$ $|0\rangle^{\otimes M}$ $N$

H = \frac{2}{N} \sum_{n = 1}^{N - 1} \sqrt{n (N. - n)} (| 10 ⟩ ⟨ 01 |_{n, n + 1} \otimes U + | 01 ⟩ ⟨ 10 |_{n, n + 1} \otimes U^{†}) .

$H=\frac{2}{N}\sum_{n=1}^{N-1}\sqrt{n(N-n)}\left(|10\rangle\langle 01|_{n,n+1}\otimes U+|01\rangle\langle 10|_{n,n+1}\otimes U^\dagger\right).$

| 1 ⟩ | 0 ⟩^{\otimes (N - 1)} | 0 ⟩^{\otimes M}

$|1\rangle|0\rangle^{\otimes(N-1)}|0\rangle^{\otimes M}$

N π / 4

$N\pi/4$

| 0 ⟩^{\otimes (N - 1)} | 1 ⟩ | Φ ⟩

$|0\rangle^{\otimes (N-1)}|1\rangle|\Phi\rangle$

| Φ ⟩

$|\Phi\rangle$ jest wynikiem żądanego obliczenia. Zabawne siły sprzężenia, których tu użyłem, zostały wybrane specjalnie w celu uzyskania deterministycznej ewolucji i są związane z ideą idealnego przeniesienia stanu . Zwykle zobaczysz wyniki podane przy równych sprzężeniach, ale ewolucji probabilistycznej.

\sqrt{n (N - n)}

$\sqrt{n(N-n)}$

Aby zobaczyć, jak to działa, zdefiniuj zestaw stanów Działanie Hamiltona to zatem co dowodzi, że zmiany te są ograniczone do podprzestrzeni, która jest reprezentowana przez tridiagonal matrycy (co jest rzeczą specyficzne badania na optymalne przeniesienie stanu).

| ψ_{n} ⟩ = | 0 ⟩^{\otimes (n - 1)} | 1 ⟩ | 0 ⟩^{\otimes N - n} \otimes (U_{n - 1} U_{n - 2} \dots U_{1} | 0 ⟩^{\otimes M}) .

$|\psi_n\rangle=|0\rangle^{\otimes(n-1)}|1\rangle|0\rangle^{\otimes{N-n}}\otimes\left(U_{n-1}U_{n-2}\ldots U_1|0\rangle^{\otimes M}\right).$

H | ψ_{n} ⟩ = \frac{2}{N} \sqrt{(n - 1) (N + 1 - n)} | ψ_{n - 1} ⟩ + \frac{2}{N} \sqrt{n (N - n)} | ψ_{n + 1} ⟩,

$H|\psi_n\rangle=\frac2N\sqrt{(n-1)(N+1-n)}|\psi_{n-1}\rangle+\frac2N\sqrt{n(N-n)}|\psi_{n+1}\rangle,$

N \times N

$N\times N$

Oczywiście ten hamiltonian nie ma żadnych szczególnie miłych właściwości - na przykład jest wysoce nielokalny. Istnieje wiele sztuczek, które można zagrać, aby uprościć hamiltonian do bycia, na przykład, jednowymiarowym. Może nawet być niezmiennie translacyjnie, jeśli chcesz, kosztem przygotowania bardziej złożonego początkowego stanu produktu (w tym momencie obliczenia nie są już kodowane w Hamiltonianie, który jest uniwersalny, ale jest kodowany w stanie wejściowym) . Zobacz tutaj , na przykład.

Symulacja Hamiltona

Ewolucja dowolnego hamiltonianu, który jest lokalny w jakiejś sieci, działając na początkowy stan produktu, przez czas nie większy niż wielomian w rozmiarze systemu, może być symulowany przez komputer kwantowy, a każdy efektywnie możliwy do wykonania pomiar może być zastosowany do oszacować obserwowalne. W tym sensie widać, że symulacja Hamiltona nie jest trudniejsza niż obliczenie kwantowe, co jest kontrapunktem do poprzedniego stwierdzenia, że obliczenie kwantowe nie jest trudniejsze niż symulacja Hamiltona.

Można to zrobić na wiele sposobów (ostatnio pojawiły się artykuły, które pokazują znaczną poprawę skalowania błędów dla niektórych klas hamiltonianów). Jest dość prosty. Weź Hamiltonian , który chcesz zasymulować. Podziel go na różne części, , z których każda dojeżdża. Na przykład na najbliższym sąsiadu Hamiltonian na jakimś wykresie nie potrzebujesz więcej elementów niż maksymalny stopień wykresu. Następnie Trotterize ewolucji, pisząc przybliżenie Musisz więc zbudować obwód, który implementuje warunki takie jak , na które składają się terminy dojazdów $H$ $H_i$

e^{i H t} \approx {(e^{- i H_{1} δ t} e^{- i H_{2} δ t} \dots e^{- i H_{n} δ t})}^{t / δ t}

$e^{iHt}\approx \left(e^{-iH_1\delta t}e^{-iH_2\delta t}\ldots e^{-iH_n\delta t}\right)^{t/\delta t}$

e^{- i H_{1} δ t}

$e^{-iH_1\delta t}$

H_{1} = \sum_{n} h_{n}

$H_1=\sum_nh_n$ , z których każdy działa tylko na niewielką liczbę kubitów. Ponieważ jest to tylko jednostka na niewielkiej liczbie terminów, uniwersalny komputer kwantowy może to zaimplementować.

e^{- i H_{1} δ t} = \prod_{n} e^{- i h_{n} δ t}

$e^{-iH_1\delta t}=\prod_{n}e^{-ih_n\delta t}$

— DaftWullie
źródło

Symulacja Hamiltona jest zakończona BQP

Dalsze szczegóły

Symulacja Hamiltona jest trudna do BQP

Symulacja Hamiltona