Understanding how quantum annealing solves QUBO problems

  • A
  • Thread starter siddjain
  • Start date
  • #1
2
1
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$?
 

Answers and Replies

Related Threads on Understanding how quantum annealing solves QUBO problems

Replies
0
Views
75
Replies
7
Views
3K
  • Last Post
Replies
8
Views
3K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
8
Views
4K
Replies
13
Views
3K
Replies
90
Views
14K
Replies
2
Views
713
Replies
35
Views
3K
  • Last Post
Replies
2
Views
2K
Top