PaperlayerView exact revision on arXiv

Source-linked AI summary

Improved quantum data analysis

Costin Bădescu, Ryan O'Donnell

arXiv:2011.10908v4quant-phcs.CC

TL;DR

The paper addresses sample efficiency for quantum data-analysis routines, including Shadow Tomography and Hypothesis Selection. It introduces a quantum Threshold Search algorithm and derives improved sample complexities, including best-known dependence on m, d, and ε for Shadow Tomography.

  • Problem

    Shadow Tomography seeks to estimate tr(ρA_i) for m fixed observables within ±ε, while prior work left open whether substantially lower sample complexity was possible.

    Source: §1 · p. 2

  • Method

    The paper develops a quantum Threshold Search algorithm and applies it to Shadow Tomography and quantum Hypothesis Selection.

    Source: §1 · p. 2, §1.1.1 · p. 3, §1.1.3 · p. 5

  • Results

    Shadow Tomography achieves best-known dependence on m, d, and ε, while an alternative Hypothesis Selection method uses roughly (log^3 m)/ε^2 samples.

    Source: §1.1.3 · p. 5

  • Takeaways & Limitations

    The results provide more sample-efficient quantum data-analysis routines and connect Shadow Tomography with Adaptive Data Analysis.

    Source: §1 · p. 2

    The paper notes that the 1/ε^4 dependence in Shadow Tomography remains challenging.

    Source: §1.1.3 · p. 6

Abstract

from arXiv · show

We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum "Threshold Search" algorithm that requires only $O((\log^2 m)/\epsilon^2)$ samples of a $d$-dimensional state $\rho$. That is, given observables $0 \le A_1, A_2, ..., A_m \le 1$ such that $\mathrm{tr}(\rho A_i) \ge 1/2$ for at least one $i$, the algorithm finds $j$ with $\mathrm{tr}(\rho A_j) \ge 1/2-\epsilon$. As a consequence, we obtain a Shadow Tomography algorithm requiring only $\tilde{O}((\log^2 m)(\log d)/\epsilon^4)$ samples, which simultaneously achieves the best known dependence on each parameter $m$, $d$, $\epsilon$. This yields the same sample complexity for quantum Hypothesis Selection among $m$ states; we also give an alternative Hypothesis Selection method using $\tilde{O}((\log^3 m)/\epsilon^2)$ samples.

1. Introduction

The introduction frames the challenge of reusable quantum measurements and presents improved Threshold Search and χ2-stable threshold reporting as central advances. It then develops applications to Shadow Tomography and quantum Hypothesis Selection, including online and alternative methods with differing parameter dependence.

1. Introduction

  • Quantum data analysis replaces observable classical samples with measurable quantum states, making sample reuse problematic because measurements alter the state.The motivating task is estimating tr(ρA_i) for fixed observables, known as Shadow Tomography [2].Source: §1 · p. 2
  • The introduction identifies Adaptive Data Analysis as a closer classical match for Shadow Tomography because adaptive estimates can skew the conditioned data distribution.This analogy explains why naive reuse fails in both settings.Source: §1 · p. 2

1.1.1 Threshold Search

  • The work introduces quantum Threshold Search, which either finds an observable exceeding its threshold up to ε or certifies that none does.The algorithm is online: it receives observable-threshold pairs sequentially and may halt after identifying a qualifying pair.Source: §1.1.1 · p. 3

1.1.2 χ2-stable threshold reporting

  • The key technical ingredient is a χ2-stable exponential-noise threshold test whose conditioning minimally changes the sample distribution, enabling composition across repeated tests.The stability is stronger than KL or total variation control and supports reusing the same quantum sample until an above-threshold outcome becomes likely.Source: §1.1.2 · p. 4

