Understanding how quantum annealing solves QUBO problems

[siddjain]

TL;DR Summary

understanding the math behind how quantum annealing or adiabatic quantum optimization works in general

This question is in regards to Dwave's quantum computer which is tailored to solve QUBO problems (minimize $x^T Q x$ where $Q$ is a symmetric matrix and $x$ is $n$ length vector of $0$s and $1$s) using quantum annealing. I would like to understand how it works. The claim is that it does so by minimizing the energy associated with a Hamiltonian. The system is evolved from initial state $H_0$ to target state $H_1$ ($H_0$ and $H_1$ denote the Hamiltonians associated with the initial and final states) and theorem of adiabatic quantum computation guarantees that if the system started in ground state of $H_0$, it will be found in the ground state of $H_1$. QM also tells us that the ground state of a quantum system is given by the eigenvector corresponding to lowest eigenvalue of the associated Hamiltonian $H$.

I would like to understand how does finding the minimum of $x^T Q x$ equate to finding (the lowest eigenvalued) eigenvector of a matrix $H$ and if so what is the relation between $Q$ (a $n \times n$ matrix) and $H$ (a $2^n \times 2^n$ matrix since the Hamiltonian acts on the wave function or state vector of the quantum system)? If these two problems are the same how come books on quadratic programming and wikipedia have nothing to say about it?

Here is my argument:

• $x$ = $n$ length vector of $0$s and $1$s
• $\Psi = 2^n$ length unit vector of complex probability amplitudes (continuous variables)
• The quantum annealing process will minimize $\Psi^T H \Psi$ and we get $\Psi^* = (\alpha_1, \ldots , \alpha_{2^n})$. $\Psi^*$ is ground-state of the final system.
• when we measure, one of the $\alpha$'s will collapse to $1$ and all others will collapse to $0$ and the result can be transformed into one of the $2^n$ values of $x$
• So how have we minimized $x^T Q x$?

 

[azntoon]

To answer this question we need to consider how the Hamiltonian $H$ relates to the quadratic form $x^T Q x$. The Hamiltonian $H$ is composed of two parts, a "drift" part $H_0$ and a "problem" part $H_1$. The problem part is defined as $H_1 = \sum_i \sum_j Q_{ij}x_ix_j$ in a way that when minimized it will minimize the quadratic form $x^T Q x$. This is done by encoding the values of $Q_{ij}$ in the matrix $H_1$ which is then applied to the initial state $\Psi$. The adiabatic theorem then guarantees that if the system started in the ground state of $H_0$ it will end up in the ground state of $H_1$ and this is where the minimum of the quadratic form is found. In summary, to minimize $x^T Q x$, Dwave's quantum computer works by encoding the values of $Q_{ij}$ in the "problem" part of the Hamiltonian $H_1$ and evolving the system from the initial state (ground state of $H_0$) to the final state (ground state of $H_1$). The adiabatic theorem then guarantees that the system will be found in the ground state of the Hamiltonian which corresponds to the minimum of $x^T Q x$.