Quantum Metropolis Algorithm

Overview

The Metropolis algorithm is the most famous method in computational physics for sampling from a thermal distribution. It proposes a random change to the current configuration and accepts it with a probability that favors lower energy, in such a way that the long-run frequencies match the Boltzmann distribution. Quantum Metropolis sampling is its quantum counterpart: it proposes random quantum moves, uses quantum measurements to compare energies, and converges to the thermal state of a quantum Hamiltonian.

Its main attraction is that it works for quantum Hamiltonians for which classical Monte Carlo methods fail because of the sign problem, such as frustrated magnets and fermionic systems. Its main limitation is that, like classical MCMC, the time it needs depends on how quickly the chain mixes, which is unknown in general.

The problem it solves

Sampling from quantum thermal states — needed for quantum simulation of physical systems at finite temperature — without the circuit depth requirements of phase estimation.

History and background

Nicholas Metropolis, Arianna and Marshall Rosenbluth, and Augusta and Edward Teller published the classical algorithm in 1953. Temme, Osborne, Vollbrecht, Poulin, and Verstraete posted the quantum version in 2009, and it appeared in Nature in 2011 under the title Quantum Metropolis Sampling. It was a proof that thermal states of quantum systems can be sampled on a quantum computer, subject to convergence conditions.

Yung and Aspuru-Guzik published a quantum-quantum Metropolis algorithm in 2012 based on quantum walks, which improved the dependence on the spectral gap. Ozols, Roetteler, and Roland showed in 2013 that quantum rejection sampling speeds up the key step. More recently, Gilyén, Chen, Doriguello, and Kastoryano developed quantum generalizations of Glauber and Metropolis dynamics in 2024 that satisfy detailed balance more cleanly, as part of the wider revival of quantum Gibbs sampling.

How it works

Applies quantum moves (random local unitaries) followed by quantum accept/reject steps that satisfy detailed balance — ensuring convergence to the thermal state. Avoids the sign problem that plagues classical Monte Carlo for quantum systems.

In a classical Metropolis step, you pick a random change, compute the energy difference, and accept with probability one if the energy goes down and with probability e to the minus beta times the increase if it goes up. Rejected moves leave the configuration unchanged. Under mild conditions, repeating this many times gives samples from the Boltzmann distribution.

In the quantum version, the system is kept in an energy eigenstate of the Hamiltonian, or close to it. A random local operation, such as a Pauli operator on a few qubits, is applied to propose a move. The new state is not an eigenstate, but a measurement of the energy, done with quantum phase estimation, collapses it into one, with probabilities given by the overlaps. The energy difference is then known, and the move is accepted with the usual Metropolis probability.

The difficulty is rejection. If the move is rejected, the system should return to its original eigenstate, but the energy measurement has already disturbed it. The original paper solves this with a rewinding procedure, based on the Marriott-Watrous technique from quantum complexity theory, which restores the original state with high probability given that the proposal was reversible.

Step by step

1. Start in an energy eigenstate of the Hamiltonian, for example one prepared by a simple method, and choose a set of random local unitaries as proposals.
2. Apply a randomly chosen proposal unitary to the current state, producing a superposition of energy eigenstates.
3. Use quantum phase estimation to measure the energy of the new state, collapsing it to an eigenstate with a definite energy.
4. Compute the energy change and decide whether to accept the move with the Metropolis probability.
5. If accepted, keep the new eigenstate. If rejected, apply the rewinding procedure to return to the original eigenstate.
6. Repeat for many steps, until the chain has mixed, then use the final state as a sample from the thermal distribution.

A worked example

Take a small chain of four spins with a Hamiltonian that has 16 energy eigenstates. Start in the ground state. A random single-spin flip proposal moves it to a superposition of excited states, and the energy measurement picks one, say with energy 2 units above the ground state. At inverse temperature beta equal to 1, the Metropolis acceptance probability is e to the minus 2, about 0.135, so the move is usually rejected and the state is rewound.

Over many steps, the chain visits the eigenstates with frequencies matching the Boltzmann weights, so averaging observables over the visited states gives thermal expectation values. For larger systems the number of steps needed depends on the mixing time, which is unknown for most Hamiltonians.

Complexity and resources

What hardware it needs

• Fault-tolerant hardware, since each step uses quantum phase estimation of the energy.
• Efficient implementations of time evolution under the Hamiltonian, for example by Trotterization or qubitization.
• Ancilla registers for phase estimation and for the rewinding procedure.

Applications

• Sampling from thermal states of frustrated quantum magnets and other systems where classical Monte Carlo fails.
• Estimating thermal expectation values and partition functions.
• A subroutine for quantum algorithms that need thermal states, such as SDP solvers and Boltzmann machine training.
• A conceptual model for quantum Gibbs samplers.

Limitations and caveats

• Mixing times are unknown for most Hamiltonians, and may be exponential at low temperature.
• Phase estimation of the energy is costly and imprecise energy measurement breaks detailed balance.
• The rewinding step adds overhead and can fail with some probability.
• Newer Gibbs samplers based on Lindbladians offer cleaner guarantees.

Common misconceptions

• Quantum Metropolis sampling does not remove the need to wait for the chain to mix. It removes the sign problem, not the mixing problem.
• It does not use phase estimation to avoid state preparation. It uses it to measure energies.
• It is not guaranteed to be efficient for all Hamiltonians.

How it compares

• Classical Metropolis sampling is simple and fast but applies to classical energy functions or to quantum systems without a sign problem.
• Quantum Gibbs samplers based on Lindbladians are the modern successors, with rigorous results at high temperature.
• Quantum imaginary-time evolution targets the ground state instead of a thermal ensemble.

Real-world impact

Potentially significant for quantum chemistry and materials simulation at finite temperature. Provides a route to simulating quantum systems that are classically intractable due to the fermionic sign problem.

Why it matters

Quantum Metropolis sampling was the first complete proposal for sampling thermal states of quantum systems on a quantum computer, and it established the framework for later work. It also illustrates a general lesson: quantum algorithms can avoid obstacles such as the sign problem that block classical methods.

Its limitations, especially the unknown mixing time and the rewinding overhead, pointed the field toward better-structured quantum thermalization methods.

Frequently asked questions

Keep learning

• Related algorithm: Quantum Gibbs Sampling
• Related algorithm: Quantum Rejection Sampling
• Related algorithm: Quantum Phase Estimation (QPE)
• Related algorithm: Quantum Boltzmann Machine (QBM)

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database