NISQ Algorithms

Quantum Adiabatic Algorithm

Adiabatic theorem, slowly varying Hamiltonians

The Quantum Adiabatic Algorithm exploits the adiabatic theorem of quantum mechanics to evolve a quantum system from the ground state of a simple, initial Hamiltonian to the ground state of a complex problem Hamiltonian. By varying the Hamiltonian sufficiently slowly, the system remains in its instantaneous ground state throughout the evolution, ultimately encoding the solution to an optimization problem in the final quantum state. This framework naturally connects to quantum annealing and represents one of the earliest proposed models for quantum-enhanced computation.

The Adiabatic Theorem & Interpolating Hamiltonians

The quantum adiabatic theorem, formulated by Born and Fock in 1928, states that a quantum system initially prepared in the non-degenerate ground state of a time-dependent Hamiltonian will remain in the instantaneous ground state provided the Hamiltonian changes sufficiently slowly. In the context of quantum computation, this principle is harnessed by constructing an interpolating Hamiltonian that smoothly transforms from a trivial initial Hamiltonian, whose ground state is easy to prepare, to a problem Hamiltonian whose ground state encodes the solution to a computationally hard optimization problem.

The standard interpolating schedule takes the form of a linear combination where a dimensionless parameter s = t/T sweeps from 0 to 1 over a total evolution time T. The initial Hamiltonian is typically chosen as a transverse-field Hamiltonian with a simple product-state ground state, such as the uniform superposition |+ angle^{otimes n}. The problem Hamiltonian is constructed to be diagonal in the computational basis, with its eigenvalues corresponding to the cost function of the optimization problem. The time-dependent Schrodinger equation governs the exact dynamics, but in practice the evolution is implemented through Trotterized product formulas on gate-based hardware.

The computational complexity of the adiabatic algorithm is governed by the minimum energy gap between the ground state and the first excited state along the interpolation path. If this gap remains polynomially small, the adiabatic runtime T scales polynomially with system size. However, if the gap closes exponentially, as occurs for certain hard instances, the required evolution time becomes exponentially long, negating any quantum speedup. This gap dependence makes the adiabatic approach intimately connected to the spectral properties of the problem Hamiltonian and its embedding in the computational landscape.

\hat{H}(s) = (1 - s) \hat{H}_0 + s \hat{H}_p, \quad s = \frac{t}{T}

Interpolating Hamiltonian

i \hbar \frac{d}{dt} |\psi(t)\rangle = \hat{H}(t) |\psi(t)\rangle

Time-Dependent Schrodinger Equation

T \gg \frac{\max_{s} |\langle e_1(s) | \partial_s \hat{H}(s) | e_0(s) \rangle|}{\min_s \Delta E(s)^2}

Adiabatic Condition

•Adiabatic Condition: The evolution time T must scale inversely with the square of the minimum spectral gap to maintain adiabaticity with bounded error.
•Hamiltonian Interpolation: A linear path H(s) = (1-s)H_0 + sH_p is standard, though non-linear paths can sometimes improve the minimum gap.
•Ground State Preparation: The initial Hamiltonian H_0 is chosen so its ground state |\psi(0)\rangle is a product state that can be prepared with single-qubit gates.
•Digitization: On gate-based NISQ devices, continuous time evolution is approximated via Suzuki-Trotter decomposition into discrete quantum circuits.

Quantum Annealing & NISQ Limitations

Quantum annealing is the physical realization of the adiabatic algorithm in analog quantum hardware, most notably D-Wave systems. In these devices, the Hamiltonian is implemented through tunable couplings between superconducting qubits, and the system undergoes thermal fluctuations at finite temperature rather than purely coherent evolution. The combination of non-zero temperature and limited coherence times means that quantum annealing operates in a regime intermediate between adiabatic quantum computing and classical thermal annealing.

On NISQ gate-based devices, the adiabatic algorithm must be digitized through Trotter-Suzuki decomposition, breaking the continuous evolution into a sequence of short discrete gates. Each Trotter step approximates the infinitesimal evolution under the instantaneous Hamiltonian, but the approximation introduces errors that scale with the step size. Deep circuits resulting from many Trotter steps exacerbate decoherence and gate errors, creating a tension between adiabatic fidelity and hardware constraints. Consequently, variational and hybrid approaches have emerged as pragmatic alternatives for NISQ-era hardware.

Recent research has explored shortcuts to adiabaticity, counter-diabatic driving, and optimized annealing schedules that can reduce the required evolution time without violating adiabatic conditions. These techniques add control Hamiltonians that actively suppress non-adiabatic transitions, effectively widening the spectral bottleneck. While theoretically powerful, their implementation on current hardware remains challenging due to the non-local and potentially complex nature of counter-diabatic terms.

e^{-i \hat{H} t} \approx \left( e^{-i \hat{H}_0 t/n} e^{-i \hat{H}_p t/n} \right)^n + O\left(\frac{t^2}{n}\right)

Trotterized Evolution

