Ground-state energy by phase estimation

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

Aspuru-Guzik et al. state the identification the method rests on — "A molecular ground-state energy is the lowest eigenvalue of a time-independent Schrödinger equation. The phase estimation algorithm (PEA) of Abrams and Lloyd can be used to obtain eigenvalues of Hermitian operators; we address issues concerning its implementation for molecular Hamiltonians" — and then name the condition that decides whether it works: "the algorithm requires that any estimated ground state has a large overlap with the actual eigenstate. We show how a good estimate of the ground-state wave function may be prepared adiabatically from a crude starting point". Their preparation is stated concretely: "Our Hamiltonian is changed slowly by discretized linear interpolation from the trivial HF case to the FCI operator". The evolution operator is a product-formula approximation whose error is a free parameter — "M can always be chosen such that the error is bounded by some preset threshold. The number of gates to implement Û then scales polynomially with the system size".

Requires

These do not move the route along. The method needs each of them alongside its own work, and the cost of getting them is part of what the method costs.

• Prepare an input state

  Map $|0\ldots0⟩$ to a state whose amplitudes are proportional to a specified vector $b$, to within $\varepsilon$. The cost is set by which description of $b$ you hold, not by the algorithm that consumes it.

  The paper's gate analysis covers $\hat U$ alone and attaches no count to the input state: $\mathbf{S}$ is simply initialized to the Hartree-Fock wave function, one of the configurations the compact singlet-subspace mapping enumerates and equates with qubit states — eight qubits for $\mathrm{H_2O}$'s 196 singlet-spin configurations in STO-3G, eleven for LiH's 1210 in 6-31G. The route pays in overlap, not amplitudes: the probability of observing the exact $|\Psi\rangle$, hence the PEA's success, is proportional to $|\langle\Psi|\Psi^{HF}\rangle|^2$. assumption: the HF wave function keeps large overlap with the true eigenstate — known to vanish in some cases, such as molecules close to the dissociation limit or in the limit of large system size Where it does not, adiabatic state preparation systematically improves that same state along $\hat H^{HF}\to\hat H$, $\hat H^{HF}$ being zero in every matrix element except $H_{1,1}$, the HF energy. assumption: the adiabatic theorem's condition — the Hamiltonian changed slowly enough, set by the gap between ground-state and first-excited-state energies along the path approximation: that interpolation is linear and discretized — 1000 steps, demonstrated only for $\mathrm{H_2}$ at large separations, where $|\langle\Psi|\Psi^{HF}\rangle|^2$ is one half

  approximationassumption

• Estimate the eigenphase of a unitary

  Given a circuit whose controlled powers you can apply, and a routine preparing a state with non-negligible overlap on one of its eigenvectors, return that eigenvector's phase as a number with an error bar. The phase is read out of an ancilla, never out of the system register — the system is only ever the thing the controlled powers act on.

  Round zero sets $\hat V_0 = \hat U$ and runs a four-qubit PEA: Hadamards on $\mathbf{R}$, then controlled $\hat V_0$, $\hat V_0^2$, $\hat V_0^4$, $\hat V_0^8$ on $\mathbf{S}$, leaving $|\mathbf{R}\rangle\otimes|\mathbf{S}\rangle = \big(\sum_n e^{(i2\pi\phi)n}|n\rangle\big)\otimes|\Psi\rangle$, then the inverse Fourier transform and measurement — resolving $\phi$ on zero to unity to a precision of $1/16$. That estimate gives a shift $\phi_0$ lower-bounding $\phi$; the next round runs $\hat V_1 = \big[e^{-i2\pi\phi_0}\hat V_0\big]^2$, returning the remainder above that bound on half the previous interval; the paper reads the shift as a running reference energy, with only the deviation from it measured. Taking $\phi_k$ a quarter below the measured phase keeps the $\hat V_{k+1}$ eigenphase approximately centred on the interval zero to unity, so each round adds one bit and precision is independent of the register, four being the smallest the paper found stable. The energy is $E = 2\pi\phi/\tau$. assumption: that state is written for an exact eigenstate; started from $|\Psi^{HF}\rangle$ the read-out lands on the ground-state eigenphase only with probability proportional to the squared overlap

  assumption

Example

given  H, the molecular electronic Hamiltonian, second-quantized and mapped
       onto a qubit register S (direct or compact mapping)                (Eq. 3)
       tau, an evolution time fixed beforehand from a polynomially-scaling
       classical estimate of E, chosen so that 0 <= (phi ~ 1/2) < 1
       R, a read-out register of as few as four qubits -- found stable at
       four, down from about twenty for a single-shot PEA
       K, the number of iterations to run -- a free parameter chosen by the
       user, not fixed by the method; the paper repeats "until the desired
       precision is obtained" and reports K = 20 for its own runs
       a state prepared in S -- delegated to the state-preparation hop, not
       re-specified here (Hartree-Fock, or adiabatically improved from it)

