Viele Veröffentlichungen behaupten, dass die Hamilton-Simulation BQP-vollständig ist (z. B. Hamilton-Simulation mit nahezu optimaler Abhängigkeit von allen Parametern und Hamilton-Simulation durch Qubitisierung ).

Es ist leicht zu erkennen, dass die Hamilton-Simulation BQP-schwer ist, da jeder Quantenalgorithmus auf die Hamilton-Simulation reduziert werden kann. Wie ist die Hamilton-Simulation in BQP?

dh was ist genau das Hamilton - Simulation Entscheidungsproblem in BQP und unter welchen Bedingungen auf dem Hamilton - Operator?

Es gibt viele verschiedene Varianten, insbesondere in Bezug auf die Bedingungen auf dem Hamiltonian. Es ist zum Beispiel ein bisschen wie ein Spiel, zu versuchen, die einfachste Klasse von Hamiltonianern zu finden, für die die Simulation noch BQP-vollständig ist.

Die Aussage wird ungefähr so ​​lauten: let (normierter) Produkt werden, H sein , ein Hamilton - Operator von einer bestimmten Klasse (zB nur aus nearest-neighbor - Kupplungen auf einem eindimensionalen Gitter), O eine beobachtbare ein Tensorprodukt von einem Körper Operatoren umfaßt , so daß ‖ O ‖ ≤ 1 , und t eine Zeit sein. In Anbetracht der Versprechen , dass ⟨ & psgr; | e i H t O e - i H t | & psgr; $|\psi\rangle$$H$$\hat O$$\|\hat O\|\leq 1$$t$$\langle\psi|e^{iHt}\hat O e^{-iHt}|\psi\rangle$entweder größer als oder weniger als$\frac12+a$für einigea(zBa=$\frac12-a$$a$ ) entscheiden, was der Fall ist.$a=\frac16$

---

Weitere Details

Die Hamilton-Simulation ist BQP-hart

Die Basiskonstruktion (ursprünglich von Feynman, hier ein wenig überarbeitet) zeigt im Grunde, wie Sie einen Hamilton-Operator entwerfen können, der jede Quantenberechnung, einschließlich jeder BQP-vollständigen Berechnung, implementiert. Die beobachtbare Größe, die Sie messen würden, ist nur für ein bestimmtes Qubit. Die beiden Messergebnisse entsprechen 'Ja' und 'Nein'.$Z$

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

$$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\rangle|0\rangle^{\otimes(N-1)}|0\rangle^{\otimes M}$$N\pi/4$, it will be in a state $|0\rangle^{\otimes (N-1)}|1\rangle|\Phi\rangle$ where $|\Phi\rangle$ is the output of the desired computation. The funny coupling strengths that I've used here, the $\sqrt{n(N-n)}$ are chosen specifically to give deterministic evolution, and are related to the concept of perfect state transfer. Usually you'll see results stated with equal couplings, but probabilistic evolution.

To see how this works, you define a set of states

$$|\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).$$ The action of the Hamiltonian is then $$H|\psi_n\rangle=\frac2N\sqrt{(n-1)(N+1-n)}|\psi_{n-1}\rangle+\frac2N\sqrt{n(N-n)}|\psi_{n+1}\rangle,$$ which proves that the evolution is restricted to an $N\times N$ subspace which is represented by a tridiagonal matrix (which is the specific thing studied in perfect state transfer).

Of course, this Hamiltonian doesn't have any particularly nice properties - it is highly non-local, for example. There are many tricks that can be played to simplify the Hamiltonian to being, for example, one-dimensional. It can even be translationally invariant if you want, at the cost of having to prepare a more complex initial product state (at that point, the computation is no longer encoded in the Hamiltonian, which is universal, but is encoded in the input state). See here, for example.

Hamiltonian Simulation

The evolution of any Hamiltonian which is local on some lattice, acting on an initial product state, for a time that is no more than polynomial in the system size, can be simulated by a quantum computer, and any efficiently implementable measurement can be applied to estimate an observable. In this sense, you can see that Hamiltonian simulation is no harder than a quantum computation, the counter-point to the previous statement that quantum computation is no harder than Hamiltonian simulation.

There are many ways to do this (and there have been some recent papers that show significant improvements in error scaling for certain classes of Hamiltonian). Hre's quite a simple one. Take the Hamiltonian $H$ that you want to simulate. Split it up into different parts, $H_i$, each of which commutes. For example, on a nearest-neighbour Hamiltonian on some graph, you don't need more pieces than the maximum degree of the graph. You then Trotterize the evolution, writing the approximation

$$e^{iHt}\approx \left(e^{-iH_1\delta t}e^{-iH_2\delta t}\ldots e^{-iH_n\delta t}\right)^{t/\delta t}$$ So, you just have to construct a circuit that implements terms like $e^{-iH_1\delta t}$, which is composed of commuting terms $H_1=\sum_nh_n$, each of which acts only on a small number of qubits. $$e^{-iH_1\delta t}=\prod_{n}e^{-ih_n\delta t}$$ Since this is just a unitary on a small number of terms, a universal quantum computer can implement it.