1.1.3 Applications: Shadow Tomography and Hypothesis Selection

  • The Shadow Tomography application achieves the best known dependence simultaneously on m, d, and ε and operates online against adversarially or adaptively chosen observables.The algorithm receives observables one by one and estimates tr(ρA_t).Source: §1.1.3 · p. 5
  • When the hypothesis states are pairwise far apart, the quantum Hypothesis Selection procedure matches the optimal classical bound.The broader problem replaces probability distributions and total variation distance with quantum states and trace distance.Source: §1.1.3 · p. 6
  • Quantum Hypothesis Selection reduces to Shadow Tomography as a black box, while a separate Threshold Search method trades a (log^3 m)/ε^2 copy complexity against Shadow Tomography’s (log^2 m)/ε^4.The alternative method improves ε-dependence but worsens m-dependence.Source: §1.1.3 · p. 6
  • Theorem 1.5 selects, from m fixed hypothesis states, a state achieving trace distance η from ρ using n = O(log(m/δ)/ε^2) copies, except with probability at most δ.Here η is the minimum trace distance between ρ and the candidate states.Source: §1.1.3 · p. 7
  • The quantum Hypothesis Selection reduction motivates seeking Shadow Tomography with linear log m dependence, which would enable learning a state class C using log(|cover(C)|) · polylog(d) copies.This would parallel classical cover-based learning and could support more efficient learning of structured quantum-state classes.Source: §1.1.3 · p. 7

2. Preliminaries

This section establishes the classical and quantum probability foundations, definitions, distance measures, and estimation and sequential-measurement lemmas used later. It also develops an alternative proof of a Damage Lemma result and derives a union-bound-style guarantee for recovering full outcome strings under sequential measurements.

2.1 Classical probability distributions and distances

  • Classical preliminaries model probability distributions on [d] and recall distances and divergences including the Bhattacharyya coefficient and squared Hellinger distance.Source: §2.1 · pp. 7–8

2.2 Quantum states and measurements

  • Quantum preliminaries define states as positive semidefinite trace-one matrices, observables and quantum events, POVMs, canonical implementations, quantum operations, and Naimark dilation.A state assigns each quantum event A a probability E_ρ[A], while a POVM produces outcome probabilities p_i = E_ρ[A_i].Source: §2.2 · pp. 8–9

2.3 Quantum state distances

  • Quantum state distances are related to measured classical divergences: total variation corresponds to trace distance and the Bhattacharyya coefficient to fidelity, with the Holevo–Helstrom theorem characterizing trace distance [27, 26].The section also gives a simpler fidelity formula for a conditioned version of a state, related to gentle-measurement results [39, Cor. 3.15].Source: §2.3 · pp. 10–11

2.4 Naive expectation estimation

  • Naive expectation estimation uses O(log(1/δ)/ε^2) copies and a measurement whose outcome estimates the expectation of a quantum event, while a constructed event B detects deviations from a target τ.For |tr(ρE) − τ| ≤ c − ε, the construction guarantees E_{ρ^⊗n}[B] ≤ δ.Source: §2.4 · pp. 11–12

2.5 Quantum union bound-style results

  • Quantum union-bound preliminaries compare independent acceptance probabilities with sequential acceptance and provide lemmas controlling sequential outcomes for quantum operations and events.The section supplies a different inductive proof of a Damage Lemma result after the original proof was found incorrect, and invokes Gao’s quantum Union Bound [20] for unique decoding.Source: §2.5 · p. 13
  • Sequentially measuring the pairs (Π0_i, Π1_i) for i=1,…,m produces the target outcomes x_1,…,x_m with probability at least 1−4εm.The condition is that E_ρ[Π^{x_i}_i] ≥ 1−ε for every i.Source: §2.5 · p. 14

3. 𝝌2-stable Threshold Reporting

The section develops a χ2-stable threshold-reporting result and transfers it to quantum states through projective measurements whose statistics follow a binomial distribution.

3. χ2-stable Threshold Reporting

  • A 1-Lipschitz transformation cannot increase variance, providing a basic ingredient for bounding the conditional statistic used in threshold reporting.The proof applies the variance contraction property to the relevant clipped function.Source: §3 · pp. 15–16
  • The numerical bounds rely on elementary exponential inequalities, including the choice C=(e−1)^2≤3, to establish the needed threshold probability estimate.The resulting estimate is summarized by (q+p e^λ)^n≲1 and a lower bound based on P[X>θn].Source: §3 · pp. 15–16
  • The core classical argument controls how conditioning on an event changes a distribution through χ2 divergence, with rare-event probabilities treated as close to one.The proof introduces conditional likelihood ratios and relates variance control to χ2 stability.Source: §3 · p. 15

