MethodLayer 1
Quantum imaginary-time evolution
Approximate evolution in imaginary time, which damps every excited state faster than the ground state, by a sequence of unitaries determined from measurements on a local domain. There is no variational ansatz and no classical optimiser: the method converges because imaginary time converges.
A Hermitian reachable as a sum of terms, as sparse-access oracles or as a block-encoding; a way to prepare trial states, and — for the methods that need it — a trial state whose overlap with the ground state is not negligible; a target additive error and a confidence .
A scalar estimate of the lowest eigenvalue with a stated additive-error guarantee, plus the run or query budget it consumed. Whether that estimate is also a rigorous upper bound is a property of the method and is not promised by the slot.
Same contract as the slot it fills.
This one, drawn
From Hamiltonian whose ground state is wanted to Number with an error bar
A circle is an object you are holding. This method is drawn heavier, opened into its own steps; the other lines between the same two ends are the alternatives recorded for the same slot. Circles are named on hover, and each one is a link.
3 lines here have ways through that this figure does not open. The map opens them in place. See it on the map
What it fills
- Estimate a Hamiltonian's ground-state energy
Given a Hamiltonian you can query and some way of preparing trial states, return an estimate of its lowest eigenvalue to a stated additive error. The state achieving that energy may or may not come back with the number; almost every application wants the number.
When it applies
Motta et al. position this against both of its neighbours by naming what each costs: phase estimation "requires deep circuits with ancillae, that are hard to execute reliably without error correction", while variational algorithms "entail additional high-dimensional classical optimization". Their algorithms "can be implemented without deep circuits and ancillae, or high-dimensional optimization", and the exponential saving they claim — "exponentially less space and time per iteration" — is stated against the classical analogues of these algorithms, not against the other quantum methods in this slot.
Requires
Every step this method names moves its route along, so there is nothing it needs alongside them.
Example
given geometric k-local Hamiltonian H = sum_m h[m] on an underlying graph,
each h[m] acting on at most k neighboring qubits (main text, def. of H)
imaginary-time step dtau, total imaginary time beta,
so the Trotter decomposition uses n = beta / dtau steps
exp(-beta*H) = ( exp(-dtau*h[1]) exp(-dtau*h[2]) ... )^n + O(dtau) (Eq. 1)
an initial state |Psi> (e.g. a product state)
a domain size D > k, fit to the correlation length reached at each
step rather than fixed in advance (Fig. 1 caption)
# the paper writes the bound strictly, D > k. D = k is licensed only
# for the zero-correlation product state of the opening example,
# after which "this is no longer the case" (main text, after Eq. 5)
requires Uhlmann's theorem: if |Psi> has correlations between observables at
distance L bounded by exp(-L/C), the normalized imaginary-time step is
reproducible by a unitary confined to a domain of width at most O(C)
qubits around h[m]'s support -- this, not an ansatz, is what licenses
truncating to a finite D at all (Sec. "Quantum Imaginary Time Evolution")
# that O(C) width, and the O(C^d) domain quoted for a nearest-neighbor
# Hamiltonian on a d-dimensional cubic lattice, are the main text's
# informal statements. The rigorous version is not a fixed O(C): it is
# N_q = k(2C)^d ln^d(2*sqrt(2)*n*m/eps), growing with the step count
# n*m and with 1/eps (SI, Theorem 1; main text, "Cost of QITE")
# --- one Trotter step: apply every term's imaginary-time propagator in turn --
for step in 1 .. n: (Eq. 1)
for each term h[m] in H:
# --- the non-unitary imaginary-time action of this one term ---------
|Psi'> = exp(-dtau * h[m]) |Psi> (Eq. 2)
c = <Psi| exp(-2*dtau*h[m]) |Psi> # unnumbered, stated before Eq. 3
|Psi_bar'> = |Psi'> / sqrt(c) # normalize (Eq. 6)
# --- replace it by a unitary on a D-qubit domain around h[m] --------
expand A[m] = sum_I a[m]_I sigma_I over Pauli strings sigma_I on
the D qubits surrounding h[m]'s support, A[m] Hermitian (Eq. 7)
|Delta_0> = ( |Psi_bar'> - |Psi> ) / dtau (Eq. 8)
measure S_{I,J} = <Psi| sigma_I^dagger sigma_J |Psi> (Eq. 11)
b_I = i <Psi| sigma_I^dagger |Delta_0>
- i <Delta_0| sigma_I |Psi> (Eq. 12)
solve (S + S^transpose) a[m] = -b for REAL a[m], minimizing
|| Delta_0 - Delta || with Delta = -i A[m] |Psi> (Eq. 9, Eq. 13)
# S + S^transpose generally has a NULL SPACE, so this is solved by
# its generalized inverse or by conjugate gradient: a[m] is
# selected by that rule, not uniquely determined by the system
# (SI, after Eq. 13)
# the problem is linear, so there is no local minimum to get
# stuck in -- that, and not uniqueness, is the paper's claim
# (main text, after Eq. 5)
# the shorter main-text form S a[m] = b with
# b_I = (-i/sqrt(c)) <Psi| sigma_I^dagger h[m] |Psi> is stated
# for the opening example where |Psi> is a PRODUCT state and the
# expectation values are over k qubits; the paper does not show
# it reduces to Eq. 12 for a correlated |Psi> on D > k qubits,
# which is the regime this loop runs in (Eq. 5)
# if H and |Psi> are real in the Z basis this collapses to
# b_I = -2 Im <Psi| sigma_I^dagger |Delta_0>, so b_I = 0 unless
# sigma_I carries an odd number of Y factors (SI, Eq. 14)
apply exp(-i*dtau*A[m]) to |Psi> # synthesized as two-qubit gates
|Psi> <- exp(-i*dtau*A[m]) |Psi> (Sec. "Cost of QITE")
measure E(beta) = <Psi| H |Psi> # tracked at every step, not only at the end (Fig. 2)
return |Psi> and the trajectory E(beta) as beta grows
# as beta -> infinity, E(beta) converges to the exact ground-state energy,
# PROVIDED D was never smaller than the correlation length actually reached
# at any step along the way (Fig. 1 caption; text on Fig. 2)
# --- inexact QITE: the heuristic that runs when D is fixed and too small ----
# choosing D smaller than the correlation length demands gives inexact QITE;
# D = 1 is a mean-field approximation, larger D approximates the ground
# state better, and the energy is no longer guaranteed to decrease at every
# step -- but stopping the first time it stops decreasing still yields a
# variational upper bound (Sec. "Inexact QITE")
# no ansatz and no classical optimizer appear above: a[m] comes from one
# LINEAR least-squares solve per term per step, not from a variational
# parameter tuned by an outer optimization loop (Abstract)
# the quantum Lanczos extension (QLanczos), which converges faster than plain
# QITE by combining several beta's worth of states, is a separate algorithm
# and is not part of this listing (Sec. "Inexact QITE"; Fig. 2 caption)Cost, as the source states it
Motta et al. bound the work per step, never the number of steps. Each unitary update on a -qubit domain costs Pauli-string expectation values ( at ), so one second-order Trotter step of a -term Hamiltonian costs . Rigorously (Theorem 1, Eq. (36)): for a -local on a -dimensional lattice with , a product initial state, , and correlation length bounded by on every intermediate state, each of the unitaries acts on at most qubits and the total quantum-plus-classical time is — exponential in , quasi-polynomial in and (typically for sites), an -dependence the authors call “still prohibitive in practice”. Here bounds only the distance to the Trotterized state, not the Trotter error and not the distance to the ground state; nothing bounds , since convergence is the limit, and the paper's own analysis expects to grow linearly in . By exact classical emulation, not proof: Pauli expectation values reach of the exact energy on a 6-site Heisenberg chain in a field at .
Implementations
Exact classical emulation on spin, fermionic and molecular models
The numerical demonstration the algorithm was introduced with. Motta et al. state its scope directly: "To illustrate the QITE algorithm, we have carried out exact classical emulations (assuming perfect expectation values and gates) for several Hamiltonians (see SI): short-range 1D Heisenberg (with and without a field); 1D AFM transverse-field Ising; long-range 1D Heisenberg with spin-spin coupling ...; 1D Hubbard at half-filling; a 6-qubit MAXCUT [10-12] instance, and a minimal basis 2-qubit dihydrogen molecular Hamiltonian [28]." "Exact" there qualifies the emulation and not the algorithm: expectation values and gates are perfect, while the domain size is fixed in advance rather than grown with the correlation length, which is the paper's own inexact QITE - "For small , the inexact QITE tracks the exact QITE for a time until the correlation length exceeds ." What the study is built to measure is what that truncation costs, so is the parameter swept across the spin and fermionic models. The author list assigns the work: "MM, CS, ATKT carried out classical exact emulations."
QITE is run with "different fixed domain sizes for the unitary or fermionic unitary"; the fermionic treatment is the one the SI attaches to "the fermionic Hubbard Hamiltonian treated in Fig. 3 in the main text", where the Pauli operators of Eq. (7) are replaced by fermionic field operators and only terms with equal numbers of creation and annihilation operators are retained, to conserve particle number. Imaginary time is stepped with the second-order Trotter decomposition of SI Eq. (67), which the paper prints as with - note that the trailing factor is printed with exponent where a symmetric second-order product would carry . The measurement count that follows from it is SI Eq. (68), , the being at and the number of Trotter steps. Initial states are stated per model: "|0101 . . .⟩ for the 1D Heisenberg model" and a "maximally-mixed state for the 1D AFM transverse-field Ising model" in the measurement-count runs, and for the MAXCUT instance, which is then measured in the computational basis so the outcome is itself an eigenfunction of the cut operator. The QITE stabilisation parameter , which regularises against sampling noise, is quoted only for the 1- and 2-qubit calculations ( and ), and the released `code_v4/qite.py` solves the QITE linear system by bare least squares with no diagonal shift; the paper does not say whether was applied to the larger exact emulations. QLanczos, run on the same Heisenberg trajectories, is stabilised by dropping time-evolved vectors whose overlap with the last retained one exceeds and discarding eigenvalues of the regularised overlap matrix below , with "stabilization parameter and " for the exact emulations. The measurement comparison against VQE is run inside the same study: "We conducted the VQE calculations using Qiskit, a quantum emulator Python package provided by IBM", with the SPSA optimiser at , , expectation values evaluated exactly "to prevent sampling errors from influencing the comparison", 10 trajectories per point analysed as the average trajectory, and for iterations over Pauli strings.
The model Hamiltonians are written out in the SI: 1D short-range Heisenberg (Eq. 48) and the same with a field (Eq. 49), 1D long-range Heisenberg with (Eq. 50), 1D AFM transverse-field Ising (Eq. 51), and the Jordan-Wigner-encoded 1D Hubbard model (Eq. 54). The measurement-count comparison fixes "a 1D Heisenberg chain in a magnetic field with the parameters " and "1D AFM transverse-field Ising model ()". For the molecular input the SI makes two statements and leaves them side by side. It describes a calculation the authors perform - H2 at "the STO-6G level of theory", and "Given a molecular geometry (H-H distance ) we perform a restricted Hartree-Fock calculation and express the second-quantized Hamiltonian in the orthonormal basis of RHF molecular orbitals" - and then, having Bravyi-Kitaev encoded that Hamiltonian onto the two-qubit form (Eq. 56), it states that the numbers are borrowed: "with coefficients given in Table I of [28]", reference 28 being O'Malley et al., Phys. Rev. X 6, 031007 (2016). The paper does not say which of the two supplied the coefficients actually used. The released repository carries that table as `code_v4/h2.dat`, seven columns over 54 bond lengths from to in steps of .
Python, released by the first author as the repository the paper names: "The code used to generate the data presented in this study can be publicly accessed on GitHub at https://github.com/mariomotta/QITE.git". The emulation lives in `code_v4`, whose modules the repository's `README.txt` names one by one - `pauli.py` for Pauli algebra over integer strings modulo 4, `hamiltonian.py` for the models "we studied in the QITE paper, the Heisenberg short-range, Maxcut etc", `ite.py` for the ordinary imaginary-time evolution used as a reference, which the README says proceeds either by constructing the Hamiltonian matrix in the computational basis and diagonalising it or by applying as a Taylor series, `qite.py` which "constructs the matrix A and the vector b (Amat,bvec) of the linear system, solves it by least-squares methods, and applies the corresponding unitary transformation to the current wavefunction", and `qlanz.py` for the quantum Lanczos calculations and their numerical stabilisation. It is a statevector code built on NumPy and SciPy, not a circuit simulator: `qite.py` imports `numpy`, `numpy.linalg` and `scipy.linalg` and applies the Hamiltonian to a wavefunction directly. Output data sits beside it in `numerics/`, one directory per model (`h2`, `heisenberg_lr`, `heisenberg_sr`, `hubbard`, `lanczos_heisenberg_sr`, `maxcut`), and a separate `mettscode` directory holds the thermal-average code. The repository carries no licence file.
All of the following are exact classical emulation, "assuming perfect expectation values and gates" - no device and no sampling - on the authors' own NumPy/SciPy statevector code, the repository the paper says generated the data in the study. On a 1D 10-site Heisenberg model the QITE energy and the fidelity between the finite-time state and the exact ground state converge as the domain is widened (Fig. 2a, 2b). On a 1D Heisenberg model with qubits, at domains of and , QLanczos converges faster than QITE (Fig. 2c, 2d). Fig. 3 adds a 6-site 1D long-range Heisenberg model "for unitary domains ", a 4-site 1D Hubbard model with "for unitary domains ", the 6-site MAXCUT instance where the probability of measuring a maximum cut "remains above 60%" even at the smallest domain where the energy oscillates, and the H2 STO-6G energy against bond length at compared with the exact curve. The paper's headline cost figures are the measurement counts at and : on the 1D Heisenberg model with field, Pauli-string expectation values reach of the exact ground-state energy at 4 sites and at 6 sites, against and for VQE in Qiskit; on the 1D AFM transverse-field Ising model at , at 4 sites to and at 6 sites to , against and for VQE, the looser criterion used because "VQE could not converge to within 1%". Restricting to Pauli strings with an odd number of factors, which the real Hamiltonians permit, cuts the QITE counts to , , and . The authors read this as competitiveness rather than dominance: "While the number of measurements could potentially be reduced in VQE by different optimizers and Ansätze, the data suggests that QITE is a promising alternative to VQE on near-term devices."
Prototype circuits on the Rigetti QVM and Aspen-1 QPUs
The device half of the same paper, and the smallest possible test of whether QITE survives sampling and hardware noise: "To assess the feasibility of implementation on near-term quantum devices, we have carried out noisy classical emulation (sampling expectation values and with an error model) using the Rigetti quantum virtual machine (QVM) and a physical simulation using the Rigetti Aspen-1 QPUs", on a single-qubit field model and a two-qubit AFM transverse-field Ising model. The abstract calls these "prototype circuits". Authorship and access are both stated: "ATKT and AJM designed and carried out the Rigetti QVM and QPU experiments", and "The Rigetti computations were made possible by a generous grant through Rigetti Quantum Cloud services supported by the CQIA-Rigetti Partnership Program."
"We used pyQuil, an open source Python library, to express quantum circuits that interface with both Rigetti's quantum virtual machine (QVM) and the Aspen-1 quantum processing units (QPUs)." Readout error is characterised by and and corrected through pyQuil's high-level API by estimating those probabilities and correcting the estimated expectation values; gate noise is applied in the emulator as Kraus maps, one relaxation-and-dephasing channel set by and and one depolarising channel with separate single- and two-qubit probabilities , that the authors added themselves. Because expectation values are now sampled, the linear solve is regularised: "We regularize against such statistical errors by adding a small to its diagonal", with for the 1-qubit calculations and for the 2-qubit ones, and QLanczos is stabilised with and rather than the emulation's , , because here "the main source of error in the simulations was" finite precision and noise. Run parameters are tabulated: 1-qubit QITE and QLanczos on the QPUs at Trotter stepsize with samples (Table I), 2-qubit at Trotter stepsize with samples on both the QPUs (Table II) and the QVM (Table IV). Three QVM noise models are compared, of which "Noise model 1 reflects realistic parameters that characterize the Aspen-1 QPUs we run our calculations on": , , , , . Only four of those five are device numbers - ", , , and are reported values whereas and are values typically used to benchmark error mitigation algorithms [59]", reference 59 being Temme, Bravyi and Gambetta, Phys. Rev. Lett. 119, 180509 (2017). On hardware the two-qubit runs were repeated on two qubit pairs, "with Q1 consisting of qubits 14, 15 and Q2 consisting of qubits 0,1", quoted as , , for Q1 and , , for Q2. Because "the results from the actual devices varied from run to run", each device point is the mean and standard deviation of 10 runs on each pair; the QVM was also repeated 10 times per noise model, where "there is practically no variation from run to run".
Two Hamiltonians, a 1-qubit field model and a 2-qubit AFM transverse-field Ising model. The single-qubit model is (SI Eq. 47) with " and ", the qubit "assumed to be initialized in the Z basis"; it is not invented for this paper but taken because it "has previously been used as a model for quantum simulations on physical devices in Ref. [29]", reference 29 being Lamm and Lawrence, Phys. Rev. Lett. 121, 170501 (2018). The two-qubit model is the 1D AFM transverse-field Ising Hamiltonian of SI Eq. (51); the paper does not state and for the runs on the device. The SI calls , , and "reported values" for the Aspen-1 QPUs, and the main text cites Rigetti's own dashboard for the noise parameters it reproduces the 2-qubit shift with: "Rigetti computing: quantum cloud services", https://qcs.rigetti.com/dashboard, "accessed: 2019-01-21".
The same repository as the emulation, https://github.com/mariomotta/QITE.git, in a separate directory `QPU_implementation` holding `qite.py`, `lanczos.py`, `metts.py`, `helper.py` and `index.py`. It is Python written directly against pyQuil - `qite.py` imports `Program` and `get_qc` from `pyquil`, `estimate_bitstring_probs` from `pyquil.noise`, and builds each measurement as a `Program` wrapped in a shot loop with an explicit readout correction matrix - so the same file drives the emulator and the device, selected by the quantum computer object it is handed; its own entry point sets that object to `1q-qvm` and is commented "Produces Figure 2(e)". What is released covers the 1-qubit case only: every gate in `helper.py` targets `qbits[0]`, the readout register is declared one bit wide, `get_expectation` returns a four-element vector, and `index.py` is a single-qubit Pauli multiplication table. The 2-qubit QVM and QPU code behind Fig. 2f and Fig. 5 is not in the repository. The repository carries no licence file.
"Figs. 2e and 2f show the results of running the QITE algorithm on Rigetti's QVM and Aspen-1 QPUs for 1- and 2-qubits, respectively." The paper attributes the error bars and dismisses sampling in two separate statements: "The error bars are due to gate, readout, incoherent and cross-talk errors. Sufficient samples were used to ensure that sampling error is negligible." Tables I, II and IV record samples. On one qubit the algorithm reaches the answer on hardware: "despite these errors it is possible to converge to a ground-state energy close to the exact energy for the 1-qubit case", which the authors attribute to a robustness "sometimes informally observed in imaginary time evolution algorithms in which the ground state energy is approached even if the imaginary time step is not perfectly implemented". On two qubits it does not: "although the QITE energy converges, there is a systematic shift which is reproduced on the QVM using available noise parameters for readout, decoherence and depolarizing noise", with the residual gap between emulator and device "likely attributable to cross-talk between parallel gates not included in the noise model". No energy error is quoted for either case. The controls point the same way. Sweeping the QVM noise models shows "that reducing the readout error does not greatly affect the converged ground state energy after readout error mitigation has been performed. However, reducing the other sources of error does improve the converged energy." Running the same two-qubit circuits on the noisier Aspen-1 pair "indeed demonstrates that Q2 provides a less faithful implementation of the quantum algorithm", as its , and readout fidelities predict. QLanczos, built on the same QITE trajectories, "provides more rapid convergence than QITE with both noisy classical emulation as well as on the physical device for 1 and 2 qubits".
What it needs
Nobody has taken this apart yet. That is a gap in this graph, not a claim that the method has no parts.
Other ways to fill the same slot
Different approaches
- Variational quantum eigensolver
Prepare a parameterised trial state on the quantum computer, measure the Hamiltonian's expectation value in it, and let a classical optimiser move the parameters. The quantum computer never runs a long coherent evolution; it runs a short one many times, and the loop closes through a classical number.
- Variational imaginary-time evolution
Keep the parameterised trial state, but stop treating the parameters as something to optimise: derive their equation of motion from a variational principle and integrate it in imaginary time. The parameters move because a differential equation says where they go, not because a search tried somewhere and liked the answer.
- Ground-state energy by phase estimation
Prepare a state that already overlaps the ground state, evolve it under the molecular Hamiltonian, and read the energy off the accumulated phase. Nothing is optimized and nothing is varied — the answer is a measured eigenvalue, and the whole difficulty moves into the starting state.
In the Atlas
- Quantum imaginary-time evolution
A ground-state preparation method that projects non-unitary imaginary-time evolution onto a parameterized quantum circuit.