PaperlayerView exact revision on arXiv

Source-linked AI summary

Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolution

Mario Motta, Chong Sun, Adrian Teck Keng Tan, Matthew J. O' Rourke, Erika Ye, Austin J. Minnich, Fernando G. S. L. Brandao, Garnet Kin-Lic Chan

arXiv:1901.07653v3quant-ph

TL;DR

Quantum algorithms for ground, excited, and thermal states seek resource-efficient alternatives to deep quantum Metropolis circuits and classical optimization. This paper develops quantum imaginary-time evolution, quantum Lanczos, and a METTS-like thermal-state approach, reporting accurate ground-state convergence and practical near-term implementation prospects.

  • Problem

    Quantum thermal-state sampling needs alternatives to quantum Metropolis procedures, whose rejection and reset steps require deep circuits.

  • Method

    The approach replaces imaginary-time evolution with local unitaries, stabilizes time-evolved states for quantum Lanczos, and uses QITE within a METTS-like sampling procedure.

  • Results

    QITE converged the ground state to arbitrary accuracy, and the authors report that its protocol should be practical for intermediate system sizes on near-term devices.

  • Takeaways & Limitations

    The algorithms support resource-efficient ground-state and thermal-state calculations on near-term quantum devices.

  • Takeaways & Limitations

    Although QITE improves over exp(O(N)) classical scaling, its quasi-polynomial dependence on the number of Hamiltonian terms can remain prohibitive in practice.

Abstract

from arXiv · show

The accurate computation of Hamiltonian ground, excited, and thermal states on quantum computers stands to impact many problems in the physical and computer sciences, from quantum simulation to machine learning. Given the challenges posed in constructing large-scale quantum computers, these tasks should be carried out in a resource-efficient way. In this regard, existing techniques based on phase estimation or variational algorithms display potential disadvantages; phase estimation requires deep circuits with ancillae, that are hard to execute reliably without error correction, while variational algorithms, while flexible with respect to circuit depth, entail additional high-dimensional classical optimization. Here, we introduce the quantum imaginary time evolution and quantum Lanczos algorithms, which are analogues of classical algorithms for finding ground and excited states. Compared to their classical counterparts, they require exponentially less space and time per iteration, and can be implemented without deep circuits and ancillae, or high-dimensional optimization. We furthermore discuss quantum imaginary time evolution as a subroutine to generate Gibbs averages through an analog of minimally entangled typical thermal states. Finally, we demonstrate the potential of these algorithms via an implementation using exact classical emulation as well as through prototype circuits on the Rigetti quantum virtual machine and Aspen-1 quantum processing unit.

SUPPLEMENTAL INFORMATION

The supplemental material explains how QITE replaces local non-unitary imaginary-time steps with measurement-assisted local unitaries and establishes their approximation and resource requirements. It also describes computational simplifications, extensions to long-range and fermionic Hamiltonians, and temperature-dependent support growth.

  • Measurement-assisted unitary construction: QITE emulates each local non-unitary step e^−∆τh[l] with a unitary e^−i∆τA[l] acting on a domain around h[l].A[l] is Hermitian and expanded in Pauli strings over D qubits; the domain must be sufficiently large relative to the state’s correlation length for small-∆τ accuracy.
  • Measurement-assisted unitary construction: The coefficients of the approximating unitary are obtained by minimizing a quadratic error and solving a linear system involving S + S^T.When S + S^T has a null space, the system can be solved using a generalized inverse or conjugate-gradient iteration.
  • Simplifications and extensions: For real Hamiltonians and states, b and S + S^T require y(D) Pauli-string expectation values, reducing dense linear-system cost by a factor of 1/8.The method also extends to long-range terms by modifying the unitary domain and replaces Pauli operators with fermionic field operators for fermionic Hamiltonians.
  • QITE approximation guarantees: A theorem guarantees local unitaries approximating Trotter updates, with support controlled by correlation properties and approximation accuracy.The construction follows from nearby reduced density matrices and Uhlmann’s theorem, which supplies a unitary on the purifying region.
  • Resource scaling: The total tomography and classical linear-system cost scales as exp(O(Nq)), while the resulting runtime is exponential in correlation length and quasi-polynomial in Trotter steps and Hamiltonian terms.For local-state approximation, unitary support becomes independent of the number of Hamiltonian terms, unlike the polylogarithmic dependence required for global approximation.
  • Temperature dependence: At inverse temperature β, unitary support scales as O(β/∆), giving linear growth with temperature when ∆ is constant.The supplemental analysis expects analogous linear correlation and support growth in two dimensions, although rigorous results are unavailable there.

