PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Metropolis Sampling

K. Temme, T. J. Osborne, K. G. Vollbrecht, D. Poulin, F. Verstraete

arXiv:0911.3635v2quant-phcond-mat.str-elhep-lat

TL;DR

Efficiently preparing ground and Gibbs states is a central challenge in quantum simulation, where classical approaches can encounter a sign problem. The paper introduces a quantum Metropolis algorithm that walks over Hamiltonian eigenstates, reproduces Gibbs-state averages, and avoids that sign problem. Its convergence depends on spectral gaps and update choices, while finite resources can produce errors and full-scale implementations may remain technologically out of reach.

  • Problem

    Preparing physically relevant ground and Gibbs states for generic interacting quantum systems remains unresolved, while classical quantum Monte Carlo can suffer from a sign problem.

  • Method

    The paper proposes a direct quantum generalization of Metropolis sampling using phase estimation, random local unitaries, and reversible quantum accept/reject procedures.

  • Results

    The algorithm generates states reproducing Gibbs-state averages for observables and samples Hamiltonian eigenstates directly, avoiding the fermionic sign problem.

  • Takeaways & Limitations

    Quantum Metropolis sampling provides a route to simulating generic bosonic and fermionic many-body systems on quantum computers.

  • Takeaways & Limitations

    Convergence depends on the stochastic map’s spectral gap and update choices, and finite resources can shift the fixed point away from the Gibbs state.

Abstract

from arXiv · show

The original motivation to build a quantum computer came from Feynman who envisaged a machine capable of simulating generic quantum mechanical systems, a task that is believed to be intractable for classical computers. Such a machine would have a wide range of applications in the simulation of many-body quantum physics, including condensed matter physics, chemistry, and high energy physics. Part of Feynman's challenge was met by Lloyd who showed how to approximately decompose the time-evolution operator of interacting quantum particles into a short sequence of elementary gates, suitable for operation on a quantum computer. However, this left open the problem of how to simulate the equilibrium and static properties of quantum systems. This requires the preparation of ground and Gibbs states on a quantum computer. For classical systems, this problem is solved by the ubiquitous Metropolis algorithm, a method that basically acquired a monopoly for the simulation of interacting particles. Here, we demonstrate how to implement a quantum version of the Metropolis algorithm on a quantum computer. This algorithm permits to sample directly from the eigenstates of the Hamiltonian and thus evades the sign problem present in classical simulations. A small scale implementation of this algorithm can already be achieved with today's technology

1 Introduction

Many-body quantum simulations are difficult because Hilbert space grows exponentially, especially for strongly interacting systems. The paper proposes a quantum Metropolis algorithm to prepare ground and thermal states without the classical sign problem.

  • 1 Introduction: Hilbert space grows exponentially with particle number, making many-body quantum systems difficult to study computationally.Existing approximate methods are often limited to weak interactions, while strong interactions are central to high-Tc superconductors, large-molecule electronic structure, and quark confinement.
  • 1 Introduction: Classical Metropolis sampling provides a general approach for calculating properties of interacting systems, but quantum Monte Carlo methods can face a sign problem.The classical method samples configurations according to their statistical significance and has influenced many fields.
  • 1 Introduction: Quantum computers can simulate dynamical evolution, but preparing physically relevant ground or thermal states remains a crucial unresolved problem.Quantum phase estimation is not generally scalable because it requires a variational state with large ground-state overlap.
  • 1 Introduction: The proposed quantum Metropolis algorithm generalizes the classical method directly and implements one iteration in polynomial time on a quantum computer.It is designed for generic bosonic and fermionic many-body systems and avoids the aforementioned sign problem.
  • 1 Introduction: The algorithm can prepare ground states, but like classical Metropolis sampling it is not expected to reach an arbitrary Hamiltonian’s ground state in polynomial time.The authors note that efficient thermalization is expected when the physical system itself thermalizes in polynomial time.

2 Summary of results

