PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum algorithms for Gibbs sampling and hitting-time estimation

Anirban Narayan Chowdhury, Rolando D. Somma

arXiv:1603.02940v1quant-ph

TL;DR

The paper addresses Gibbs-state preparation and Markov-chain hitting-time estimation, important tasks in statistical mechanics and stochastic processes. It develops quantum algorithms combining Hamiltonian simulation, spectral-gap amplification, quantum metrology, and linear-system techniques. The algorithms improve precision and parameter dependence relative to prior methods.

  • Problem

    Gibbs-state preparation and Markov-chain hitting-time estimation are important stochastic-process problems with existing classical and quantum methods.

  • Method

    The algorithms combine Hamiltonian simulation, spectral-gap amplification, quantum metrology, and quantum linear-system techniques.

  • Results

    The Gibbs algorithm uses polylogarithmic dependence on 1/ε and improves dependence on β, while the hitting-time algorithm provides almost quadratically fewer resources than a classical algorithm in the worst case.

  • Takeaways & Limitations

    The algorithms provide speedups for Gibbs-state preparation and hitting-time estimation, with relevance to statistical physics, optimization, and search algorithms.

Abstract

from arXiv · show

We present quantum algorithms for solving two problems regarding stochastic processes. The first algorithm prepares the thermal Gibbs state of a quantum system and runs in time almost linear in $\sqrt{N β/{\cal Z}}$ and polynomial in $\log(1/ε)$, where $N$ is the Hilbert space dimension, $β$ is the inverse temperature, ${\cal Z}$ is the partition function, and $ε$ is the desired precision of the output state. Our quantum algorithm exponentially improves the dependence on $1/ε$ and quadratically improves the dependence on $β$ of known quantum algorithms for this problem. The second algorithm estimates the hitting time of a Markov chain. For a sparse stochastic matrix $P$, it runs in time almost linear in $1/(εΔ^{3/2})$, where $ε$ is the absolute precision in the estimation and $Δ$ is a parameter determined by $P$, and whose inverse is an upper bound of the hitting time. Our quantum algorithm quadratically improves the dependence on $1/ε$ and $1/Δ$ of the analog classical algorithm for hitting-time estimation. Both algorithms use tools recently developed in the context of Hamiltonian simulation, spectral gap amplification, and solving linear systems of equations.

I. INTRODUCTION

The paper targets Gibbs-distribution sampling and Markov-chain hitting-time estimation, two problems important in statistical mechanics and stochastic processes. It introduces quantum algorithms for both tasks, with improved parameter dependence over prior approaches.

  • Gibbs sampling supports computing thermodynamic quantities and understanding systems in thermal equilibrium, with applications including optimization.
  • Hitting-time estimation characterizes Markov chains and supports search for marked configurations.
  • Classical approaches commonly use Monte Carlo simulations whose runtime depends on repeated applications of a probability rule and Markov-chain properties such as spectral gap.
  • Prior quantum work studied Gibbs-state preparation and quantum hitting times, often obtaining polynomial speedups in parameters such as spectral gap or Hilbert-space dimension.
  • The paper presents quantum algorithms for preparing thermal Gibbs states and estimating Markov-chain hitting times.
  • The Gibbs-state algorithm has complexity almost linear in √(Nβ/Z), with polylogarithmic factors in the problem quantities and inverse output precision.
  • The hitting-time algorithm estimates the hitting time of a reversible, irreducible, aperiodic Markov chain using linear-system and quantum-metrology techniques.

II. MAIN TECHNIQUES

The algorithms combine Hamiltonian simulation, spectral-gap amplification, linear combinations of unitaries, amplitude amplification, and amplitude estimation. Their implementation relies on structured Hamiltonian representations and oracle or circuit access to relevant operators.

  • Core tools: The framework uses Hamiltonian simulation, spectral-gap amplification, quantum metrology, and quantum linear-system methods.
  • Hamiltonian model: Hamiltonians are modeled through eigenenergies and eigenstates, with dimension N=2^n for an n-qubit system.
  • Hamiltonian model: The method assumes positive semidefinite Hermitian components, possibly after rescaling the Hamiltonian.
  • Spectral-gap amplification: Spectral-gap amplification constructs an auxiliary Hamiltonian that behaves like the square root of the original Hamiltonian.
  • Hamiltonian simulation: The evolution operator of the auxiliary Hamiltonian is approximated by a circuit with gate complexity C_W(t,ε).
  • Hamiltonian simulation: For local physical Hamiltonians, efficient preprocessing and simulation methods can yield complexity polylogarithmic in 1/ε.
  • Hamiltonian representation: Hamiltonians can be represented using positive coefficients, projectors, or ±1-eigenvalue unitaries such as Pauli operators.
  • Hamiltonian simulation: The auxiliary simulation uses ancillary registers and conditional unitary operations whose gate cost scales with the number of terms.

