# Problem with approximating adiabatic evolution with quantum circuit

I am reading on how to approximate adiabatic evolution with quantum circuit and I had some trouble following the arguments given in the early papers which proves this results. I am mainly following

W. van Dam, M. Mosca, and U. Vazirani, “How Powerful is Adiabatic Quantum Computation?,” Proceedings 2001 IEEE International Conference on Cluster Computing, pp. 279–287, 2001.

In it the authors assumed a problem Hamiltonian

$$H_p=f(z)|z\rangle\langle z|$$

so $$H_p$$ is diagonal in the computational basis. Towards the end of the proof, it is kind of assumed that $$H_p$$ and its associated evolution operator can be efficiently computed and implemented in quantum circuits. I struggled to see why this is so. Doesn't one need to fully specify $$H_p$$ to implement the unitary associated with it? In this case does it become equivalent to assuming we can already solve the optimization problem?

Also, if we don't assume $$H_p$$ to be diagonal in the computational basis, would it be possible that we need exponential number of gates to implement the adiabatic evolution?

Maybe a relevant and more general question is, in general is there any hard Hamiltonian's that is difficult to simulate on a quantum circuit?

I'm not sure if you're wanting to implement $$H_p=f(z)|z\rangle\langle z|$$ for a specific $$z$$, or $$H_p=\sum_zf(z)|z\rangle\langle z|.$$ I'm going to assume the latter because you can easily redefine the function to convert it into the former. Now, assume that $$g(z)$$ is a function that we can compute efficiently on a classical computer that gives the best $$k$$-bit approximation for $$f(z)$$. Now, construct a unitary that can compute $$U|z\rangle|y\rangle=|z\rangle|y\oplus g(z)\rangle$$ for $$y\in\{0,1\}^k$$. You can implement $$U$$ because it can be computed classically, and $$U^\dagger=U$$. So, if you have a first register on which you want to implement the Hamiltonian (state $$\sum_z\alpha_z|z\rangle$$), a second register of $$k$$ qubits, initialised in $$|0\rangle^{\otimes k}$$, and you implement $$U$$, then you've got state $$\sum_z\alpha_z|z\rangle|g(z)\rangle.$$ Now think about the binary representation of $$g(z)$$. If you implement a phase gate $$e^{i\phi Z}$$ on the least significant bit, a phase $$e^{i2\phi Z}$$ on the second bit, and $$e^{i2^{j-1}\phi Z}$$ of the $$j^{th}$$ least significant bit, then the net effect is a phase $$e^{ig(z)\phi}$$. $$\sum_z\alpha_ze^{ig(z)\phi}|z\rangle|g(z)\rangle$$ Now we run $$U$$ again, leaving $$\sum_z\alpha_ze^{ig(z)\phi}|z\rangle|0\rangle^{\otimes k}.$$ This is as if the Hamiltonian $$\sum_zg(z)|z\rangle\langle z|$$ has been applied for a time $$\phi$$, and this, for sufficiently large $$k$$, will be a good approximation to $$H_p$$.

In terms of different bases, if there's a unitary $$V$$ that you can efficiently implement that changes basis, then you're certainly fine - you just add that before the evolution I've described, and add a $$V^\dagger$$ after.

More generally, is there a Hamiltonian evolution that you can't efficiently implement on a quantum computer? Assuming certain basic properties such as a bounded energy, then the answer is no: Hamiltonian simulation is BQP-complete, meaning that every Hamiltonian can be efficiently simulated on a quantum computer (up to some accuracy), and there are some for which it is the hardest thing you could ask of a quantum computer and it still be efficient. The caveat here is the way in which the Hamiltonian is specified. For instance, the way you specify the Hamiltonian could make it hard to implement, while specifying it a different way would be OK.

However, that's not necessarily the question that you want to be asking. In terms of "implementing the adiabatic evolution", it's one thing to be able to implement the Hamiltonian. The other issue is how long do you have to simulate the adiabatic evolution for. There are certain Hamiltonians for which we know that finding the ground state is QMA-complete (see here, for example), which means it's strongly believed to be an exponential time problem (the difference between BQP and QMA is effectively the quantum version of the difference between P and NP).

• Thanks a lot for your answer. It is very informative. One thing I am still unclear is that how we know implementing $U$ does not take exponential number of gates? – xi dai Jan 1 '19 at 15:57
• Also. What do you mean by different specifications of Hamiltonian? Could you give an example on when it is hard and the alternative way to specify it to make it easy? – xi dai Jan 1 '19 at 16:05
• The point is that the calculation is basically the same as the classical calculation. So it simply depends on whether you can efficiently evaluate the function classically. You’re usually talking about an NP problem which basically guarantees that f can be implemented classically. – DaftWullie Jan 1 '19 at 17:39
• If I tell you the Hamiltonian by telling you every matrix element of the Hamiltonian, that’s guaranteed to be bad. But there certainly are Hamiltonians that I can specify without exponentially large resources. – DaftWullie Jan 1 '19 at 17:41