Technical Summary: Measurement Complexity of Quantum Compressed Sensing

Problem Statement

Conventional compressed sensing (CS) establishes that reconstructing a $K$-sparse signal of dimension $N$ under non-adaptive measurements requires a lower bound of $M = \Omega(K \log(N/K))$ measurements. The logarithmic factor represents the unavoidable combinatorial entropy cost of identifying an unknown support set. Recent experimental reports on Quantum Compressed Sensing (QCS) suggest measurement counts below this classical bound. However, the theoretical origin of this advantage, the specific mechanisms by which QCS might circumvent classical information-theoretic limits, and the precise conditions under which this advantage holds have not been rigorously established within a general information-theoretic framework. This work aims to fill that gap by deriving fundamental lower bounds on the measurement complexity of QCS from both information-theoretic and quantum-physical perspectives.

Methodology

The authors establish a rigorous comparison framework between classical non-adaptive linear CS and QCS by enforcing five common constraints:

1. Known Sparse Basis, Unknown Support: The sparse basis $\Psi$ is known, but the specific support set $\Omega$ and signal coefficients are unknown.
2. Non-adaptive Measurements: The measurement scheme is fixed prior to data acquisition and does not depend on previous outcomes.
3. Finite Resources: Measurements have finite quantization and information budgets.
4. No Additional Priors: No instance-specific information about amplitudes, phases, or support structure is assumed.
5. Common Recovery Criterion: Both schemes are evaluated on the task of exactly recovering the unknown support set with a failure probability $\le \delta$.

The analysis distinguishes between two resource metrics:

• $M_s$ (Effective Index Samples): The total number of independent statistical samples (index outcomes) used for recovery.
• $M$ (Experimental Rounds): The number of times the quantum experiment is repeated.

The QCS protocol is formalized into four steps: (1) preparation of a uniform quantum probe state, (2) linear signal-to-state mapping, (3) unitary domain-alignment evolution (which maps the sparse basis to the measurement basis one-to-one), and (4) projective measurement yielding index outcomes. The authors analyze the complexity at three levels of recovery: basic statistical estimation, exact support recovery, and joint support recovery with coordinate-wise amplitude estimation.

Key Contributions and Results

1. Fundamental Distinction in Information Encoding

The paper identifies that the core difference between QCS and classical CS lies in the measurement architecture. In classical CS, support information is mixed into continuous-valued outcomes and must be inferred. In QCS, the unitary domain-alignment evolution maps the sparse basis directly to the measurement basis, meaning the locations of nonzero components are explicitly carried by the index labels of the measurement outcomes. This shifts the problem from inferring positions to covering the set of active indices.

2. Lower Bounds on Effective Index Samples ($M_s$)

The authors derive three levels of lower bounds for the total number of effective index samples required:

• Level I (Basic Statistics): To obtain basic statistical information about $K$ nonzero components (assuming known support and fixed relative accuracy), the sample complexity is $M_s = \Omega(K)$. This is a coarse necessary condition reflecting the linear scaling with sparsity but does not account for the difficulty of identifying an unknown support.
• Level II (Exact Support Recovery): For the core task of exactly recovering an unknown support set (where nonzero probabilities satisfy $p_n = \Theta(1/K)$), the required sample complexity is $M_s = \Theta(K \ln K)$.
  • This result is derived using the "coupon collector" problem logic: to ensure all $K$ nonzero indices are observed at least once with high probability, $\Theta(K \ln K)$ samples are necessary.
  • Crucially, this bound removes the explicit dependence on $N$ (the signal dimension) found in the classical bound $M = \Omega(K \log(N/K))$. The dimension $N$ only affects the readout resolution (length of the index label), not the statistical sampling requirement, because the measurement outcomes directly provide location labels.
• Level III (Joint Recovery with Amplitude Estimation): If, in addition to support recovery, each nonzero amplitude must be estimated with a coordinate-wise relative root-mean-square error $\varepsilon$, the complexity becomes $M_s = \Theta(K \ln K + K/\varepsilon^2)$.
  • The $K \ln K$ term arises from support coverage.
  • The $K/\varepsilon^2$ term arises from the statistical cost of estimating probabilities of order $1/K$ to a relative precision $\varepsilon$.
  • For fixed $\varepsilon$, the complexity remains $\Theta(K \ln K)$.

3. Multi-Index Readout and Experimental Rounds

The paper analyzes the effect of multimode photon-number-resolving detection, where a single experimental round can produce $L$ effective index samples.

• Result: Increasing $L$ reduces the number of experimental rounds $M$ (where $M \approx M_s/L$), but does not reduce the total effective index sample complexity $M_s$.
• Even with $L = \Theta(K)$, reducing rounds to $O(\ln K)$ or $O(1)$, the total statistical resource (total detection events) required remains $\Theta(K \ln K)$. The paper emphasizes that reducing experimental rounds is a throughput improvement, not a reduction in the fundamental statistical information required for recovery.

Significance and Claims

The paper claims that its results establish a conditional quantum advantage for QCS, rather than an unconditional one.

• The Advantage: QCS achieves a measurement complexity of $\Theta(K \ln K)$ for support recovery, which is asymptotically superior to the classical non-adaptive bound of $\Omega(K \log(N/K))$ when $N$ is large. This advantage stems from the ability of quantum parallelism and domain-alignment evolution to directly encode support locations into measurement indices, bypassing the combinatorial search cost associated with continuous-valued classical measurements.
• The Conditions: This advantage is strictly conditional on:
  • A known sparse basis.
  • The physical implementability of the unitary domain-alignment evolution.
  • Resolvable index-based readout.
  • Independent single-index (or equivalent multi-index) sampling.
• Limitations: The authors explicitly state that this is not a universal lower bound for all quantum measurements. The results do not apply if the sparse basis is unknown, if the support is structured, or if adaptive measurements are allowed. Furthermore, the analysis focuses on the magnitudes of normalized coefficients; it does not address the recovery of signs, phases, or unknown overall scales.

In conclusion, the work demonstrates that while quantum parallelism is a transformative resource for measurement science, the reduction in measurement complexity is bounded by statistical sampling requirements (specifically the coupon collector problem) rather than being a violation of information-theoretic limits. The "quantum advantage" is a shift in the scaling from $N$-dependent to $N$-independent, contingent on specific physical implementations and signal models.