III. PREPARATION OF GIBBS STATES

The algorithm prepares an approximation of the thermal Gibbs state by implementing an operator proportional to e^(-βH/2) as a finite linear combination of unitary evolutions. Its complexity is polylogarithmic in 1/ε and improves the dependence on β relative to earlier methods.

  • The thermal Gibbs state is the density matrix describing a quantum system H at inverse temperature β ≥ 0.
  • The Gibbs distribution assigns measurement probability p_j = e^(-βE_j)/Z to eigenstate |ψ_j⟩.Here, Z is the partition function.
  • The algorithm targets Gibbs-distribution sampling through a unitary that prepares a normalized version of X|φ0⟩.The resulting state approximates the desired Gibbs state after discarding the ancillary register.
  • The algorithm has complexity polylogarithmic in 1/ε and improves the dependence on β compared with methods in.
  • The method implements e^(-βH/2) using a linear combination of unitary operations generated from evolutions under an auxiliary Hamiltonian.The decomposition is obtained through the Hubbard–Stratonovich transformation and discretized into a finite sum.

A. Algorithm

The Gibbs-state circuit first prepares a maximally entangled input state and then applies a normalized linear combination of Hamiltonian-evolution unitaries using amplitude amplification.

  • A. Algorithm: The first circuit step prepares a maximally entangled state using an additional n-qubit ancillary system.The ancillary systems together form the register a.
  • A. Algorithm: The second step prepares a normalized version of X|φ0⟩ using linear-combination-of-unitaries techniques and amplitude amplification.Implementing X requires a Hamiltonian simulation method for the unitaries W_j.

B. Validity and complexity

After tracing out the ancillas, the prepared state is an approximation to the Gibbs state, with amplitude amplification and Hamiltonian simulation determining the gate complexity.

  • B. Validity and complexity: The algorithm prepares the normalized state with constant probability using amplitude amplification.The number of amplification steps scales as O(1/||X|φ0⟩||).
  • B. Validity and complexity: Tracing out the ancillary register yields the Gibbs state, because measurement probabilities are proportional to e^(-βE_j).Trace distance is controlled using the non-increasing property of the trace norm under quantum operations.
  • B. Validity and complexity: The gate complexity includes preparation of |φ0⟩ and implementation of X through Hamiltonian simulation.Preparing |φ0⟩ requires O(n) controlled operations, while implementing X is dominated by the simulation cost of W_j.
  • B. Validity and complexity: The resulting complexity contains the factor Z(C_W(t, ε′) + n + log(J)).

IV. ESTIMATION OF HITTING TIMES

The paper estimates the expected time for a reversible Markov chain to reach a marked subset by relating hitting time to an inverse Hamiltonian and implementing that relation quantumly. The resulting complexity improves the classical dependence on precision and the spectral parameter.

  • IV. ESTIMATION OF HITTING TIMES: The hitting time is the expected first time a Markov process reaches a marked subset M from the stationary initial distribution.The remaining configurations form the unmarked subset U.
  • IV. ESTIMATION OF HITTING TIMES: Classical estimation requires O(th(σ/ε)^2) expected applications of P at constant confidence.This follows from averaging repeated samples and applying Chebyshev’s inequality.
  • IV. ESTIMATION OF HITTING TIMES: In the worst case, the classical complexity is O(1/(Δ^3ε^2)) when Δ ≪ 1.This case has th = π_U/Δ and σ^2 = O(π_U/Δ^2).
  • IV. ESTIMATION OF HITTING TIMES: The hitting time can be expressed as π_U times the expected value of the inverse Hamiltonian 1/H in a suitable state.This relation supplies the basis for the quantum algorithm.
  • IV. ESTIMATION OF HITTING TIMES: The quantum algorithm estimates th within precision ε and constant confidence using a unitary procedure based on Hamiltonian simulation and oracle access.The construction assumes procedures for accessing marked states, stationary amplitudes, and nonzero entries of P.
  • IV. ESTIMATION OF HITTING TIMES: The dominant complexity is ˜O(1/(εΔ^3/2)), a quadratic improvement over the classical complexity.The dependence on d is hidden in additional factors that are polylogarithmic in d/(εΔ).