requires  the state prepared in S has a large overlap with the true ground
    state |Psi> -- "the algorithm requires that any estimated ground state
    has a large overlap with the actual eigenstate"
    # this hop does not supply that overlap; it is bought upstream by
    #   state-preparation. Starting from |Psi_HF>, the whole method's
    #   success probability is proportional to |<Psi|Psi_HF>|^2, and
    #   nothing below improves that number

# --- put E into the phase of a unitary eigenvalue --------------------------
U <- hamiltonian-simulation(H, tau)   # delegated -- Trotterized exp(+i H tau)
    # the paper's exponent carries a plain PLUS sign in both places it is
    #   written: U|Psi> = e^{+i H tau}|Psi> = e^{i 2pi phi}|Psi>, E = 2pi
    #   phi/tau (Eq. 1), and the product formula e^{+i H tau} ~
    #   [prod_X e^{+i h_X tau/M}]^M                                   (Eq. 4)
    # the only minus sign in the construction is the one in the shift factor
    #   exp(-i*2*pi*phi_{k-1}) below, which removes accumulated phase

# --- recursive four-qubit phase estimation, k = 0 .. K-1 -------------------
V_0 <- U
phi_hat_0 <- four_qubit_PEA(V_0, S)
    # Hadamards on R, controlled V_0, V_0^2, V_0^4, V_0^8 onto S, inverse
    #   QFT, measure -- resolves phi on [0,1) to a precision of 1/16
    #                                                  (Results text; Fig. 2A)
phi_0 <- a shift built from phi_hat_0 that lower-bounds phi
    # the paper commits to no fraction at iteration zero -- only "a shift
    #   phi_0 which is a lower bound on phi". The explicit "1/4 lower" rule
    #   is stated for the subsequent iterations k, so it is not asserted
    #   here; in practice any margin below a precision-1/16 estimate that
    #   keeps the bound valid will do                     (Results text)

for k = 1 to K-1:
    V_k <- [ exp(-i*2*pi*phi_{k-1}) * V_{k-1} ]^2
        # squares the eigenphase each round, so the interval still to be
        #   resolved halves and each round adds one bit of phi -- the
        #   register itself stays fixed at four qubits throughout
        #                                     (Results text, follows Eq. 2)
    phi_hat_k <- four_qubit_PEA(V_k, S)
    phi_k <- phi_hat_k - 1/4
        # choosing phi_k a quarter below the V_k estimate is what centers
        #   the NEXT round's eigenphase near the middle of [0,1)
        #                                     (Results text, follows Eq. 2)

# k iterations obtain k bits of phi (Fig. 2 caption); the H2O/LiH runs
#   below used K = 20 -- an empirical stopping point, not a derived bound
phi <- the K-bit binary phi assembled from phi_hat_0 .. phi_hat_{K-1}
    # the paper gives no closed form for this assembly -- only "in each
    #   iteration, we therefore obtain one additional bit of phi" and the
    #   circuit of Fig. 2A. Not reconstructed here rather than invented
E <- 2*pi*phi / tau                                                       (Eq. 1)

return  E
# no classical optimization loop and no varied parameter -- E is measured
#   off the accumulated phase, once, not minimized
# the H2O demonstration (K=20) gave -84.203663 a.u. against -84.203665 a.u.
#   from exact diagonalization; the residual is attributed to error in
#   forming U from H by matrix exponentiation, not to this readout
# a poor result here is a failure of overlap bought upstream, not of this
#   recursion -- nothing on this hop raises |<Psi|Psi_HF>|^2

Cost, as the source states it

Aspuru-Guzik, Dutoi, Love and Head-Gordon cost the recursive PEA per bit. Each iteration is a four-qubit read-out PEA — down from roughly twenty — resolving its phase to $1/16$ and keeping one bit of $\phi$: precision is independent of register size. $\hat V_k = \left[\exp(-i2\pi\phi_{k-1})\hat V_{k-1}\right]^2$ squares the evolution each bit, so the $1+2+4+8$ controlled powers cost $15\cdot2^k$ applications of $\hat U$ at iteration $k$: arithmetic on Figure 2A, never composed in the paper into a $1/\varepsilon$ scaling. One $\hat U$ is $M$ Trotter steps times a term count going as the fourth power of the atom count, each at most a controlled four-qubit unitary; ref. 13 bounds an uncontrolled four-qubit gate by under 400 gates, the controlled one only by "a similar order of magnitude". The gate analysis assumes the direct mapping — two qubits per basis function, 116 for $\mathrm{H_2O}$/cc-pVTZ against 47 compact — and is polynomial only "for a given $M$", whose growth is "reasonable to assume". Success is "proportional to $|\langle\Psi|\Psi^{HF}\rangle|^2$", no repetition count is derived, and nothing bounds the adiabatic preparation, run as 1000 discretized steps on $\mathrm{H_2}$. 20 iterations matched diagonalization to $2\times10^{-6}$ a.u. for $\mathrm{H_2O}$, in simulation.