The quantum Metropolis algorithm performs a random walk over Hamiltonian eigenstates, using quantum energy estimation and reversible accept/reject procedures. Its fixed point can be the Gibbs state, while convergence depends on ergodicity, spectral gaps, update choices, and finite-resource errors.

  • Classical Metropolis setup: The classical Metropolis algorithm samples important configurations by accepting lower-energy moves and probabilistically accepting higher-energy moves.For an energy increase, the acceptance probability is exp(β(Eold − Enew)).
  • Quantum Metropolis challenge: The quantum version must create an ergodic random walk over Hamiltonian eigenstates with appropriate Boltzmann weights.Its complications include unknown eigenvectors, irreversible energy measurements, and proving that the Gibbs state is a fixed point.
  • Quantum Metropolis step: Phase estimation prepares or measures energy eigenstates, after which a random local unitary creates a superposition of candidate eigenstates.For simplicity, the presentation initially assumes non-degenerate commensurate eigenvalues, although the supplementary material removes those conditions.
  • Quantum Metropolis step: Directly measuring the candidate energy would irreversibly collapse the state, preventing restoration of the original state after rejection.The quantum procedure therefore uses a measurement designed to reveal only one bit and minimally disturb the new state.
  • Rejection procedure: A rejection is implemented through a binary-measurement process that returns the computer to the input eigenstate with success probability exponentially close to 1.The process operates in a two-dimensional subspace and recursively repeats measurements when necessary.
  • Summary of results: The algorithm generates states whose statistical averages reproduce those of the Gibbs state ρG = e^−βH/Z for any observable X.The sampled states are computed with respect to actual Hamiltonian eigenstates.
  • Fixed point: Quantum detailed balance makes the Gibbs state a possible fixed point, while ergodicity of the update map ensures uniqueness.A universal gate set can satisfy the required ergodicity condition.
  • Summary of results: The quantum Metropolis algorithm avoids the fermionic sign problem because it samples directly from Hamiltonian eigenstates.The method can therefore support fermionic simulations using the Jordan–Wigner transformation.

3 Description of the quantum Metropolis algorithm

The quantum Metropolis algorithm uses phase estimation, local quantum updates, and measurement-based rejection to sample Gibbs states while handling imperfect rejection and finite precision. Its correctness and runtime depend on detailed balance, reject-step convergence, Markov-chain mixing, and implementation errors.

  • Initialization and energy estimation: Quantum phase estimation prepares an energy eigenstate and records its energy before each Metropolis update.The algorithm assumes perfect phase estimation in its basic description, with finite-precision effects treated separately.
  • Errors and convergence: Overall runtime includes mixing error, imperfect deterministic rejection, and finite-precision errors that shift the map's fixed point away from the Gibbs state.Rapid mixing requires a polynomial spectral gap for each problem instance, while finite resources produce a fixed-point error bounded by ε*.
  • Proposal and acceptance: A randomly selected efficiently implementable unitary C proposes a local update, after which coherent phase estimation determines the proposed state's energy.The unitary set must be rich enough to generate all possible transitions, although its choice affects convergence time.
  • Proposal and acceptance: A controlled one-qubit operation W conditioned on the two energy registers implements the energy-dependent acceptance step, followed by an ancilla measurement.Outcome 1 accepts the move; outcome 0 rejects it and initiates the recovery procedure.
  • Reject-step recovery: After rejection, alternating measurements of projectors Pα and Qα recover an eigenstate in the original energy subspace before the next iteration.A P1 outcome signals successful recovery, while repeated measurements continue otherwise.
  • Reject-step recovery: The reject-step failure probability decays exponentially with the number of repetitions, and n = O(1/ε) recursion steps reduce failure below ε.The algorithm must choose ε so failure over a complete Metropolis cycle remains a small constant.

4 Fixed point of the algorithm and influence of imperfections