A. Algorithm

The hitting-time algorithm uses amplitude estimation to estimate a matrix-element expression and rescales that estimate to obtain the hitting time.

  • B. Validity and complexity: Amplitude estimation estimates ⟨0|⟨0|a3 T |0⟩|0⟩a3 within precision ǫ′ and constant confidence c ≈ 0.81.The resulting estimate is denoted ˜th, and the algorithm outputs ˆth = zK˜th.

B. Validity and complexity

The algorithm achieves absolute precision O(ǫ) for the hitting time while controlling intermediate precision and simulation costs through amplitude estimation and Hamiltonian evolution.

  • Validity: O(ǫ) absolute precision is achieved for the hitting-time estimate ˆth.The chosen intermediate precision ǫ′ ensures the total error remains O((zK/γ)ǫ).
  • Complexity: O(1/ǫ′) uses of T support the amplitude-estimation procedure.Each T uses the oracle and square-root-unitary operations required by the algorithm.
  • Complexity: O((1/∆) log(1/(∆ǫ))) is the maximum evolution time needed for each unitary implementing X′.The construction also requires preparing a state whose gate complexity is O(log(1/(∆ǫ))).
  • Complexity: Polylogarithmic factors in d/(ǫ∆) are disregarded in the resulting gate-complexity expression.This expression follows after substituting the chosen ǫ′ and evolution time.

V. CONCLUSIONS

The paper presents quantum algorithms for Gibbs-state preparation and Markov-chain hitting-time estimation using Hamiltonian simulation, spectral gap amplification, and quantum linear-system techniques. It reports improved precision and parameter scaling for both problems.

  • Contributions: Two quantum algorithms address thermal Gibbs-state preparation and Markov-chain hitting-time estimation.The stated techniques include Hamiltonian simulation, spectral gap amplification, and quantum linear-system methods.
  • Gibbs-state preparation: Polylogarithmic 1/ǫ resource scaling prepares an ǫ-close thermal Gibbs state in trace distance.The approach approximates the exponential operator by a finite linear combination of unitary operations and uses spectral gap amplification to improve β dependence to almost linear in √β.
  • Hitting-time estimation: Almost quadratically fewer resources than a classical algorithm estimate hitting time in all parameters in the worst-case scenario.The algorithm assumes initialization in the Markov chain’s stationary distribution and applies the inverse of a positive operator derived from the stochastic matrix.
  • Hitting-time estimation: ˜O(1/ǫ) complexity dependence arises from amplitude estimation at constant confidence c ≈ 0.81.The hitting time is expressed as an expectation value involving the inverse of an operator H.

Appendix A: Simulation of ˜H

Appendix A constructs and simulates ˜H for sparse stochastic matrices by decomposing it into efficiently implementable unitary terms, with costs expressed through oracle access and sparsity.

  • Oracle model: The simulation assumes a procedure QP that computes locations and magnitudes of nonzero entries of P.The transition probabilities are assumed to use a constant number of bits, with rounding errors disregarded.
  • Complexity parameters: The sparsity parameter d is the largest number of nonzero matrix elements per row or column of P.This parameter controls the number of decomposition terms and additional gate costs.
  • Hamiltonian construction: H is constructed from transition-probability-dependent states and projected into the subspace U.The construction yields a decomposition as a linear combination of rank-1 projectors.
  • Simulation construction: ˜H is decomposed into simple unitary operations so that exp(−i ˜Ht) can be simulated.Diagonal terms are implemented using phase operations conditioned on transition-probability data.
  • Unitary decomposition: K′ = O(d^2) colored terms decompose the first component into sums of commuting rank-1 projectors.The graph is colored using a bipartite graph coloring, with each color corresponding to one term.
  • Implementation details: The implementation of each colored unitary uses QP to identify neighboring vertices and construct the required circuit transformation.The procedure reverses the oracle computations after retaining the circuit description needed for the map.
  • Unitary implementation: O(1) uses of QU and QP and O(d log(N)) additional gates implement each unitary ˜Uk.The full decomposition contains ˜K = O(d^2) terms.
  • Simulation complexity: The simulation complexity is stated in terms of the required uses of QU and QP and the corresponding overall gate complexity.These bounds follow from Hamiltonian-simulation results applied to exp(−i ˜Ht).
Loading 1603.02940v1…