Fast quantum measurement tomography with optimal error bounds

Technical Summary: Fast Quantum Measurement Tomography with Optimal Error Bounds

Problem Statement
Quantum measurement tomography (QMT), or detector tomography, aims to reconstruct an unknown Positive Operator-Valued Measure (POVM) from experimental statistics obtained using a known ensemble of probe states. Accurate characterization of measurement noise is critical for benchmarking hardware and enabling error-mitigation strategies, such as correcting outcome probabilities or refining classical shadow protocols. However, existing methods face two primary limitations:

1. Computational Cost: Standard approaches, such as Maximum Likelihood Estimation (MLE) with constrained optimization, become computationally intractable as the system dimension ($d$) and the number of measurement outcomes ($L$) increase.
2. Theoretical Guarantees: Convergence guarantees for many existing estimators are often asymptotic (relying on the central limit theorem), leaving finite-sample error bars without rigorous theoretical grounding.

The challenge is to develop a protocol that is both computationally efficient in classical post-processing and sample-optimal, providing rigorous non-asymptotic error bounds.

Methodology
The authors propose a two-step protocol for QMT that decouples statistical estimation from physical constraint satisfaction:

1. Least-Squares Estimation (LSE):

   • Given measurement frequencies $\hat{f}_{ij}$ from a known set of probe states $\{|\psi_i\rangle\}$, the protocol first computes an unconstrained linear estimator $\hat{E}_j$ for each POVM element.
   • The estimator is defined as $\hat{E}_j = \sum_{i} \hat{f}_{ij} \nu_i$, where $\nu_i$ are specific operators derived from the probe ensemble.
   • This step admits an analytic solution if the probe ensemble forms a global 2-design or a tensor product of local 2-designs (e.g., single-qubit Pauli eigenstates). This avoids iterative optimization in the first stage.

2. Projection onto the POVM Set:

   • The raw LSE estimate $\hat{E}$ typically violates physical constraints (positivity and completeness).
   • The protocol projects $\hat{E}$ onto the convex set of valid POVMs by solving a constrained optimization problem:
     $$\min_{\{Z_j\}} d(\hat{E}, Z) \quad \text{subject to} \quad Z_j \geq 0, \sum_j Z_j = \mathbb{I}$$
   • The distance metric $d$ can be the operational distance ($d_{op}$) or the average-case distance ($d_{av}$).
   • To ensure computational scalability, the authors utilize Dykstra's alternating projection algorithm rather than exact Semidefinite Programming (SDP), significantly reducing runtime while maintaining accuracy.

Key Contributions

1. Optimal Sample Complexity:
   The paper establishes that the proposed protocol achieves optimal sample complexity for both worst-case (operational) and average-case distances, matching fundamental lower bounds derived via Fano's inequality.

   • Worst-case (Operational) Distance ($d_{op}$): Requires $O((d^3 + d^2L)/\epsilon^2)$ samples for global 2-designs and $O((12n + 6nL)/\epsilon^2)$ for local 2-designs (where $n$ is the number of qubits, $d=2^n$).
   • Average-case Distance ($d_{av}$): Requires $O(d^2L/\epsilon^2)$ samples for global 2-designs and $O(5nL/\epsilon^2)$ for local 2-designs.
   • Lower Bounds: The authors prove that any non-adaptive, single-copy POVM tomography protocol requires at least $\Omega((d^3 + d^2L)/\epsilon^2)$ and $\Omega(d^2L/\epsilon^2)$ samples for the respective distances, confirming the protocol's optimality in both $d$ and $L$.

2. Rigorous Non-Asymptotic Error Bounds:
   Unlike asymptotic methods, the paper provides explicit, non-asymptotic error bounds that hold for finite sample sizes with high probability ($1-\delta$). These bounds are derived using concentration inequalities (Bernstein's inequality) and net arguments over the unit sphere.

3. Computational Scalability:
   The authors demonstrate that replacing exact SDP with Dykstra's alternating projection reduces the time complexity from $O(d^6L^3)$ (standard MLE) to $O(d^3L)$ per iteration, with memory complexity reduced from $O(d^4L^2)$ to $O(d^2L)$. This makes the method feasible for larger system sizes where MLE becomes intractable.

4. Application to Error Mitigation:
   The paper explicitly links the tomographic error bounds to the residual error in classical noise-mitigation schemes. By bounding the distance between the estimated and true POVM, the protocol quantifies the accuracy of correcting measurement noise via a column-stochastic matrix $\Lambda$.

Results

• Numerical Simulations: Benchmarks against standard MLE show that the LSE + Dykstra approach achieves comparable reconstruction accuracy (under both $d_{op}$ and $d_{av}$) but is orders of magnitude faster in execution time. The empirical errors consistently remain below the theoretical non-asymptotic upper bounds for system sizes up to $n=6$ qubits and $L=32$ outcomes.
• Experimental Validation: The protocol was implemented on a noisy superconducting quantum computer with two flux-tunable transmon qubits. The team successfully reconstructed a noisy Symmetric Informationally Complete (SIC-)POVM using $1.66 \times 10^5$ shots. The reconstruction closely matched the target, and the protocol successfully characterized the deviations caused by gate and readout noise, enabling the construction of a "half-sided noisy measurement channel" for error mitigation.

Significance and Claims
The paper claims to provide a sample-optimal and computationally efficient solution to quantum measurement tomography. Its significance lies in:

• Theoretical Optimality: Proving that the protocol's scaling matches the fundamental information-theoretic lower bounds for non-adaptive protocols, a property not guaranteed by previous heuristic methods.
• Practical Viability: Offering a method that scales polynomially with system size and outcome count, making it suitable for near-term quantum devices where resources are limited.
• Rigorous Guarantees: Providing finite-sample error bounds that are essential for reliable error-mitigation strategies, moving beyond asymptotic assumptions.
• Experimental Relevance: Validating the method on real hardware, demonstrating its ability to characterize complex, noisy measurements and directly support error-mitigation pipelines for protocols like classical shadows.

The authors emphasize that while the operational distance ($d_{op}$) offers strict guarantees for all states (crucial for rigorous error mitigation), the average-case distance ($d_{av}$) offers a resource-efficient alternative for randomized protocols, with the proposed method supporting both regimes optimally.