1 qubit field model

The section specifies a one-qubit Hamiltonian model previously used for quantum simulations on physical devices, with α = 1 and initialization in the Z basis.

  • The Hamiltonian was previously used as a model for quantum simulations on physical devices, with α = 1.
  • Simulations initialize the qubit in the Z basis.

1D Heisenberg and transverse field Ising model

This section introduces four one-dimensional spin Hamiltonians used in the paper: short-range and long-range Heisenberg models, a field-dependent Heisenberg model, and an antiferromagnetic transverse-field Ising model.

  • The 1D short-range Heisenberg Hamiltonian is defined.
  • The 1D short-range Heisenberg Hamiltonian is also specified in the presence of a field.
  • The 1D long-range Heisenberg Hamiltonian is defined.
  • The 1D AFM transverse-field Ising Hamiltonian is defined.

1D Hubbard model

This section specifies the 1D Hubbard model on an open-boundary lattice and describes its basis-function labeling and Jordan–Wigner representation.

  • 1D Hubbard model: The 1D Hubbard Hamiltonian is introduced for a lattice with nearest-neighbor summation and open-boundary conditions.The supplied passage states that nearest neighbors are summed and that the boundaries are open.
  • 1D Hubbard model: The n lattice sites are indexed as i = 0 . . . n −1, with spin labels σ ∈{↑, ↓}.The notation distinguishes the two spin states at each lattice site.
  • 1D Hubbard model: The basis functions are ordered by site and spin, beginning with |ϕ0⟩= |0 ↑⟩, |ϕ1⟩= |0 ↓ ⟩, |ϕ2⟩= |1 ↑⟩, and |ϕ3⟩= |1 ↓⟩.The passage states that the construction contains 2n −1 basis functions.
  • 1D Hubbard model: Under the Jordan-Wigner transformation, the Hamiltonian is written using indices p = 0 . . . 2n −2 and q < p.The transformed form is specified through these index ranges and ordering condition.

H2 molecule minimal basis model · MAXCUT Hamiltonian

The paper models H2 in the STO-6G minimal basis and maps its molecular Hamiltonian to a two-qubit operator. It also formulates MAXCUT as a Hamiltonian ground-state problem and shows that imaginary-time evolution yields MAXCUT solutions with probability above 60% despite oscillations.

  • H2 molecule minimal basis model: H2 is modeled at the STO-6G level using a restricted Hartree–Fock calculation in an orthonormal molecular-orbital basis.The molecular geometry is specified by the H–H distance R.
  • H2 molecule minimal basis model: The second-quantized H2 Hamiltonian is encoded through a Bravyi–Kitaev transformation into a two-qubit operator.The resulting operator acts on two qubits associated with the molecular-orbital representation.
  • H2 molecule minimal basis model: The encoded H2 operator contains identity, single-qubit Z terms, ZZ coupling, and XX and YY couplings with coefficients g_i.The coefficients g_i are specified in Table I of reference.
  • MAXCUT Hamiltonian: MAXCUT seeks a subset S of graph vertices that maximizes the number of edges crossing between S and its complement S^c.The cut weight is denoted C(S).
  • MAXCUT Hamiltonian: For the illustrated graph, the listed cuts and their complements solve MAXCUT with weight Cmax = 5.The solutions include {0, 2, 4}, {0, 1, 2}, and {3, 4}.
  • MAXCUT Hamiltonian: MAXCUT is formulated as a Hamiltonian ground-state problem by assigning one qubit per vertex and each partition to a computational-basis state.The partition bit z_i equals 1 for vertices in S and 0 for vertices in S^c; the minimal eigenvalue identifies the solution.
  • MAXCUT Hamiltonian: Starting from |+⟩⊗n and evolving in imaginary time, measurements collapse onto computational-basis eigenstates of the MAXCUT Hamiltonian.The measured eigenvalue C determines the cut value, and the probability of obtaining a solution with C = Cmax remains above 60% even with oscillations at D = 2.

Numerical simulation details · QITE stabilization · QLanczos stabilization