The ideal quantum Metropolis chain has the Gibbs state as a fixed point, with uniqueness ensured by ergodic updates. Imperfect simulation, finite energy resolution, and phase-estimation fluctuations produce controllable deviations from this ideal behavior.

  • Fixed point of the ideal chain: The quantum Metropolis algorithm yields the exact Gibbs state as its fixed point when phase estimation resolves all eigenstate energies exactly.For non-integer energies, finite precision is unavoidable, but polynomial resolution can still approximate the Gibbs state well under suitable mixing conditions.
  • Influence of imperfections: Trotter-Suzuki simulation error can be suppressed at polynomial cost when the required simulation effort grows sub-polynomially in 1/ε_H.For typical condensed-matter and quantum-chemistry Hamiltonians, the Hamiltonian simulation circuit length scales polynomially with system size.
  • Influence of imperfections: Rounding energies to r bits changes thermal weights by factors of exp(β2^-r), so choosing r ≫ log β makes this error arbitrarily small.The simulation cost grows exponentially with r, giving complexity that increases linearly with β.
  • Influence of imperfections: Phase-estimation outputs fluctuate around the true energy, producing generalized POVM measurements rather than deterministic projectors onto energy bins.The worst case occurs when an eigenenergy lies exactly between two r-bit values, making the two estimates equally likely.
  • Fixed point of the ideal chain: In the non-degenerate-energy case, the quantum dynamics reduce to the standard classical Metropolis algorithm and satisfy detailed balance.The projectors onto energy subspaces become projectors onto individual eigenstates.
  • Fixed point of the ideal chain: Ergodicity of the update map ensures uniqueness of the Gibbs fixed point, and universal-gate updates make the chain ergodic for finite β.Detailed balance alone establishes that the Gibbs state is a possible fixed point; uniqueness depends on the update set.

5 Implementation

The implementation decomposes the quantum Metropolis procedure into Hamiltonian simulation and energy measurement using quantum phase estimation. These operations can be realized efficiently for relevant k-particle Hamiltonians, with polynomial scaling under stated conditions.

  • Hamiltonian simulation: Hamiltonian evolution e−itH is simulated by decomposing H into s terms that are individually easy to simulate.The circuit uses the Berry–Childs approach and has length T_H dependent on simulation time, error, and Hamiltonian structure.
  • Hamiltonian simulation: Polynomial effort simulates e−itH for t ∼p(N) with precision ǫ_H ∼1/q(N), where p and q are polynomials.For typical condensed-matter and quantum-chemistry Hamiltonians, s scales polynomially with particle number N.
  • Energy measurement: For an eigenstate |ψ_j⟩, sufficiently accurate pointer-position measurement provides an approximation to E_j.The continuous pointer is discretized into a 2^r-dimensional register represented by r qubits.
  • Energy measurement: The discretized system–pointer Hamiltonian contains terms involving at most k + 1 particles when H is a k-particle Hamiltonian.This permits simulation of the phase-estimation dynamics with the same Hamiltonian-simulation method.
  • Energy measurement: Quantum phase estimation approximately projects the system into an energy eigenstate and outputs an r-bit approximation to its energy.The procedure appends r ancilla qubits, applies Φ, and measures them in the computational basis.

6 Quantum detailed balance

Quantum detailed balance is introduced to ensure that the quantum Markov chain has the desired fixed point. For a completely positive map, the condition implies a real spectrum and guarantees the reference state is stationary.

  • Consequences: A completely positive map obeying detailed balance has a real spectrum because E is similar to E_σ.This is one of the properties inferred directly from the detailed-balance condition.
  • Consequences: The reference state σ is guaranteed to be a fixed point of the completely positive map.Equivalently, σ is the steady state of E under the stated condition.
  • Verification: When the diagonal basis of σ is known, detailed balance can be checked straightforwardly in that basis.The criterion represents σ as σ = Σ_i p_i|ψ_i⟩⟨ψ_i| and tests whether E_σ is Hermitian.

7 Binary measurements and pairs of subspaces