\hat{H}(t) = A(t) \hat{H}_0 + B(t) \hat{H}_p, \quad A(0) \gg B(0), \; A(T) \ll B(T)

Quantum Annealing Schedule

•Thermal Effects: Finite-temperature environments can excite the system out of the ground state, making quantum annealing a thermally-assisted process.
•Trotter Error: Digitization introduces an error O(dt^2) per step for first-order Trotter, requiring a trade-off between circuit depth and approximation fidelity.
•Gap Closure: Exponentially small gaps in the spectrum lead to exponentially long evolution times, fundamentally limiting the algorithm's efficiency on hard instances.
•Counter-Diabatic Driving: Additional control terms can suppress non-adiabatic transitions but often require non-local interactions difficult to realize physically.

Code in Action

Runnable implementations you can copy and experiment with.

Qiskit: Trotterized Adiabatic Evolution

Simulate adiabatic evolution for an Ising chain using Qiskit's PauliEvolutionGate to implement Trotterized time steps.

adiabatic_qiskit.py

from qiskit import QuantumCircuit
from qiskit.circuit.library import PauliEvolutionGate
from qiskit.quantum_info import SparsePauliOp
import numpy as np

n_qubits = 3
T = 10.0
steps = 50
dt = T / steps

# Initial Hamiltonian: transverse field (ground state |+>^n)
H_0 = SparsePauliOp(["XII", "IXI", "IIX"], coeffs=[1.0, 1.0, 1.0])
# Problem Hamiltonian: Ising chain with ZZ interactions
H_p = SparsePauliOp(["ZZI", "IZZ"], coeffs=[1.0, 1.0])

circuit = QuantumCircuit(n_qubits)
# Prepare ground state of H_0
circuit.h(range(n_qubits))

# Adiabatic evolution via Trotter steps
for t in range(steps):
    s = t / steps
    H_s = (1 - s) * H_0 + s * H_p
    evol = PauliEvolutionGate(H_s, time=dt)
    circuit.append(evol, range(n_qubits))

circuit.measure_all()
print(circuit.draw(output="text"))

PennyLane: Digital Adiabatic Evolution

Implement digitized adiabatic evolution for a three-qubit Ising chain using PennyLane's native gates.

adiabatic_pennylane.py

import pennylane as qml
import numpy as np

n_qubits = 3
dev = qml.device("default.qubit", wires=n_qubits)

T = 10.0
steps = 50
dt = T / steps

@qml.qnode(dev)
def adiabatic_evolution():
    # Ground state of transverse field Hamiltonian
    for i in range(n_qubits):
        qml.Hadamard(i)
    # Trotterized adiabatic evolution
    for t in range(steps):
        s = t / steps
        # Problem Hamiltonian (ZZ interactions)
        qml.IsingZZ(2 * s * dt, wires=[0, 1])
        qml.IsingZZ(2 * s * dt, wires=[1, 2])
        # Initial Hamiltonian (transverse field)
        for i in range(n_qubits):
            qml.RX(2 * (1 - s) * dt, wires=i)
    return qml.probs()

print(adiabatic_evolution())

Explore next

Quantum Approximate Optimization Algorithm

Explore next

Quantum Natural Gradient

from qiskit import QuantumCircuit from qiskit.circuit.library import PauliEvolutionGate from qiskit.quantum_info import SparsePauliOp import numpy as np n_qubits = 3 T = 10.0 steps = 50 dt = T / steps # Initial Hamiltonian: transverse field (ground state |+>^n) H_0 = SparsePauliOp(["XII", "IXI", "IIX"], coeffs=[1.0, 1.0, 1.0]) # Problem Hamiltonian: Ising chain with ZZ interactions H_p = SparsePauliOp(["ZZI", "IZZ"], coeffs=[1.0, 1.0]) circuit = QuantumCircuit(n_qubits) # Prepare ground state of H_0 circuit.h(range(n_qubits)) # Adiabatic evolution via Trotter steps for t in range(steps): s = t / steps H_s = (1 - s) * H_0 + s * H_p evol = PauliEvolutionGate(H_s, time=dt) circuit.append(evol, range(n_qubits)) circuit.measure_all() print(circuit.draw(output="text"))

import pennylane as qml import numpy as np n_qubits = 3 dev = qml.device("default.qubit", wires=n_qubits) T = 10.0 steps = 50 dt = T / steps @qml.qnode(dev) def adiabatic_evolution(): # Ground state of transverse field Hamiltonian for i in range(n_qubits): qml.Hadamard(i) # Trotterized adiabatic evolution for t in range(steps): s = t / steps # Problem Hamiltonian (ZZ interactions) qml.IsingZZ(2 * s * dt, wires=[0, 1]) qml.IsingZZ(2 * s * dt, wires=[1, 2]) # Initial Hamiltonian (transverse field) for i in range(n_qubits): qml.RX(2 * (1 - s) * dt, wires=i) return qml.probs() print(adiabatic_evolution())