Quantum Annealing, Optimization Algorithms
Open in the Padhaiko app7.1 Principles of quantum annealing
Many real-world combinatorial optimization problems—such as vehicle routing, portfolio optimization, Max-Cut, and job-shop scheduling—are NP-hard: the number of candidate solutions grows exponentially as , and the objective function landscape contains countless local minima separated by high energy barriers.
Quantum Annealing (QA) is a specialized quantum metaheuristic (Kadowaki & Nishimori, 1998) that finds low-energy solutions to combinatorial optimization problems by exploiting quantum superposition and quantum tunneling.
Time-Dependent Quantum Annealing Hamiltonian
In transverse-field quantum annealing, an -qubit system evolves under a time-dependent Hamiltonian over total annealing duration (with normalized time ):
- Initial Driver Hamiltonian (): A transverse magnetic field along the -axis that induces quantum tunneling between computational basis states:
Its unique ground state is the uniform superposition of all candidate solutions:
- Problem Hamiltonian (): A diagonal Ising Hamiltonian in the -basis whose eigenvalues equal the classical cost function we wish to minimize:
- Annealing Schedules and :
- At : (quantum fluctuations dominate; system starts in ).
- As : decreases monotonically to while increases monotonically, locking the system into a low-energy computational basis state of .
Quantum Tunneling vs. Classical Thermal Hopping
In Classical Simulated Annealing (SA), a candidate solution escapes a local minimum by borrowing thermal energy to climb over an energy barrier of height . If the barrier is tall, thermal escape probability becomes negligibly small as .
In Quantum Annealing, the transverse field allows the quantum wavefunction to tunnel directly through tall, narrow energy barriers. The tunneling probability depends on barrier width and height roughly as , giving QA a distinct advantage on cost landscapes dominated by tall, thin spikes.
| Aspect | Simulated Annealing (Classical) | Quantum Annealing (QA) |
|---|---|---|
| Escape Mechanism | Thermal activation over energy barriers | Quantum tunneling through thin energy barriers |
| Control Parameter | Temperature cooled toward | Transverse field reduced toward |
| Initial State | Single random bitstring (or thermal ensemble) | Coherent uniform superposition |
| Bottleneck | Tall energy barriers trap search in local minima | Exponentially small minimum spectral gaps |
7.2 Relationship with adiabatic quantum computation
Quantum Annealing is physically inspired by—and is a specialized, open-system variant of—Adiabatic Quantum Computation (AQC) (Farhi et al., 2000).
The Quantum Adiabatic Theorem
Consider a closed quantum system governed by a slowly varying Hamiltonian () with instantaneous eigenstates and ordered eigenvalues . If the system is prepared in the initial ground state , it will remain in the instantaneous ground state throughout the evolution with high probability provided the total annealing time satisfies the adiabatic condition:
where is the minimum spectral energy gap between the ground state and the first excited state.
Key Distinctions: AQC vs. Quantum Annealing
Although both paradigms evolve ground states via , they differ fundamentally in computational universality and physical assumptions:
| Property | Gate-Model QC | Adiabatic Quantum Computation (AQC) | Quantum Annealing (QA) |
|---|---|---|---|
| Execution Paradigm | Discrete unitary gates () | Continuous closed-system adiabatic evolution | Continuous open-system heuristic evolution |
| Universality | Universal | Universal (polynomially equivalent to gate model if non-stoquastic allowed) | Non-universal (stoquastic Ising optimization/sampling only) |
| Error & Thermal Model | Fault-tolerant QEC possible | Idealized zero-temperature (), noise-free | Finite temperature (), environmental decoherence present |
| Primary Use Cases | Shor, Grover, QPE, HHL | Theoretical complexity equivalence, universal Hamiltonians | QUBO/Ising combinatorial optimization, Boltzmann sampling |
7.3 Optimization problem formulation (QUBO, Ising models)
To solve an optimization problem on a quantum annealer, the objective function and any constraints must be encoded into one of two mathematically equivalent representations: QUBO or the Ising spin model.
QUBO and Ising Formulations
- Quadratic Unconstrained Binary Optimization (QUBO): Uses binary decision variables and an real upper-triangular (or symmetric) matrix :
(Because for , linear terms sit directly on the diagonal .)
- Ising Spin Glass Model: Uses bipolar spin variables (eigenvalues of Pauli ):
- (Local bias / magnetic field): Biases spin toward (if ) or (if ).
- (Coupling strength): is ferromagnetic (prefers ); is antiferromagnetic (prefers ).
- Exact Equivalence Transformation: QUBO and Ising models map bijectively via:
Substituting into produces , where is an irrelevant constant energy offset.
Encoding Constraints with Penalty Terms
Because QUBO and Ising models are unconstrained, equality or inequality constraints must be converted into quadratic penalty terms added to the objective:
- Suppose we must enforce (for example, choosing exactly items). We add:
where the Lagrange multiplier / penalty weight is chosen strictly larger than the maximum possible objective gain from violating the constraint.
- Any feasible configuration satisfies , whereas any infeasible configuration incurs a strict energy penalty .
Canonical Problem Encodings
- Max-Cut Problem: Partition graph vertices of a weighted graph into two sets () and () to maximize the sum of edge weights crossing the cut:
Maximizing is equivalent to minimizing the Ising Hamiltonian:
- Number Partitioning: Split positive numbers into two subsets with equal sums by minimizing .
7.4 Quantum annealer architecture
Commercial quantum annealers (such as D-Wave Systems processors) implement programmable transverse-field Ising Hamiltonians in superconducting integrated circuits.
Physical Implementation: Superconducting Flux Qubits
- Flux Qubit: A superconducting loop interrupted by Josephson junctions. Two opposite directions of persistent circulating current correspond to spin states () and ().
- Programmable Biases & Couplers: External magnetic flux lines tilt each double-well potential to set , while tunable RF-SQUID coupler loops mediate magnetic mutual inductance between connected qubits.
- Cryogenic Operation: Chips operate at inside heavily shielded dilution refrigerators to suppress magnetic flux noise and thermal excitations.
Hardware Coupling Topologies and Minor Embedding
Physical superconducting wires cannot connect every qubit to every other qubit directly. Quantum annealers use sparse planar-fabricated graphs:
| Topology | Unit Cell / Structure | Qubit Degree (Connections) | Key Advantage |
|---|---|---|---|
| Chimera | 2D grid of bipartite cells | ( intra-cell + inter-cell) | Simple planar layout (D-Wave 2000Q) |
| Pegasus | Shifted interlocking cells with odd couplers | Shorter chains, native cliques (Advantage) | |
| Zephyr | High-density 4-way couplers | Further reduced embedding overhead |
Minor Embedding and Chain Breaks
When an optimization problem's logical interaction graph is denser than the annealer's physical hardware graph, minor embedding maps each logical variable to a connected chain of physical qubits :
- Physical qubits inside are linked with a strong ferromagnetic chain coupling so they strongly prefer taking the same spin value.
- Chain Break: If is too small compared to the problem couplings , physical qubits in the same chain may end up in opposite states ( and ) at readout, requiring post-processing (such as majority voting).
- Chain Strength Trade-off: Making too large compresses the dynamic range of the actual problem parameters due to finite hardware DAC resolution, degrading solution quality.
Worked Examples
7.1
Convert the two-variable QUBO objective function:
into an equivalent Ising Hamiltonian using . Verify that all four spin configurations yield the exact same energies as QUBO, and identify the optimal ground state.
Substituting into : Replace and :
Simplify each term:
Collecting Linear, Quadratic, and Constant Terms: Summing all terms:
Thus the Ising parameters are , , (antiferromagnetic), and constant offset .
Verifying All Four Configurations:
- : ; .
- : ; .
- : ; .
- : ; .
The unique minimum energy is at , i.e., .
Ising Hamiltonian: (). Every configuration matches QUBO identically, with unique ground state ().
7.2
Formulate the Max-Cut optimization problem on a 3-vertex weighted triangle graph with edge weights , , and as an Ising minimization Hamiltonian . Evaluate the Ising energy and cut weight for all non-trivial partitions to determine the optimal Max-Cut.
Constructing the Max-Cut Ising Hamiltonian: Recall that , where and:
Minimizing maximizes .
Evaluating Non-Trivial Partitions (up to global spin-flip symmetry ):
- All same (): .
- Isolate vertex 1 ( or ): (cuts edges and : ).
- Isolate vertex 3 (): (cuts edges and : ).
- Isolate vertex 2 ( or ): (cuts edges and : ).
Ising Hamiltonian: . The optimal Max-Cut isolates vertex (), giving minimum Ising energy and maximum cut weight .
7.3
- According to the adiabatic condition , by what factor must the required annealing time increase if the minimum spectral gap of an optimization problem shrinks from to ?
- How many physical qubits are contained in a Chimera quantum annealer array (where each unit cell is a bipartite graph)?
Adiabatic Time Scaling with Spectral Gap: Because , the ratio of required annealing times is:
A narrower spectral gap demands a longer annealing duration to avoid diabatic transitions into excited states.
Qubit Count in a Chimera Grid: Each Chimera unit cell is a bipartite graph containing physical qubits. Over a cell grid:
- The required annealing time must increase by a factor of .
- A Chimera array contains physical qubits.
Practice Exercises
Practice Exercises — Quantum Annealing and Optimization
Explain the physical difference between Simulated Annealing and Quantum Annealing when escaping local minima separated by tall, narrow potential energy barriers. Write the standard transverse-field quantum annealing Hamiltonian and identify the roles of and .
Thermal Hopping vs. Quantum Tunneling:
- Simulated Annealing (SA) relies on thermal fluctuations () to hop over an energy barrier of height , with transition probability decaying exponentially with barrier height (). Tall barriers easily trap SA in suboptimal local minima.
- Quantum Annealing (QA) introduces a transverse magnetic field that creates quantum superposition and lets the state tunnel horizontally through tall, narrow energy barriers (), enabling rapid exploration across thin spikes.
The Transverse-Field Hamiltonian: For normalized time :
- (Driver Hamiltonian): Drives quantum tunneling and prepares the initial equal superposition ; ramps down from large to .
- (Problem Hamiltonian): Encodes the classical optimization cost in computational basis eigenvalues; ramps up from to dominate at .
Simulated annealing hops over barriers thermally, whereas quantum annealing tunnels through tall, narrow barriers via the transverse field in , gradually transferring ground-state control to the Ising problem Hamiltonian .
State the Quantum Adiabatic Theorem and explain how the minimum spectral energy gap limits the runtime of Adiabatic Quantum Computation and Quantum Annealing. If (in dimensionless units) and the numerator matrix element is , estimate the scaling scale of the adiabatic runtime .
Statement of the Quantum Adiabatic Theorem: A closed quantum system initialized in the instantaneous ground state of a slowly varying Hamiltonian remains close to the instantaneous ground state throughout the evolution if the total evolution time satisfies:
where is the minimum spectral gap.
Evaluating the Runtime Scale: For :
If closes exponentially with problem size (a first-order quantum phase transition), must grow exponentially; if is shorter than coherence time , thermal excitation and diabatic Landau–Zener jumps degrade success probability.
The adiabatic theorem guarantees ground-state tracking when . For , the runtime scale is .
Formulate the following constrained binary optimization problem as an unconstrained QUBO using a quadratic penalty with weight :
Write the QUBO matrix , evaluate all binary states, and verify that the feasible optimal solution is preserved.
Adding the Quadratic Penalty Term: The constraint becomes with :
Expanding and using for binary variables:
Adding the original objective :
Constructing and Evaluating All States: Dropping the constant , the upper-triangular QUBO matrix is . Evaluating (including ) for all :
- (infeasible):
- (feasible): (minimum!)
- (feasible):
- (infeasible):
QUBO objective: , with . The global minimum is with energy (strictly below infeasible states and ).
Given the Ising model with , convert it into an equivalent QUBO expression in using , and determine the ground state in both representations.
Substituting :
Expanding each term:
Summing all terms:
Finding the Ground State: Evaluate all states:
- :
- :
- : (minimum!)
- :
Equivalent QUBO: . Ground state: / with minimum energy .
What is minor embedding in quantum annealer architectures (such as Chimera and Pegasus), why is it necessary, and what is a chain break?
Why Minor Embedding Is Needed: Superconducting quantum annealers have sparse physical qubit connectivity (degree in Chimera, degree in Pegasus), whereas real-world QUBO/Ising problems often require dense or all-to-all couplings. Minor embedding resolves this mismatch by mapping each logical variable to a connected chain of physical qubits linked together on the hardware graph.
How Chains Work and What Causes Chain Breaks: Physical qubits in a chain representing logical variable are coupled with a strong ferromagnetic interaction so they act as a single collective spin. A chain break occurs when thermal noise or strong competing problem couplings cause physical qubits within the same chain to disagree ( on one end, on the other) at the end of the anneal. Chain breaks are resolved classically (e.g., via majority voting), though frequent breaks degrade solution optimality.
Minor embedding maps each logical variable of a dense optimization graph onto a chain of ferromagnetically coupled physical qubits () on a sparse hardware graph (Chimera/Pegasus). A chain break happens when qubits inside the same chain settle into opposite spin states due to noise or overly weak .