Applies when $O$ is given as a Pauli or fermionic-operator sum with an efficiently enumerable term count, and the extra single-qubit basis-change layer is affordable. Each shot destroys the state, so the preparation must be repeatable. There is no coherence-derived advantage available here: this is a strict $\varepsilon^-2$ method, and grouping commuting terms changes the constant, not the exponent.

A preparation routine $A$ with $A\lvert 0\rangle = \lvert \psi\rangle$, or repeated copies of $\rho$; a description of $O$; a target additive error $\varepsilon$ and a confidence $1-\delta$. Coherent, controlled access to $A$ and $A^\dagger$ is required by some methods here and by none of the sampling-based ones.

1. State you can prepare → Number with an error barmeasure each Pauli term, sum by weight

   The observable is first written as a Pauli sum, $\mathcal{H} = \sum_{i\alpha}h^{i}_{\alpha}\sigma_{\alpha}^{i} + \sum_{ij\alpha\beta}h^{ij}_{\alpha\beta}\sigma_{\alpha}^{i}\sigma_{\beta}^{j} + \ldots$ with real coefficients. assumption: the decomposition must have a number of terms "polynomial in the size of the system", since every term is measured separately and the count is the bill. Then it is linearity and nothing else: $\langle\mathcal{H}\rangle = \sum_{i\alpha}h^{i}_{\alpha}\langle\sigma_{\alpha}^{i}\rangle + \sum_{ij\alpha\beta}h^{ij}_{\alpha\beta}\langle\sigma_{\alpha}^{i}\sigma_{\beta}^{j}\rangle + \ldots$, so the quantity is rebuilt from per-term averages weighted by the coefficients they came with. approximation: each $\langle\sigma\cdots\rangle$ is a sample mean over repeated preparations, not the expectation itself; reaching precision $p$ on a term of coefficient $h$ costs $O(|h|^{2}/p^{2})$ repetitions, so the coefficient enters twice — once as a weight and once as a sampling cost.

   approximationassumption

A scalar estimate with a stated additive-error guarantee, plus the shot or query budget and the maximum circuit depth actually consumed.

• Prepare an input state runs O(1/ε²) shots, and one preparation per shot

  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 loop closes through a measurement: every turn ends in a readout and starts from a fresh preparation. The price is a count of runs, not a depth. This is the loop that closes through a measurement, and the whole cost is in that fact. Each shot destroys the state, so the state-preparation circuit below is not run once and read many times — it is run again, in full, for every sample, and the samples needed grow as ε^-2. Grouping commuting terms changes the constant; it cannot change the exponent, because the exponent is what averaging independent classical outcomes costs. A method that keeps the loop coherent pays ε^-1 instead, which is the whole of the row below.

  Within one evaluation of $\langle H\rangle$ the trial state is fixed: iteration $j$ has prepared $|\psi^j\rangle$ on $n$ qubits, parameterized by $\{\theta^j_i\}$, and all $M$ terms of the Hamiltonian are estimated from that one state. What this method asks of the ingredient is therefore not one long-lived instance reused across those estimates but a fresh instantiation of the same $|\psi^j\rangle$ for every shot: Peruzzo et al. note that the coherence time to make a single measurement after preparing the state is $O(1)$, and one projective measurement spends the instance. The per-term repetition cost recorded above compounds across the sum, and the paper estimates the cost of each function evaluation at $O(|h_{\max}|^{2}M/p^{2})$ calls to state-preparation, with $p$ the target precision and $|h_{\max}|$ the largest Pauli coefficient. assumption: that count prices $M$ terms measured separately, each to the same precision $p$; with no grouping of commuting terms and no variance-weighted reallocation of shots.

  assumption

given  O as a Pauli or fermionic-operator sum with an efficiently
       enumerable term count, a repeatable state preparation, and room for
       the extra single-qubit basis-change layer, to a target error epsilon

decompose O into Pauli strings

for each Pauli string:
    rotate it into the computational basis with a layer of single-qubit
        Cliffords
    sample bitstrings, and average the outcomes for this term
    # no ancilla, no controlled operations, minimum added depth

# O(1/epsilon^2) shots in all, and one state preparation per shot: each
# shot destroys the state, so the preparation is not run once and read many
# times -- it is run again, in full, for every sample

recombine the per-term averages linearly

return the estimate of the expectation value of O

# a strict epsilon^-2 method: grouping commuting terms changes the
# constant, not the exponent, because the exponent is what averaging
# independent classical outcomes costs. There is no coherence-derived
# advantage available here -- Huggins et al. record the coherent endpoint of
# this layer at O(1/epsilon) state preparations for a single expectation
# value, and the shot-based averaging above is the epsilon^-2 endpoint

# Gonthier et al.'s resource analysis concludes that modern improvements
# including low-rank Hamiltonian factorization will not be sufficient to
# achieve practical quantum computational advantage for their molecular set
# or similar molecules, and points instead at operator estimation that
# leverages quantum coherence: a near-term chemistry advantage claim
# resting on shot-based readout has to answer that analysis

Huggins et al. record the coherent endpoint of this layer: "Optimal strategies for estimating a single expectation value are known, requiring a number of state preparations that scales with the target error $\varepsilon$ as $O(1/\varepsilon)$." Shot-based averaging as described here is the $\varepsilon^-2$ endpoint.

Gonthier et al.'s resource analysis of combustion energies of small organic molecules to chemical accuracy concludes that modern improvements including low-rank Hamiltonian factorization "will not be sufficient to achieve practical quantum computational advantage for our molecular set, or for similar molecules", and points instead at operator estimation that leverages quantum coherence. Any near-term chemistry advantage claim resting on shot-based readout has to answer that analysis.

• The photonic HeH+ ground-state run

  • A variational eigenvalue solver on a quantum processor

    Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, Jeremy L. O'Brien · 2013

  About

  The experiment this readout layer came out of. Its stated motivation is that phase estimation "can efficiently find the eigenvalue of a given eigenvector but requires fully coherent evolution", where the approach demonstrated "greatly reduces the requirements for coherent evolution" — the trade this record's `conditions` states from the other side, as a strict $\varepsilon^{-2}$ shot cost. Published as Nature Communications 5:4213 (2014).

  Methods

  The algorithm was implemented by combining a small-scale photonic quantum processor with a conventional computer, with state preparation based on ansätze and classical optimization.

  Data

  None found yet.

  Code

  None found yet.

  Results

  The ground-state molecular energy of He-H+ was calculated to within chemical accuracy. The abstract states the accuracy in exactly those words and reports no numerical value, so none is quoted here.