Q&AIntermediateOptimisation

What is the difference between quantum annealing and gate-based quantum computing?

Annealing slowly evolves from a simple Hamiltonian to the problem Hamiltonian to find its ground state; the gate model applies general gate sequences.

In Quantum Annealing, the system starts in the ground state of a simple “transverse field” Hamiltonian $-\sum X_i$, and the Hamiltonian is then changed slowly towards the problem's Ising Hamiltonian. If the change is slow enough, the system stays close to its ground state (Kadowaki & Nishimori 1998). Specialised devices for this model target optimisation problems written in Ising or QUBO form.

The Gate Model is general: it can run Shor, Grover and phase estimation, and approximately simulate annealing itself. QAOA can be seen as a “discretised” version of adiabatic evolution with a finite number of layers.

There is no general evidence that quantum annealing outperforms classical simulated annealing or the best classical solvers on practical problems. The optimisation lab simulates only the gate model (QAOA) and compares it with classical simulated annealing.

Related topics

References

  1. Tadashi Kadowaki; Hidetoshi Nishimori (1998). Quantum annealing in the transverse Ising model. Phys. Rev. E 58(5):5355–5363 doi:10.1103/PhysRevE.58.5355
  2. Edward Farhi; Jeffrey Goldstone; Sam Gutmann (2014). A Quantum Approximate Optimization Algorithm. arXiv:1411.4028 doi:10.48550/arXiv.1411.4028
  3. S. Kirkpatrick; C. D. Gelatt; M. P. Vecchi (1983). Optimization by Simulated Annealing. Science 220(4598):671–680 doi:10.1126/science.220.4598.671
  4. Andrew Lucas (2014). Ising formulations of many NP problems. Frontiers in Physics 2:5 doi:10.3389/fphy.2014.00005