Adiabatic Quantum Computing

Adiabatic Quantum Computing#

The adiabatic theorem and quantum annealing for optimization. QAOA as the gate-model bridge to adiabatic computing.

Adiabatic quantum computing (AQC) offers a fundamentally different approach to quantum computation. Instead of applying a sequence of gates, the system is prepared in the ground state of a simple Hamiltonian and then slowly evolved to a problem Hamiltonian whose ground state encodes the answer. The Quantum Approximate Optimization Algorithm (QAOA) bridges adiabatic and gate-model paradigms, making this approach accessible on circuit-based quantum hardware.

The Adiabatic Theorem#

The adiabatic theorem states: if a quantum system starts in the ground state of a Hamiltonian \(H_0\) and the Hamiltonian is changed sufficiently slowly to \(H_1\), the system remains in the instantaneous ground state throughout the evolution.

The interpolating Hamiltonian is:

\[H(s) = (1 - s)\,H_0 + s\,H_1, \quad s \in [0, 1]\]

where \(s = t/T\) parameterizes the evolution time. The runtime \(T\) must satisfy:

\[T \gg \frac{\max_{s} |\langle E_1(s)| \frac{dH}{ds} |E_0(s)\rangle|}{\Delta_{\min}^2}\]

where \(\Delta_{\min} = \min_s (E_1(s) - E_0(s))\) is the minimum energy gap between the ground state and the first excited state. Small gaps require slow evolution and long runtimes.

The gap determines the difficulty

The minimum spectral gap \(\Delta_{\min}\) is the critical quantity. For problems where the gap closes polynomially in system size, AQC runs in polynomial time. When the gap closes exponentially (as in some NP-hard problems), AQC provides no speedup over classical brute force.

Setting Up an Optimization Problem#

To solve a combinatorial optimization problem using AQC:

Encode the cost function as a diagonal Hamiltonian \(H_1\). For binary optimization, map \(x_i \in \{0,1\}\) to \(\sigma_i^z\) eigenvalues via \(x_i \to (1 - \sigma_i^z)/2\). The cost function becomes an Ising Hamiltonian:

\[H_1 = -\sum_{\langle i,j\rangle} J_{ij}\,\sigma_i^z \sigma_j^z + \sum_i h_i\,\sigma_i^z\]

Choose a mixing Hamiltonian \(H_0 = -\sum_i \sigma_i^x\), whose ground state is the uniform superposition \(|+\rangle^{\otimes n}\). This state is easy to prepare.
Evolve from \(H_0\) to \(H_1\) according to the interpolation schedule.
Measure in the computational basis. The result is the (approximate) solution to the optimization problem.

Quantum Annealing#

Quantum annealing is the practical, finite-temperature implementation of AQC. D-Wave’s quantum processors implement this approach with thousands of qubits. Key differences from ideal AQC:

The system operates at finite temperature, so thermal excitations can kick the system out of the ground state.
The annealing schedule is not guaranteed to be slow enough for adiabaticity.
Connectivity is limited; not all qubit pairs interact directly.

Despite these limitations, quantum annealing has shown practical utility for sampling, optimization heuristics, and hybrid workflows.

From Adiabatic to Gate Model: QAOA#

The Quantum Approximate Optimization Algorithm (QAOA) discretizes the adiabatic path into \(p\) steps, each parameterized by angles \((\beta_k, \gamma_k)\):

\[|\boldsymbol{\gamma}, \boldsymbol{\beta}\rangle = \prod_{k=1}^{p} e^{-i\beta_k H_0}\, e^{-i\gamma_k H_1}\, |+\rangle^{\otimes n}\]

For \(p \to \infty\) with appropriate parameter schedules, QAOA recovers the adiabatic evolution. For finite \(p\), QAOA is a variational algorithm: \(\gamma_k\) and \(\beta_k\) are optimized classically to minimize \(\langle H_1 \rangle\).

QAOA Circuit Structure#

For a MaxCut problem on a graph \(G = (V, E)\):

Initialize all qubits in \(|+\rangle\) (apply \(H\) to each qubit).
For each QAOA layer \(k = 1, \ldots, p\):
- Cost layer: For each edge \((i,j) \in E\), apply \(e^{-i\gamma_k \sigma_i^z \sigma_j^z}\) (implemented as CNOT-\(R_z\)-CNOT).
- Mixer layer: For each qubit \(i\), apply \(R_x(2\beta_k)\).
Measure all qubits.