3.1 The quantum version

  • The quantum transfer applies under the parameter conditions of the classical theorem, yielding a quantum event with the same threshold probability as the classical construction.The event is defined on n copies of the unknown state and is built from orthogonal tensor-product projectors.Source: §3.1 · pp. 17–19
  • The quantum version represents threshold events on ρ^⊗n using a quantum event B whose probability matches a classical threshold event involving a binomial variable and noise.For a projector A, the construction uses tensor-product projectors grouped by the number of measurement outcomes corresponding to A.Source: §3.1 · pp. 17–18

4. Threshold Search

This section develops and analyzes a reuse-based Threshold Search algorithm by reducing general observables to projectors and a fixed-gap promise problem. It establishes correctness guarantees, including control of false negatives and false positives, with copy complexity scaling as stated.

4.1 Preliminary reductions

  • The reduction replaces each observable with a projector while preserving expectations, incurs an additional n0 = O(1/ε^2) copy factor, and retains no dependence on the dimension parameter.Source: §4.1 · p. 20
  • Theorem 4.1 obtains O((log^2 m + log(1/δ)) · log(1/δ)) copies of ρ⊗n* and, except with probability at most δ, outputs the correct claim.Source: §4.1 · p. 20
  • Lemma 4.2 reduces the promised case to O(log^2 m) copies: when some projector has expectation above 3/4, the online algorithm selects an index with probability at least 0.01.The projectors are presented sequentially, and the algorithm may halt after any projector.Source: §4.1 · p. 20

4.2 The main algorithm (proof of Lemma 4.2)

  • The main algorithm measures a reusable current state initialized as ρ^⊗n, updating it after each projector; under E[X] = Ω(√n), its false-negative probability is at most 4/5.A key claim finds t with q_t ≤ 4/5, so the algorithm selects an index at most t with probability at least 1/5.Source: §4.2 · p. 22
  • For low-expectation projectors, choosing n = O(log^2(m/η)) makes each event probability at most (η/m)^2, while the failsafe limits erroneous selections below 1/4 to δ′.The augmented subroutine still selects an index with expectation at least 1/3 with probability at least 0.005 under the promise.Source: §4.1 · p. 21, §4.2 · p. 23
  • With η = 0.01, the proof sets n = O(log^2 m) as required.Source: §4.2 · p. 24
  • The proof identifies returns with E_ρ[A_i] ≥ 1/3 and uses bounds on p_1 + ··· + p_t, q_t, and fidelity to establish correctness.It applies Claim 4.5 with the Cauchy–Schwarz inequality, uses p_1 + ··· + p_t ≤ 1/4 and q_t ≤ 4/5, and invokes F(ρ^⊗n, ϱ_t) ≤ 1.Source: §4.2 · p. 24
  • The algorithm is correct with probability at least 0.03.This is the concluding guarantee of Lemma 4.2.Source: §4.2 · p. 24

5. Shadow Tomography and Hypothesis Selection

This section develops methods for Shadow Tomography and quantum Hypothesis Selection using Threshold Search. It also presents an alternative Hypothesis Selection approach based on a decision version of quantum Threshold Search.

5.1 Shadow Tomography

  • Theorem 5.1 guarantees a student algorithm making at most C0(log d)/epsilon^2 mistakes, regardless of how many quantum events are presented [3].The setting involves predicting expectations of adaptively presented events and receiving teacher feedback when predictions are inaccurate.Source: §5.1 · p. 25

P R O OF OF THEOREM 1.4. Define

  • The online Shadow Tomography algorithm simulates the student and teacher, using Threshold Search to certify predictions or identify mistakes and obtain fresh batches of rho.Each teacher mistake starts a new round, while a passing Threshold Search result supplies the final estimate.Source: P R O OF OF THEOREM 1.4. Define · pp. 26–27
  • With correct Threshold Search outcomes, the algorithm estimates all m values tr(rho A_i) within additive epsilon, while its mistake-bounded analysis limits the number of rounds.The construction allows at most R−1 mistakes with high probability; exceeding the available R batches is declared an overall failure.Source: P R O OF OF THEOREM 1.4. Define · p. 27