The reject move relies on a normal form for pairs of non-commuting projectors. Jordan’s decomposition supplies a basis in which the projectors have a structured block representation, enabling the required binary measurements.

  • Motivation: Implementing the reject move depends on a special normal form for two non-commuting Hermitian projectors.The normal form makes the measurement structure tractable for the quantum Metropolis procedure.
  • Jordan decomposition: Jordan’s lemma gives a basis in which projectors P_1 and Q_1 have a structured block form when their ranks satisfy p + q ≤ n.The assumption q ≥ p can be made without loss of generality.
  • Jordan decomposition: The block form is parameterized by a real diagonal p × p matrix D with entries between 0 and 1.Its ordered entries satisfy 0 ≤ d_1 ≤ … ≤ d_p ≤ 1.
  • Construction: The decomposition is obtained by choosing a basis for P_1, expressing Q_1 in block form, and applying singular-value decomposition to its rectangular block.Block-diagonal unitary transformations preserve P_1 while producing the desired representation.
  • Binary measurements: Complementary projectors P_0 = I − P_1 and Q_0 = I − Q_1 complete the binary measurements and have analogous structure.These complementary projectors are used alongside P_1 and Q_1 in the measurement scheme.

8 An experimental implementation

A five-qubit circuit demonstrates the quantum Metropolis building blocks for a two-qubit Heisenberg system. The implementation uses exact phase estimation, random Pauli updates, controlled Metropolis rotations, and iterative rejection recovery.

  • Example system: A two-qubit example shows that the quantum Metropolis algorithm can be implemented with circuits using today’s technology.The example targets Gibbs-state preparation for a two-spin-1/2 Heisenberg ferromagnet.
  • Example system: The Heisenberg Hamiltonian has spectrum {0, 2}, with a threefold-degenerate zero eigenvalue, enabling exact one-bit phase estimation.For this system, phase estimation requires simulating the Hamiltonian for t = π/2, corresponding to a SWAP gate.
  • Metropolis update: The controlled Metropolis unitary uses two controlled R_y rotations, with temperature encoded by θ_β through cos(θ_β) = e^−β.The circuit can be simplified by conditioning later operations on the first phase-estimation result.
  • Metropolis update: The update step randomly selects Pauli operations from {σ_x2, σ_x3, σ_z2, σ_z3} and applies the corresponding unitary.The selected operation acts on one of the two system qubits.
  • Reject recovery: If an update is rejected, alternating P_s and Q_s measurements eventually returns the system to its original energy subspace when P_1 is obtained.Outcome s = 1 indicates matching energies; failure s = 0 triggers the alternating recovery procedure.
  • Iteration: After recovery, ancilla registers are cleaned and prepared for the next Metropolis iteration.The procedure then returns to Step 1 with a new input state.

9 Simulation of quantum many-body systems

The paper sketches how quantum Metropolis sampling could support simulations of quantum many-body systems across chemistry, Hubbard models, and gauge theories. These applications require efficient qubit-based representations and Hamiltonian simulation, but gauge-theory implementations face major practical obstacles.

  • The Hubbard model: The Hubbard model describes electrons in a periodic potential within a lowest-band tight-binding approximation using hopping and interaction terms.Its Hamiltonian acts on fermionic creation and annihilation operators defined over lattice sites.
  • Fermionic encodings: After fixing a lattice-site order, each Jordan-Wigner-transformed summand can be implemented with cost scaling at most linearly in total system size.More general fermionic Hamiltonians can be implemented similarly.
  • Quantum chemistry: Quantum Metropolis applications include quantum chemistry, where molecular electron binding energies depend on nuclear positions.The electronic Hamiltonian is obtained using the Born-Oppenheimer approximation, treating nuclear positions as external parameters.
  • Gauge theories: Gauge-theory simulations require a Hamiltonian formulation with gauge constraints, but the Kogut-Susskind approach is hard to implement quantum mechanically.Each link carries an infinite-dimensional Hilbert space, creating a significant implementation challenge.
Loading 0911.3635v2…