Implementations

• Photonic iterative phase estimation for H2's energy surface

  • Towards Quantum Chemistry on a Quantum Computer

  Lanyon, Whitfield, Gillet and coauthors build a two-photon device around exactly the three-step algorithm this method describes: "encoding a molecular wavefunction into qubits; simulating its time evolution using quantum logic gates; and extracting the approximate energy using the phase estimation algorithm." They pick the smallest instance that fits the hardware they had: "a photonic implementation for the smallest problem: obtaining the energies of H2, the hydrogen molecule in a minimal basis." Their own statement of the eigenvalue relation, $e^{-i\hat H t/\hbar}|\Psi\rangle=e^{-iEt/\hbar}|\Psi\rangle=e^{-i2\pi\varphi}|\Psi\rangle$, carries the opposite sign convention from the one this hop's theory states, but is the same identification of energy with an accumulated phase. They flag which single piece is genuinely demonstrated in full: "a key algorithmic step — the iterative phase estimation algorithm — in full, achieving a high level of precision and robustness to error," while "other algorithmic steps" run "with assistance from a classical computer."

  In the STO-3G minimal basis the six two-electron configurations of H2 make the molecular Hamiltonian block-diagonal into four subspaces, two of which are 2x2, so "one qubit suffices to represent the wavefunction" for each and finding their eigenvalues by phase estimation "amounts to performing" full configuration interaction. Rather than adiabatic state preparation, "we encode exact eigenstates, obtained via a preliminary calculation on a classical computer" — a shortcut the paper names as non-scalable and describes how to remove in future work. They implement the iterative phase estimation algorithm (IPEA): "the result of a logical measurement of the top 'control' qubit after each iteration determines the k-th bit of the binary expansion" of the phase, built from $\hat U^{(p,q)}=e^{i\alpha}\hat R_y(\beta)\hat R_z(\gamma)\hat R_y(-\beta)$, with $\hat U^j$ obtained at this small scale by rescaling the angles $\alpha,\gamma$ to $j\alpha,j\gamma$ rather than by re-running the circuit $j$ times. Each phase is resolved to 20 bits, each bit sampled $n=31$ times and decided by majority vote, which the paper ties to the Chernoff bound: once single-shot bit accuracy is above one half, repeated sampling drives the error down exponentially in $n$. A separate sweep varies the fidelity $F$ between the encoded register state and the true ground state and finds the scheme "robust for $F\gtrsim0.5$" — the paper's own quantitative stand-in for the overlap condition this method's theory states qualitatively.

  H2 in the STO-3G minimal basis. "Restricted Hartree-Fock calculations were carried out on a classical computer using the STO-3G basis. The software used was the PyQuante quantum chemistry package version 1.6," and the resulting molecular integrals fix the matrix elements of the two 2x2 Hamiltonian blocks that the photonic device then estimates the eigenvalues of.

  The device encodes qubits in the polarization of single photons entangled by "a photonic two-qubit controlled-unitary quantum logic gate," pumped by spontaneous parametric down-conversion at about 50 mW to hold the coincidence rate to roughly 15 events/s and limit multi-photon-pair error. Sweeping the internuclear separation and running a 20-bit IPEA at each point, "in every case, the algorithm successfully returned the energy to within the target precision of $\pm(2^{-20}\times2\pi)E_h\approx10^{-5}E_h$." At the equilibrium bond length, $1.3886\,a_0$, the measured ground-state energy is $-0.20399\pm0.00001\,E_h$, which "agrees exactly with the result obtained on a classical computer to an uncertainty in the least significant bit." Each iteration was limited by reconfiguring the optics, not by counting: at ~15 coincidences/s and ~7 s to rotate waveplates between iterations, "obtaining a 20-bit estimation of a phase takes about 3 minutes," about 95% of it spent rotating waveplates. The paper separately prices what a scalable version of the same H2 calculation would cost, using the general operator-splitting route rather than the shortcut run here: "4 qubits and ~522 perfect gates are required to simulate the full unitary propagator such that the error of the simulated evolution is within chemical precision," and holding 13 bits of phase accuracy with $\hat U^j$ built up rather than rescaled needs "about $8.5\times10^6$ gates," a figure that "does not include the resources associated with preparing a system eigenstate."

