Direct sampling in a measurement basis

What it fills

• Estimate an observable

  Given the ability to prepare $|ψ⟩$ and a description of an observable $O$, return a classical scalar within $\varepsilon$ of $⟨O⟩$ at confidence $1−δ$. The state is never returned; only the number is.

When it applies

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.

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

Example

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

Cost, as the source states it

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.

Implementations

• The photonic HeH+ ground-state run

  • A variational eigenvalue solver on a quantum processor

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

  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.

  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.

What it needs

Every step this method names is listed under Requires above. It walks its own span in one hop and calls out to the rest — that is a fact about the recorded route, not a claim that the span is simple.

Other ways to fill the same slot

Different approaches

• Coherent amplitude-estimation readout

  Encode the expectation value into an amplitude and estimate that amplitude coherently — phase estimation on the Grover operator $Q = −A S_0 A^{-1} S_χ$, or one of the QPE-free variants — instead of averaging independent shots.

• Classical shadow readout

  Apply a random unitary from a chosen ensemble, measure in the computational basis, and keep the (unitary, outcome) pair; inverting the measurement channel turns each pair into an unbiased single-shot snapshot of $ρ$, and median-of-means over snapshots predicts many observables at once. The observables may be chosen after the data has been taken.

• Measure commuting terms together

  A Hamiltonian's terms are measured one group at a time rather than one term at a time. Terms that commute qubit-wise can share a single set of measurements, so the question becomes how few groups the terms can be covered by — a graph problem, and a hard one.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• 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 · 2013theory yes · simulation ? · hardware yes
• Measurements as a roadblock to near-term practical quantum advantage in chemistry: resource analysis↗Jérôme F. Gonthier, Maxwell D. Radin, Corneliu Buda, Eric J. Doskocil, Clena M. Abuan, Jhonathan Romero · 2020theory yes · simulation yes · hardware no
• Nearly Optimal Quantum Algorithm for Estimating Multiple Expectation Values↗William J. Huggins, Kianna Wan, Jarrod McClean, Thomas E. O'Brien, Nathan Wiebe, Ryan Babbush · 2021theory yes · simulation ? · hardware no