PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning sparse quantum states from single-qubit measurements

Su-un Lee, Liang Jiang, Kunal Sharma

arXiv:2609.35648v1quant-phcs.DScs.ITmath.IT

TL;DR

Sparse states can encode long-range entanglement that local reduced density matrices cannot reveal, while prior approaches to such states use entangling gates. This paper learns them using single-qubit measurements, with polynomial sample complexity and classical-runtime guarantees that depend on sparsity and basis restrictions.

  • Problem

    Sparse states can have long-range entanglement that prevents reconstruction from local reduced density matrices, while existing methods for such states require entangling gates.

    Source: §1 · pp. 3–4

  • Method

    The algorithms use single-qubit measurements, combining low-order Pauli moments to find candidate bases with selected-entry tomography to reconstruct sparse states.

    Source: §1.1 · p. 4, §4.1 · p. 14

  • Results

    Polynomially many copies suffice for polynomially sparse states; classical runtime is quasipolynomial for a fixed finite set of single-qubit bases, while polynomial classical complexity is guaranteed for constant sparsity.

    Source: §1.1 · p. 5

  • Takeaways & Limitations

    Sparse states with long-range entanglement can be learned without entangling gates using single-qubit measurements.

    Source: §1 · p. 3, §1.1 · p. 4

    For polynomially growing s, polynomial classical runtime is not guaranteed for general sparse states, and the quasipolynomial guarantee assumes a fixed finite set of single-qubit bases.

    Source: §1.1 · p. 4, §1.2 · p. 6

Abstract

from arXiv · show

We study the problem of learning a sparse quantum state, an $n$-qubit quantum state whose density matrix has at most $s$ nonzero matrix entries in an unknown product basis. While such states admit compact classical descriptions, they can carry long-range entanglement that prevents reconstruction from local reduced density matrices alone. Therefore, previous learning approaches addressed such long-range-entangled states using many entangling gates to extract the necessary information. In this work, we show that sparse states can nevertheless be efficiently learned using only single-qubit measurements. Specifically, when the sparsity $s$ is constant, our algorithm can learn sparse states from single-qubit measurements with polynomial sample complexity and classical computational complexity. When $s$ grows polynomially with $n$, sparse states can still be learned from single-qubit measurements with polynomial sample complexity, although efficient classical computation is not guaranteed in general. In this regime, however, the classical computational complexity becomes quasipolynomial when the state is sparse in an unknown basis that is a product of a known fixed finite set of single-qubit bases (e.g., eigenbases of Pauli operators). These results establish efficient learning of sparse states with long-range entanglement without entangling gates, and the single-qubit measurement requirements make our algorithms compatible with current quantum devices.

1 Introduction

The paper asks whether sparse states with long-range entanglement can be learned using only single-qubit measurements. It answers yes, with polynomial sample complexity and varying classical-runtime guarantees depending on sparsity and the basis.

1 Introduction

  • Long-range entanglement can make every local reduced density matrix uninformative about a GHZ state's phase, so local reconstruction methods do not cover general sparse states.Earlier approaches addressing long-range entanglement require many entangling gates, including progressive disentangling in MPS learning.Source: §1 · pp. 3–4

1.1 Results

  • With a known sparse product basis, selected-entry tomography learns an s-sparse state using single-qubit measurements, O(s^4 log(s)/ε^2) copies, and O(ns^4 log(s)/ε^2) classical runtime.The method estimates any selected matrix entry in that basis.Source: §1.1 · pp. 4–5
  • For constant s, Algorithm 1 combines low-order Pauli moments to generate candidate bases with selected-entry tomography, achieving polynomial sample and classical complexity.The candidate list includes a basis in which the state is s-sparse.Source: §1.1 · p. 5
  • Algorithm 2 partitions qubits into small blocks, learns local states, then merges blocks using selected-entry tomography; it has polynomial sample complexity in n and s.Its classical runtime grows rapidly in n and s for arbitrary product bases; the Donoho–Stark uncertainty principle helps reduce runtime when bases come from a fixed finite set.Source: §1.1 · p. 5
  • For polynomially growing s, Algorithm 2 learns with polynomially many copies; its classical runtime is quasipolynomial when the unknown basis uses a fixed finite set of single-qubit bases.For general sparse states, polynomial classical runtime is not guaranteed; constant s admits polynomial sample and classical complexity.Source: §1.1 · pp. 4–5