Code Examples#

Qiskit

from qiskit.circuit import QuantumCircuit, Parameter
import numpy as np

n_qubits = 4
p = 2  # QAOA depth
edges = [(0,1), (1,2), (2,3), (3,0)]  # cycle graph

gamma = [Parameter(f'γ_{k}') for k in range(p)]
beta = [Parameter(f'β_{k}') for k in range(p)]

qc = QuantumCircuit(n_qubits)

# Initial state: uniform superposition
qc.h(range(n_qubits))

for k in range(p):
    # Cost layer: ZZ interactions for each edge
    for i, j in edges:
        qc.cx(i, j)
        qc.rz(2 * gamma[k], j)
        qc.cx(i, j)
    # Mixer layer: X rotations
    for i in range(n_qubits):
        qc.rx(2 * beta[k], i)

qc.measure_all()
print(qc)

Cirq

import cirq
import sympy

n_qubits = 4
p = 2
qubits = cirq.LineQubit.range(n_qubits)
edges = [(0,1), (1,2), (2,3), (3,0)]

circuit = cirq.Circuit()
circuit.append(cirq.H.on_each(*qubits))

for k in range(p):
    gamma = sympy.Symbol(f'γ_{k}')
    beta = sympy.Symbol(f'β_{k}')
    # Cost layer
    for i, j in edges:
        circuit.append(cirq.ZZPowGate(exponent=gamma / np.pi).on(qubits[i], qubits[j]))
    # Mixer layer
    for i in range(n_qubits):
        circuit.append(cirq.rx(2 * beta).on(qubits[i]))

circuit.append(cirq.measure(*qubits, key='result'))
print(circuit)

PennyLane

import pennylane as qml
from pennylane import numpy as np

n_qubits = 4
p = 2
edges = [(0,1), (1,2), (2,3), (3,0)]
dev = qml.device("default.qubit", wires=n_qubits)

def cost_hamiltonian():
    coeffs = [-0.5] * len(edges)
    obs = [qml.PauliZ(i) @ qml.PauliZ(j) for i, j in edges]
    return qml.Hamiltonian(coeffs, obs)

@qml.qnode(dev)
def qaoa_circuit(gamma, beta):
    for i in range(n_qubits):
        qml.Hadamard(wires=i)
    for k in range(p):
        # Cost layer
        for i, j in edges:
            qml.CNOT(wires=[i, j])
            qml.RZ(2 * gamma[k], wires=j)
            qml.CNOT(wires=[i, j])
        # Mixer layer
        for i in range(n_qubits):
            qml.RX(2 * beta[k], wires=i)
    return qml.expval(cost_hamiltonian())

gamma = np.random.uniform(0, 2*np.pi, p)
beta = np.random.uniform(0, np.pi, p)
print(f"Cost: {qaoa_circuit(gamma, beta):.4f}")

PyQuil

from pyquil import Program
from pyquil.gates import H, CNOT, RZ, RX, MEASURE
import numpy as np

n_qubits = 4
p = 2
edges = [(0,1), (1,2), (2,3), (3,0)]

prog = Program()
ro = prog.declare('ro', 'BIT', n_qubits)

# Initial superposition
for i in range(n_qubits):
    prog += H(i)

# QAOA layers (with fixed example parameters)
gamma = np.random.uniform(0, 2*np.pi, p)
beta = np.random.uniform(0, np.pi, p)

for k in range(p):
    for i, j in edges:
        prog += CNOT(i, j)
        prog += RZ(2 * gamma[k], j)
        prog += CNOT(i, j)
    for i in range(n_qubits):
        prog += RX(2 * beta[k], i)

for i in range(n_qubits):
    prog += MEASURE(i, ro[i])

print(prog)

QAOA Performance#

\(p\) (depth)	Approximation Ratio (MaxCut)	Notes
1	\(\geq 0.6924\)	Proven bound for 3-regular graphs
2	\(\geq 0.7559\)	Improved but diminishing returns
\(p \to \infty\)	1.0	Recovers optimal solution
Classical best (GW)	\(\geq 0.878\)	Goemans-Williamson SDP relaxation

At low depth, QAOA underperforms the best classical approximation algorithms. The potential advantage lies in scaling to larger \(p\) on quantum hardware where classical simulation becomes intractable.

Adiabatic Quantum Computing

Contents