Learning Sparse Quantum States

1 Introduction

• ˜O(k/ε) samples and ˜O(kn/ε) time suffice for fidelity 1−ε pure-state learning; at k=2^n, the bounds recover worst-case optimality up to logarithmic factors.For k ≪ 2^n, the authors report exponential improvement over general tomography; known efficiently computable sparse bases with k=poly(n) also yield polynomial-time learning.Source: §1 · pp. 1–2
• ˜O(kr/ε) samples suffice to learn k-sparse rank-r mixed states, matching a lower bound up to logarithmic factors, but the algorithm is not time-optimal.The approach uses a random purification channel to map the mixed state to a kr-sparse pure state before applying the pure-state algorithm.Source: §1 · p. 2, §1.3 · pp. 5–6

1.1 Prior Work

• Earlier support-learning plus general tomography incurred ˜O(nk^2/ε) time, while [GL25] remained O(k^3 + nk^2); this work targets linear dependence on k.The authors identify obtaining linear scaling in k for time complexity as the main challenge.Source: §1.1 · p. 3

1.2 Phase States

• Sparse phase-state learning bounds the distinguishing time for subset phase states in [ABF+22] and gives near-optimal polynomial-time learning for poly(n)-sparse phase states, related to an open question in [ABDY22].Source: §1.2 · p. 4

1.3 Technical Overview

• Random linear hash functions create pairwise phase measurements; their matchings form short paths from a reference basis state, enabling phase recovery over paths of length O(log(k)).The algorithm first learns the support and projects hashed superpositions onto pairs of basis states.Source: §1.3 · pp. 4–5
• For nonuniform pure states, probability buckets permit phase learning at mass-proportional precision, with phases across buckets aligned to a shared reference state.A global phase graph could force overprecision for low-probability states; the bucketed method sums error in proportion to each bucket's probability mass. The guarantees also hold when at least 1−ε of the mass lies on at most k basis states.Source: §1.3 · pp. 5–6

1.4 Open Questions

• Optimal mixed-state runtime remains open; improving random purification could yield O(nkr/ε) time for k-sparse rank-r states.Source: §1.4 · p. 6, §1.3 · p. 6
• The introduction also asks whether single-qubit Pauli measurements can attain near-optimal sparse pure-state time and whether unknown Fock-basis sparsity permits sample-optimal, efficient learning.Source: §1.4 · p. 7

2 The Phase State Algorithm

• Random linear functions create partial matchings whose union forms an image-pairs graph of diameter O(log k) with probability at least 1 − δ.The graph connects support elements that are the only two inputs colliding under a function.Source: §2 · p. 9
• With δ = 1/n, the algorithm achieves fidelity at least 1 − ε using ˜O(k/ε) samples and ˜O(kn/ε) time, up to logarithmic factors.The running-time analysis includes implementing the hash functions and graph post-processing.Source: §2 · pp. 11–12
• O(k log(k/δ)) computational-basis measurements recover the full support with probability at least 1 − δ/4.This uses a coupon collector argument.Source: §2 · p. 12
• Hash outcomes with exactly two support preimages yield basis-state superpositions whose Pauli X and Y expectations estimate their relative phase.The algorithm uses the resulting relative-phase estimates as graph edges.Source: §2 · pp. 9, 12

3 The Pure State Algorithm

• Classical preprocessing learns a retained support and an approximate Z-basis distribution, then partitions the retained states into probability bins.The preprocessing uses ˜O(k/ε) samples overall.Source: §3 · pp. 13, 15, 17
• Each bin gets a phase graph built with random linear hashes, while the maximum-probability state serves as a common reference across bins.The bins are nearly uniform in probability, and each graph has small diameter and contains the reference state.Source: §3 · pp. 13, 16
• Phase accuracy is allocated by probability level, so each bin’s phase error contributes a probability-weighted amount to the fidelity error.The phase error for a state in a bin is bounded using that bin’s graph diameter and edge-estimation accuracy.Source: §3 · p. 13
• ˜O(k/ε) samples and ˜O(kn/ε) time achieve fidelity at least 1−ε with probability at least 1−δ using only single-copy measurements.The stated bounds use δ=1/n; the logarithmic factors may not be tight.Source: §3 · pp. 15, 17
• Projection onto a colliding pair isolates its two basis states, allowing relative-phase estimation despite other bins appearing in the hashed superposition.The projection succeeds with probability px + py.Source: §3 · p. 16

