quantum annealing

# tag · @ author · ! scientist

Quantum annealing is a heuristic method for solving integer optimization problems, relying on the principles of quantum mechanics. Unlike the classical analog, where crossing a high barrier requires thermal excitation and is random, here quantum tunneling dominates: the system 'passes' through narrow barriers, effectively leaving local minima and striving for the global one. Programming the problem reduces to setting longitudinal fields and couplings in the Ising model.

History

The idea appeared in the 1980s-90s as a generalization of the classical simulated annealing algorithm. The first commercial machine based on this principle was created by the Canadian company D-Wave Systems in 2011.

How it works

The problem is encoded in the energy of an artificial 'quantum magnet' consisting of many elements (qubits). The system is started in a simple but highly uncertain state and the control fields are slowly changed. Thanks to the tunneling effect (seeping through obstacles), it ends up with high probability in the state with the lowest energy — that is the answer.

💡 The D-Wave Advantage processor with 5000+ qubits solves some quadratic optimization problems in milliseconds, while a classical supercomputer would take hours for the same — but only for specially crafted instances.

Quantum annealing is a specialized paradigm of adiabatic quantum computing. The system is initialized in the ground state of an easily prepared Hamiltonian H_i (e.g., transverse field) and evolves under a slowly varying total Hamiltonian H(t) = A(t)H_i + B(t)H_p, where H_p is the problem Hamiltonian (in the simplest case, the Ising model), A(t) monotonically decreases, B(t) increases. According to the adiabatic theorem, if the change is slow enough, the system remains in the instantaneous ground state and at the end of the anneal gives a measurement corresponding to the minimum of H_p with high probability. Advantage is achieved when the landscape has tall but thin barriers: tunneling through them scales better than thermal activation. In practice, excitations are inevitable due to finite time, noise, and small gaps in the spectrum.

History

The idea of quantum annealing dates back to annealing models in neural networks (1989). It was formalized in 1998 by Tadashi Kadowaki and Hidetoshi Nishimori as a quantum version of the simulated annealing method. A practical breakthrough is associated with the development of superconducting circuits: the D-Wave team (founded in 1999) introduced the first commercial 128-qubit annealer in 2011. Theoretical foundations rest on early research on tunneling (Leo Esaki, 1958) and adiabatic evolution.

How it works

Qubits (superconducting loops with Josephson junctions) form an array described by the Ising model with longitudinal fields h_i and couplings J_ij. Initialization is a deep transverse field Γ, creating a superposition of all binary states. Then Γ is smoothly turned off, and h_i and J_ij are turned on. Evolution is governed by the adiabatic condition: τ ≫ max_t |⟨1(t)|∂H/∂t|0(t)⟩| / (E_1(t)−E_0(t))^2, requiring the annealing time τ to be much larger than the inverse square of the minimum energy gap. The tunneling amplitude is exponentially suppressed with increasing barrier width, so for wide barriers, classical algorithms can compete.

H(t) = (1 - s(t)) H_i + s(t) H_p

H_i — initial Hamiltonian (e.g., transverse field), H_p — problem Hamiltonian (Ising model), s(t) — dimensionless annealing parameter, monotonically changing from 0 to 1 over time T.

Open problems & fun facts

It has not yet been proven that quantum annealing provides a fundamental exponential speedup for practically significant problem classes compared to the best classical algorithms.; Decoherence and thermal excitations limit the size and accuracy of existing devices.; The problem of programming arbitrary connectivity graphs is solved by minor embedding, reducing the effective number of qubits.

💡 The D-Wave processor is cooled to 15 millikelvin — a temperature 180 times lower than in outer space, so that superconducting circuits operate without thermal noise.

No articles yet

quantum annealing

History

How it works

History

How it works

History

How it works

Open problems & fun facts

Related articles