The simulations stabilized QITE by regularizing noisy overlap matrices, while QLanczos constructed and filtered time-evolved state sequences before solving a generalized eigenvalue problem. Different stabilization parameters were used for exact emulation versus QVM and QPU calculations.

  • QITE stabilization: Sampling noise can destabilize Eq. (13), so S + S^T was regularized by adding δ to its diagonal.The simulations used δ = 0.01 for 1-qubit calculations and δ = 0.1 for 2-qubit calculations.
  • QLanczos stabilization: QLanczos generates normalized wavefunctions from different imaginary-time projections of an initial state, using QITE as a subroutine.The projected states are indexed by l with 0 ≤ l < L_max.
  • QLanczos stabilization: For exact imaginary-time evolution with projections of matching parity, matrix elements can be computed using experimentally accessible expectation values.The quantities n_r are evaluated recursively, and under inexact evolution they approximate S_l,l′ and H_l,l′.
  • QLanczos stabilization: QLanczos solves Hx = ESx to approximate the ground state from a linear combination of the time-evolved states.The generalized eigenvalue problem can be ill-conditioned because S may have small or negative eigenvalues from dependence, finite precision, noise, and approximate matrix construction.
  • QLanczos stabilization: A regularized QLanczos sequence retains each next state only when its overlap with the last retained state satisfies |⟨Φ_l|Φ_last⟩| < s.The procedure repeats until the desired number of vectors is reached, then solves the generalized eigenvalue equation in the resulting subspace.
  • QLanczos stabilization: The regularized problem removes eigenvalues of S̃ below ε before solving H̃x = ES̃x.Exact emulated QLanczos used s = 0.95 and ε = 10^-14, whereas QVM and QPU calculations used s = 0.75 and ε = 10^-2.
  • QLanczos stabilization: The stabilization procedure was sufficient for all reported models and calculations, although it was unlikely to eliminate every numerical instability.The main error source was approximate matrix construction for exact emulation and finite precision and noise for QVM and QPU simulations.

METTS algorithm

The METTS algorithm estimates thermal observables by sampling minimally entangled typical thermal states generated through imaginary-time evolution, avoiding the complicated rejection-and-reset procedure of quantum Metropolis sampling. Its QITE implementation alternates product-state preparation, imaginary-time evolution, measurement, and collapse, with alternating X- and Z-basis collapses used to reduce sample correlations.

  • Sampling principle: METTS estimates thermal observables by sampling |φ_i⟩ with probability P_i/Z and averaging ⟨φ_i|O|φ_i⟩.The sampled states have the correct Gibbs distribution.
  • Motivation: METTS avoids quantum Metropolis rejection and resetting, which require deep circuits on a quantum computer.It provides an alternative method for sampling |φ_i⟩ distributed with probability P_i/Z.
  • Quantum implementation: The QITE implementation prepares a product state, imaginary-time evolves it to |φ_i⟩, measures observables, and collapses it to another product state.The procedure repeats by using the collapsed state as the next input.
  • Correlation control: Alternating X- and Z-basis collapses reduce long statistical correlations between METTS samples.Odd steps use tensor products of |+⟩ and |−⟩, while even steps use tensor products of |0⟩ and |1⟩; statistical error is estimated by block analysis.

Implementation on emulator and quantum processor

The implementation used pyQuil to run quantum circuits on Rigetti’s quantum virtual machine and Aspen-1 quantum processing units. Noise modeling and mitigation were evaluated in simulations and on different Aspen-1 qubit pairs, with reduced noise improving algorithm performance.

  • Implementation: pyQuil interfaced quantum circuits with Rigetti’s quantum virtual machine and Aspen-1 quantum processing units.The library provided the implementation framework for both simulated and physical-device experiments.
  • Noise modeling and mitigation: pyQuil modeled readout, gate, relaxation, and dephasing errors, while readout errors were mitigated by correcting estimated expectation values.Readout errors use p00 and p11, whereas decoherence is characterized by T1 and T2; gate noise can be applied through Kraus maps.
  • QVM noise experiments: 10 calculations per noise model showed practically no run-to-run variation, and reducing readout error did not greatly affect the converged ground state energy after mitigation.Three QVM noise models varied p00, p11, T1, T2, p1, and p2, with Noise model 1 reflecting realistic Aspen-1 parameters.
  • Aspen-1 experiments: Q2, using qubits 0,1 with p00 = 0.90, p11 = 0.90, T1 = 6.5 µs, and T2 = 8.0 µs, provided a less faithful implementation than Q1.Q1 used qubits 14, 15 and had reported parameters p00 = 0.95, p11 = 0.95, T1 = 10.5 µs, and T2 = 14.0 µs; physical-device results varied across runs.

Parameters used in QVM and QPUs simulations