1.2 Discussion

  • A variant of Algorithm 1 tests sparsity: it accepts approximately s-sparse states with a close sparse reconstruction and rejects states ε-far from every s-sparse state.Acceptance provides a compact description whose accuracy can be certified.Source: §1.2 · pp. 5–6
  • The algorithms use copy-to-copy adaptivity, choosing later measurement bases from earlier-copy outcomes, but do not use within-copy qubit-to-qubit adaptivity.The latter essentially requires mid-circuit measurement and feed-forward.Source: §1.2 · p. 6, Figure 1 · p. 6
  • The protocols estimate product-observable expectation values and probability masses, making them compatible with standard error mitigation; probabilistic error cancellation adds sampling overhead exp(O(ne)).The paper notes current processors' readout errors e ≲ 1/n make this overhead manageable.Source: §1.2 · pp. 6–7

2 Technical overview

The overview develops two single-qubit-measurement algorithms that find a product basis in which a sparse state can be learned. Algorithm 1 uses low-order Pauli moments for fixed sparsity; Algorithm 2 merges blocks to support polynomial sparsity, with classical runtime depending on the allowed local bases.

2 Technical overview

  • For a known product basis B, direct measurements sample pB(x) = [ρ]B(x, x), then the procedure estimates the submatrix on the found support using single-qubit measurements.The support includes all bitstrings except those with negligible probabilities; selected-entry tomography estimates matrix entries using randomized single-qubit measurements.Source: §2 · p. 7

2.1 Algorithm 1: low-order Pauli moments

  • Algorithm 1 uses low-order Pauli moment tensors to infer candidate local bases; contracting against bases on difficult qubits cancels off-diagonal contributions and reveals the remaining bases.Except for O(log s) qubits, each qubit appears in a small moment tensor with a non-negligible Fourier coefficient.Source: §2.1 · pp. 8–10, Figure 2 · p. 8
  • Algorithm 1 has sample and classical computational complexities n^O(s), hence polynomial for fixed s.It enumerates candidate difficult-qubit sets and local bases, then tests candidate bases by selected-entry tomography.Source: §2.1 · p. 10

2.2 Algorithm 2: tree-structured merging

  • Algorithm 2 has polynomial sample complexity in n and s; its runtime is super-exponential for arbitrary product bases but n^O(log s) for a fixed finite set of local bases.For polynomially growing s, the finite-set runtime is quasipolynomial.Source: §2.2 · pp. 10, 12
  • Algorithm 2 recursively merges adjacent blocks, learning each block’s reduced state from child outcomes because partial traces preserve the state’s s-sparse representation.The tree begins with blocks of at most floor(log2 s) qubits and reaches a block containing all n qubits.Source: §2.2 · pp. 10–11
  • Merging two child supports of at most s vectors yields at most s^4 entries to estimate, so each merge searches for a product basis that compacts the representation back to at most s basis vectors.The algorithm performs selected-entry tomography on the merged submatrix before the search and compaction.Source: §2.2 · p. 11
  • For a fixed finite set of local bases, the Donoho–Stark uncertainty principle limits candidate bases to those differing on O(log s) qubits, reducing the search to at most |Q|^O(log s) choices.This yields the n^O(log s) runtime reported for Algorithm 2.Source: §2.2 · pp. 11–12
  • For arbitrary local bases, the uncertainty-principle bound can be vacuous, leaving an exponentially large search space.The change-of-basis entries may be too close to one for the principle to provide a useful reduction.Source: §2.2 · p. 12

3 Preliminaries

This section sets up Bloch-vector representations of single-qubit bases and approximation tools for controlling projection leakage. It also defines a finite net for discretizing possible local bases.

Preliminaries

  • A single-qubit orthonormal basis is represented, up to sign, by a unit Bloch vector n in R^3.The two opposite vectors represent the same basis with labels 0 and 1 swapped.Source: §3 · p. 12
  • A single-qubit ε-net is a finite set of unit Bloch vectors that approximates every unit vector within label-invariant angular distance ε.For a product basis on a qubit subset Q, the product net approximates every local axis within ε.Source: §3 · pp. 12–13
  • Leakage error η bounds the probability mass outside a projected subspace, expressed as Tr[(I − A)ρ] ≤ η.The section states that this leakage controls both Frobenius- and trace-norm projection errors.Source: §3 · pp. 13–14
  • If Tr[(I − A)ρ] ≤ η, Lemma 3.2 bounds the Frobenius-distance error caused by projection.The supplied passage gives the lemma’s condition but not its bound’s expression.Source: §3 · p. 13
  • If Tr[(I − A)ρ] ≤ η, Lemma 3.3 bounds the trace-distance error caused by projection.The section also gives a triangle inequality for propagating leakage through successive projectors.Source: §3 · pp. 13–14

4 Selected-entry tomography

Selected-entry tomography estimates chosen matrix elements using randomized single-qubit measurements and extends to small submatrices. For a known sparse product basis, sampling and estimating selected entries yields a sparse trace-distance approximation with polynomial resource bounds.