5.2 Hypothesis Selection

  • Quantum Hypothesis Selection uses known pairwise Holevo–Helstrom events and Shadow Tomography estimates, followed by a classical minimum-distance selection method.The estimates approximate every pairwise event expectation within epsilon/2, enabling selection among the fixed hypotheses.Source: §5.2 · p. 28
  • The quantum Hypothesis Selection result uses a number of copies of ρ that is the same as in Shadow Tomography, up to constant factors, with probability at most δ.Source: §5.2 · p. 28
  • The result follows from Inequality (4).Source: §5.2 · p. 28
  • A different, incomparable method for Hypothesis Selection is introduced.Source: §5.2 · p. 29
  • The method uses a decision version of quantum Threshold Search.Source: §5.2 · p. 29

Appendix A (see Corollary A.4):

The appendix develops a Threshold Search-based route for Hypothesis Selection, converting candidate-state tests into projectors and selecting a hypothesis close to the target state under explicit error conditions.

Appendix A (see Corollary A.4):

  • When η is known, finding ℓ with Δ_ℓ ≤ η + ε implies d_tr(σ_ℓ, ρ) ≤ 2η + η + ε.The bound follows from the candidate-distance guarantee used in Proposition 5.3.Source: Appendix A · p. 29
  • O(log(m/δ)/ε^2) copies suffice for the Threshold Decision subroutine, and Corollary 5.4 supplies projectors on n₀ = O(log(m)/ε^2) copies.Threshold Search is applied to projectors B_k constructed for candidate hypotheses.Source: Appendix A · p. 29
  • The alternative Hypothesis Selection method uses geometric estimates of η, fresh copies per iteration, and a failure allocation δ′ = δ/Θ(log(1/max{η, ε})).Its total copy usage is O(n_TS(m, 1/6, δ′) · log(1/max{η, ε})) copies of Ϛ, multiplied by n₀ copies of ρ.Source: Appendix A · p. 29
  • d_tr(σ_ℓ, ρ) ≤ 4η + 2ε when the geometric search proceeds without Threshold Search failure.The method searches decreasing estimates of η and stops when a search fails or η ≤ ε.Source: Appendix A · p. 29
  • Under η < 1/2(α − ε), the target candidate is separated from every other hypothesis by the Threshold Search condition.Here α is the minimum pairwise trace distance between distinct hypotheses.Source: Appendix A · p. 30

A. The quantum Threshold Decision problem

This appendix introduces a quantum Threshold Decision procedure based on a projector onto high-eigenvalue components of the summed observables, yielding a mild qualitative improvement over prior work and lower copy complexity.

A. The quantum Threshold Decision problem

  • The appendix presents the result as a new version of the Harrow–Lin–Montanaro theorem [24, Cor. 11] and notes similarity to Aaronson [1, Lem. 14].The cited prior work provides the comparison context for the decision procedure.Source: A. The quantum Threshold Decision… · pp. 32–33
  • The result is a mild qualitative improvement over the Harrow–Lin–Montanaro theorem [24, Cor. 11], whose lower bound is never close to 1 even when p_max is close to 1.The paper attributes its slight Threshold Decision improvement to this difference.Source: A. The quantum Threshold Decision… · pp. 32–33
  • Theorem A.2 defines B as the projector onto eigenspaces of Σ_i A_i with eigenvalue at least ν, relating B to p_max = max_i E_ρ[A_i].The construction uses observables 0 ≤ A_i ≤ 1 and a d-dimensional state ρ.Source: A. The quantum Threshold Decision… · p. 33
  • O(log(m/δ)/ε^2) copies solve quantum Threshold Decision with error probability at most δ.The decision algorithm has two possible outputs distinguishing whether some expectation exceeds the threshold or all are below it by ε.Source: A. The quantum Threshold Decision… · p. 33
  • Measuring B distinguishes the two cases: some E_ρ[A_j] > θ versus all E_ρ[A_i] ≤ θ − ε, with the corresponding probabilities separated by the construction.The proof uses a Chernoff-bound-derived set of events and a projector B.Source: A. The quantum Threshold Decision… · p. 34
Loading 2011.10908v4…