| adiabatic quantum computation | |
|---|---|
| Name | Adiabatic quantum computation |
| Caption | Schematic of adiabatic evolution between Hamiltonians |
| Type | Quantum computation model |
| Invented by | Edward Farhi, Sam Gutmann, Jeffrey Goldstone, Michael Sipser et al. |
| Year | 2000 |
| Field | Quantum Physics / Quantum computing |
| Key concepts | Adiabatic theorem, Hamiltonian evolution, quantum annealing |
| Implementations | D-Wave, IBM, Google, Rigetti |
adiabatic quantum computation
Adiabatic quantum computation (AQC) is a model of quantum computation in which a quantum system is evolved slowly under a time-dependent Hamiltonian from an easy-to-prepare ground state to a Hamiltonian whose ground state encodes the solution of a computational problem. The method exploits the quantum adiabatic theorem to remain in the instantaneous ground state during the evolution, thereby transforming computationally useful encodings into measurable outputs. AQC is significant to Quantum Physics and quantum information because it connects fundamental principles of quantum mechanics and many-body physics to practical notions of algorithmic complexity and is experimentally realized in devices marketed as quantum annealers.
The core theoretical basis is the adiabatic theorem of quantum mechanics, formulated originally by Max Born and V. Fock and extended in modern treatments. AQC defines an initial Hamiltonian H_i with known, nondegenerate ground state and a problem Hamiltonian H_p whose ground state represents the solution (often an instance of an Ising model or QUBO). The time-dependent Hamiltonian is typically H(t) = (1 - s(t)) H_i + s(t) H_p with a monotonic schedule s(t) ∈ [0,1]. The runtime T required to maintain high fidelity is bounded by inverse powers of the minimum spectral gap between the ground and first-excited states; small gaps necessitate slow, adiabatic evolution. Rigorous analyses connect gap scaling to quantum phase transitions and many-body physics, invoking perturbation theory, Landau–Zener estimates, and spectral gap theorems.
AQC is computationally equivalent to the standard quantum circuit model under polynomial-time reductions, as shown by constructive mappings between adiabatic Hamiltonians and quantum circuits. Complexity theoretic work relates AQC to classes such as BQP and QMA, with problem Hamiltonians often encoding NP-complete or QMA-complete decision problems. The efficiency of AQC for specific tasks depends on spectral gap behavior; worst-case instances can force exponential runtimes. Connections to quantum annealing emphasize heuristic optimization uses, while universality results demonstrate that adiabatic constructions can simulate universal quantum computation given engineered interactions and local Hamiltonians.
Physical realizations of AQC and annealing use a variety of hardware platforms leveraging coherent control of low-energy states. Prominent implementations include superconducting flux qubits developed by D-Wave and research groups at Google, IBM, and Rigetti. Other platforms under investigation include trapped ions (e.g., groups at Innsbruck and Maryland), cold atoms in optical lattices, and nitrogen-vacancy centers in diamond. Experimental devices implement transverse-field Ising-type Hamiltonians with programmable couplers and annealing schedules; engineering challenges include connectivity graphs, control precision, and cryogenic environments. Hybrid strategies combine AQC-inspired hardware with classical solvers in quantum-classical workflows.
AQC's performance is affected by thermal excitations, coupling to environments, control noise, and diabatic transitions from finite evolution speed. Open quantum system analyses use Lindblad equations and master-equation techniques to model decoherence and dissipation; thermalization can both hinder and, in some cases, assist convergence to ground states. Error-resilience properties differ from gate-based quantum error correction: while AQC exhibits some intrinsic robustness to control errors and certain perturbations, scalable fault tolerance requires adapted error-correction schemes or energy-gap protection strategies. Research into error suppression techniques includes optimized annealing schedules, pause-and-quench protocols, error-correcting Hamiltonians, and embedding logical qubits using quantum error correction concepts.
AQC and quantum annealing have been applied to combinatorial optimization, sampling, and machine learning tasks. Representative algorithmic targets include MAX-CUT, graph coloring, spin glass ground-state searches, and QUBO formulations for logistics and portfolio optimization. Specialized quantum algorithms map to adiabatic evolutions for exact tasks (e.g., constructive simulations of quantum circuits), while heuristic annealing strategies are used in approximate optimization. Cross-disciplinary applications span operations research, material design via ground-state searches, and training of models like quantum Boltzmann machines. Benchmarking against classical heuristics (simulated annealing, tabu search) remains an active area of evaluation.
Key milestones include the original theoretical proposal (Farhi et al., 2000), early superconducting annealer prototypes, and commercial machines from D-Wave Systems demonstrating large numbers of qubits with programmable couplers. Notable experimental benchmarks examine scaling of time-to-solution on problems mapped to Ising models, studies of quantum tunneling vs thermal effects, and tests of entanglement and coherence in annealer samples. Large-scale comparisons with classical solvers, participation in competitions and community benchmarks, and demonstrations of problem embeddings (e.g., Chimera and Pegasus graphs) have shaped understanding of practical performance. Active experimental programs at Perimeter Institute, MIT, Caltech, and national labs continue to probe gap scaling, control improvements, and hybrid algorithms to bridge theory and real-world application.
Category:Quantum computing Category:Quantum annealing Category:Computational physics