4.1 Estimating selected entries and submatrices

  • Selected-entry tomography estimates any chosen entry [ρ]B(x,y) in a known product basis using only single-qubit measurements.It randomizes a bitstring z and measures a tensor product of Pauli observables rotated by the local basis transformations.Source: §4.1 · pp. 14–15
  • Estimating every entry of a selected t-by-t submatrix produces a Hermitian estimate within ε in Frobenius distance with probability at least 1 − δ.The supplied corollary states the guarantee and copy bound, though the bound is truncated in the passage.Source: §4.1 · p. 15
  • Selected-entry tomography is used in both algorithms to estimate matrix entries or small submatrices once a product basis has been chosen.Its single-qubit measurement requirement avoids entangling gates.Source: §4.1 · pp. 14, 16

4.2 Learning sparse states in a known product basis

  • The known-basis procedure samples in B to identify likely support bitstrings, then applies selected-entry tomography to estimate the submatrix on that support.Entries estimated below ε/(4s) are discarded; the resulting matrix remains s-sparse.Source: §4.2 · pp. 16–17
  • A known product basis permits learning an s-sparse state with trace-distance error at most ε using single-qubit measurements, O(s^4ε^-2 log(s/δ)) copies, and runtime O(ns^4ε^-2 log(s/δ)).The algorithm captures observed basis bitstrings, estimates entries on their selected support, and truncates small estimates.Source: §4.2 · pp. 16–17

5 Learning with low-order Pauli moments

This section presents a single-qubit-measurement algorithm that uses low-order Pauli moments to identify a candidate product basis and test and reconstruct states sparse in an arbitrary unknown product basis. Subject to the stated estimation events, the procedure returns an s-sparse approximation with trace-norm error at most ε.

5.1 Explicit algorithm and result

  • With probability at least 1 − δ, Algorithm 1 uses only single-qubit measurements and outputs an s-sparse operator bρ with ∥bρ − ρ∥1 ≤ ε for states sparse in an arbitrary unknown product basis.The algorithm constructs candidate product bases, tests their output distributions for sparsity, and applies selected-entry tomography to candidates that pass.Source: §5.1 · p. 19

5.2 Fourier analysis of sparse distributions

  • For a distribution supported on at most s bitstrings, at most 2 log2 s qubits are low-contrast, while each other qubit has a detecting Fourier coefficient on a set of size at most ℓ0.The detecting set contains that qubit and its coefficient has magnitude greater than 1/(4s log2 s).Source: §5.2 · pp. 20, 22, 23

5.3 Factorization of Pauli moment tensors and the difficult set

  • Contracting low-order Pauli moment tensors on a difficult set of at most s + 2 log2 s qubits cancels off-diagonal contributions and enables SVD recovery of basis vectors on the other qubits.The difficult set combines representatives of off-diagonal flip sets with low-contrast qubits; qubits outside it have a detecting moment tensor with a large leading singular value.Source: §5.3 · pp. 24–25

5.4 Robust basis recovery

  • Basis recovery is analyzed with estimated Pauli moment tensors and approximate Bloch vectors on difficult qubits, with moment-estimation failure bounded using Hoeffding’s inequality and a union bound.Only proposed vectors on difficult qubits enter the contractions; recovered vectors on other qubits do not enter later contractions.Source: §5.4 · p. 25
  • Conditioned on E1, Step 1 produces a candidate-basis list containing a sufficiently accurate basis, and that basis preserves an s-sparse state approximation.Lemma 5.10 establishes the sparse approximation under product-basis errors bounded by γ.Source: §5.4 · pp. 27–28

5.5 Completeness and soundness of reconstruction

  • On the stated estimation events, the accurate candidate basis passes both reconstruction tests, while every accepted matrix has trace-norm error at most ε.The tests select a set of at most s bitstrings capturing nearly all measurement probability, then retain entries of magnitude at least θ only when at most s remain.Source: §5.5 · pp. 30–31

5.6 Proof of Theorem 5.1

  • On E1 ∩ E2 ∩ E3, Algorithm 1 returns a matrix with at most s nonzero entries in a product basis and trace-norm error at most ε, with total failure probability at most δ.The proof bounds the three event failures by δ/3 each.Source: §5.6 · p. 33
  • The resource analysis counts candidate bases from partial basis assignments and sums the costs of low-order Pauli-moment estimation, basis testing, and selected-entry tomography.The runtime components are O(GnNobs poly(3^ℓ0)) for basis construction, O(GnN2) for Step 2, and O(G(nN3 + s2)) for Step 3.Source: §5.6 · pp. 33–34

