Quantum Annealing Explained

The Annealing Process

Classical simulated annealing, a well-known optimization technique, takes its name from metallurgical annealing, where a metal is heated and slowly cooled to reduce defects and reach a low-energy crystalline state. In simulated annealing, a classical computer explores an optimization landscape by making random changes and accepting changes that improve the objective function while occasionally accepting worse changes (with a probability that decreases over time, controlled by a "temperature" parameter). This random acceptance of worse solutions allows the algorithm to escape local minima and explore more of the solution space.

Quantum annealing replaces the thermal fluctuations of simulated annealing with quantum fluctuations. The system starts in a state of strong quantum superposition, where all possible solutions are represented simultaneously. As the anneal progresses (typically over 1 to 2000 microseconds), the quantum fluctuations are gradually reduced while the problem Hamiltonian (which encodes the optimization objective) is gradually increased. If the reduction is slow enough, the system remains in or near its ground state throughout the process, ending in the state that minimizes the problem Hamiltonian, which corresponds to the optimal solution.

The key quantum advantage, in principle, is tunneling. Classical simulated annealing must go "over" energy barriers between local minima, which requires the temperature to be high enough to provide sufficient thermal energy. Quantum annealing can "tunnel through" energy barriers, reaching lower-energy solutions even when tall barriers separate them from the current state. This tunneling advantage is most pronounced for problems with tall, narrow barriers, where classical thermal hopping is exponentially suppressed but quantum tunneling remains efficient. Whether this tunneling advantage translates to practically faster optimization than the best classical algorithms remains an active research question.

D-Wave's Quantum Annealers

D-Wave Systems, founded in 1999 in Burnaby, British Columbia, is the only company building commercial quantum annealers. Their processors use superconducting flux qubits, which are different from the transmon qubits used in gate-based processors. Flux qubits encode information in the direction of persistent current flow in a superconducting loop, and they are designed for the analog control required by the annealing process rather than the precise digital gate operations of circuit-model quantum computers.

D-Wave's Advantage processor, launched in 2020, contains 5,760 qubits connected in a Pegasus graph topology where each qubit connects to 15 others. The Advantage2 processor, in development, targets over 7,000 qubits with higher connectivity (20 connections per qubit) and longer coherence times. These qubit counts dwarf gate-based processors (which have hundreds to roughly 1,000 qubits), but the comparison is misleading because annealers and gate-based processors serve different purposes and their qubits have different capabilities. Annealer qubits cannot perform arbitrary gate operations, cannot be individually measured during computation, and have shorter coherence times than gate-based qubits.

Users program D-Wave processors by specifying a QUBO (Quadratic Unconstrained Binary Optimization) problem or equivalently an Ising model. The QUBO formulation assigns a binary variable (0 or 1) to each qubit and defines an objective function as a quadratic polynomial over these variables, with linear terms (biases) on individual qubits and quadratic terms (couplings) between connected qubit pairs. The annealer finds the assignment of binary values that minimizes this objective function. Any optimization problem that can be cast as a QUBO can be solved on the annealer, though the mapping is sometimes non-trivial and can require additional qubits for embedding the problem onto the processor's connectivity graph.

Applications of Quantum Annealing

Optimization problems suitable for quantum annealing appear in logistics, finance, manufacturing, and scientific research. Volkswagen demonstrated a traffic flow optimization system using D-Wave to route buses in Lisbon, minimizing congestion by assigning vehicles to routes that balance load across the road network. The problem was formulated as a QUBO where each variable represents a bus-route assignment, and the objective penalizes assignments that create congestion.

Financial portfolio optimization involves selecting investments that maximize return while minimizing risk, subject to constraints on total investment, sector exposure, and transaction costs. The combinatorial nature of the problem (choosing from thousands of possible assets with interdependent risk correlations) makes it a natural candidate for quantum annealing. Multiple financial institutions have tested portfolio optimization on D-Wave hardware, with results that match or approach classical solvers for small problem instances.

Manufacturing scheduling determines the order in which jobs are processed on machines to minimize total completion time, setup changes, or other cost metrics. DENSO, a major automotive parts manufacturer, uses D-Wave to optimize factory scheduling for thousands of production tasks across hundreds of machines. The scheduling problem is NP-hard in general, and even approximate solutions on large instances require sophisticated algorithms. Quantum annealing provides an alternative approach that explores the solution space differently from classical methods, potentially finding good solutions in time-constrained scenarios.

Materials science and drug discovery use quantum annealing to solve molecular conformation problems, finding the lowest-energy arrangement of atoms in a molecule. The protein folding problem, determining the 3D structure of a protein from its amino acid sequence, can be partially formulated as a QUBO by discretizing the possible bond angles and minimizing the total energy. While current quantum annealers are too small for realistically sized proteins, the approach demonstrates the connection between physics-native quantum hardware and molecular science problems.

Quantum Annealing vs Gate-Based Quantum Computing

Quantum annealing and gate-based (circuit-model) quantum computing are fundamentally different approaches. Gate-based quantum computers are universal: they can implement any quantum algorithm, including Shor's factoring, Grover's search, quantum simulation, and variational methods. Quantum annealers are special-purpose: they can only solve optimization problems formulated as QUBO or Ising models. This specialization is both a limitation (no factoring, no simulation, no arbitrary quantum algorithms) and an advantage (the hardware is simpler and can support more qubits).

The question of whether quantum annealing provides computational advantages over classical optimization has been debated for over a decade without definitive resolution. Multiple benchmarking studies have compared D-Wave processors against classical optimization algorithms (simulated annealing, parallel tempering, population annealing) on various problem classes. The results are mixed: for some problem instances, D-Wave finds solutions faster than classical methods, while for others, well-tuned classical algorithms match or beat the annealer. The difficulty of making fair comparisons (ensuring both approaches are optimally configured, using appropriate problem instances, and accounting for all overhead) has prevented a consensus conclusion.

Theoretical analysis suggests that quantum annealing can provide exponential speedups for specific problem structures involving certain energy barrier profiles, but not for general optimization problems. For many practical optimization problems, the energy landscapes do not have the specific structures that maximize the tunneling advantage. Hybrid approaches that combine quantum annealing with classical optimization (using the annealer to generate candidate solutions that are refined classically) may be the most practical path to extracting value from current quantum annealing hardware.