4 The Mixed State Algorithm

• Every purification of a k-sparse rank-r mixed state is kr-sparse as a pure state, enabling use of the pure-state learner.The purification lies in a subspace isomorphic to Ck ⊗ Cr.Source: §4 · p. 18
• ˜O(kr/ε) samples and poly(m, n) time achieve fidelity at least 1−ε for k-sparse rank-r mixed states.The stated bounds use δ=1/n and suppress logarithmic factors in k and 1/ε.Source: §4 · p. 18
• The algorithm applies a random purification channel to the mixed-state copies, then runs the pure-state tomography algorithm on the purified samples.The channel can be implemented within ε error in diamond distance by a circuit taking poly(m, log d, log(1/ε)) time.Source: §4 · pp. 18–19
• The purification channel dominates total runtime, leaving the mixed-state algorithm’s runtime as poly(m, n).The pure-state learner on the purified inputs requires ˜O(kr/ε) samples and ˜O(krn/ε) time.Source: §4 · p. 19

A Lower Bound

• Ω(kr/ε) samples are necessary to learn a k-sparse rank-r mixed state to fidelity greater than 1−ε, even with its support revealed.The proposition assumes k>1 and 1≤r≤k≤d.Source: A Lower Bound · p. 23
• The proof reduces arbitrary rank-r tomography in dimension k to sparse tomography by embedding the state into k fixed computational-basis vectors.The isometry produces a rank-r state supported on at most k computational-basis vectors.Source: A Lower Bound · p. 23
• Applying the sparse learner to the embedded state and inverting the isometry would yield a learner for the original state.The proof converts the estimate back by restricting it to the isometry’s image.Source: A Lower Bound · p. 23

B.1 Phase States

• The analysis evaluates fidelity between the two states being compared.The passage introduces the fidelity calculation for the error analysis.Source: §B.1 · p. 24
• The proof invokes the triangle inequality in bounding the phase-state error.The supplied passage identifies this step as a triangle-inequality bound.Source: §B.1 · p. 24
• The estimates use a fixed global phase convention relative to a reference basis state.This convention is applied to all the estimates discussed in the analysis.Source: §B.1 · p. 24

• The lemma assumes √p_xq_x ≥ 1 − η with η ≤ 1/2.The supplied lemma statement is partial.Source: §B.2 · p. 25
• After a global-phase adjustment, the coordinate phase errors are measured relative to the same reference phase.Source: §B.2 · p. 25
• The proof uses η ≤ 1/2 in its final step.Source: §B.2 · p. 25

• O(k log(k/δ)/η) samples yield a support S′, a distribution q, and labeled probability buckets with probability at least 1 − δ.The number of buckets is bounded by L = O(log(k/η)).Source: C Classical preprocessing · p. 25
• In the supplied definition, the threshold T = {x : p̄_x ≥ 2ρ} retains exactly those points whose empirical probabilities are at least 2ρ.Source: C Classical preprocessing · p. 26
• With probability at least 1 − δ/3, multiplicative Chernoff bounds and a union bound give simultaneous guarantees over the support of p.Source: C Classical preprocessing · p. 26
• On T, retained points satisfy p_x ≥ ρ and p̄_x = Θ(p_x); restricting p̄ to T and renormalizing changes error by only O(η).Source: C Classical preprocessing · p. 26
• Dyadic bucketing of the restricted distribution gives at most L = O(log(k/η)) levels, with each point satisfying t_j ≤ q_x < 2t_j.The true probabilities on T are within a constant factor of the bucketed probabilities.Source: C Classical preprocessing · pp. 25–26
• Discarding levels with q̃-mass below η/(100L) removes only O(η) total mass, and each remaining level has q-mass and p-mass Ω(η/L).Restricting to the remaining levels and renormalizing preserves q_x = Θ(p_x) on S′.Source: C Classical preprocessing · p. 26