A Understanding how quantum annealing solves QUBO problems

  • A
  • Thread starter Thread starter siddjain
  • Start date Start date
  • Tags Tags
    Quantum
siddjain
Messages
2
Reaction score
1
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$?
 
Physics news on Phys.org
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$.
 
Not an expert in QM. AFAIK, Schrödinger's equation is quite different from the classical wave equation. The former is an equation for the dynamics of the state of a (quantum?) system, the latter is an equation for the dynamics of a (classical) degree of freedom. As a matter of fact, Schrödinger's equation is first order in time derivatives, while the classical wave equation is second order. But, AFAIK, Schrödinger's equation is a wave equation; only its interpretation makes it non-classical...
I am not sure if this falls under classical physics or quantum physics or somewhere else (so feel free to put it in the right section), but is there any micro state of the universe one can think of which if evolved under the current laws of nature, inevitably results in outcomes such as a table levitating? That example is just a random one I decided to choose but I'm really asking about any event that would seem like a "miracle" to the ordinary person (i.e. any event that doesn't seem to...
Back
Top