PadhaikoAll subjects

Quantum Annealing, Optimization Algorithms

Quantum Computing (ENCT 328)

Open in the Padhaiko app

7.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.

Definition

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 ):

  1. 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:

  1. Problem Hamiltonian (): A diagonal Ising Hamiltonian in the -basis whose eigenvalues equal the classical cost function we wish to minimize:
  1. 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.

AspectSimulated Annealing (Classical)Quantum Annealing (QA)
Escape MechanismThermal activation over energy barriersQuantum tunneling through thin energy barriers
Control ParameterTemperature cooled toward Transverse field reduced toward
Initial StateSingle random bitstring (or thermal ensemble)Coherent uniform superposition
BottleneckTall energy barriers trap search in local minimaExponentially 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).

Theorem

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:

Comparison of Gate-Model QC, AQC, and Quantum Annealing
PropertyGate-Model QCAdiabatic Quantum Computation (AQC)Quantum Annealing (QA)
Execution ParadigmDiscrete unitary gates ()Continuous closed-system adiabatic evolutionContinuous open-system heuristic evolution
UniversalityUniversalUniversal (polynomially equivalent to gate model if non-stoquastic allowed)Non-universal (stoquastic Ising optimization/sampling only)
Error & Thermal ModelFault-tolerant QEC possibleIdealized zero-temperature (), noise-freeFinite temperature (), environmental decoherence present
Primary Use CasesShor, Grover, QPE, HHLTheoretical complexity equivalence, universal HamiltoniansQUBO/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.

Definition

QUBO and Ising Formulations

  1. 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 .)

  1. Ising Spin Glass Model: Uses bipolar spin variables (eigenvalues of Pauli ):
  1. 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:

where the Lagrange multiplier / penalty weight is chosen strictly larger than the maximum possible objective gain from violating the constraint.

Canonical Problem Encodings

  1. 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:

  1. 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

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:

Evolution of Quantum Annealer Connectivity Graphs
TopologyUnit Cell / StructureQubit Degree (Connections)Key Advantage
Chimera2D grid of bipartite cells ( intra-cell + inter-cell)Simple planar layout (D-Wave 2000Q)
PegasusShifted interlocking cells with odd couplersShorter chains, native cliques (Advantage)
ZephyrHigh-density 4-way couplersFurther reduced embedding overhead
Definition

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 :


Worked Examples

Example 7.1

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., .

Answer:

Ising Hamiltonian: (). Every configuration matches QUBO identically, with unique ground state ().

Example 7.2

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 ):

  1. All same (): .
  2. Isolate vertex 1 ( or ): (cuts edges and : ).
  3. Isolate vertex 3 (): (cuts edges and : ).
  4. Isolate vertex 2 ( or ): (cuts edges and : ).
Answer:

Ising Hamiltonian: . The optimal Max-Cut isolates vertex (), giving minimum Ising energy and maximum cut weight .

Example 7.3

7.3

  1. 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 ?
  2. 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:

Answer:
  1. The required annealing time must increase by a factor of .
  2. A Chimera array contains physical qubits.

Practice Exercises

Practice Exercises — Quantum Annealing and Optimization

Question 1

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 .
Answer:

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 .

Question 2

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.

Answer:

The adiabatic theorem guarantees ground-state tracking when . For , the runtime scale is .

Question 3

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):
Answer:

QUBO objective: , with . The global minimum is with energy (strictly below infeasible states and ).

Question 4

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!)
  • :
Answer:

Equivalent QUBO: . Ground state: / with minimum energy .

Question 5

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.

Answer:

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 .

← Quantum Error and CorrectionQuantum Machine Learning →