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$.
 
Insights auto threads is broken atm, so I'm manually creating these for new Insight articles. Towards the end of the first lecture for the Qiskit Global Summer School 2025, Foundations of Quantum Mechanics, Olivia Lanes (Global Lead, Content and Education IBM) stated... Source: https://www.physicsforums.com/insights/quantum-entanglement-is-a-kinematic-fact-not-a-dynamical-effect/ by @RUTA
If we release an electron around a positively charged sphere, the initial state of electron is a linear combination of Hydrogen-like states. According to quantum mechanics, evolution of time would not change this initial state because the potential is time independent. However, classically we expect the electron to collide with the sphere. So, it seems that the quantum and classics predict different behaviours!
Back
Top