Nearly Time-Optimal Pure State Tomography with Pauli Measurements
Pith reviewed 2026-05-16 15:54 UTC · model grok-4.3
The pith
An algorithm reconstructs any n-qubit pure state to fidelity 1-ε using only nonadaptive single-qubit Pauli measurements in near-optimal Õ(2^n/ε) time and copies.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
Given Õ(2^n/ε) copies of an unknown n-qubit pure state, there exists an algorithm that performs only nonadaptive single-qubit Pauli measurements, executes in Õ(2^n/ε) time, and outputs a state vector whose fidelity with the unknown state is at least 1-ε with high probability. This establishes the first near time-optimal method for pure state tomography using Pauli measurements.
What carries the argument
A nonadaptive collection of single-qubit Pauli measurements together with an efficient classical post-processing routine that reconstructs the pure-state amplitude vector from the resulting statistics.
If this is right
- Pure-state tomography no longer requires adaptive choice of measurements or multi-qubit operations to reach near-optimal time.
- The copy and time costs remain matched even when n grows and 2^n becomes large but still computationally feasible.
- Verification protocols that rely on Pauli measurements can now certify pure states in time linear in the output size.
- The high-probability guarantee holds uniformly over all possible pure states.
Where Pith is reading between the lines
- The same measurement schedule might be reusable across multiple tomography tasks on the same device, amortizing setup cost.
- Combining the procedure with error-mitigation techniques could extend it to mildly noisy hardware while preserving the asymptotic scaling.
- The nonadaptive nature suggests the algorithm could be parallelized across independent copies measured simultaneously.
Load-bearing premise
The input state must be exactly pure and the single-qubit Pauli measurements must be performed perfectly and non-adaptively on identical copies.
What would settle it
A concrete lower-bound proof showing that any algorithm limited to nonadaptive single-qubit Pauli measurements requires ω(2^n/ε) time to guarantee constant fidelity for some family of n-qubit pure states would falsify the near-optimality claim.
read the original abstract
We give an algorithm for pure state tomography with near-optimal copy and time complexity using only single-qubit measurements. Specifically, given $\widetilde{O}(2^n/\epsilon)$ copies of an unknown $n$-qubit pure state $|\psi\rangle$, the algorithm performs only nonadaptive Pauli measurements, runs in time $\widetilde{O}(2^n/\epsilon)$, and outputs $|\widehat{\psi} \rangle$ with fidelity at least $1-\epsilon$ with $|\psi\rangle$ with high probability. This is the first algorithm for pure state tomography that achieves near-optimal running time.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript presents an algorithm for pure-state tomography of an n-qubit pure state |ψ⟩ using only non-adaptive single-qubit Pauli measurements. With Õ(2^n/ε) copies, the procedure randomly selects a Pauli basis for each qubit on each copy, collects the resulting 2^n-dimensional empirical frequency vector, and recovers an estimate |ψ̂⟩ in linear time by thresholding the dominant eigenvector of the estimated density matrix and adjusting phases; the output satisfies fidelity 1−ε with high probability. The analysis relies on vector-valued concentration bounds to control the deviation of the empirical statistics and shows that the post-processing remains within the stated Õ bound. The paper claims this is the first algorithm achieving near-optimal copy and time complexity under these measurement restrictions.
Significance. If the central claims hold, the result is significant: it supplies the first explicit construction for pure-state tomography that simultaneously meets the information-theoretic sample lower bound (up to log factors) and runs in near-linear time while using only experimentally standard non-adaptive Pauli measurements. The combination of a simple random measurement schedule, vector concentration, and a linear-time recovery step that avoids super-linear linear-algebra primitives constitutes a concrete technical advance over prior tomography algorithms whose time complexity was at least quadratic in the dimension.
major comments (1)
- [Section 4 (Recovery Procedure)] The linear-time claim for the recovery step (dominant-eigenvector extraction via matrix-vector multiplication on the empirical frequencies) is load-bearing for the overall Õ(2^n/ε) runtime. The manuscript should explicitly state the data structure used to represent the estimated density matrix and confirm that each matrix-vector product indeed costs O(2^n) arithmetic operations rather than O(2^{2n}).
minor comments (2)
- [Theorem 1] The notation Õ is used throughout without an explicit statement of the hidden polylog factors in n and 1/ε; adding a short remark after the main theorem would improve readability.
- [Figure 1] Figure 1 (measurement schedule illustration) would benefit from an explicit legend indicating how the random Pauli choices per qubit are encoded in the circuit diagram.
Simulated Author's Rebuttal
We thank the referee for the positive assessment and constructive comment. We address the major comment below.
read point-by-point responses
-
Referee: [Section 4 (Recovery Procedure)] The linear-time claim for the recovery step (dominant-eigenvector extraction via matrix-vector multiplication on the empirical frequencies) is load-bearing for the overall Õ(2^n/ε) runtime. The manuscript should explicitly state the data structure used to represent the estimated density matrix and confirm that each matrix-vector product indeed costs O(2^n) arithmetic operations rather than O(2^{2n}).
Authors: We agree that an explicit description of the data structure improves clarity. In the revised manuscript we will add a paragraph to Section 4 stating that the estimated density matrix is never materialized as a dense 2^n × 2^n array. Instead it is represented implicitly through the 2^n-dimensional empirical frequency vector together with the (known) random Pauli-basis choices for each copy. Each matrix-vector product is performed by a single pass over the frequency vector: for every outcome index we apply the corresponding tensor-product Pauli operator (a product of single-qubit ±1 or ±i factors) to the input vector entry, accumulate the weighted contribution, and repeat. Because the Pauli factors are local, the work per entry is O(1) and the total cost per multiplication is therefore O(2^n). The dominant eigenvector is then obtained by a constant number of such multiplications (power iteration or Lanczos), preserving the overall Õ(2^n/ε) runtime. revision: yes
Circularity Check
No significant circularity; algorithmic construction is self-contained
full rationale
The paper constructs a new non-adaptive algorithm: random Pauli basis selection per qubit per copy, empirical frequency collection into a 2^n-dimensional vector, and linear-time recovery by thresholding plus phasing the dominant eigenvector of the estimated density matrix. The main theorem bounds deviation via standard vector-valued concentration inequalities and shows post-processing stays within the Õ(2^n/ε) time bound. No equation reduces to a fitted parameter renamed as prediction, no self-citation is load-bearing for the central claim, and no ansatz or uniqueness result is smuggled in. The derivation relies on explicit probabilistic analysis independent of the target result, so the claimed near-optimal runtime follows directly from the stated construction and standard tools.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.