This section specifies the parameters used for QPU and QVM simulations, including noise-model assumptions and measurement sampling, and identifies tables covering QITE, QLanczos, and METTS simulations.

  • Simulation parameters: Noisy QVM simulations generally used noise parameters from noise model 1 unless otherwise stated.The section notes this as the default noise-model condition for noisy QVM simulations.
  • Simulation parameters: Measurement sampling was specified by the number of samples used for each Pauli operator.The section indicates that measurement sample counts were included among the simulation parameters.
  • Simulation parameters: Table I reports QPUs: 1-qubit QITE and QLanczos.The supplied table caption identifies the simulation scope.
  • Simulation parameters: Table II reports QPUs: 2-qubit QITE and QLanczos.The supplied table caption identifies the simulation scope.

nMETTs

This section reports QVM results for two-qubit QITE and QLanczos, alongside one-qubit METTS results across listed β settings.

  • nMETTs: Table IV reports QVM results for two-qubit QITE and QLanczos.

nMETTs … Counting Pauli strings in VQE

The paper examines nMETTS data and compares QITE with VQE by counting Pauli-string measurements required to reach approximate ground states. VQE uses a hardware-efficient Ansatz with SPSA optimization, exact expectation values, and convergence criteria based on energy error.

  • Comparison of QITE and VQE: The study evaluates 4-site and 6-site instances, defining convergence as energy within 1% for Heisenberg and 1% or 2% for Ising.The 2% Ising criterion was selected to allow VQE optimization to complete in a reasonable number of steps.
  • Counting Pauli strings in VQE: VQE uses a hardware-efficient variational Ansatz with initial single-qubit rotations followed by depth-d layers of nearest-neighbor CZ gates and rotations.The rotations are represented using Rz, Rx, and Rz operations.
  • Counting Pauli strings in VQE: SPSA was used for VQE optimization because it tolerates stochastic fluctuations and updates parameters using two objective-function evaluations regardless of parameter count.Its performance depends on hyperparameters α and γ.
  • Counting Pauli strings in VQE: Expectation values were evaluated exactly with a modified Qiskit implementation of the Ansatz and SPSA to prevent sampling errors from affecting the comparison.The objective function estimates expectation values of the Pauli strings appearing in the Hamiltonian.
  • Counting Pauli strings in VQE: VQE convergence measurements use different layer depths and iteration counts, with each iteration evaluating the objective function twice and measuring M Hamiltonian Pauli strings.The total Pauli-string count is determined from these repeated objective-function evaluations.
  • Counting Pauli strings in VQE: Results average 10 VQE trajectories, and the 6-site Ising case uses a 2% rather than 1% convergence criterion because 1% convergence was not achieved.The summarized VQE parameters were those producing the lowest total Pauli-measurement count for ground-state convergence.

Counting Pauli strings in QITE

QITE used a second-order Trotter decomposition and converged to ground states from model-specific initial states with Δτ = 0.1 and domain size D = 4. For D = 4, evaluating each local imaginary-time operator requires measuring 256 Pauli strings, while convergence was assessed using the same criterion as VQE.

  • QITE used a second-order Trotter decomposition to implement the evolution.
  • The simulations initialized the Heisenberg model in |0101 . . .⟩ and the AFM transverse-field Ising model in a maximally mixed state.
  • With Δτ = 0.1 and domain size D = 4, QITE converged to the ground state in both models.
  • 256 Pauli strings are required to evaluate e^−Δτ/2 h[i] for domain size D = 4, without exploiting the Hamiltonian’s real-valued nature.
  • QITE reached arbitrary ground-state accuracy using the same convergence criterion as VQE for comparison.

VQE and QITE

QITE is presented as competitive with VQE in Pauli-string measurement cost and potentially practical for intermediate system sizes on near-term quantum devices. For a six-qubit system, QITE required significantly fewer measurements, while VQE convergence depended strongly on optimization choices.

  • Measurement cost: QITE required significantly fewer Pauli-string measurements than VQE for the six-qubit system.The passage attributes this difference largely to SPSA iterations required for VQE energy convergence.
  • Measurement cost: VQE measurement costs could potentially decrease with a better optimizer or Ansatz, while QITE counts could also be reduced by restricting measured Pauli strings.For real Hamiltonians, Table X notes that QITE measurements can be reduced to strings containing only an odd number of Y operators.
  • Near-term implementation: QITE is described as practical to implement for intermediate system sizes on near-term devices.This assessment is based on the reported QITE results.
  • Convergence: VQE failed to converge within 1% of the ground-state energy in the final comparison, so a 2% convergence criterion was used.The same 2% criterion was used for QITE to facilitate comparison.
Loading 1901.07653v3…