• Trotterized phase estimation on superconducting qubits for H2

  • Scalable Quantum Simulation of Molecular Energies

  O'Malley, Babbush, Kivlichan and coauthors run two chemistry algorithms on the same three-qubit superconducting device and name the phase-estimation half directly against this method's own source paper, describing it as "the original algorithm for the quantum simulation of chemistry" — "this approach involves Trotterized simulation and the quantum phase estimation algorithm (PEA)" — and call the run a milestone independent of the accuracy reached: "this is the first time the canonical quantum algorithm for chemistry has been executed in its entirety." They place it against three earlier phase-estimation chemistry demonstrations — photonic, nuclear magnetic resonance, nitrogen-vacancy-center — none of which "implemented the propagator in a scalable fashion (e.g. using Trotterization) as doing so requires long coherent evolutions," and none of which used more than a single qubit or qutrit to hold the whole molecule, where this experiment represents H2 in the scalable Bravyi-Kitaev qubit encoding instead of a configuration basis.

  H2 is written as $H=g_0\mathbb{1}+g_1\hat Z_0+g_2\hat Z_1+g_3\hat Z_0\hat Z_1+g_4\hat Y_0\hat Y_1+g_5\hat X_0\hat X_1$ on two qubits via the Bravyi-Kitaev transformation. The system register starts in the Hartree-Fock state $|\varphi\rangle=|01\rangle$, and "since the Hartree-Fock state has strong overlap with the ground state of molecular hydrogen (i.e. $|\langle0|\varphi\rangle|^2>0.5$) we were able to measure each bit independently with a majority-voting scheme" over one thousand repetitions per bit — the paper's own numeric stand-in for the overlap condition this method's theory states qualitatively. "Our PEA implementation is based on a modification of Kitaev's iterative phase estimation algorithm": a single ancilla is held in a superposition, the propagator is Trotterized as $e^{-iHt}\approx\big[\prod_\gamma e^{-ig_\gamma\hat H_\gamma t/\rho}\big]^\rho$ and applied controlled on the ancilla, and each measured bit feeds a classically computed phase-kickback rotation on the ancilla before the next round, so that $b$ measured bits give the ground-state energy as a binary expansion. "The primary difficulty of the PEA experiment is that the controlled application" of the Trotterized propagator "requires complex quantum circuitry and long coherent evolutions," so they "approximated the propagator ... using a single Trotter step ($\rho=1$), which is not sufficient for chemical accuracy" — a limitation the paper attributes to this run, not to the method. A PEA sequence used "at least 51 single-qubit gates, four $CZ_{\phi\neq\pi}$ gates, and ten $CZ_\pi$ gates," run on three Xmon transmon qubits (two system, one ancilla) in a dilution refrigerator at 20 mK.

  H2's dissociation curve, swept from near the equilibrium bond length ($R=0.72\,\text{Å}$) out past $3.0\,\text{Å}$; the coefficients of the qubit Hamiltonian are the Bravyi-Kitaev-transformed second-quantized molecular Hamiltonian of H2 as a function of bond length, and the paper's acknowledgements record that an earlier version of the reported $g_0$ values contained an error that was later corrected.

  The PEA readout reproduces exactly what the Trotterized circuit computes: "because energies are measured digitally in iterative phase estimation, the experimentally determined PEA energies ... agree exactly with theoretical simulations ... which differ from the exact energies due to the approximation" in the Trotter step — so the entire deviation from the exact curve is attributed to taking one Trotter step, not to hardware readout error. Measured against exact diagonalization, "PEA approach shows dissociation energy error of $(1\pm1)\times10^{-2}$ Hartree," roughly six times the $1.6\times10^{-3}$ Hartree the paper calls chemical accuracy, stated alongside the companion VQE run on the same device and molecule, which reached $(8\pm5)\times10^{-4}$ Hartree. The authors read the comparison as a lesson about near-term hardware rather than a verdict on phase estimation itself: "while PEA has asymptotically better scaling in terms of precision than VQE, long and coherent gate sequences are required for its accurate implementation," concluding that "adaptive algorithms (e.g. VQE) may generally be more resilient for pre-error corrected quantum computing than traditional gate model algorithms (e.g. PEA)."

What it needs

1. Simulate Hamiltonian evolution 3 methods

   Implement $e^{-iHt}$ to error $\varepsilon$ given some access model for $H$. It is an application in its own right and also the engine inside phase estimation and several linear-system solvers.

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.

• 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.

• 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.

In the Atlas

• Molecular ground-state energies by phase estimation

  Compute the ground-state energy of an atom or molecule, a calculation whose time the paper states scales exponentially with system size on a classical computer.

Sources

• Simulated Quantum Computation of Molecular Energies↗Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, Martin Head-Gordon · 2006theory yes · simulation yes · hardware no