Во многих работах утверждается, что гамильтоново моделирование является BQP-полным (например, гамильтоново моделирование с почти оптимальной зависимостью от всех параметров и гамильтоново моделирование с помощью кубитизации ).

Легко видеть, что гамильтоново моделирование является BQP-сложным, потому что любой квантовый алгоритм может быть сведен к гамильтоновому моделированию, но как гамильтоново моделирование в BQP?

то есть, что именно является задачей решения гамильтонова симуляции в BQP и при каких условиях на гамильтониане?

Существует множество различных вариантов, особенно в отношении условий на гамильтониане. Например, попытка найти простейший класс гамильтонианов, для которых симуляция еще BQP-завершена, является чем-то вроде игры.

Это утверждение будет примерно таким: let быть (нормированная) состояние продукта, Н гамильтонова из некоторого определенного класса (например , состоящие только из ближайших соседних соединительных муфт на одномерной решетке), О наблюдаемой , содержащий тензорное произведение операторов одного тела , таких , что | | O | | ≤ 1 , а т быть время. Учитывая обещание , что ⟨ г | | е я Н т О е - я Н т | г | $|\psi\rangle$$H$$\hat O$$\|\hat O\|\leq 1$$t$$\langle\psi|e^{iHt}\hat O e^{-iHt}|\psi\rangle$либо больше или меньше$\frac12+a$для некоторогоa(например,a=$\frac12-a$$a$ ) решите, в чем дело.$a=\frac16$

---

Дальнейшие подробности

Гамильтоново моделирование - BQP-сложный

Базовая конструкция (первоначально из-за Фейнмана, здесь немного подправленная) в основном показывает, как можно спроектировать гамильтониан, который реализует любые квантовые вычисления, включая любые BQP-полные вычисления. Наблюдаемая вами измеренная величина - это просто на конкретном выходном кубите, два результата измерения, соответствующие «да» и «нет».$Z$

Самый простой вид гамильтониана, о котором вы можете подумать, - это рассмотреть вычисление последовательных унитарных U n, действующих на M кубитов, начиная с состояния | 0 ⟩ ⊗ М . Тогда вы можете ввести дополнительные N кубитов и указать гамильтониан H = $N-1$$U_n$$M$$|0\rangle^{\otimes M}$$N$ Если вы готовите свое начальное состояние как| 1⟩| 0⟩ ⊗ ( N - 1 ) | 0⟩ ⊗ М , то через некоторое время

$$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}$ , он будет в состоянии | 0 ⟩ ⊗ ( N - 1 ) | 1 ⟩ | Ф ⟩ , где | Ф ⟩ является выходом требуемого вычисления. Забавные силы сцепления, которые я использовал здесь,$N\pi/4$$|0\rangle^{\otimes (N-1)}|1\rangle|\Phi\rangle$$|\Phi\rangle$ выбраны специально, чтобы дать детерминистическую эволюцию, и связаны с концепцией передачиидеального состояния. Обычно вы увидите результаты с равными связями, но вероятностная эволюция.$\sqrt{n(N-n)}$

$$|\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|\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.