6
$\begingroup$

I am reading on how the adiabatic evolution can be approximated by a quantum circuit of size poly(nT) and I am trying to follow the derivation in the paper

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 section 4, page 4, it states that:

"The Campbell-Baker-Hausdorff theorem tells us how well we can approximate ‘parallel Hamiltonians’ by consecutive ones: $|||\exp(A+B) − \exp(A)\exp(B)||| \in O(|||AB|||)$."

The norm I believe is just the operator induced norm. I am familiar with the BCH formula but could not see the above relation directly coming out from the formula. So how is this relation derived?

I tried looking into the reference which is "matrix analysis" by Rajendra Bhatia but didn't get any success.

Improve this question
$\endgroup$
3
$\begingroup$

The Baker-Campbell-Hausdorff formula says that you can expand $$ \log(e^Ae^B)=A+B+[A,B]/2+\ldots=M $$ where higher order terms have 3 or more uses of $A$ and $B$. Now, let's say that $A$ and $B$ are anti-Hermitian so that $e^A$, and similar terms, are unitary. We have $$ \|\exp(A+B)-\exp(A)\exp(B)\|=\|e^{A+B}\left(\mathbb{I}-e^Me^{-(A+B)}\right)\|. $$ The matrix norm is invariant under the action of unitaries, so this is the same as $$ \|\mathbb{I}-e^Me^{-(A+B)}\|. $$ Now, you might apply the BCH formula again to get $$ \|\mathbb{I}-e^{M-A-B-[M,A+B]/2+\ldots}\|, $$ the point being that the leading order $A+B$ stuff cancels from $M-A-B$ and the commutator, leaving terms like $[A,B]$. If both $A$ and $B$ are small ($O(\epsilon)$), then higher order terms have vanishing relevance, so we have $$ \|\mathbb{I}-e^{[A,B]/2+O(\epsilon^3)}\|, $$ and if we do an expansion on that, we get $$ \|\mathbb{I}-(\mathbb{I}+[A,B]/2+O(\epsilon^3))\|=\|[A,B]\|/2+O(\epsilon^3)=O(\|AB\|). $$

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for the answer. I wonder in the of quantum annealing,(A and B are i times the starting and end hamiltonian of annealing respectively), whether we can assume A and B are actually small. $\endgroup$
    – xi dai
    Dec 10 '18 at 17:44
  • $\begingroup$ Your original question was about the simulation of an adiabatic quantum computation. When doing that, the thing that you're simulating is $\cos\theta A+\sin\theta B$, and you're probably trying to build it out of $A$ and $B$. You break this evolution down into lots of tiny steps of size $\epsilon$. If each step can be achieved to $O(\epsilon^2)$, you can achieve the overall evolution of $O(\epsilon)$. $\endgroup$
    – DaftWullie
    Dec 11 '18 at 7:40
  • $\begingroup$ Do you mean that because each time step is small, so each of the A and B are also small, so we can disregard the higher power terms? $\endgroup$
    – xi dai
    Dec 12 '18 at 2:57
  • $\begingroup$ Yes, exactly right. $\endgroup$
    – DaftWullie
    Dec 12 '18 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.