6 Learning with tree-structured merging

This section develops and analyzes tree-structured merging with single-qubit measurements for learning sparse states in arbitrary unknown product bases and in bases drawn from a known finite set. It tracks error propagation through adaptive merges and gives the finite-basis search and its resource analysis, using the Donoho–Stark uncertainty principle to control leakage during recursion.

6.1 Explicit algorithm and results

  • For an arbitrary unknown product basis, Algorithm 2 uses single-qubit measurements and polynomially many samples to output an s-sparse state within trace distance ε with probability at least 1 − δ, while its classical basis search remains exhaustive.The algorithm initializes leaf blocks, recursively merges adjacent blocks, and compresses sparsity between merges; the final output is truncated to at most s entries.Source: §6.1 · pp. 36–37
  • For a known finite set A of single-qubit bases, the Donoho–Stark uncertainty principle reduces the product-basis search from |A|^n assignments to n^O(log s) candidates.Theorem 6.2 guarantees that the algorithm uses only single-qubit measurements and outputs an s-sparse estimate in a product basis from A^n within trace distance ε, with probability at least 1 − δ.Source: §6.1 · p. 37

6.2 Leakage propagation through merges

  • At each merge, leakage can grow from inherited child leakage, tomography error, and—only for arbitrary-basis searches—basis approximation; the bound includes 2η_d + ξ + 2sε1.For the known finite-set case, the search includes the true product basis, so this additional basis-approximation error is zero.Source: §6.2 · pp. 38–39

6.3 Arbitrary continuous product bases (Theorem 6.1)

  • For arbitrary continuous product bases, searching a product of single-qubit ε2-nets contributes ξ = |Q| sin(ε2/2) to the leakage bound at a merge.The analysis applies this bound to control the leakage entering the final reconstruction step.Source: §6.3 · pp. 40–41
  • For arbitrary continuous product bases, Algorithm 2 outputs an s-sparse state in a product basis, with its approximation guarantee derived from the final merge and compression bounds.Tomography uses O(n^6s^12ε^-4 log(ns/δ)) copies per level across O(log n) levels; the classical runtime is bounded by (sn/ε)^O(n), up to polylog(δ^-1) factors.Source: §6.3 · pp. 43–44

6.4 Known finite set of single-qubit bases (Theorem 6.2)

  • For a known finite set of single-qubit bases, the Donoho–Stark uncertainty principle reduces each merge’s basis search to n^O(log s) candidates while controlling leakage through recursion.The remaining algorithm steps are the same as for arbitrary product bases.Source: §6.4 · pp. 44, 47
  • The finite-basis algorithm outputs a state with at most s entries in its returned basis and Frobenius error at most ε/(4√s).The tomography sample count and success probability match the arbitrary-product-basis case.Source: §6.4 · pp. 48–49
  • The finite-basis restriction yields quasipolynomial classical runtime, with tomography and sample processing contributing an ε^-4 factor while basis search is independent of ε.The number of candidate product bases at each merge is bounded by (H + 1)(n|A|)^H, where H = O(log(s)/κ).Source: §6.4 · p. 49

7 Testing sparsity of arbitrary quantum states.

The section adapts Algorithm 1 to test arbitrary quantum states for approximate sparsity, rather than assuming the input is sparse. For fixed sparsity, it gives a YES/NO guarantee with a gap between the near-sparse and far-from-sparse cases.

7 Testing sparsity of arbitrary quantum states.

  • The testing variant extends Algorithm 1’s setting from inputs assumed sparse in an unknown product basis to arbitrary input states.The section states the arbitrary-input testing objective and modifies Algorithm 1 to implement it.Source: §7 · p. 49, §7.2 · p. 51

7.1 From sparse operators to sparse states

  • A state within trace distance ε < 1 of an s-sparse operator is also close to a physical s-sparse state.The construction restricts to a small subspace, removes entries outside the operator’s support, then restores positivity and unit trace.Source: §7.1 · pp. 49–50

7.2 Testing sparsity with Algorithm 1

  • For fixed s = O(1), the test uses single-qubit measurements and has the same sample and classical computational complexities as Algorithm 1.It modifies only the initial Pauli-moment estimation, refining its statistical error to ε1/2, then tests candidate bases.Source: §7 · p. 49, §7.2 · p. 51
  • If dist1(ρ, Ms) ≤ ζ = Θ(ε^4/n), the test outputs YES with an ε-close s-sparse operator; if dist1(ρ, Ms) > ε, it outputs NO, with probability at least 1 − δ.The degrees of the sample and classical computational complexities, and the constant factor in ζ, depend on s.Source: §7.2 · p. 51
Loading 2609.35648v1…