Introduction
Quantum state tomography (QST) aims to obtain a classical description of an unknown quantum state. A major focus of QST research has been to minimize the number of copies required for accurate reconstruction. For an n n n -qubit pure state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ in dimension d = 2 n d = 2^n d = 2 n , the optimal sample complexity is Θ ( d / ϵ ) \Theta(d/\epsilon) Θ ( d / ϵ ) for infidelity 1 − ∣ ⟨ ψ ^ ∣ ψ ⟩ ∣ 2 ≤ ϵ 1 - |\langle\hat{\psi}|\psi\rangle|^2 \le\epsilon 1 − ∣ ⟨ ψ ^ ∣ ψ ⟩ ∣ 2 ≤ ϵ and constant failure probability. This scaling can already be achieved using independent single-copy measurements [16 , 29 SSW25, 17 , 14 ] .
Pure-state tomography also provides a way to learn mixed states. Recent reductions based on random purification channels [TWZ25] produce copies of the same purification of a mixed state. Learning this purification yields a classical description from which an estimate of the original mixed state can be recovered [30 ] . The collective operations across copies are confined to the purification step; the remaining reconstruction uses pure-state tomography.
Another important resource for QST is the number of distinct measurement settings. Each setting specifies a unitary circuit followed by computational-basis readout, and the same circuit can be applied repeatedly to fresh copies. Introducing a new setting can require circuit compilation and changes to the control program [11 ] . Even with optimal sample complexity and shallow circuits, using many distinct measurement settings can add substantial experimental overhead. This motivates reusing a smaller collection of measurement settings [7 ZL23, HW23, KVG+25] .
Reusing the same settings also allows measurement outcomes to be stored more compactly. A raw outcome list records every observed bit string b ∈ { 0 , 1 } n b \in\{0, 1\}^n b ∈ { 0 , 1 } n separately, along with the corresponding measurement basis U U U . Repeated measurements in each basis can instead be summarized by a histogram, with observed bit strings as keys and their occurrence counts as values. Each histogram contains at most d d d entries, and each count uses only logarithmically many bits in the number of shots. For example, the outcomes of O ( d / ϵ ) O(d/\epsilon) O ( d / ϵ ) shots in a single basis can be stored in O ~ ( d ) \widetilde{O}(d) O ( d ) memory. These histograms can be accumulated directly during the experiment without storing a raw outcome list. Working directly with this smaller input can reduce the cost of classical reconstruction as well as its memory requirements.
Learning from few measurement bases has been studied in several settings. A constant number of bases can suffice for pure-state identification and reconstruction from exact outcome distributions [4 GCℒ+15, CHIK+16, Vor13, 24 , 1 ] . Some of these works bound the reconstruction error when the outcome probabilities are known only approximately, but they do not provide explicit sample complexity bounds in terms of dimension and target infidelity. More recently, finite-sample protocols using randomly chosen bases have reduced the dimension dependence of the number of measurement settings, but this number still grows polynomially with inverse accuracy [2 , 8 ] .
Here, we aim to improve this accuracy dependence by taking more shots per measurement basis, while keeping both the total number of samples and the classical runtime small. Our analysis uses shadow estimators [18 ] constructed from randomized measurements [EFH+23], with multiple shots taken in each sampled basis. For these estimators, taking more shots reduces the noise in the empirical outcome bit string frequencies. However, the estimator can still fluctuate with the random choice of bases, even if the outcome probabilities in each sampled basis are known exactly. Establishing accurate reconstruction with few settings therefore requires controlling both the finite-shot noise and these fluctuations.
On the computational side, compact histogram input does not automatically lead to efficient classical post-processing. Explicitly forming a shadow estimator as a dense d × d d \times d d × d matrix would already require d 2 d^2 d 2 entries, losing the computational benefit of the compact input. To achieve nearly linear reconstruction time, we must exploit the measurement structure to recover a length-d d d state vector directly from the histograms without forming such a matrix.
In this work, we give a sample-optimal pure-state tomography algorithm using shallow measurements, a nearly minimal number of measurement settings, and nearly linear classical post-processing time from outcome histograms. To our knowledge, this is the first algorithm to achieve these guarantees simultaneously.
Theorem 1.1 (Informal, see Theorem 7.3 ). For any n n n -qubit pure state ∣ ψ ⟩ ∈ C d |\psi\rangle\in\mathbb{C}^{d} ∣ ψ ⟩ ∈ C d , where d = 2 n d = 2^{n} d = 2 n , and any ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) , there is a tomography algorithm using nonadaptive single-copy Clifford measurements of depth O ( log n ) O(\log n) O ( log n ) that outputs a unit vector ∣ ψ ^ ⟩ |\hat{\psi}\rangle ∣ ψ ^ ⟩ satisfying 1 − ∣ ⟨ ψ ^ ∣ ψ ⟩ ∣ 2 ≤ ϵ 1 - |\langle\hat{\psi}|\psi\rangle|^{2} \le\epsilon 1 − ∣ ⟨ ψ ^ ∣ ψ ⟩ ∣ 2 ≤ ϵ with probability at least 1 − δ 1-\delta 1 − δ . Its measurement and computational resources satisfy
N = O ~ ( 1 ) , T = O ( d log ( 1 / δ ) / ϵ ) , T i m e h i s t = O ~ ( d ) , N = \widetilde{O}(1), \qquad T = O\left(d\log(1/\delta)/\epsilon\right), \qquad\mathrm{Time}_{\mathrm{hist}} = \widetilde{O}(d), N = O ( 1 ) , T = O ( d log ( 1/ δ ) / ϵ ) , Time hist = O ( d ) , where N N N is the number of sampled measurement settings, T T T is the total number of copies, and T i m e h i s t \mathrm{Time}_{\mathrm{hist}} Time hist is the classical post-processing time given per-setting outcome histograms. Here, O ~ ( ⋅ ) \widetilde{O}(\cdot) O ( ⋅ ) suppresses polylogarithmic factors in d d d , 1 / ϵ 1/\epsilon 1/ ϵ , and 1 / δ 1/\delta 1/ δ .
Related Work
Tomography from few measurement bases. Compressed-sensing approaches exploit the low-rank structure of density matrices to reconstruct quantum states from an incomplete set of observable expectation values [15 , 25 , 11 , 22 ] . For Pauli observables, O ~ ( r d ) \widetilde{O}(rd) O ( r d ) expectation values suffice to recover a rank-r r r state [11 ] . The number of measurement bases is a related but different resource, since each basis gives access to a full distribution over d d d outcomes. A complementary line of work focused directly on the number of measurement bases, showing that a constant number suffices to distinguish pure states [4 , 12 , 3 Vor13, 24 , 1 ] . These works do not, however, derive explicit bounds on the number of copies required as a function of d d d and the target infidelity ϵ \epsilon ϵ .
The Hamiltonian-updates approach of [2 ] reduces both the number of measurement settings and classical computational costs, with rigorous finite-sample guarantees. For pure-state infidelity, the bounds summarized in Table 1 require O ~ ( 1 / ϵ ) \widetilde{O}(1/\epsilon) O ( 1/ ϵ ) settings and O ~ ( d / ϵ 2 ) \widetilde{O}(d/\epsilon^{2}) O ( d / ϵ 2 ) samples. The number of settings thus depends only polylogarithmically on dimension, but the required number of samples has suboptimal dependence on ϵ \epsilon ϵ , and the classical runtime bound is superlinear in d d d . Their analyzed global Clifford and unitary 4-design implementations also do not establish an O ( log n ) O(\log n) O ( log n ) measurement-depth bound.
Table 1. Resource upper bounds for n n n -qubit pure-state tomography with infidelity ϵ \epsilon ϵ and failure probability at most δ \delta δ , where d = 2 n d = 2^{n} d = 2 n . Here O ~ \widetilde{O} O suppresses polylogarithmic factors in d d d , 1 / ϵ 1/\epsilon 1/ ϵ , and 1 / δ 1/\delta 1/ δ . Settings denote upper bounds on the number of distinct measurement bases. The classical runtime marked with an asterisk (*) assumes per-basis outcome histograms as input.
More recently, [8 ] obtained few-setting tomography using Clifford measurements of depth O ( log n ) O(\log n) O ( log n ) . Their pure-state specialization uses O ~ ( d / ϵ ) \widetilde{O}(d/\epsilon) O ( d / ϵ ) samples and O ~ ( 1 / ϵ ) \widetilde{O}(1/\epsilon) O ( 1/ ϵ ) settings. The sample complexity is nearly optimal, but the number of settings still depends polynomially on inverse accuracy, and a nearly linear runtime guarantee for the full reconstruction is not established. Our algorithm reduces the accuracy dependence of the number of settings to logarithmic while achieving optimal sample complexity and nearly linear reconstruction time from histograms.
Sample-optimal pure-state tomography. Independent single-copy measurements suffice for sample-optimal pure-state tomography [17 , 30 , 14 ] . They average estimators of the form ( d + 1 ) U ∣ b ⟩ ⟨ b ∣ U − I (d+1)U\lvert b\rangle\langle b\rvert U-I ( d + 1 ) U ∣ b ⟩ ⟨ b ∣ U − I and recover a pure-state estimate from a top eigenvector of the resulting matrix. [17 ] transfer high matrix-moment bounds from Haar-random measurements to efficiently implementable approximate designs and apply Markov’s inequality. This gives O ( d / ϵ ) O(d/\epsilon) O ( d / ϵ ) copy complexity with failure probability at most d − 100 d^{-100} d − 100 . [30 ] bound the moments of scalar quadratic forms and combine Bernstein’s inequality with a covering-net argument. Their analysis achieves O ( ( d + log ( 1 / δ ) ) / ϵ ) O((d+\log(1/\delta))/\epsilon) O (( d + log ( 1/ δ )) / ϵ ) copies, separating the confidence overhead from the dimension dependence. Both protocols independently sample a fresh measurement basis per copy, so their upper bounds on the number of sampled measurement bases have a linear dependence on d d d . For each measurement, [17 ] use poly ( n ) \operatorname{poly}(n) poly ( n ) gates, whereas [30 ] use poly ( d ) \operatorname{poly}(d) poly ( d ) gates. Neither construction establishes an O ( log n ) O(\log n) O ( log n ) measurement-depth bound. In classical post-processing, both reconstruct the state from a top eigenvector of a d × d d \times d d × d empirical matrix, with poly ( d ) \operatorname{poly}(d) poly ( d ) -time guarantees but no nearly linear reconstruction bound O ~ ( d ) \widetilde{O}(d) O ( d ) .
Nearly time-optimal pure-state tomography. [13 ] gave an algorithm using nonadaptive Pauli measurements with sample complexity O ~ ( d / ϵ ) \widetilde{O}(d/\epsilon) O ( d / ϵ ) . With a raw list of measurement outcomes as input, their algorithm runs in time O ~ ( d / ϵ ) \widetilde{O}(d/\epsilon) O ( d / ϵ ) nearly linear in the list length. At each level of their reconstruction tree, they use Frobenius distance estimation to determine the coefficients for combining the child estimates. Their distance estimator balances the number of sampled Pauli observables against the repetitions per observable across multiple scales to achieve nearly optimal sample complexity. [19 ] extended this line of work to recovering the leading eigenvector of a mixed state using nonadaptive Pauli measurements, achieving sample complexity and runtime nearly linear in d d d for fixed accuracy and spectral gap. However, for pure-state tomography, both works give an upper bound of O ~ ( d / ϵ ) \widetilde{O}(d/\epsilon) O ( d / ϵ ) on the number of distinct measurement bases. Using shallow Clifford measurements, our algorithm requires only O ~ ( 1 ) \widetilde{O}(1) O ( 1 ) measurement settings while achieving the optimal O ( d / ϵ ) O(d/\epsilon) O ( d / ϵ ) sample complexity.
Multi-shot shadow estimation and common randomized measurements. Multi-shot shadow estimation reuses each randomized measurement circuit for multiple shots and analyzes the resulting correlations and variance [HW23, ZL23]. Repeated shots suppress sampling noise, but fluctuations due to the random choice of measurement basis remain. Common randomized measurements (CRM) [VRS+24] reduce these fluctuations by comparing experimental measurements with predictions from a reference state represented, for example, as a matrix product state (MPS) or a full classical description. Using the same random bases correlates the measured and predicted contributions, reducing variance when the reference is sufficiently close to the target state. [VRS+24] bound the variance of estimators for linear and multcopy observables in terms of the reference accuracy, and numerically demonstrate variance reduction when a reference state close to ρ \rho ρ is available. in advance. In contrast, our algorithm progressively improves an estimate of an arbitrary unknown pure state through successive stages, using only tomography data and requiring no prior classical approximation of the target state.
Small measurement ensembles for classical shadows. Previous studies construct small collections of measurement bases for classical shadow estimation [ZLZ24, YCZ26, WC24]. Our focus is how many bases are sampled and used in an experiment to achieve a target accuracy while maintaining optimal sample complexity. A small measurement collection alone does not guarantee this finite-sample efficiency. Conversely, our protocol samples and reuses only a few bases from a much larger Clifford ensemble, without requiring the ensemble itself to be small.
Technical Overview
We first explain how shadow bootstrapping halves the target infidelity at each stage using a constant number of new measurement settings. This refinement requires an initial estimate with constant overlap with the target state. We then show how to obtain such an estimate using only O ( d ) O(d) O ( d ) copies and few shallow measurement settings, so that initialization preserves the optimal dependence on d d d in the total sample complexity. Finally, we explain how both procedures can be implemented efficiently from outcome histograms.
Shadow Bootstrapping
The shadow channel M \mathcal{M} M maps a state ρ \rho ρ to the mean of the projectors U † ∣ b ⟩ ⟨ b ∣ U U^{\dagger}|b\rangle\langle b|U U † ∣ b ⟩ ⟨ b ∣ U obtained from randomized measurements [18 ] . Applying its inverse to each projector gives an unbiased shadow estimator of ρ \rho ρ [Eq. (3)]. Using these estimators, shadow bootstrapping refines an initial estimate with constant overlap with the target state through successive corrections. We partition the measurement data into independent batches, indexed by t = 1 , … , J t = 1, \ldots, J t = 1 , … , J . At stage t t t , we use the estimate ∣ σ t − 1 ⟩ |\sigma_{t-1}\rangle ∣ σ t − 1 ⟩ from the previous stage as a reference to construct ∣ σ t ⟩ |\sigma_t\rangle ∣ σ t ⟩ . The purpose of this reference is to reduce fluctuations due to the random choice of measurement bases, which cannot be removed merely by taking more shots per basis.
The key idea can be understood by analogy with classical variance reduction. Suppose we want to estimate E [ X ] \mathbb{E}[X] E [ X ] and have a prediction Y Y Y whose mean is known. Define Z : = X − Y + E [ Y ] Z := X - Y + \mathbb{E}[Y] Z := X − Y + E [ Y ] . Then E [ Z ] = E [ X ] \mathbb{E}[Z] = \mathbb{E}[X] E [ Z ] = E [ X ] and
Var ( Z ) = Var ( X − Y ) ≤ E [ ( X − Y ) 2 ] . \operatorname{Var}(Z) = \operatorname{Var}(X-Y) \le\mathbb{E}[(X-Y)^2]. Var ( Z ) = Var ( X − Y ) ≤ E [( X − Y ) 2 ] .
Thus, when Y Y Y closely predicts X X X on the same random input, Z Z Z estimates the same expectation E [ X ] \mathbb{E}[X] E [ X ] with small variance.
In our setting, ∣ σ t − 1 ⟩ |\sigma_{t-1}\rangle ∣ σ t − 1 ⟩ predicts the outcome probabilities ∣ ⟨ z ∣ U ∣ σ t − 1 ⟩ ∣ 2 |\langle z|U|\sigma_{t-1}\rangle|^2 ∣ ⟨ z ∣ U ∣ σ t − 1 ⟩ ∣ 2 in each measurement basis U U U . We subtract these predictions from the outcome frequencies observed in the experiment and use the differences to estimate the correction ψ − σ t − 1 \psi-\sigma_{t-1} ψ − σ t − 1 . Adding back σ t − 1 \sigma_{t-1} σ t − 1 gives an unbiased estimator of ψ \psi ψ . Because the observed and predicted contributions use the same basis, their difference becomes less sensitive to the random choice of measurement basis as σ t − 1 \sigma_{t-1} σ t − 1 approaches ψ \psi ψ .
Let N t N_t N t denote the number of independently sampled measurement bases at stage t t t , and S t S_t S t the number of shots per basis. Our analysis gives
E [ 1 − ∣ ⟨ ψ ∣ σ t ⟩ ∣ 2 ] ≤ C N t ( E [ 1 − ∣ ⟨ ψ ∣ σ t − 1 ⟩ ∣ 2 ] + d S t ) \mathbb{E}[1-|\langle\psi|\sigma_t\rangle|^2] \le\frac{C}{N_t}\left(\mathbb{E}[1-|\langle\psi|\sigma_{t-1}\rangle|^2]+\frac{d}{S_t}\right) E [ 1 − ∣ ⟨ ψ ∣ σ t ⟩ ∣ 2 ] ≤ N t C ( E [ 1 − ∣ ⟨ ψ ∣ σ t − 1 ⟩ ∣ 2 ] + S t d )
for a universal constant C C C . Without iterative refinement, we would take S = Θ ( d ) S = \Theta(d) S = Θ ( d ) shots per basis and N = Θ ( 1 / ϵ ) N = \Theta(1/\epsilon) N = Θ ( 1/ ϵ ) measurement bases to achieve the target accuracy ϵ \epsilon ϵ . By updating the reference after each stage, we can instead choose N t = Θ ( 1 ) N_t = \Theta(1) N t = Θ ( 1 ) and S t = Θ ( d 2 t ) S_t = \Theta(d\,2^t) S t = Θ ( d 2 t ) , with constants chosen so that the upper bound on expected infidelity is halved at each stage. After O ( log ( 1 / ϵ ) ) O(\log(1/\epsilon)) O ( log ( 1/ ϵ )) stages, the estimate therefore achieves infidelity at most ϵ \epsilon ϵ with constant failure probability. All measurement bases and shot counts are fixed in advance; only the reference used in classical post-processing changes between stages.
Beyond pure states, we extend shadow bootstrapping to low-rank tomography with nonadaptive single-copy measurements, achieving nearly optimal bounds on both the number of measurement settings and the sample complexity (Appendix § 11 ). We expect the same variance-reduction strategy to apply more broadly to channel learning and observable estimation.
Initialization
The refinement procedure requires an initial pure-state estimate ∣ σ 0 ⟩ |\sigma_0\rangle ∣ σ 0 ⟩ with constant overlap with the unknown state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ . Initialization therefore need not achieve optimal dependence on accuracy. It must still use few shallow measurement settings and admit efficient processing of outcome histograms.
We use the recursive reconstruction framework of [13 ] . At level ℓ \ell ℓ , each prefix x ∈ { 0 , 1 } ℓ x \in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ labels the normalized state ∣ ψ x ⟩ |\psi_x\rangle ∣ ψ x ⟩ of the remaining n − ℓ n-\ell n − ℓ qubits after measuring the first ℓ \ell ℓ qubits in the computational basis and obtaining outcome x x x . Reconstruction proceeds from level ℓ = n − 1 \ell=n-1 ℓ = n − 1 to the root at ℓ = 0 \ell=0 ℓ = 0 . Given normalized child estimates ∣ ψ ^ x 0 ⟩ |\widehat{\psi}_{x0}\rangle ∣ ψ x 0 ⟩ and ∣ ψ ^ x 1 ⟩ |\widehat{\psi}_{x1}\rangle ∣ ψ x 1 ⟩ , we seek coefficients α ^ 0 , α ^ 1 \widehat{\alpha}_0,\widehat{\alpha}_1 α 0 , α 1 satisfying ∣ α ^ 0 ∣ 2 + ∣ α ^ 1 ∣ 2 = 1 |\widehat{\alpha}_0|^2+|\widehat{\alpha}_1|^2=1 ∣ α 0 ∣ 2 + ∣ α 1 ∣ 2 = 1 such that
∣ ψ ^ x ⟩ = α ^ 0 ∣ 0 ⟩ ⊗ ∣ ψ ^ x 0 ⟩ + α ^ 1 ∣ 1 ⟩ ⊗ ∣ ψ ^ x 1 ⟩ |\widehat{\psi}_x\rangle=\widehat{\alpha}_0|0\rangle\otimes|\widehat{\psi}_{x0}\rangle+\widehat{\alpha}_1|1\rangle\otimes|\widehat{\psi}_{x1}\rangle ∣ ψ x ⟩ = α 0 ∣0 ⟩ ⊗ ∣ ψ x 0 ⟩ + α 1 ∣1 ⟩ ⊗ ∣ ψ x 1 ⟩
approximates ∣ ψ x ⟩ |\psi_x\rangle ∣ ψ x ⟩ . [13 ] recover these coefficients through nested noisy searches using a Frobenius-distance oracle. Their construction achieves nearly optimal sample complexity and running time with nonadaptive Pauli measurements, using up to O ~ ( d / ϵ ) \widetilde{O}(d/\epsilon) O ( d / ϵ ) sampled measurement bases. In contrast, we recover the coefficients from linear shadow averages, allowing a small collection of shallow Clifford bases to be reused across all nodes x ∈ { 0 , 1 } ℓ x \in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ at each level ℓ \ell ℓ .
To describe this recovery, write the projection coefficients onto the two estimated child vectors as
α ~ b : = ⟨ b ∣ ⊗ ⟨ ψ ^ x b ∣ ψ x ⟩ , b ∈ { 0 , 1 } . \widetilde{\alpha}_b:=\langle b|\otimes\langle\widehat{\psi}_{xb}|\psi_x\rangle,\qquad b\in\{0,1\}. α b := ⟨ b ∣ ⊗ ⟨ ψ x b ∣ ψ x ⟩ , b ∈ { 0 , 1 } .
Whenever this projection is nonzero, the normalized pair ( α ~ 0 , α ~ 1 ) ∣ α ~ 0 ∣ 2 + ∣ α ~ 1 ∣ 2 \frac{(\widetilde{\alpha}_0,\widetilde{\alpha}_1)}{\sqrt{|\widetilde{\alpha}_0|^2+|\widetilde{\alpha}_1|^2}} ∣ α 0 ∣ 2 + ∣ α 1 ∣ 2 ( α 0 , α 1 ) yields the state with minimum infidelity to ∣ ψ x ⟩ |\psi_x\rangle ∣ ψ x ⟩ within the span of the two estimated child vectors. For fixed child estimates, this pair is therefore the optimal target for ( α ^ 0 , α ^ 1 ) (\widehat{\alpha}_0,\widehat{\alpha}_1) ( α 0 , α 1 ) . These estimated coefficients are obtained, up to a common phase, from estimates of the following coefficient products:
( ∣ α ~ 0 ∣ 2 α ~ 0 α ~ 1 ∗ α ~ 0 ∗ α ~ 1 ∣ α ~ 1 ∣ 2 ) . \begin{pmatrix}
|\widetilde{\alpha}_0|^2 & \widetilde{\alpha}_0\widetilde{\alpha}_1^* \\
\widetilde{\alpha}_0^*\widetilde{\alpha}_1 & |\widetilde{\alpha}_1|^2
\end{pmatrix}. ( ∣ α 0 ∣ 2 α 0 ∗ α 1 α 0 α 1 ∗ ∣ α 1 ∣ 2 ) .
Each entry can be expressed as an expectation value Tr ( O ψ x ) \operatorname{Tr}(O\psi_x) Tr ( O ψ x ) , where ψ x = ∣ ψ x ⟩ ⟨ ψ x ∣ \psi_x=|\psi_x\rangle\langle\psi_x| ψ x = ∣ ψ x ⟩ ⟨ ψ x ∣ and O O O is determined by the estimated child states. Writing p x p_x p x for the probability of observing prefix x x x , we estimate p x p_x p x times each entry directly from the joint measurement outcomes. A normalized top eigenvector of the resulting 2 × 2 2\times2 2 × 2 Hermitian matrix gives the coefficient estimates α ^ 0 , α ^ 1 \widehat{\alpha}_0,\widehat{\alpha}_1 α 0 , α 1 .
At level ℓ \ell ℓ , let N ℓ N_\ell N ℓ denote the number of independently sampled measurement bases and S ℓ S_\ell S ℓ the number of shots per basis. Increasing S ℓ S_\ell S ℓ reduces shot noise, but leaves uncertainty from the random choice of bases. Our analysis bounds the contribution of this uncertainty to the expected reconstruction error at each node x x x by O ( p x / N ℓ ) O(p_x/\sqrt{N_\ell}) O ( p x / N ℓ ) . Since ∑ x ∈ { 0 , 1 } ℓ p x = 1 \sum_{x\in\{0,1\}^{\ell}}p_x=1 ∑ x ∈ { 0 , 1 } ℓ p x = 1 , summing over all nodes at level ℓ \ell ℓ gives an error contribution of O ( 1 / N ℓ ) O(1/\sqrt{N_\ell}) O ( 1/ N ℓ ) , independently of the number of nodes.
For a fixed constant target infidelity ϵ \epsilon ϵ in initialization, we allocate an O ( ϵ / n ) O(\epsilon/n) O ( ϵ / n ) error budget to the contribution from random basis selection at each level ℓ = 0 , … , n − 1 \ell=0,\ldots,n-1 ℓ = 0 , … , n − 1 . The bound above therefore leads to the choice N ℓ = Θ ( n 2 / ϵ 2 ) = Θ ( n 2 ) N_\ell=\Theta(n^2/\epsilon^2)=\Theta(n^2) N ℓ = Θ ( n 2 / ϵ 2 ) = Θ ( n 2 ) . We choose S ℓ S_\ell S ℓ sufficiently large at each level so that the total shot-noise contribution is O ( ϵ ) O(\epsilon) O ( ϵ ) , while keeping the total number of copies ∑ ℓ = 0 n − 1 N ℓ S ℓ = O ( d ) \sum_{\ell=0}^{n-1}N_\ell S_\ell=O(d) ∑ ℓ = 0 n − 1 N ℓ S ℓ = O ( d ) . Summing both contributions over the n n n levels gives an accumulated expected infidelity of O ( ϵ ) O(\epsilon) O ( ϵ ) . The total number of sampled measurement bases is ∑ ℓ = 0 n − 1 N ℓ = O ( n 3 ) \sum_{\ell=0}^{n-1}N_\ell=O(n^3) ∑ ℓ = 0 n − 1 N ℓ = O ( n 3 ) , and the resulting outcome histograms can be processed in O ~ ( d ) \widetilde{O}(d) O ( d ) classical time.
Post-processing from Histograms
Given the outcome histograms, the computational task is to apply shadow estimators to state vectors without forming dense matrices. Our implementation uses two properties of the measurement ensemble. First, the shallow circuit for each sampled basis U U U allows both U ∣ v ⟩ U|v\rangle U ∣ v ⟩ and U † ∣ v ⟩ U^\dagger|v\rangle U † ∣ v ⟩ to be computed in O ~ ( d ) \widetilde{O}(d) O ( d ) time. Second, the Clifford structure allows the contribution of histogram weights h h h to be written as
M − 1 ( U † diag ( h ) U ) = U † diag ( λ ) U . \mathcal{M}^{-1}\left(U^\dagger\operatorname{diag}(h)U\right)=U^\dagger\operatorname{diag}(\lambda)U. M − 1 ( U † diag ( h ) U ) = U † diag ( λ ) U .
For our ensemble, the vector λ \lambda λ can be computed in O ~ ( d ) \widetilde{O}(d) O ( d ) time using fast Walsh–Hadamard transforms. Thus, each histogram can be processed using only O ~ ( d ) \widetilde{O}(d) O ( d ) time and working memory, without constructing a dense d × d d\times d d × d estimator.
Preliminaries
Notation and Quantum-State Distances
Throughout, we write d = 2 n d=2^n d = 2 n and identify computational-basis outcomes with bit strings b ∈ { 0 , 1 } n b\in\{0,1\}^n b ∈ { 0 , 1 } n . The unknown pure state is denoted by ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ , and ψ = ∣ ψ ⟩ ⟨ ψ ∣ \psi=|\psi\rangle\langle\psi| ψ = ∣ ψ ⟩ ⟨ ψ ∣ denotes its density matrix. Similarly, we write σ = ∣ σ ⟩ ⟨ σ ∣ \sigma=|\sigma\rangle\langle\sigma| σ = ∣ σ ⟩ ⟨ σ ∣ for a pure-state estimate. We write H d : = C d \mathcal{H}^d:=\mathbb{C}^d H d := C d for the d d d -dimensional complex Hilbert space and L ( H d ) \mathcal{L}(\mathcal{H}^d) L ( H d ) for the space of linear operators on H d \mathcal{H}^d H d . The Hadamard (H H H ), phase (S S S ), and controlled-NOT (C X \mathrm{CX} CX ) gates are defined by
H : = 1 2 ( 1 1 1 − 1 ) , S : = ( 1 0 0 i ) , C X : = ( 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 ) . H:=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad S:=\begin{pmatrix}1&0\\0&i\end{pmatrix},\qquad\mathrm{CX}:=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\end{pmatrix}. H := 2 1 ( 1 1 1 − 1 ) , S := ( 1 0 0 i ) , CX := 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 .
For vectors, ∥ ⋅ ∥ 2 \|\cdot\|_2 ∥ ⋅ ∥ 2 denotes the Euclidean norm. For matrices, ∥ ⋅ ∥ o p \|\cdot\|_{\mathrm{op}} ∥ ⋅ ∥ op , ∥ ⋅ ∥ F \|\cdot\|_{\mathrm{F}} ∥ ⋅ ∥ F , and ∥ ⋅ ∥ t r \|\cdot\|_{\mathrm{tr}} ∥ ⋅ ∥ tr denote the operator, Frobenius, and trace norms, respectively. For Hermitian matrices A A A and B B B , we write A ⪯ B A\preceq B A ⪯ B when B − A B-A B − A is positive semidefinite.
We measure reconstruction error by the infidelity
1 − Tr ( ψ σ ) = 1 − ∣ ⟨ ψ ∣ σ ⟩ ∣ 2 . 1-\operatorname{Tr}(\psi\sigma)=1-|\langle\psi|\sigma\rangle|^2. 1 − Tr ( ψ σ ) = 1 − ∣ ⟨ ψ ∣ σ ⟩ ∣ 2 .
For pure states, this is related to the Frobenius and trace distances by
1 − Tr ( ψ σ ) = 1 2 ∥ ψ − σ ∥ F 2 = 1 4 ∥ ψ − σ ∥ t r 2 . (1) 1-\operatorname{Tr}(\psi\sigma)=\frac{1}{2}\|\psi-\sigma\|_{\mathrm{F}}^2=\frac{1}{4}\|\psi-\sigma\|_{\mathrm{tr}}^2. \tag*{(1)} 1 − Tr ( ψ σ ) = 2 1 ∥ ψ − σ ∥ F 2 = 4 1 ∥ ψ − σ ∥ tr 2 . (1)
In particular, the trace distance D ( ψ , σ ) = 1 2 ∥ ψ − σ ∥ t r D(\psi,\sigma)=\frac{1}{2}\|\psi-\sigma\|_{\mathrm{tr}} D ( ψ , σ ) = 2 1 ∥ ψ − σ ∥ tr satisfies the triangle inequality.
Two-layer Clifford circuit
We use the following two-layer Clifford ensemble for our measurements.
Definition 3.1 (Two-layer Clifford ensemble [31 LL26] ). Let k k k be an even divisor of n n n . The ensemble E 2 L \mathcal{E}_{2\mathrm{L}} E 2 L consists of circuits U = U 2 U 1 U = U_2U_1 U = U 2 U 1 with two staggered layers. Each layer is a tensor product of Clifford unitaries acting on non-overlapping contiguous k k k -qubit blocks, with periodic boundary conditions. The second-layer partition is shifted by k / 2 k/2 k /2 qubits relative to the first. All block unitaries are sampled independently and uniformly from C l ( k ) \mathrm{Cl}(k) Cl ( k ) . The staggered block structure is illustrated in Figure 1 .
Figure 1. Two-layer Clifford circuit.
Classical Shadows
Definition 3.2 (Shadow channel [18 ] ). Let E \mathcal{E} E be an ensemble of n n n -qubit unitaries. A randomized measurement samples U ∼ E U \sim\mathcal{E} U ∼ E , applies U U U to a copy of ρ \rho ρ , and measures in the computational basis. The resulting bit string b ∈ { 0 , 1 } n b \in\{0,1\}^{n} b ∈ { 0 , 1 } n occurs with probability Pr ( b ∣ U ) = Tr ( ρ U † ∣ b ⟩ ⟨ b ∣ U ) \Pr(b \mid U) = \operatorname{Tr}(\rho U^\dagger\lvert b\rangle\langle b\rvert U) Pr ( b ∣ U ) = Tr ( ρ U † ∣ b ⟩ ⟨ b ∣ U ) , and the pair ( U , b ) (U,b) ( U , b ) forms a measurement record. The shadow channel associated with E \mathcal{E} E is
M E ( ρ ) : = E U ∼ E ∑ b U † ∣ b ⟩ ⟨ b ∣ U Tr ( ρ U † ∣ b ⟩ ⟨ b ∣ U ) . (2) \mathcal{M}_{\mathcal{E}}(\rho) := \mathbb{E}_{U\sim\mathcal{E}} \sum_b U^\dagger\lvert b\rangle\langle b\rvert U \operatorname{Tr}(\rho U^\dagger\lvert b\rangle\langle b\rvert U). \tag*{(2)} M E ( ρ ) := E U ∼ E b ∑ U † ∣ b ⟩ ⟨ b ∣ U Tr ( ρ U † ∣ b ⟩ ⟨ b ∣ U ) . (2) If M E \mathcal{M}_{\mathcal{E}} M E is invertible, each record ( U , b ) (U,b) ( U , b ) gives the shadow estimator
ρ ^ = M E − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) . (3) \hat{\rho} = \mathcal{M}_{\mathcal{E}}^{-1}\left(U^\dagger\lvert b\rangle\langle b\rvert U\right). \tag*{(3)} ρ ^ = M E − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) . (3) By construction, E U , b [ ρ ^ ] = ρ \mathbb{E}_{U,b}[\hat{\rho}] = \rho E U , b [ ρ ^ ] = ρ . Consequently, for any Hermitian observable O O O , Tr ( O ρ ^ ) \operatorname{Tr}(O\hat{\rho}) Tr ( O ρ ^ ) is an unbiased estimator of Tr ( O ρ ) \operatorname{Tr}(O\rho) Tr ( O ρ ) . We omit the subscript E \mathcal{E} E when the ensemble is clear from context.
We use P ∈ { I , X , Y , Z } ⊗ n P \in\{I,X,Y,Z\}^{\otimes n} P ∈ { I , X , Y , Z } ⊗ n to denote a Pauli operator. A Clifford unitary maps Pauli operators to Pauli operators up to a sign under conjugation. For a Clifford measurement ensemble, the shadow channel is diagonal in the Pauli basis [6 ] :
M E ( P ) = m P P , m P = Pr U ∼ E [ U P U † ∈ ± { I , Z } ⊗ n ] . (4) \mathcal{M}_{\mathcal{E}}(P) = m_P P,\qquad m_P = \Pr_{U\sim\mathcal{E}}\left[UPU^\dagger\in\pm\{I,Z\}^{\otimes n}\right]. \tag*{(4)} M E ( P ) = m P P , m P = U ∼ E Pr [ U P U † ∈ ± { I , Z } ⊗ n ] . (4)
We call m P m_P m P the visibility of P P P . The shadow channel M E \mathcal{M}_{\mathcal{E}} M E is invertible when m P > 0 m_P > 0 m P > 0 for every Pauli operator, in which case
M E − 1 ( P ) = m P − 1 P . (5) \mathcal{M}_{\mathcal{E}}^{-1}(P) = m_P^{-1}P. \tag*{(5)} M E − 1 ( P ) = m P − 1 P . (5)
Lemma 3.3 ([5 Appendix G] ). Consider the two-layer Clifford ensemble with block size k k k in Definition 3.1, and define
K 0 : = 1 2 k + 1 ( 2 k + 1 1 0 0 ) , K 1 : = 1 ( 2 k + 1 ) 2 ( 1 1 2 k + 1 2 k ) . K_0 := \frac{1}{2^k+1}\begin{pmatrix}2^k+1 & 1\\0 & 0\end{pmatrix},\qquad K_1 := \frac{1}{(2^k+1)^2}\begin{pmatrix}1 & 1\\2^{k+1} & 2^k\end{pmatrix}. K 0 := 2 k + 1 1 ( 2 k + 1 0 1 0 ) , K 1 := ( 2 k + 1 ) 2 1 ( 1 2 k + 1 1 2 k ) .
@references For a Pauli operator P P P , let w i ( P ) = 0 w_i(P)=0 w i ( P ) = 0 if P P P acts as the identity on the i i i th block of the first layer, and let w i ( P ) = 1 w_i(P)=1 w i ( P ) = 1 otherwise. Then
m P = Tr ( K w 1 ( P ) K w 2 ( P ) ⋯ K w n / k ( P ) ) . m_P=\operatorname{Tr}\left(K_{w_1(P)}K_{w_2(P)}\cdots K_{w_{n/k}(P)}\right). m P = Tr ( K w 1 ( P ) K w 2 ( P ) ⋯ K w n / k ( P ) ) .
In particular, m P m_P m P can be evaluated in O ( n ) O(n) O ( n ) time.
Lemma 3.4 (Implicit in [18 Lemma 1] ). For any A , B ∈ C d × d A,B\in\mathbb{C}^{d\times d} A , B ∈ C d × d ,
Tr ( A M E − 1 ( B ) ) = Tr ( M E − 1 ( A ) B ) . (6) \operatorname{Tr}\left(A\mathcal{M}_{\mathcal{E}}^{-1}(B)\right)=\operatorname{Tr}\left(\mathcal{M}_{\mathcal{E}}^{-1}(A)B\right). \tag*{(6)} Tr ( A M E − 1 ( B ) ) = Tr ( M E − 1 ( A ) B ) . (6)
Lemma 3.5. Let M \mathcal{M} M be the invertible shadow channel of a Clifford ensemble E \mathcal{E} E . For every U ∈ E U\in\mathcal{E} U ∈ E and A ∈ C d × d A\in\mathbb{C}^{d\times d} A ∈ C d × d ,
∑ b Tr ( A U † ∣ b ⟩ ⟨ b ∣ U ) M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) = ∑ b Tr ( A M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) U † ∣ b ⟩ ⟨ b ∣ U . \sum_b \operatorname{Tr}\left(AU^\dagger|b\rangle\langle b|U\right)\mathcal{M}^{-1}\left(U^\dagger|b\rangle\langle b|U\right)=\sum_b \operatorname{Tr}\left(A\mathcal{M}^{-1}\left(U^\dagger|b\rangle\langle b|U\right)\right)U^\dagger|b\rangle\langle b|U. b ∑ Tr ( A U † ∣ b ⟩ ⟨ b ∣ U ) M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) = b ∑ Tr ( A M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) U † ∣ b ⟩ ⟨ b ∣ U .
Lemma 3.6 ([6 Appendix A.2] ). Let b , c b,c b , c be independent measurement outcomes of a fixed state conditional on the same basis U U U . For every Hermitian observable O O O ,
E U , b , c [ Tr ( O M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) Tr ( O M − 1 ( U † ∣ c ⟩ ⟨ c ∣ U ) ) ] ≤ E U , b [ Tr ( O M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) 2 ] . \mathbb{E}_{U,b,c}\left[\operatorname{Tr}\left(O\mathcal{M}^{-1}\left(U^\dagger|b\rangle\langle b|U\right)\right)\operatorname{Tr}\left(O\mathcal{M}^{-1}\left(U^\dagger|c\rangle\langle c|U\right)\right)\right]\leq\mathbb{E}_{U,b}\left[\operatorname{Tr}\left(O\mathcal{M}^{-1}\left(U^\dagger|b\rangle\langle b|U\right)\right)^2\right]. E U , b , c [ Tr ( O M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) Tr ( O M − 1 ( U † ∣ c ⟩ ⟨ c ∣ U ) ) ] ≤ E U , b [ Tr ( O M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) 2 ] .
Lemma 3.7 ([5 Appendix D] ). For the two-layer Clifford ensemble with block size k ≥ 2 k\geq2 k ≥ 2 satisfying k 2 k / 2 = Ω ( n ) k2^{k/2}=\Omega(n) k 2 k /2 = Ω ( n ) ,
∥ E ρ ^ ∥ o p = ∥ E M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ∥ o p = O ( d ) . (7) \left\|\mathbb{E}\hat{\rho}\right\|_{\mathrm{op}}=\left\|\mathbb{E}\mathcal{M}^{-1}\left(U^\dagger|b\rangle\langle b|U\right)\right\|_{\mathrm{op}}=O(d). \tag*{(7)} ∥ E ρ ^ ∥ op = E M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) op = O ( d ) . (7)
Lemma 3.8 ([8 Theorem 1] ). For the two-layer Clifford ensemble with block size k ≥ 8 k\geq8 k ≥ 8 satisfying k 2 k / 2 = Ω ( n ) k2^{k/2}=\Omega(n) k 2 k /2 = Ω ( n ) , any Hermitian observable O O O satisfies
Var [ Tr ( O ρ ^ ) ] ≤ C F ∥ O ∥ F 2 , C F = O ( 1 ) . (8) \operatorname{Var}[\operatorname{Tr}(O\hat{\rho})]\leq C_F\|O\|_F^2,\qquad C_F=O(1). \tag*{(8)} Var [ Tr ( O ρ ^ )] ≤ C F ∥ O ∥ F 2 , C F = O ( 1 ) . (8)
Histogram Representation
Let b 1 , … , b S ∈ { 0 , 1 } n b_1,\ldots,b_S\in\{0,1\}^n b 1 , … , b S ∈ { 0 , 1 } n be independent and identically distributed measurement outcomes. The histogram records the number of occurrences of each outcome, with empirical frequencies
f ^ z = 1 S ∑ a = 1 S 1 { b a = z } , ∑ z f ^ z = 1. \hat{f}_z=\frac{1}{S}\sum_{a=1}^{S}\mathbf{1}\{b_a=z\},\qquad\sum_z\hat{f}_z=1. f ^ z = S 1 a = 1 ∑ S 1 { b a = z } , z ∑ f ^ z = 1.
We represent the experimental data as a dictionary whose keys are the observed bit strings and whose values are their corresponding counts. Each histogram therefore contains at most 2 n 2^n 2 n entries. A lookup for a bit string absent from the dictionary returns zero. Our input consists of the measurement-circuit descriptions and these histograms.
Walsh–Hadamard Transform
For a vector x ∈ C d x\in\mathbb{C}^d x ∈ C d indexed by i ∈ { 0 , 1 } n i\in\{0,1\}^n i ∈ { 0 , 1 } n , define its Walsh–Hadamard transform WH ( x ) ∈ C d \operatorname{WH}(x)\in\mathbb{C}^d WH ( x ) ∈ C d by
WH ( x ) j : = 1 2 n ∑ i ( − 1 ) i ⋅ j x i , j ∈ { 0 , 1 } n . \operatorname{WH}(x)_j:=\frac{1}{2^n}\sum_i(-1)^{i\cdot j}x_i,\qquad j\in\{0,1\}^n. WH ( x ) j := 2 n 1 i ∑ ( − 1 ) i ⋅ j x i , j ∈ { 0 , 1 } n .
where i ⋅ j i\cdot j i ⋅ j is evaluated modulo two. Its inverse is
WH − 1 ( x ) j = ∑ i ( − 1 ) i ⋅ j x i , j ∈ { 0 , 1 } n . \operatorname{WH}^{-1}(x)_j=\sum_i(-1)^{i\cdot j}x_i,\qquad j\in\{0,1\}^n. WH − 1 ( x ) j = i ∑ ( − 1 ) i ⋅ j x i , j ∈ { 0 , 1 } n .
Both transforms can be computed using O ( d log d ) O(d\log d) O ( d log d ) arithmetic operations and O ( d ) O(d) O ( d ) storage [10 ] .
Basic Inequalities
We use the following two standard inequalities.
Lemma 3.9 (Markov’s inequality). Let X X X be a nonnegative random variable with finite expectation. For every a > 0 a>0 a > 0 ,
Pr [ X ≥ a ] ≤ E [ X ] a . \Pr[X \ge a] \le\frac{\mathbb{E}[X]}{a}. Pr [ X ≥ a ] ≤ a E [ X ] .
Lemma 3.10 (Matrix norm inequality). For any random matrix A A A ,
E ∥ A ∥ o p ≤ E ∥ A ∥ F ≤ E ∥ A ∥ F 2 . \mathbb{E}\lVert A\rVert_{\mathrm{op}} \le\mathbb{E}\lVert A\rVert_{F} \le\sqrt{\mathbb{E}\lVert A\rVert_{F}^{2}}. E ∥ A ∥ op ≤ E ∥ A ∥ F ≤ E ∥ A ∥ F 2 .
Shadow Bootstrapping
Shadow bootstrapping divides reconstruction into successive stages, using the current estimate as a reference to reduce the variance of the next update. This adaptation occurs entirely in classical post-processing: all measurement bases, shot counts, and assignments to stages are fixed before any outcomes are observed.
We assume access to an initial unit vector ∣ σ 0 ⟩ \lvert\sigma_{0}\rangle ∣ σ 0 ⟩ , satisfying
Tr ( ψ σ 0 ) = ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ≥ 1 2 . (9) \operatorname{Tr}(\psi\sigma_{0})=\lvert\langle\psi\vert\sigma_{0}\rangle\rvert^{2}\ge\frac{1}{2}. \tag*{(9)} Tr ( ψ σ 0 ) = ∣⟨ ψ ∣ σ 0 ⟩ ∣ 2 ≥ 2 1 . (9)
Any positive constant lower bound on the overlap suffices; we choose 1 / 2 1/2 1/2 for simplicity. § 5 constructs such an estimate using O ( d ) O(d) O ( d ) copies, O ~ ( 1 ) \widetilde{O}(1) O ( 1 ) measurement settings, and O ~ ( d ) \widetilde{O}(d) O ( d ) histogram post-processing time.
Residual estimator
Given an unknown state ρ \rho ρ and a reference state σ \sigma σ , we define the residual as the difference between the usual shadow estimator and its counterpart constructed from the outcome probabilities predicted by σ \sigma σ in the same measurement basis.
Definition 4.1 (Residual estimator). Let E \mathcal{E} E be a Clifford ensemble satisfying Lemma 3.8 . Fix a reference state σ \sigma σ and draw U ∼ E U\sim\mathcal{E} U ∼ E . Let f ^ ( z ) \hat{f}(z) f ^ ( z ) denote the empirical frequencies obtained from S S S independent shots { b i } i = 1 S \{b_i\}_{i=1}^{S} { b i } i = 1 S on ρ \rho ρ in basis U U U , as defined in § 3.4 . Define
Δ : = ∑ z ( f ^ ( z ) − Tr ( U σ U † ∣ z ⟩ ⟨ z ∣ ) ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) . (10) \Delta:= \sum_{z}\left(\hat{f}(z)-\operatorname{Tr}\left(U\sigma U^{\dagger}\lvert z\rangle\langle z\rvert\right)\right)\mathcal{M}^{-1}\left(U^{\dagger}\lvert z\rangle\langle z\rvert U\right). \tag*{(10)} Δ := z ∑ ( f ^ ( z ) − Tr ( U σ U † ∣ z ⟩ ⟨ z ∣ ) ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) . (10)
Adding and subtracting the true outcome probabilities separates the residual into Δ = Δ s h o t + Δ f l o o r \Delta=\Delta_{\mathrm{shot}}+\Delta_{\mathrm{floor}} Δ = Δ shot + Δ floor , where
Δ s h o t : = ∑ z ( f ^ ( z ) − Tr ( U ρ U † ∣ z ⟩ ⟨ z ∣ ) ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) , \Delta_{\mathrm{shot}} := \sum_{z}\left(\hat{f}(z)-\operatorname{Tr}\left(U\rho U^{\dagger}\lvert z\rangle\langle z\rvert\right)\right)\mathcal{M}^{-1}\left(U^{\dagger}\lvert z\rangle\langle z\rvert U\right), Δ shot := z ∑ ( f ^ ( z ) − Tr ( U ρ U † ∣ z ⟩ ⟨ z ∣ ) ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) ,
Δ f l o o r : = ∑ z Tr ( ( ρ − σ ) U † ∣ z ⟩ ⟨ z ∣ U ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) . \Delta_{\mathrm{floor}} := \sum_{z}\operatorname{Tr}\left((\rho-\sigma)U^{\dagger}\lvert z\rangle\langle z\rvert U\right)\mathcal{M}^{-1}\left(U^{\dagger}\lvert z\rangle\langle z\rvert U\right). Δ floor := z ∑ Tr ( ( ρ − σ ) U † ∣ z ⟩ ⟨ z ∣ U ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) .
The term Δ s h o t \Delta_{\mathrm{shot}} Δ shot captures finite-shot fluctuations around the true outcome probabilities. The term Δ f l o o r \Delta_{\mathrm{floor}} Δ floor fluctuates with the random choice of basis even as S → ∞ S\to\infty S → ∞ , setting a variance floor for fixed ρ \rho ρ and σ \sigma σ . Its variation over random bases depends on the discrepancy ρ − σ \rho-\sigma ρ − σ and is not suppressed by increasing S S S .
Lemma 4.2 (Residual mean and variance). For fixed states ρ \rho ρ , σ \sigma σ , the residual estimator in Definition Definition 4.1 satisfies
E [ Δ ] = ρ − σ \mathbb{E}[\Delta] = \rho- \sigma E [ Δ ] = ρ − σ and
∥ E [ Δ 2 ] − ( E [ Δ ] ) 2 ∥ o p ≤ C ( ∥ ρ − σ ∥ F 2 + d S ) , C = O ( 1 ) , \left\lVert\mathbb{E}[\Delta^2] - \left(\mathbb{E}[\Delta]\right)^2 \right\rVert_{\mathrm{op}} \le C\left(\lVert\rho-\sigma\rVert_{\mathrm{F}}^2+\frac{d}{S}\right), \qquad C=O(1), E [ Δ 2 ] − ( E [ Δ ] ) 2 op ≤ C ( ∥ ρ − σ ∥ F 2 + S d ) , C = O ( 1 ) , where S S S is the number of shots taken in the sampled measurement basis, and expectations are over the random basis and its S S S measurement outcomes.
Proof. For a fixed basis U U U , write b : = { b i } i = 1 S \mathbf{b}:=\{b_i\}_{i=1}^{S} b := { b i } i = 1 S for the measurement outcomes. Since
E b [ f ^ z ∣ U ] = Tr ( ρ U † ∣ z ⟩ ⟨ z ∣ U ) , \mathbb{E}_{\mathbf{b}}[\widehat{f}_z\mid U]=\operatorname{Tr}(\rho U^\dagger\lvert z\rangle\langle z\rvert U), E b [ f z ∣ U ] = Tr ( ρ U † ∣ z ⟩ ⟨ z ∣ U ) , E b [ Δ s h o t ∣ U ] = 0 \mathbb{E}_{\mathbf{b}}[\Delta_{\mathrm{shot}}\mid U]=0 E b [ Δ shot ∣ U ] = 0 , and hence E [ Δ s h o t ] = 0 \mathbb{E}[\Delta_{\mathrm{shot}}]=0 E [ Δ shot ] = 0 . Moreover, by linearity and the definition of the shadow channel in Eq. (2) ,
E [ Δ f l o o r ] = E U [ Δ f l o o r ] = E U [ ∑ z Tr ( ( ρ − σ ) U † ∣ z ⟩ ⟨ z ∣ U ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) ] \mathbb{E}[\Delta_{\mathrm{floor}}]=\mathbb{E}_{U}[\Delta_{\mathrm{floor}}]=\mathbb{E}_{U}\left[\sum_z\operatorname{Tr}\left((\rho-\sigma)U^\dagger\lvert z\rangle\langle z\rvert U\right)\mathcal{M}^{-1}\left(U^\dagger\lvert z\rangle\langle z\rvert U\right)\right] E [ Δ floor ] = E U [ Δ floor ] = E U [ z ∑ Tr ( ( ρ − σ ) U † ∣ z ⟩ ⟨ z ∣ U ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) ] = M − 1 ( E U [ ∑ z Tr ( ( ρ − σ ) U † ∣ z ⟩ ⟨ z ∣ U ) U † ∣ z ⟩ ⟨ z ∣ U ] ) =\mathcal{M}^{-1}\left(\mathbb{E}_{U}\left[\sum_z\operatorname{Tr}\left((\rho-\sigma)U^\dagger\lvert z\rangle\langle z\rvert U\right)U^\dagger\lvert z\rangle\langle z\rvert U\right]\right) = M − 1 ( E U [ z ∑ Tr ( ( ρ − σ ) U † ∣ z ⟩ ⟨ z ∣ U ) U † ∣ z ⟩ ⟨ z ∣ U ] ) = M − 1 M ( ρ − σ ) = ρ − σ . =\mathcal{M}^{-1}\mathcal{M}(\rho-\sigma)=\rho-\sigma. = M − 1 M ( ρ − σ ) = ρ − σ . Combining these identities gives
E [ Δ ] = E [ Δ s h o t ] + E [ Δ f l o o r ] = ρ − σ . \mathbb{E}[\Delta]=\mathbb{E}[\Delta_{\mathrm{shot}}]+\mathbb{E}[\Delta_{\mathrm{floor}}]=\rho-\sigma. E [ Δ ] = E [ Δ shot ] + E [ Δ floor ] = ρ − σ . Since Δ f l o o r \Delta_{\mathrm{floor}} Δ floor depends only on U U U ,
E [ Δ 2 ] = E [ Δ s h o t 2 ] + E [ Δ f l o o r 2 ] + E [ Δ s h o t Δ f l o o r ] + E [ Δ f l o o r Δ s h o t ] \mathbb{E}[\Delta^2]=\mathbb{E}[\Delta_{\mathrm{shot}}^2]+\mathbb{E}[\Delta_{\mathrm{floor}}^2]+\mathbb{E}[\Delta_{\mathrm{shot}}\Delta_{\mathrm{floor}}]+\mathbb{E}[\Delta_{\mathrm{floor}}\Delta_{\mathrm{shot}}] E [ Δ 2 ] = E [ Δ shot 2 ] + E [ Δ floor 2 ] + E [ Δ shot Δ floor ] + E [ Δ floor Δ shot ] = E [ Δ s h o t 2 ] + E [ Δ f l o o r 2 ] + E U [ ( E b [ Δ s h o t ∣ U ] ) Δ f l o o r ] + E U [ Δ f l o o r ( E b [ Δ s h o t ∣ U ] ) ] =\mathbb{E}[\Delta_{\mathrm{shot}}^2]+\mathbb{E}[\Delta_{\mathrm{floor}}^2]+\mathbb{E}_{U}\left[\left(\mathbb{E}_{\mathbf{b}}[\Delta_{\mathrm{shot}}\mid U]\right)\Delta_{\mathrm{floor}}\right]+\mathbb{E}_{U}\left[\Delta_{\mathrm{floor}}\left(\mathbb{E}_{\mathbf{b}}[\Delta_{\mathrm{shot}}\mid U]\right)\right] = E [ Δ shot 2 ] + E [ Δ floor 2 ] + E U [ ( E b [ Δ shot ∣ U ] ) Δ floor ] + E U [ Δ floor ( E b [ Δ shot ∣ U ] ) ] = E [ Δ s h o t 2 ] + E [ Δ f l o o r 2 ] . =\mathbb{E}[\Delta_{\mathrm{shot}}^2]+\mathbb{E}[\Delta_{\mathrm{floor}}^2]. = E [ Δ shot 2 ] + E [ Δ floor 2 ] . Write ρ ^ U , z : = M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) \widehat{\rho}_{U,z}:=\mathcal{M}^{-1}(U^\dagger\lvert z\rangle\langle z\rvert U) ρ U , z := M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) . Since the measurement outcomes from different shots are independent conditional on U U U and E [ Δ s h o t ∣ U ] = 0 \mathbb{E}[\Delta_{\mathrm{shot}}\mid U]=0 E [ Δ shot ∣ U ] = 0 ,
E [ Δ s h o t 2 ] = Var [ Δ s h o t ] = 1 S Var U , z [ ρ ^ U , z − E b [ ρ ^ U , z ∣ U ] ] \mathbb{E}[\Delta_{\mathrm{shot}}^2]=\operatorname{Var}[\Delta_{\mathrm{shot}}]=\frac{1}{S}\operatorname{Var}_{U,z}\left[\widehat{\rho}_{U,z}-\mathbb{E}_{\mathbf{b}}[\widehat{\rho}_{U,z}\mid U]\right] E [ Δ shot 2 ] = Var [ Δ shot ] = S 1 Var U , z [ ρ U , z − E b [ ρ U , z ∣ U ] ] = 1 S ( E U , z [ ρ ^ U , z 2 ] − E U [ ( E z [ ρ ^ U , z ∣ U ] ) 2 ] ) ⪯ 1 S E U , z [ ρ ^ U , z 2 ] . =\frac{1}{S}\left(\mathbb{E}_{U,z}[\widehat{\rho}_{U,z}^2]-\mathbb{E}_{U}\left[\left(\mathbb{E}_{z}[\widehat{\rho}_{U,z}\mid U]\right)^2\right]\right)\preceq\frac{1}{S}\mathbb{E}_{U,z}[\widehat{\rho}_{U,z}^2]. = S 1 ( E U , z [ ρ U , z 2 ] − E U [ ( E z [ ρ U , z ∣ U ] ) 2 ] ) ⪯ S 1 E U , z [ ρ U , z 2 ] . By Lemma 3.7,
∥ E [ Δ s h o t 2 ] ∥ o p ≤ 1 S ∥ E U , z [ ρ ^ U , z 2 ] ∥ o p = O ( d S ) . \left\lVert\mathbb{E}[\Delta_{\mathrm{shot}}^2]\right\rVert_{\mathrm{op}}\le\frac{1}{S}\left\lVert\mathbb{E}_{U,z}[\widehat{\rho}_{U,z}^2]\right\rVert_{\mathrm{op}}=O\left(\frac{d}{S}\right). E [ Δ shot 2 ] op ≤ S 1 E U , z [ ρ U , z 2 ] op = O ( S d ) . By Lemma 3.4 and Lemma 3.5,
Δ f l o o r = ∑ z Tr ( ( ρ − σ ) U † ∣ z ⟩ ⟨ z ∣ U ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) \Delta_{\mathrm{floor}}=\sum_z\operatorname{Tr}\left((\rho-\sigma)U^\dagger\lvert z\rangle\langle z\rvert U\right)\mathcal{M}^{-1}\left(U^\dagger\lvert z\rangle\langle z\rvert U\right) Δ floor = z ∑ Tr ( ( ρ − σ ) U † ∣ z ⟩ ⟨ z ∣ U ) M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) = ∑ z Tr ( ( ρ − σ ) ρ ^ U , z ) U † ∣ z ⟩ ⟨ z ∣ U . =\sum_z\operatorname{Tr}\left((\rho-\sigma)\widehat{\rho}_{U,z}\right)U^\dagger\lvert z\rangle\langle z\rvert U. = z ∑ Tr ( ( ρ − σ ) ρ U , z ) U † ∣ z ⟩ ⟨ z ∣ U .
Orthogonality of the basis projectors gives
Δ f l o o r 2 = ∑ z Tr ( ( ρ − σ ) ρ ^ U , z ) 2 U † ∣ z ⟩ ⟨ z ∣ U . \Delta_{\mathrm{floor}}^2 = \sum_z \operatorname{Tr}\left((\rho-\sigma)\hat{\rho}_{U,z}\right)^2 U^\dagger|z\rangle\langle z| U. Δ floor 2 = z ∑ Tr ( ( ρ − σ ) ρ ^ U , z ) 2 U † ∣ z ⟩ ⟨ z ∣ U .
Since E [ Δ f l o o r ] = ρ − σ \mathbb{E}[\Delta_{\mathrm{floor}}]=\rho-\sigma E [ Δ floor ] = ρ − σ ,
∥ E [ Δ f l o o r 2 ] − ( E [ Δ f l o o r ] ) 2 ∥ o p = E U [ ∑ z Tr ( ( ρ − σ ) ρ ^ U , z ) 2 Tr ( ∣ v ⟩ ⟨ v ∣ U † ∣ z ⟩ ⟨ z ∣ U ) ] − ⟨ v ∣ ( ρ − σ ) 2 ∣ v ⟩ = E U , z [ Tr ( ( ρ − σ ) ρ ^ U , z ) 2 ] − ⟨ v ∣ ( ρ − σ ) 2 ∣ v ⟩ = E U , z [ Tr ( ( ρ − σ ) ρ ^ U , z ) 2 ] − ⟨ v ∣ ρ − σ ∣ v ⟩ 2 + ⟨ v ∣ ρ − σ ∣ v ⟩ 2 − ⟨ v ∣ ( ρ − σ ) 2 ∣ v ⟩ ≤ E U , z [ Tr ( ( ρ − σ ) ρ ^ U , z ) 2 ] − ⟨ v ∣ ρ − σ ∣ v ⟩ 2 = Var U , z [ Tr ( ( ρ − σ ) ρ ^ U , z ) ] = O ( ∥ ρ − σ ∥ F 2 ) , \begin{aligned}
\left\|\mathbb{E}\left[\Delta_{\mathrm{floor}}^2\right]-\left(\mathbb{E}\left[\Delta_{\mathrm{floor}}\right]\right)^2\right\|_{\mathrm{op}}
&=\mathbb{E}_U\left[\sum_z \operatorname{Tr}\left((\rho-\sigma)\hat{\rho}_{U,z}\right)^2\operatorname{Tr}\left(|v\rangle\langle v|U^\dagger|z\rangle\langle z|U\right)\right]-\langle v|(\rho-\sigma)^2|v\rangle\\
&=\mathbb{E}_{U,z}\left[\operatorname{Tr}\left((\rho-\sigma)\hat{\rho}_{U,z}\right)^2\right]-\langle v|(\rho-\sigma)^2|v\rangle\\
&=\mathbb{E}_{U,z}\left[\operatorname{Tr}\left((\rho-\sigma)\hat{\rho}_{U,z}\right)^2\right]-\langle v|\rho-\sigma|v\rangle^2+\langle v|\rho-\sigma|v\rangle^2-\langle v|(\rho-\sigma)^2|v\rangle\\
&\leq\mathbb{E}_{U,z}\left[\operatorname{Tr}\left((\rho-\sigma)\hat{\rho}_{U,z}\right)^2\right]-\langle v|\rho-\sigma|v\rangle^2\\
&=\operatorname{Var}_{U,z}\left[\operatorname{Tr}\left((\rho-\sigma)\hat{\rho}_{U,z}\right)\right]=O\left(\|\rho-\sigma\|_F^2\right),
\end{aligned} E [ Δ floor 2 ] − ( E [ Δ floor ] ) 2 op = E U [ z ∑ Tr ( ( ρ − σ ) ρ ^ U , z ) 2 Tr ( ∣ v ⟩ ⟨ v ∣ U † ∣ z ⟩ ⟨ z ∣ U ) ] − ⟨ v ∣ ( ρ − σ ) 2 ∣ v ⟩ = E U , z [ Tr ( ( ρ − σ ) ρ ^ U , z ) 2 ] − ⟨ v ∣ ( ρ − σ ) 2 ∣ v ⟩ = E U , z [ Tr ( ( ρ − σ ) ρ ^ U , z ) 2 ] − ⟨ v ∣ ρ − σ ∣ v ⟩ 2 + ⟨ v ∣ ρ − σ ∣ v ⟩ 2 − ⟨ v ∣ ( ρ − σ ) 2 ∣ v ⟩ ≤ E U , z [ Tr ( ( ρ − σ ) ρ ^ U , z ) 2 ] − ⟨ v ∣ ρ − σ ∣ v ⟩ 2 = Var U , z [ Tr ( ( ρ − σ ) ρ ^ U , z ) ] = O ( ∥ ρ − σ ∥ F 2 ) ,
(by Lemma 3.8 ) where ∣ v ⟩ |v\rangle ∣ v ⟩ is a normalized eigenvector of E [ Δ f l o o r 2 ] − ( E [ Δ f l o o r ] ) 2 \mathbb{E}[\Delta_{\mathrm{floor}}^2]-(\mathbb{E}[\Delta_{\mathrm{floor}}])^2 E [ Δ floor 2 ] − ( E [ Δ floor ] ) 2 with eigenvalue equal to its operator norm. Here, z z z follows the outcome distribution obtained by applying U U U to the auxiliary state ∣ v ⟩ ⟨ v ∣ |v\rangle\langle v| ∣ v ⟩ ⟨ v ∣ and measuring in the computational basis with probability p z = Tr ( U ∣ v ⟩ ⟨ v ∣ U † ∣ z ⟩ ⟨ z ∣ ) p_z=\operatorname{Tr}(U|v\rangle\langle v|U^\dagger|z\rangle\langle z|) p z = Tr ( U ∣ v ⟩ ⟨ v ∣ U † ∣ z ⟩ ⟨ z ∣ ) .
Finally, using E [ Δ ] = ρ − σ \mathbb{E}[\Delta]=\rho-\sigma E [ Δ ] = ρ − σ , we obtain
∥ E [ Δ 2 ] − ( E [ Δ ] ) 2 ∥ o p = ∥ E [ Δ s h o t 2 ] + E [ Δ f l o o r 2 ] − ( ρ − σ ) 2 ∥ o p ≤ ∥ E [ Δ s h o t 2 ] ∥ o p + ∥ E [ Δ f l o o r 2 ] − ( ρ − σ ) 2 ∥ o p ≤ C ( ∥ ρ − σ ∥ F 2 + d S ) , C = O ( 1 ) . \begin{aligned}
\left\|\mathbb{E}[\Delta^2]-(\mathbb{E}[\Delta])^2\right\|_{\mathrm{op}}
&=\left\|\mathbb{E}[\Delta_{\mathrm{shot}}^2]+\mathbb{E}[\Delta_{\mathrm{floor}}^2]-(\rho-\sigma)^2\right\|_{\mathrm{op}}\\
&\leq\left\|\mathbb{E}[\Delta_{\mathrm{shot}}^2]\right\|_{\mathrm{op}}+\left\|\mathbb{E}[\Delta_{\mathrm{floor}}^2]-(\rho-\sigma)^2\right\|_{\mathrm{op}}\\
&\leq C\left(\|\rho-\sigma\|_F^2+\frac{d}{S}\right),\qquad C=O(1).
\end{aligned} E [ Δ 2 ] − ( E [ Δ ] ) 2 op = E [ Δ shot 2 ] + E [ Δ floor 2 ] − ( ρ − σ ) 2 op ≤ E [ Δ shot 2 ] op + E [ Δ floor 2 ] − ( ρ − σ ) 2 op ≤ C ( ∥ ρ − σ ∥ F 2 + S d ) , C = O ( 1 ) .
Residual updates
Starting from an initial estimate ∣ σ 0 ⟩ |\sigma_0\rangle ∣ σ 0 ⟩ , we refine the reconstruction in successive stages. At stage t = 1 , … , J t=1,\ldots,J t = 1 , … , J , we use the previous estimate σ t − 1 = ∣ σ t − 1 ⟩ ⟨ σ t − 1 ∣ \sigma_{t-1}=|\sigma_{t-1}\rangle\langle\sigma_{t-1}| σ t − 1 = ∣ σ t − 1 ⟩ ⟨ σ t − 1 ∣ as a reference to construct an updated estimate ∣ σ t ⟩ |\sigma_t\rangle ∣ σ t ⟩ . For this update, we use N t N_t N t independently sampled bases U t , 1 , … , U t , N t U_{t,1},\ldots,U_{t,N_t} U t , 1 , … , U t , N t , each measured on S t S_t S t fresh copies, and denote their empirical frequencies by f ^ t , i ( z ) \hat{f}_{t,i}(z) f ^ t , i ( z ) . Different stages use independent bases and disjoint copies.
For the i i i th measurement basis U t , i U_{t,i} U t , i at stage t t t , let Δ t , i \Delta_{t,i} Δ t , i be the residual in Definition 4.1 , with ρ ← ψ \rho\leftarrow\psi ρ ← ψ , σ ← σ t − 1 \sigma\leftarrow\sigma_{t-1} σ ← σ t − 1 , U ← U t , i U\leftarrow U_{t,i} U ← U t , i , and S ← S t S\leftarrow S_t S ← S t . Since ψ \psi ψ and σ t − 1 \sigma_{t-1} σ t − 1 are pure, ∥ ψ − σ t − 1 ∥ F 2 = 2 [ 1 − Tr ( ψ σ t − 1 ) ] \|\psi-\sigma_{t-1}\|_F^2=2[1-\operatorname{Tr}(\psi\sigma_{t-1})] ∥ ψ − σ t − 1 ∥ F 2 = 2 [ 1 − Tr ( ψ σ t − 1 )] . Lemma 4.2 therefore gives
E [ Δ t , i ∣ σ t − 1 ] = ψ − σ t − 1 , ∥ E [ Δ t , i 2 ∣ σ t − 1 ] − ( E [ Δ t , i ∣ σ t − 1 ] ) 2 ∥ o p ≤ C ( 2 [ 1 − Tr ( ψ σ t − 1 ) ] + d S t ) . (11) \mathbb{E}[\Delta_{t,i}\mid\sigma_{t-1}]=\psi-\sigma_{t-1},\qquad
\left\|\mathbb{E}[\Delta_{t,i}^2\mid\sigma_{t-1}]-\left(\mathbb{E}[\Delta_{t,i}\mid\sigma_{t-1}]\right)^2\right\|_{\mathrm{op}}\leq C\left(2[1-\operatorname{Tr}(\psi\sigma_{t-1})]+\frac{d}{S_t}\right). \tag*{(11)} E [ Δ t , i ∣ σ t − 1 ] = ψ − σ t − 1 , E [ Δ t , i 2 ∣ σ t − 1 ] − ( E [ Δ t , i ∣ σ t − 1 ] ) 2 op ≤ C ( 2 [ 1 − Tr ( ψ σ t − 1 )] + S t d ) . (11)
Thus adding the average residual to σ t − 1 \sigma_{t-1} σ t − 1 gives an unbiased estimator of ψ \psi ψ . We apply this corrected estimator to the fixed initial vector and define
∣ σ ~ t ⟩ : = ( σ t − 1 + 1 N t ∑ i = 1 N t Δ t , i ) ∣ σ 0 ⟩ . (12) |\widetilde{\sigma}_t\rangle:=\left(\sigma_{t-1}+\frac{1}{N_t}\sum_{i=1}^{N_t}\Delta_{t,i}\right)|\sigma_0\rangle. \tag*{(12)} ∣ σ t ⟩ := ( σ t − 1 + N t 1 i = 1 ∑ N t Δ t , i ) ∣ σ 0 ⟩ . (12)
The next estimate is
∣ σ t ⟩ : = { ∣ σ ~ t ⟩ ∥ ∣ σ ~ t ⟩ ∥ 2 , ∥ ∣ σ ~ t ⟩ ∥ 2 > 0 , ∣ σ t − 1 ⟩ , ∥ ∣ σ ~ t ⟩ ∥ 2 = 0. (13) |\sigma_t\rangle:=
\begin{cases}
\dfrac{|\widetilde{\sigma}_t\rangle}{\lVert|\widetilde{\sigma}_t\rangle\rVert_2}, & \lVert|\widetilde{\sigma}_t\rangle\rVert_2 > 0, \\
|\sigma_{t-1}\rangle, & \lVert|\widetilde{\sigma}_t\rangle\rVert_2 = 0.
\end{cases} \tag*{(13)} ∣ σ t ⟩ := ⎩ ⎨ ⎧ ∥ ∣ σ t ⟩ ∥ 2 ∣ σ t ⟩ , ∣ σ t − 1 ⟩ , ∥ ∣ σ t ⟩ ∥ 2 > 0 , ∥ ∣ σ t ⟩ ∥ 2 = 0. (13)
The reference state changes between stages, while the vector ∣ σ 0 ⟩ |\sigma_0\rangle ∣ σ 0 ⟩ remains fixed. To analyze the resulting update, define the residual estimation error by
∣ e t ⟩ : = ( 1 N t ∑ i = 1 N t Δ t , i − ( ψ − σ t − 1 ) ) ∣ σ 0 ⟩ . (14) |e_t\rangle:= \left(\frac{1}{N_t}\sum_{i=1}^{N_t}\Delta_{t,i}-(\psi-\sigma_{t-1})\right)|\sigma_0\rangle. \tag*{(14)} ∣ e t ⟩ := ( N t 1 i = 1 ∑ N t Δ t , i − ( ψ − σ t − 1 ) ) ∣ σ 0 ⟩ . (14)
The update therefore satisfies the following identity
∣ σ ~ t ⟩ = ψ ∣ σ 0 ⟩ + ∣ e t ⟩ = ⟨ ψ ∣ σ 0 ⟩ ∣ ψ ⟩ + ∣ e t ⟩ . (15) |\widetilde{\sigma}_t\rangle=\psi|\sigma_0\rangle+|e_t\rangle=\langle\psi|\sigma_0\rangle|\psi\rangle+|e_t\rangle. \tag*{(15)} ∣ σ t ⟩ = ψ ∣ σ 0 ⟩ + ∣ e t ⟩ = ⟨ ψ ∣ σ 0 ⟩ ∣ ψ ⟩ + ∣ e t ⟩ . (15)
As ∥ ∣ e t ⟩ ∥ 2 → 0 \lVert|e_t\rangle\rVert_2\to0 ∥ ∣ e t ⟩ ∥ 2 → 0 , ∣ σ ~ t ⟩ |\widetilde{\sigma}_t\rangle ∣ σ t ⟩ approaches a nonzero multiple of ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ . After normalization, the estimate converges to the desired state. The following lemma bounds the expected squared norm of ∣ e t ⟩ |e_t\rangle ∣ e t ⟩ at each stage.
Lemma 4.3 (Residual estimation error). For a fixed current estimate σ t − 1 \sigma_{t-1} σ t − 1 , the expectation over the measurement bases and outcomes at stage t t t satisfies
E [ ∥ ∣ e t ⟩ ∥ 2 2 ∣ σ t − 1 ] ≤ 2 C N t ( 1 − Tr ( ψ σ t − 1 ) + d 2 S t ) . \mathbb{E}[\lVert|e_t\rangle\rVert_2^2\mid\sigma_{t-1}]
\le\frac{2C}{N_t}\left(1-\operatorname{Tr}(\psi\sigma_{t-1})+\frac{d}{2S_t}\right). E [∥ ∣ e t ⟩ ∥ 2 2 ∣ σ t − 1 ] ≤ N t 2 C ( 1 − Tr ( ψ σ t − 1 ) + 2 S t d ) .
Proof. Conditioned on the current estimate σ t − 1 \sigma_{t-1} σ t − 1 , the residuals Δ t , i \Delta_{t,i} Δ t , i are independent and satisfy E [ Δ t , i ∣ σ t − 1 ] = ψ − σ t − 1 \mathbb{E}[\Delta_{t,i}\mid\sigma_{t-1}]=\psi-\sigma_{t-1} E [ Δ t , i ∣ σ t − 1 ] = ψ − σ t − 1 by Lemma 4.2 . The centered cross terms therefore have zero conditional expectation, giving
E [ ∥ ∣ e t ⟩ ∥ 2 2 ∣ σ t − 1 ] = 1 N t ⟨ σ 0 ∣ ( E [ Δ t , 1 2 ∣ σ t − 1 ] − ( ψ − σ t − 1 ) 2 ) ∣ σ 0 ⟩ ≤ 1 N t ∥ E [ Δ t , 1 2 ∣ σ t − 1 ] − ( ψ − σ t − 1 ) 2 ∥ op ≤ C N t ( ∥ ψ − σ t − 1 ∥ F 2 + d S t ) (by xref‘Lemma 4.2‘) = 2 C N t ( 1 − Tr ( ψ σ t − 1 ) + d 2 S t ) . \begin{aligned}
\mathbb{E}[\lVert|e_t\rangle\rVert_2^2\mid\sigma_{t-1}]
=\frac{1}{N_t}\langle\sigma_0|\left(\mathbb{E}[\Delta_{t,1}^2\mid\sigma_{t-1}]-(\psi-\sigma_{t-1})^2\right)|\sigma_0\rangle\\
&\le\frac{1}{N_t}\left\lVert\mathbb{E}[\Delta_{t,1}^2\mid\sigma_{t-1}]-(\psi-\sigma_{t-1})^2\right\rVert_{\operatorname{op}} \\
&\le\frac{C}{N_t}\left(\lVert\psi-\sigma_{t-1}\rVert_F^2+\frac{d}{S_t}\right)
\qquad\text{(by {xref}`Lemma 4.2`)} \\
&=\frac{2C}{N_t}\left(1-\operatorname{Tr}(\psi\sigma_{t-1})+\frac{d}{2S_t}\right).
\end{aligned} E [∥ ∣ e t ⟩ ∥ 2 2 ∣ σ t − 1 ] = N t 1 ⟨ σ 0 ∣ ( E [ Δ t , 1 2 ∣ σ t − 1 ] − ( ψ − σ t − 1 ) 2 ) ∣ σ 0 ⟩ ≤ N t 1 E [ Δ t , 1 2 ∣ σ t − 1 ] − ( ψ − σ t − 1 ) 2 op ≤ N t C ( ∥ ψ − σ t − 1 ∥ F 2 + S t d ) (by xref ‘Lemma 4.2‘) = N t 2 C ( 1 − Tr ( ψ σ t − 1 ) + 2 S t d ) .
Lemma 4.4 (From vector error to infidelity). Given Tr ( ψ σ 0 ) ≥ 1 / 2 \operatorname{Tr}(\psi\sigma_0)\ge1/2 Tr ( ψ σ 0 ) ≥ 1/2 ,
1 − Tr ( ψ σ t ) ≤ ∥ ∣ e t ⟩ ∥ 2 2 Tr ( ψ σ 0 ) ≤ 2 ∥ ∣ e t ⟩ ∥ 2 2 . (16) 1-\operatorname{Tr}(\psi\sigma_t)\le
\frac{\lVert|e_t\rangle\rVert_2^2}{\operatorname{Tr}(\psi\sigma_0)}
\le2\lVert|e_t\rangle\rVert_2^2. \tag*{(16)} 1 − Tr ( ψ σ t ) ≤ Tr ( ψ σ 0 ) ∥ ∣ e t ⟩ ∥ 2 2 ≤ 2 ∥ ∣ e t ⟩ ∥ 2 2 . (16)
Proof. The update rule in Eq. (13) ensures
( I − σ t ) ∣ σ ~ t ⟩ = 0 , (I-\sigma_t)|\widetilde{\sigma}_t\rangle=0, ( I − σ t ) ∣ σ t ⟩ = 0 ,
including when ∥ ∣ σ ~ t ⟩ ∥ 2 = 0 \lVert|\widetilde{\sigma}_t\rangle\rVert_2=0 ∥ ∣ σ t ⟩ ∥ 2 = 0 . Using Eq. (15), we obtain
( I − σ t ) ∣ σ ~ t ⟩ = 0 ⇒ ( I − σ t ) ψ ∣ σ 0 ⟩ = − ( I − σ t ) ∣ e t ⟩ ⇒ ( I − σ t ) ⟨ ψ ∣ σ 0 ⟩ ∣ ψ ⟩ = − ( I − σ t ) ∣ e t ⟩ ⇒ ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ∥ ( I − σ t ) ∣ ψ ⟩ ∥ 2 2 = ∥ ( I − σ t ) ∣ e t ⟩ ∥ 2 2 ⇒ Tr ( ψ σ 0 ) ( 1 − Tr ( ψ σ t ) ) = ⟨ e t ∣ ( I − σ t ) ∣ e t ⟩ ≤ ∥ e t ∥ 2 2 (17) \begin{aligned}
(I-\sigma_t)|\widetilde{\sigma}_t\rangle=0 \\
&\Rightarrow(I-\sigma_t)\psi|\sigma_0\rangle=-(I-\sigma_t)|e_t\rangle\\
&\Rightarrow(I-\sigma_t)\langle\psi|\sigma_0\rangle|\psi\rangle=-(I-\sigma_t)|e_t\rangle\\
&\Rightarrow|\langle\psi|\sigma_0\rangle|^2\|(I-\sigma_t)|\psi\rangle\|_2^2=\|(I-\sigma_t)|e_t\rangle\|_2^2 \\
&\Rightarrow\operatorname{Tr}(\psi\sigma_0)(1-\operatorname{Tr}(\psi\sigma_t))=\langle e_t|(I-\sigma_t)|e_t\rangle\le\|e_t\|_2^2 \tag*{(17)}
\end{aligned} ( I − σ t ) ∣ σ t ⟩ = 0 ⇒ ( I − σ t ) ψ ∣ σ 0 ⟩ = − ( I − σ t ) ∣ e t ⟩ ⇒ ( I − σ t ) ⟨ ψ ∣ σ 0 ⟩ ∣ ψ ⟩ = − ( I − σ t ) ∣ e t ⟩ ⇒ ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ∥ ( I − σ t ) ∣ ψ ⟩ ∥ 2 2 = ∥ ( I − σ t ) ∣ e t ⟩ ∥ 2 2 ⇒ Tr ( ψ σ 0 ) ( 1 − Tr ( ψ σ t )) = ⟨ e t ∣ ( I − σ t ) ∣ e t ⟩ ≤ ∥ e t ∥ 2 2 (17)
Dividing by Tr ( ψ σ 0 ) ≥ 1 / 2 \operatorname{Tr}(\psi\sigma_0)\ge1/2 Tr ( ψ σ 0 ) ≥ 1/2 proves the claim.
If the initial vector ∣ σ 0 ⟩ |\sigma_0\rangle ∣ σ 0 ⟩ is chosen uniformly at random, its expected squared overlap with the target is only 1 / d = 2 − n 1/d=2^{-n} 1/ d = 2 − n . Since the bound in Eq. (16) divides by Tr ( ψ σ 0 ) \operatorname{Tr}(\psi\sigma_0) Tr ( ψ σ 0 ) , a small overlap can greatly weaken the infidelity guarantee.
Corollary 4.5. Fix an initial estimate σ 0 \sigma_0 σ 0 with Tr ( ψ σ 0 ) ≥ 1 / 2 \operatorname{Tr}(\psi\sigma_0)\ge1/2 Tr ( ψ σ 0 ) ≥ 1/2 . For any ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) , let J : = ⌈ log 2 ( 1 / ( 2 ϵ ) ) ⌉ J:=\lceil\log_2(1/(2\epsilon))\rceil J := ⌈ log 2 ( 1/ ( 2 ϵ ))⌉ . There exist choices of N t , S t N_t,S_t N t , S t for t = 1 , … , J t=1,\ldots,J t = 1 , … , J such that E [ 1 − Tr ( ψ σ J ) ] ≤ ϵ \mathbb{E}[1-\operatorname{Tr}(\psi\sigma_J)]\le\epsilon E [ 1 − Tr ( ψ σ J )] ≤ ϵ and
∑ t = 1 J N t = O ( log ( 1 / ϵ ) ) , \sum_{t=1}^{J}N_t=O(\log(1/\epsilon)), t = 1 ∑ J N t = O ( log ( 1/ ϵ )) , ∑ t = 1 J N t S t = O ( d / ϵ ) . \sum_{t=1}^{J}N_tS_t=O(d/\epsilon). t = 1 ∑ J N t S t = O ( d / ϵ ) .
Proof. Choose N t : = ⌈ 16 ( C + 1 ) ⌉ N_t:=\lceil16(C+1)\rceil N t := ⌈ 16 ( C + 1 )⌉ and S t : = d 2 t − 1 S_t:=d\,2^{t-1} S t := d 2 t − 1 for t = 1 , … , J t=1,\ldots,J t = 1 , … , J . By Lemmas 4.3 and 4.4 , with all previous stages held fixed,
E [ 1 − Tr ( ψ σ t ) ∣ σ t − 1 ] ≤ 2 E [ ∥ e t ∥ 2 2 ∣ σ t − 1 ] ≤ 4 C N t ( 1 − Tr ( ψ σ t − 1 ) + d 2 S t ) ≤ 1 4 [ 1 − Tr ( ψ σ t − 1 ) ] + d 8 S t . \begin{aligned}
\mathbb{E}[1-\operatorname{Tr}(\psi\sigma_t)\mid\sigma_{t-1}]\le2\mathbb{E}[\|e_t\|_2^2\mid\sigma_{t-1}] \\
&\le\frac{4C}{N_t}\left(1-\operatorname{Tr}(\psi\sigma_{t-1})+\frac{d}{2S_t}\right) \\
&\le\frac{1}{4}[1-\operatorname{Tr}(\psi\sigma_{t-1})]+\frac{d}{8S_t}.
\end{aligned} E [ 1 − Tr ( ψ σ t ) ∣ σ t − 1 ] ≤ 2 E [ ∥ e t ∥ 2 2 ∣ σ t − 1 ] ≤ N t 4 C ( 1 − Tr ( ψ σ t − 1 ) + 2 S t d ) ≤ 4 1 [ 1 − Tr ( ψ σ t − 1 )] + 8 S t d .
The initial error is at most 1 / 2 1/2 1/2 . If E [ 1 − Tr ( ψ σ t − 1 ) ] ≤ 2 − t \mathbb{E}[1-\operatorname{Tr}(\psi\sigma_{t-1})]\le2^{-t} E [ 1 − Tr ( ψ σ t − 1 )] ≤ 2 − t , then averaging over previous stages gives
E [ 1 − Tr ( ψ σ t ) ] ≤ 1 4 E [ 1 − Tr ( ψ σ t − 1 ) ] + d 8 S t ≤ 1 4 ⋅ 2 t + 1 8 ⋅ 2 t − 1 = 2 − ( t + 1 ) . \begin{aligned}
\mathbb{E}[1-\operatorname{Tr}(\psi\sigma_t)]\le\frac{1}{4}\mathbb{E}[1-\operatorname{Tr}(\psi\sigma_{t-1})]+\frac{d}{8S_t} \\
&\le\frac{1}{4\cdot2^t}+\frac{1}{8\cdot2^{t-1}}=2^{-(t+1)}.
\end{aligned} E [ 1 − Tr ( ψ σ t )] ≤ 4 1 E [ 1 − Tr ( ψ σ t − 1 )] + 8 S t d ≤ 4 ⋅ 2 t 1 + 8 ⋅ 2 t − 1 1 = 2 − ( t + 1 ) .
Induction therefore gives E [ 1 − Tr ( ψ σ J ) ] ≤ 2 − ( J + 1 ) ≤ ϵ \mathbb{E}[1-\operatorname{Tr}(\psi\sigma_J)]\le2^{-(J+1)}\le\epsilon E [ 1 − Tr ( ψ σ J )] ≤ 2 − ( J + 1 ) ≤ ϵ .
Finally, N t = O ( 1 ) N_t=O(1) N t = O ( 1 ) and J = O ( log ( 1 / ϵ ) ) J=O(\log(1/\epsilon)) J = O ( log ( 1/ ϵ )) , so
∑ t = 1 J N t = O ( J ) = O ( log ( 1 / ϵ ) ) , \sum_{t=1}^{J}N_t=O(J)=O(\log(1/\epsilon)), t = 1 ∑ J N t = O ( J ) = O ( log ( 1/ ϵ )) ,
∑ t = 1 J N t S t = O ( d ∑ t = 1 J 2 t ) = O ( d 2 J ) = O ( d / ϵ ) . \sum_{t=1}^{J}N_tS_t=O\left(d\sum_{t=1}^{J}2^t\right)=O(d\,2^J)=O(d/\epsilon). t = 1 ∑ J N t S t = O ( d t = 1 ∑ J 2 t ) = O ( d 2 J ) = O ( d / ϵ ) .
Corollary 4.6 (Constant success probability). Fix an initial estimate σ 0 \sigma_0 σ 0 with Tr ( ψ σ 0 ) ≥ 1 / 2 \operatorname{Tr}(\psi\sigma_0)\ge1/2 Tr ( ψ σ 0 ) ≥ 1/2 . For any 0 < ϵ < 1 0<\epsilon<1 0 < ϵ < 1 , running the refinement with expected-error target ϵ / 12 \epsilon/12 ϵ /12 yields
Pr [ 1 − Tr ( ψ σ J ) > ϵ ] ≤ 1 12 . \Pr[1-\operatorname{Tr}(\psi\sigma_J)>\epsilon]\le\frac{1}{12}. Pr [ 1 − Tr ( ψ σ J ) > ϵ ] ≤ 12 1 .
The asymptotic resource bounds of Corollary 4.5 remain unchanged.
Proof. By Corollary 4.5 and Markov’s inequality,
Pr [ 1 − Tr ( ψ σ J ) > ϵ ] ≤ E [ 1 − Tr ( ψ σ J ) ] ϵ ≤ ϵ / 12 ϵ = 1 12 . \Pr[1-\operatorname{Tr}(\psi\sigma_J)>\epsilon]\leq\frac{\mathbb{E}[1-\operatorname{Tr}(\psi\sigma_J)]}{\epsilon}
\leq\frac{\epsilon/12}{\epsilon}=\frac{1}{12}. Pr [ 1 − Tr ( ψ σ J ) > ϵ ] ≤ ϵ E [ 1 − Tr ( ψ σ J )] ≤ ϵ ϵ /12 = 12 1 .
Replacing ϵ \epsilon ϵ by ϵ / 12 \epsilon/12 ϵ /12 increases the number of stages by only an additive constant and preserves the asymptotic resource bounds.
Initialization
We construct a normalized estimate ∣ σ 0 ⟩ |\sigma_0\rangle ∣ σ 0 ⟩ with constant overlap with an unknown pure state ∣ ψ ⟩ ∈ C d |\psi\rangle\in\mathbb{C}^d ∣ ψ ⟩ ∈ C d , where d = 2 n d=2^n d = 2 n , to serve as the starting point for shadow bootstrapping. The procedure uses nonadaptive shallow Clifford measurements and recursively combines estimates of smaller conditional states. The following theorem summarizes its guarantees.
Theorem 5.1 (Initialization). Under the measurement assumptions above, there are choices of N ℓ N_\ell N ℓ and S ℓ S_\ell S ℓ such that the reconstruction below outputs a unit vector ∣ σ 0 ⟩ |\sigma_0\rangle ∣ σ 0 ⟩ satisfying
Pr [ ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ≥ 1 2 ] ≥ 11 12 . \Pr\left[|\langle\psi|\sigma_0\rangle|^2\geq\frac{1}{2}\right]\geq\frac{11}{12}. Pr [ ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ≥ 2 1 ] ≥ 12 11 . The protocol is nonadaptive and single-copy, with
∑ ℓ = 0 n − 1 N ℓ S ℓ = O ( d ) , ∑ ℓ = 0 n − 1 N ℓ = O ( n 3 ) . \sum_{\ell=0}^{n-1}N_\ell S_\ell=O(d),\qquad\sum_{\ell=0}^{n-1}N_\ell=O(n^3). ℓ = 0 ∑ n − 1 N ℓ S ℓ = O ( d ) , ℓ = 0 ∑ n − 1 N ℓ = O ( n 3 ) . Each measurement has Clifford depth O ( log n ) O(\log n) O ( log n ) .
Review of the tree representation of ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩
The reconstruction proceeds along a binary tree whose nodes at level ℓ \ell ℓ are indexed by prefixes x ∈ { 0 , 1 } ℓ x\in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ .
Definition 5.2 (Conditional states). For a prefix x ∈ { 0 , 1 } ℓ x\in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ , define p x : = ∥ ( ⟨ x ∣ ⊗ I ) ∣ ψ ⟩ ∥ 2 2 p_x:=\|(\langle x|\otimes I)|\psi\rangle\|_2^2 p x := ∥ (⟨ x ∣ ⊗ I ) ∣ ψ ⟩ ∥ 2 2 . If p x > 0 p_x>0 p x > 0 , define the normalized conditional state
∣ ψ x ⟩ : = ( ⟨ x ∣ ⊗ I ) ∣ ψ ⟩ p x ∈ C 2 n − ℓ , ψ x : = ∣ ψ x ⟩ ⟨ ψ x ∣ . |\psi_x\rangle:=\frac{(\langle x|\otimes I)|\psi\rangle}{\sqrt{p_x}}\in\mathbb{C}^{2^{n-\ell}},\qquad\psi_x:=|\psi_x\rangle\langle\psi_x|. ∣ ψ x ⟩ := p x (⟨ x ∣ ⊗ I ) ∣ ψ ⟩ ∈ C 2 n − ℓ , ψ x := ∣ ψ x ⟩ ⟨ ψ x ∣. At the root, p ∅ = 1 p_{\varnothing}=1 p ∅ = 1 and ∣ ψ ∅ ⟩ = ∣ ψ ⟩ |\psi_{\varnothing}\rangle=|\psi\rangle ∣ ψ ∅ ⟩ = ∣ ψ ⟩ .
Lemma 5.3 ([13 ] , The proof of Lemma 4). For every ℓ = 0 , … , n − 1 \ell=0,\ldots,n-1 ℓ = 0 , … , n − 1 and prefix x ∈ { 0 , 1 } ℓ x\in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ , the parent and child states satisfy
p x = p x 0 + p x 1 , p_x=p_{x0}+p_{x1}, p x = p x 0 + p x 1 , p x ∣ ψ x ⟩ = p x 0 ∣ 0 ⟩ ⊗ ∣ ψ x 0 ⟩ + p x 1 ∣ 1 ⟩ ⊗ ∣ ψ x 1 ⟩ . (18) \sqrt{p_x}|\psi_x\rangle=\sqrt{p_{x0}}|0\rangle\otimes|\psi_{x0}\rangle+\sqrt{p_{x1}}|1\rangle\otimes|\psi_{x1}\rangle. \tag*{(18)} p x ∣ ψ x ⟩ = p x 0 ∣0 ⟩ ⊗ ∣ ψ x 0 ⟩ + p x 1 ∣1 ⟩ ⊗ ∣ ψ x 1 ⟩ . (18) In particular, ∑ x ∈ { 0 , 1 } ℓ p x = 1 \sum_{x\in\{0,1\}^{\ell}}p_x=1 ∑ x ∈ { 0 , 1 } ℓ p x = 1 at every level.
Measurement setup
Lemma 5.4 (Informal, see Lemma A.2). For each ℓ = 0 , … , n − 1 \ell= 0,\ldots,n-1 ℓ = 0 , … , n − 1 , there exists an O ( log n ) O(\log n) O ( log n ) -depth Clifford ensemble E ℓ \mathcal{E}_{\ell} E ℓ on n − ℓ n-\ell n − ℓ qubits with a shadow channel M ℓ \mathcal{M}_{\ell} M ℓ satisfying Eq. (8) for every state and Hermitian observable, with a universal constant.
At each level ℓ \ell ℓ , independently sample
U 1 , … , U N ℓ ∼ E ℓ . U_1,\ldots,U_{N_{\ell}} \sim\mathcal{E}_{\ell}. U 1 , … , U N ℓ ∼ E ℓ .
We suppress the level index in U i U_i U i . The bases sampled at different levels are independent. For each sampled U i U_i U i , apply I 2 ℓ ⊗ U i I_{2^{\ell}} \otimes U_i I 2 ℓ ⊗ U i to S ℓ S_{\ell} S ℓ copies and measure all qubits in the computational basis. As illustrated in Figure 2 , the first ℓ \ell ℓ qubits are measured in the Z Z Z basis, while the two-layer Clifford circuit acts only on the remaining n − ℓ n-\ell n − ℓ qubits.
Figure 2. Suffix unitary ensemble E ℓ \mathcal{E}_{\ell} E ℓ .
Level ℓ \ell ℓ therefore uses N ℓ N_{\ell} N ℓ sampled bases and N ℓ S ℓ N_{\ell}S_{\ell} N ℓ S ℓ copies. All bases and shot counts are chosen in advance, and different levels use independent bases and disjoint copies. We write a measurement outcome as
( x , b ) ∈ { 0 , 1 } ℓ × { 0 , 1 } n − ℓ , (x,b) \in\{0,1\}^{\ell} \times\{0,1\}^{n-\ell}, ( x , b ) ∈ { 0 , 1 } ℓ × { 0 , 1 } n − ℓ ,
where x x x is the ℓ \ell ℓ -bit prefix and b b b is the ( n − ℓ ) (n-\ell) ( n − ℓ ) -bit suffix. For a fixed basis U U U , this outcome occurs with probability
Pr ( x , b ) = p x ⟨ b ∣ U ψ x U † ∣ b ⟩ . (19) \Pr(x,b) = p_x \langle b|U\psi_x U^\dagger|b\rangle. \tag*{(19)} Pr ( x , b ) = p x ⟨ b ∣ U ψ x U † ∣ b ⟩ . (19)
Recursive reconstruction
The reconstruction proceeds from the leaves to the root. Suppose that normalized child estimates ∣ ψ ^ x 0 ⟩ |\widehat{\psi}_{x0}\rangle ∣ ψ x 0 ⟩ and ∣ ψ ^ x 1 ⟩ |\widehat{\psi}_{x1}\rangle ∣ ψ x 1 ⟩ have already been constructed. For p x > 0 p_x > 0 p x > 0 , the true parent state can be decomposed as
∣ ψ x ⟩ = p x 0 p x ∣ 0 ⟩ ⊗ ∣ ψ x 0 ⟩ + p x 1 p x ∣ 1 ⟩ ⊗ ∣ ψ x 1 ⟩ = α ~ 0 ∣ 0 ⟩ ⊗ ∣ ψ ^ x 0 ⟩ + α ~ 1 ∣ 1 ⟩ ⊗ ∣ ψ ^ x 1 ⟩ + (an orthogonal remainder) , \begin{aligned}
|\psi_x\rangle= \sqrt{\frac{p_{x0}}{p_x}} |0\rangle\otimes|\psi_{x0}\rangle+ \sqrt{\frac{p_{x1}}{p_x}} |1\rangle\otimes|\psi_{x1}\rangle\\
&= \widetilde{\alpha}_0 |0\rangle\otimes|\widehat{\psi}_{x0}\rangle+ \widetilde{\alpha}_1 |1\rangle\otimes|\widehat{\psi}_{x1}\rangle+ \text{(an orthogonal remainder)},
\end{aligned} ∣ ψ x ⟩ = p x p x 0 ∣0 ⟩ ⊗ ∣ ψ x 0 ⟩ + p x p x 1 ∣1 ⟩ ⊗ ∣ ψ x 1 ⟩ = α 0 ∣0 ⟩ ⊗ ∣ ψ x 0 ⟩ + α 1 ∣1 ⟩ ⊗ ∣ ψ x 1 ⟩ + (an orthogonal remainder) ,
where α ~ i : = ( ⟨ i ∣ ⊗ ⟨ ψ ^ x i ∣ ) ∣ ψ x ⟩ \widetilde{\alpha}_i := (\langle i| \otimes\langle\widehat{\psi}_{xi}|)|\psi_x\rangle α i := (⟨ i ∣ ⊗ ⟨ ψ x i ∣ ) ∣ ψ x ⟩ for i ∈ { 0 , 1 } i \in\{0,1\} i ∈ { 0 , 1 } , and the remainder is orthogonal to both ∣ 0 ⟩ ⊗ ∣ ψ ^ x 0 ⟩ |0\rangle\otimes|\widehat{\psi}_{x0}\rangle ∣0 ⟩ ⊗ ∣ ψ x 0 ⟩ and ∣ 1 ⟩ ⊗ ∣ ψ ^ x 1 ⟩ |1\rangle\otimes|\widehat{\psi}_{x1}\rangle ∣1 ⟩ ⊗ ∣ ψ x 1 ⟩ . Whenever ∣ α ~ 0 ∣ 2 + ∣ α ~ 1 ∣ 2 > 0 |\widetilde{\alpha}_0|^2 + |\widetilde{\alpha}_1|^2 > 0 ∣ α 0 ∣ 2 + ∣ α 1 ∣ 2 > 0 , the normalized projection onto their span has coefficient vector α : = ( α 0 , α 1 ) T ∈ C 2 \alpha:= (\alpha_0,\alpha_1)^{\mathsf{T}} \in\mathbb{C}^2 α := ( α 0 , α 1 ) T ∈ C 2 , where
α 0 = α ~ 0 ∣ α ~ 0 ∣ 2 + ∣ α ~ 1 ∣ 2 , α 1 = α ~ 1 ∣ α ~ 0 ∣ 2 + ∣ α ~ 1 ∣ 2 . \alpha_0 = \frac{\widetilde{\alpha}_0}{\sqrt{|\widetilde{\alpha}_0|^2 + |\widetilde{\alpha}_1|^2}}, \qquad\alpha_1 = \frac{\widetilde{\alpha}_1}{\sqrt{|\widetilde{\alpha}_0|^2 + |\widetilde{\alpha}_1|^2}}. α 0 = ∣ α 0 ∣ 2 + ∣ α 1 ∣ 2 α 0 , α 1 = ∣ α 0 ∣ 2 + ∣ α 1 ∣ 2 α 1 .
Our goal is to estimate α \alpha α up to a common phase. Repeating this reconstruction up the tree yields the estimate at the root.
We adopt the recursive reconstruction framework of [13 ] , but replace their nested one-dimensional noisy searches with direct estimation of a 2 × 2 2 \times2 2 × 2 reconstruction matrix using shallow Clifford measurements. Its entries are p x p_x p x times the following coefficient products:
∣ α ~ 0 ∣ 2 = Tr [ ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ ∣ ψ ^ x 0 ⟩ ⟨ ψ ^ x 0 ∣ ) ∣ ψ x ⟩ ] , α ~ 0 α ~ 1 ∗ = Tr [ ( ∣ 1 ⟩ ⟨ 0 ∣ ⊗ ∣ ψ ^ x 1 ⟩ ⟨ ψ ^ x 0 ∣ ) ∣ ψ x ⟩ ] , \lvert\widetilde{\alpha}_0\rvert^2=\operatorname{Tr}\left[\left(\lvert0\rangle\langle0\rvert\otimes\lvert\widehat{\psi}_{x0}\rangle\langle\widehat{\psi}_{x0}\rvert\right)\lvert\psi_x\rangle\right],
\qquad
\widetilde{\alpha}_0\widetilde{\alpha}_1^*=\operatorname{Tr}\left[\left(\lvert1\rangle\langle0\rvert\otimes\lvert\widehat{\psi}_{x1}\rangle\langle\widehat{\psi}_{x0}\rvert\right)\lvert\psi_x\rangle\right], ∣ α 0 ∣ 2 = Tr [ ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ ∣ ψ x 0 ⟩ ⟨ ψ x 0 ∣ ) ∣ ψ x ⟩ ] , α 0 α 1 ∗ = Tr [ ( ∣ 1 ⟩ ⟨ 0 ∣ ⊗ ∣ ψ x 1 ⟩ ⟨ ψ x 0 ∣ ) ∣ ψ x ⟩ ] ,
α ~ 0 ∗ α ~ 1 = Tr [ ( ∣ 0 ⟩ ⟨ 1 ∣ ⊗ ∣ ψ ^ x 0 ⟩ ⟨ ψ ^ x 1 ∣ ) ∣ ψ x ⟩ ] , ∣ α ~ 1 ∣ 2 = Tr [ ( ∣ 1 ⟩ ⟨ 1 ∣ ⊗ ∣ ψ ^ x 1 ⟩ ⟨ ψ ^ x 1 ∣ ) ∣ ψ x ⟩ ] . \widetilde{\alpha}_0^*\widetilde{\alpha}_1=\operatorname{Tr}\left[\left(\lvert0\rangle\langle1\rvert\otimes\lvert\widehat{\psi}_{x0}\rangle\langle\widehat{\psi}_{x1}\rvert\right)\lvert\psi_x\rangle\right],
\qquad
\lvert\widetilde{\alpha}_1\rvert^2=\operatorname{Tr}\left[\left(\lvert1\rangle\langle1\rvert\otimes\lvert\widehat{\psi}_{x1}\rangle\langle\widehat{\psi}_{x1}\rvert\right)\lvert\psi_x\rangle\right]. α 0 ∗ α 1 = Tr [ ( ∣ 0 ⟩ ⟨ 1 ∣ ⊗ ∣ ψ x 0 ⟩ ⟨ ψ x 1 ∣ ) ∣ ψ x ⟩ ] , ∣ α 1 ∣ 2 = Tr [ ( ∣ 1 ⟩ ⟨ 1 ∣ ⊗ ∣ ψ x 1 ⟩ ⟨ ψ x 1 ∣ ) ∣ ψ x ⟩ ] .
Fix a node x ∈ { 0 , 1 } ℓ x \in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ with normalized child estimates, and write
∣ q 0 ⟩ : = ∣ 0 ⟩ ⊗ ∣ ψ ^ x 0 ⟩ , ∣ q 1 ⟩ : = ∣ 1 ⟩ ⊗ ∣ ψ ^ x 1 ⟩ . \lvert q_0\rangle:= \lvert0\rangle\otimes\lvert\widehat{\psi}_{x0}\rangle,\qquad
\lvert q_1\rangle:= \lvert1\rangle\otimes\lvert\widehat{\psi}_{x1}\rangle. ∣ q 0 ⟩ := ∣ 0 ⟩ ⊗ ∣ ψ x 0 ⟩ , ∣ q 1 ⟩ := ∣ 1 ⟩ ⊗ ∣ ψ x 1 ⟩ .
These vectors are orthonormal. For w = ( w 0 , w 1 ) ∈ C 2 w=(w_0,w_1)\in\mathbb{C}^2 w = ( w 0 , w 1 ) ∈ C 2 with ∥ w ∥ 2 = 1 \lVert w\rVert_2=1 ∥ w ∥ 2 = 1 , define
∣ q w ⟩ : = w 0 ∣ q 0 ⟩ + w 1 ∣ q 1 ⟩ . \lvert q_w\rangle:= w_0\lvert q_0\rangle+w_1\lvert q_1\rangle. ∣ q w ⟩ := w 0 ∣ q 0 ⟩ + w 1 ∣ q 1 ⟩ .
Definition 5.5 (Reconstruction matrix). Define B x ∈ C 2 × 2 B_x\in\mathbb{C}^{2\times2} B x ∈ C 2 × 2 by
( B x ) a b : = p x ⟨ q a ∣ ψ x ⟩ ⟨ ψ x ∣ q b ⟩ , a , b ∈ { 0 , 1 } . (B_x)_{ab}:=p_x\langle q_a\vert\psi_x\rangle\langle\psi_x\vert q_b\rangle,\qquad a,b\in\{0,1\}. ( B x ) ab := p x ⟨ q a ∣ ψ x ⟩ ⟨ ψ x ∣ q b ⟩ , a , b ∈ { 0 , 1 } . The factor p x p_x p x allows the entries to be estimated unbiasedly from the measurement data without dividing by the unknown prefix probability.
Lemma 5.6. The matrix B x B_x B x is positive semidefinite with rank at most one. For every unit vector w ∈ C 2 w\in\mathbb{C}^2 w ∈ C 2 , w † B x w = p x ∣ ⟨ ψ x ∣ q w ⟩ ∣ 2 w^\dagger B_xw=p_x\lvert\langle\psi_x\vert q_w\rangle\rvert^2 w † B x w = p x ∣⟨ ψ x ∣ q w ⟩ ∣ 2 .
Proof. By Definition 5.5 ,
B x = p x ( ∣ α ~ 0 ∣ 2 α ~ 0 α ~ 1 ∗ α ~ 0 ∗ α ~ 1 ∣ α ~ 1 ∣ 2 ) = p x ( α ~ 0 α ~ 1 ) ( α ~ 0 ∗ α ~ 1 ∗ ) . B_x=p_x\begin{pmatrix}
\lvert\widetilde{\alpha}_0\rvert^2 & \widetilde{\alpha}_0\widetilde{\alpha}_1^*\\
\widetilde{\alpha}_0^*\widetilde{\alpha}_1 & \lvert\widetilde{\alpha}_1\rvert^2
\end{pmatrix}
=p_x
\begin{pmatrix}
\widetilde{\alpha}_0\\
\widetilde{\alpha}_1
\end{pmatrix}
\begin{pmatrix}
\widetilde{\alpha}_0^* & \widetilde{\alpha}_1^*
\end{pmatrix}. B x = p x ( ∣ α 0 ∣ 2 α 0 ∗ α 1 α 0 α 1 ∗ ∣ α 1 ∣ 2 ) = p x ( α 0 α 1 ) ( α 0 ∗ α 1 ∗ ) . If ∣ ψ x ⟩ \lvert\psi_x\rangle ∣ ψ x ⟩ is orthogonal to both ∣ q 0 ⟩ \lvert q_0\rangle ∣ q 0 ⟩ and ∣ q 1 ⟩ \lvert q_1\rangle ∣ q 1 ⟩ , then α ~ 0 = α ~ 1 = 0 \widetilde{\alpha}_0=\widetilde{\alpha}_1=0 α 0 = α 1 = 0 and B x = 0 B_x=0 B x = 0 . Otherwise,
B x = p x ( ∣ α ~ 0 ∣ 2 + ∣ α ~ 1 ∣ 2 ) α α † . B_x=p_x\left(\lvert\widetilde{\alpha}_0\rvert^2+\lvert\widetilde{\alpha}_1\rvert^2\right)\alpha\alpha^\dagger. B x = p x ( ∣ α 0 ∣ 2 + ∣ α 1 ∣ 2 ) α α † . In either case, B x B_x B x is positive semidefinite with rank at most one.
For every unit vector w ∈ C 2 w\in\mathbb{C}^2 w ∈ C 2 ,
w † B x w = p x ∑ a , b ∈ { 0 , 1 } w a ∗ w b ⟨ q a ∣ ψ x ⟩ ⟨ ψ x ∣ q b ⟩ w^\dagger B_xw=p_x\sum_{a,b\in\{0,1\}}w_a^*w_b\langle q_a\vert\psi_x\rangle\langle\psi_x\vert q_b\rangle w † B x w = p x a , b ∈ { 0 , 1 } ∑ w a ∗ w b ⟨ q a ∣ ψ x ⟩ ⟨ ψ x ∣ q b ⟩ = p x ∣ ∑ b ∈ { 0 , 1 } w b ⟨ ψ x ∣ q b ⟩ ∣ 2 = p x ∣ ⟨ ψ x ∣ q w ⟩ ∣ 2 . =p_x\left\lvert\sum_{b\in\{0,1\}}w_b\langle\psi_x\vert q_b\rangle\right\rvert^2=p_x\lvert\langle\psi_x\vert q_w\rangle\rvert^2. = p x b ∈ { 0 , 1 } ∑ w b ⟨ ψ x ∣ q b ⟩ 2 = p x ∣⟨ ψ x ∣ q w ⟩ ∣ 2 .
Corollary 5.7 (Inherited reconstruction error). For every node x x x ,
p x − α † B x α = p x 0 ( 1 − ∣ ⟨ ψ x 0 ∣ ψ ^ x 0 ⟩ ∣ 2 ) + p x 1 ( 1 − ∣ ⟨ ψ x 1 ∣ ψ ^ x 1 ⟩ ∣ 2 ) . (20) p_x-\alpha^\dagger B_x\alpha
=p_{x0}\left(1-\lvert\langle\psi_{x0}\vert\widehat{\psi}_{x0}\rangle\rvert^2\right)
+p_{x1}\left(1-\lvert\langle\psi_{x1}\vert\widehat{\psi}_{x1}\rangle\rvert^2\right). \tag*{(20)} p x − α † B x α = p x 0 ( 1 − ∣⟨ ψ x 0 ∣ ψ x 0 ⟩ ∣ 2 ) + p x 1 ( 1 − ∣⟨ ψ x 1 ∣ ψ x 1 ⟩ ∣ 2 ) . (20) Proof. Recall that α \alpha α is the normalized projection coefficient vector defined above. By Lemma 5.6 ,
α † B x α = p x ( ∣ α ~ 0 ∣ 2 + ∣ α ~ 1 ∣ 2 ) \alpha^\dagger B_x\alpha=p_x\left(\lvert\widetilde{\alpha}_0\rvert^2+\lvert\widetilde{\alpha}_1\rvert^2\right) α † B x α = p x ( ∣ α 0 ∣ 2 + ∣ α 1 ∣ 2 ) = p x 0 ∣ ⟨ ψ x 0 ∣ ψ ^ x 0 ⟩ ∣ 2 + p x 1 ∣ ⟨ ψ x 1 ∣ ψ ^ x 1 ⟩ ∣ 2 . =p_{x0}\lvert\langle\psi_{x0}\vert\widehat{\psi}_{x0}\rangle\rvert^2
+p_{x1}\lvert\langle\psi_{x1}\vert\widehat{\psi}_{x1}\rangle\rvert^2. = p x 0 ∣⟨ ψ x 0 ∣ ψ x 0 ⟩ ∣ 2 + p x 1 ∣⟨ ψ x 1 ∣ ψ x 1 ⟩ ∣ 2 . Subtracting this from p x = p x 0 + p x 1 p_x=p_{x0}+p_{x1} p x = p x 0 + p x 1 proves the claim.
Conditional shadow estimator
Definition 5.8 (Conditional shadow estimator). Fix a level ℓ \ell ℓ and a node x ∈ { 0 , 1 } ℓ x \in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ . For each i = 1 , … , N ℓ i=1,\ldots,N_{\ell} i = 1 , … , N ℓ , let { ( X i , a , b i , a ) } a = 1 S ℓ \{(X_{i,a},b_{i,a})\}_{a=1}^{S_{\ell}} {( X i , a , b i , a ) } a = 1 S ℓ denote the S ℓ S_{\ell} S ℓ measurement outcomes in basis U i U_i U i . For a Hermitian suffix observable O O O , define
o ^ : = 1 N ℓ ∑ i = 1 N ℓ o ^ x , U i , \widehat{o}:=\frac{1}{N_{\ell}}\sum_{i=1}^{N_{\ell}}\widehat{o}_{x,U_i}, o := N ℓ 1 i = 1 ∑ N ℓ o x , U i , o ^ x , U i : = 1 S ℓ ∑ a = 1 S ℓ 1 { X i , a = x } Tr [ O M ℓ − 1 ( U i † ∣ b i , a ⟩ ⟨ b i , a ∣ U i ) ] . (21) \widehat{o}_{x,U_i}:=\frac{1}{S_{\ell}}\sum_{a=1}^{S_{\ell}}\mathbf{1}_{\{X_{i,a}=x\}}\operatorname{Tr}\left[O\mathcal{M}_{\ell}^{-1}\left(U_i^{\dagger}|b_{i,a}\rangle\langle b_{i,a}|U_i\right)\right]. \tag*{(21)} o x , U i := S ℓ 1 a = 1 ∑ S ℓ 1 { X i , a = x } Tr [ O M ℓ − 1 ( U i † ∣ b i , a ⟩ ⟨ b i , a ∣ U i ) ] . (21)
When several observables are considered, write o ^ ( O ) \widehat{o}(O) o ( O ) for the corresponding estimator. Note that each basis average o ^ x , U \widehat{o}_{x,U} o x , U is normalized by all S ℓ S_{\ell} S ℓ shots.
Lemma 5.9. Fix x ∈ { 0 , 1 } ℓ x \in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ . For any Hermitian observable O ∈ L ( H 2 n − ℓ ) O \in\mathcal{L}(\mathcal{H}^{2^{n-\ell}}) O ∈ L ( H 2 n − ℓ ) on the suffix, the estimator in Eq. (21) satisfies
E [ o ^ ] = p x Tr ( O ψ x ) \mathbb{E}[\widehat{o}]=p_x\operatorname{Tr}(O\psi_x) E [ o ] = p x Tr ( O ψ x ) and
Var [ o ^ ] ≤ C ∥ O ∥ F 2 N ℓ ( p x 2 + p x S ℓ ) . \operatorname{Var}[\widehat{o}]\leq\frac{C\lVert O\rVert_F^2}{N_{\ell}}\left(p_x^2+\frac{p_x}{S_{\ell}}\right). Var [ o ] ≤ N ℓ C ∥ O ∥ F 2 ( p x 2 + S ℓ p x ) .
Proof. Take expectations over the level-ℓ \ell ℓ measurement data. Using the measurement probabilities in Eq. (19) , we obtain
E [ o ^ ] = 1 N ℓ ∑ i = 1 N ℓ E [ o ^ x , U i ] = p x E U [ ∑ b Tr ( ψ x U † ∣ b ⟩ ⟨ b ∣ U ) Tr ( O M ℓ − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) ] = p x Tr ( O M ℓ − 1 M ℓ ( ψ x ) ) = p x Tr ( O ψ x ) . \begin{aligned}
\mathbb{E}[\widehat{o}]=\frac{1}{N_{\ell}}\sum_{i=1}^{N_{\ell}}\mathbb{E}[\widehat{o}_{x,U_i}] \\
&=p_x\mathbb{E}_{U}\left[\sum_b\operatorname{Tr}(\psi_xU^{\dagger}|b\rangle\langle b|U)\operatorname{Tr}\left(O\mathcal{M}_{\ell}^{-1}(U^{\dagger}|b\rangle\langle b|U)\right)\right] \\
&=p_x\operatorname{Tr}\left(O\mathcal{M}_{\ell}^{-1}\mathcal{M}_{\ell}(\psi_x)\right) \\
&=p_x\operatorname{Tr}(O\psi_x).
\end{aligned} E [ o ] = N ℓ 1 i = 1 ∑ N ℓ E [ o x , U i ] = p x E U [ b ∑ Tr ( ψ x U † ∣ b ⟩ ⟨ b ∣ U ) Tr ( O M ℓ − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) ] = p x Tr ( O M ℓ − 1 M ℓ ( ψ x ) ) = p x Tr ( O ψ x ) .
Independence across the sampled bases and their associated measurement outcomes gives
Var [ o ^ ] = 1 N ℓ Var [ o ^ x , U ] = 1 N ℓ ( E [ o ^ x , U 2 ] − p x 2 Tr ( O ψ x ) 2 ) = 1 N ℓ ( p x S ℓ E U , b [ Tr ( O ρ ^ U , b ) 2 ] + p x 2 ( S ℓ − 1 ) S ℓ E U , b , c [ Tr ( O ρ ^ U , b ) Tr ( O ρ ^ U , c ) ] − p x 2 Tr ( O ψ x ) 2 ) = 1 N ℓ ( p x S ℓ Var U , b [ Tr ( O ρ ^ U , b ) ] + p x ( 1 − p x ) S ℓ Tr ( O ψ x ) 2 + p x 2 ( S ℓ − 1 ) S ℓ ( E U , b , c [ Tr ( O ρ ^ U , b ) Tr ( O ρ ^ U , c ) ] − Tr ( O ψ x ) 2 ) ) , \begin{aligned}
\operatorname{Var}[\widehat{o}]=\frac{1}{N_{\ell}}\operatorname{Var}[\widehat{o}_{x,U}] \\
&=\frac{1}{N_{\ell}}\left(\mathbb{E}[\widehat{o}_{x,U}^{2}]-p_x^2\operatorname{Tr}(O\psi_x)^2\right) \\
&=\frac{1}{N_{\ell}}\left(\frac{p_x}{S_{\ell}}\mathbb{E}_{U,b}\left[\operatorname{Tr}(O\widehat{\rho}_{U,b})^2\right]+\frac{p_x^2(S_{\ell}-1)}{S_{\ell}}\mathbb{E}_{U,b,c}\left[\operatorname{Tr}(O\widehat{\rho}_{U,b})\operatorname{Tr}(O\widehat{\rho}_{U,c})\right]-p_x^2\operatorname{Tr}(O\psi_x)^2\right) \\
&=\frac{1}{N_{\ell}}\left(\frac{p_x}{S_{\ell}}\operatorname{Var}_{U,b}\left[\operatorname{Tr}(O\widehat{\rho}_{U,b})\right]+\frac{p_x(1-p_x)}{S_{\ell}}\operatorname{Tr}(O\psi_x)^2+\frac{p_x^2(S_{\ell}-1)}{S_{\ell}}\left(\mathbb{E}_{U,b,c}\left[\operatorname{Tr}(O\widehat{\rho}_{U,b})\operatorname{Tr}(O\widehat{\rho}_{U,c})\right]-\operatorname{Tr}(O\psi_x)^2\right)\right),
\end{aligned} Var [ o ] = N ℓ 1 Var [ o x , U ] = N ℓ 1 ( E [ o x , U 2 ] − p x 2 Tr ( O ψ x ) 2 ) = N ℓ 1 ( S ℓ p x E U , b [ Tr ( O ρ U , b ) 2 ] + S ℓ p x 2 ( S ℓ − 1 ) E U , b , c [ Tr ( O ρ U , b ) Tr ( O ρ U , c ) ] − p x 2 Tr ( O ψ x ) 2 ) = N ℓ 1 ( S ℓ p x Var U , b [ Tr ( O ρ U , b ) ] + S ℓ p x ( 1 − p x ) Tr ( O ψ x ) 2 + S ℓ p x 2 ( S ℓ − 1 ) ( E U , b , c [ Tr ( O ρ U , b ) Tr ( O ρ U , c ) ] − Tr ( O ψ x ) 2 ) ) ,
where b , c b,c b , c are independent outcomes of measuring ψ x \psi_x ψ x conditional on U U U . By Lemma 3.6,
E U , b , c [ Tr ( O ρ ^ U , b ) Tr ( O ρ ^ U , c ) ] − Tr ( O ψ x ) 2 ≤ Var U , b [ Tr ( O ρ ^ U , b ) ] . \mathbb{E}_{U,b,c}\left[\operatorname{Tr}(O\widehat{\rho}_{U,b})\operatorname{Tr}(O\widehat{\rho}_{U,c})\right]-\operatorname{Tr}(O\psi_x)^2\leq\operatorname{Var}_{U,b}\left[\operatorname{Tr}(O\widehat{\rho}_{U,b})\right]. E U , b , c [ Tr ( O ρ U , b ) Tr ( O ρ U , c ) ] − Tr ( O ψ x ) 2 ≤ Var U , b [ Tr ( O ρ U , b ) ] .
Applying Lemma 3.8 and Tr ( O ψ x ) 2 ≤ ∥ O ∥ F 2 \operatorname{Tr}(O\psi_x)^2 \le\lVert O\rVert_F^2 Tr ( O ψ x ) 2 ≤ ∥ O ∥ F 2 gives
Var [ o ^ ] ≤ C ∥ O ∥ F 2 N ℓ ( p x 2 ( S ℓ − 1 ) S ℓ + p x S ℓ ) ≤ C ∥ O ∥ F 2 N ℓ ( p x 2 + p x S ℓ ) . \begin{aligned}
\operatorname{Var}[\widehat{o}] &\le\frac{C\lVert O\rVert_F^2}{N_\ell}\left(\frac{p_x^2(S_\ell-1)}{S_\ell}+\frac{p_x}{S_\ell}\right)\\
&\le\frac{C\lVert O\rVert_F^2}{N_\ell}\left(p_x^2+\frac{p_x}{S_\ell}\right).
\end{aligned} Var [ o ] ≤ N ℓ C ∥ O ∥ F 2 ( S ℓ p x 2 ( S ℓ − 1 ) + S ℓ p x ) ≤ N ℓ C ∥ O ∥ F 2 ( p x 2 + S ℓ p x ) .
Corollary 5.10 (Complex observables). Fix x ∈ { 0 , 1 } ℓ x \in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ . For any observable O ∈ L ( H 2 n − ℓ ) O \in\mathcal{L}(\mathcal{H}^{2^{n-\ell}}) O ∈ L ( H 2 n − ℓ ) on the suffix, the estimator in Eq. (21) satisfies E [ o ^ ] = p x Tr ( O ψ x ) \mathbb{E}[\widehat{o}] = p_x \operatorname{Tr}(O\psi_x) E [ o ] = p x Tr ( O ψ x ) and
E [ ∣ o ^ − p x Tr ( O ψ x ) ∣ 2 ] ≤ C ∥ O ∥ F 2 N ℓ ( p x 2 + p x S ℓ ) . \mathbb{E}\left[\left|\widehat{o}-p_x\operatorname{Tr}(O\psi_x)\right|^2\right]\le\frac{C\lVert O\rVert_F^2}{N_\ell}\left(p_x^2+\frac{p_x}{S_\ell}\right). E [ ∣ o − p x Tr ( O ψ x ) ∣ 2 ] ≤ N ℓ C ∥ O ∥ F 2 ( p x 2 + S ℓ p x ) .
Estimating B x B_x B x
Define
O 0 : = ∣ q 0 ⟩ ⟨ q 0 ∣ , O 1 : = ∣ q 1 ⟩ ⟨ q 0 ∣ , O_0 := |q_0\rangle\langle q_0|,\quad O_1 := |q_1\rangle\langle q_0|, O 0 := ∣ q 0 ⟩ ⟨ q 0 ∣ , O 1 := ∣ q 1 ⟩ ⟨ q 0 ∣ ,
O 2 : = ∣ q 0 ⟩ ⟨ q 1 ∣ , O 3 : = ∣ q 1 ⟩ ⟨ q 1 ∣ . O_2 := |q_0\rangle\langle q_1|,\quad O_3 := |q_1\rangle\langle q_1|. O 2 := ∣ q 0 ⟩ ⟨ q 1 ∣ , O 3 := ∣ q 1 ⟩ ⟨ q 1 ∣.
Using the estimator in Eq. (21) , define
B ^ x : = ( o ^ ( O 0 ) o ^ ( O 1 ) o ^ ( O 2 ) o ^ ( O 3 ) ) . (22) \widehat{B}_x := \begin{pmatrix}\widehat{o}(O_0) & \widehat{o}(O_1) \\ \widehat{o}(O_2) & \widehat{o}(O_3)\end{pmatrix}. \tag*{(22)} B x := ( o ( O 0 ) o ( O 2 ) o ( O 1 ) o ( O 3 ) ) . (22)
This matrix is an unbiased estimator of B x B_x B x . All four estimates use the same measurement data at level ℓ \ell ℓ . Since the shadow estimators are Hermitian and O 2 = O 1 † O_2=O_1^\dagger O 2 = O 1 † , the resulting matrix B ^ x \widehat{B}_x B x is Hermitian.
Diagonalize the 2 × 2 2\times2 2 × 2 matrix B ^ x \widehat{B}_x B x , and let α ^ = ( α ^ 0 , α ^ 1 ) T \widehat{\alpha}=(\widehat{\alpha}_0,\widehat{\alpha}_1)^{\mathsf{T}} α = ( α 0 , α 1 ) T be a normalized eigenvector corresponding to its largest eigenvalue. If this eigenvalue is repeated, choose any normalized vector in its eigenspace. We use α ^ \widehat{\alpha} α as an estimate of α \alpha α and define the normalized parent estimate by
∣ ψ ^ x ⟩ : = ∣ q α ^ ⟩ = α ^ 0 ∣ 0 ⟩ ⊗ ∣ ψ ^ x 0 ⟩ + α ^ 1 ∣ 1 ⟩ ⊗ ∣ ψ ^ x 1 ⟩ . (23) |\widehat{\psi}_x\rangle:= |q_{\widehat{\alpha}}\rangle= \widehat{\alpha}_0 |0\rangle\otimes|\widehat{\psi}_{x0}\rangle+\widehat{\alpha}_1 |1\rangle\otimes|\widehat{\psi}_{x1}\rangle. \tag*{(23)} ∣ ψ x ⟩ := ∣ q α ⟩ = α 0 ∣0 ⟩ ⊗ ∣ ψ x 0 ⟩ + α 1 ∣1 ⟩ ⊗ ∣ ψ x 1 ⟩ . (23)
When B ^ x = B x \widehat{B}_x=B_x B x = B x , Corollary 5.7 shows that this reconstruction inherits only errors from its child nodes. The following lemma bounds the additional error caused by estimating B x B_x B x .
Lemma 5.11 (Error propagation at a node). For every node x x x , normalized child estimates ∣ ψ ^ x 0 ⟩ , ∣ ψ ^ x 1 ⟩ |\widehat{\psi}_{x0}\rangle,|\widehat{\psi}_{x1}\rangle ∣ ψ x 0 ⟩ , ∣ ψ x 1 ⟩ , and Hermitian estimate B ^ x \widehat{B}_x B x , the reconstruction above satisfies
p x ( 1 − ∣ ⟨ ψ x ∣ ψ ^ x ⟩ ∣ 2 ) ≤ p x 0 ( 1 − ∣ ⟨ ψ x 0 ∣ ψ ^ x 0 ⟩ ∣ 2 ) + p x 1 ( 1 − ∣ ⟨ ψ x 1 ∣ ψ ^ x 1 ⟩ ∣ 2 ) ⏟ Error from the child nodes + 2 ∥ B ^ x − B x ∥ op ⏟ Error at the current node . \begin{aligned}
p_x\left(1-\left|\langle\psi_x|\widehat{\psi}_x\rangle\right|^2\right)
&\le\underbrace{p_{x0}\left(1-\left|\langle\psi_{x0}|\widehat{\psi}_{x0}\rangle\right|^2\right)+p_{x1}\left(1-\left|\langle\psi_{x1}|\widehat{\psi}_{x1}\rangle\right|^2\right)}_{\text{Error from the child nodes}}\\
&\quad+\underbrace{2\lVert\widehat{B}_x-B_x\rVert_{\operatorname{op}}}_{\text{Error at the current node}}.
\end{aligned} p x ( 1 − ⟨ ψ x ∣ ψ x ⟩ 2 ) ≤ Error from the child nodes p x 0 ( 1 − ⟨ ψ x 0 ∣ ψ x 0 ⟩ 2 ) + p x 1 ( 1 − ⟨ ψ x 1 ∣ ψ x 1 ⟩ 2 ) + Error at the current node 2 ∥ B x − B x ∥ op .
Proof. Set E x : = B ^ x − B x E_x:=\widehat{B}_x-B_x E x := B x − B x . Then
p x ( 1 − ∣ ⟨ ψ x ∣ ψ ^ x ⟩ ∣ 2 ) = p x ( 1 − ∣ ⟨ ψ x ∣ q α ^ ⟩ ∣ 2 ) p_x\left(1-\left|\langle\psi_x|\widehat{\psi}_x\rangle\right|^2\right)=p_x\left(1-\left|\langle\psi_x|q_{\widehat{\alpha}}\rangle\right|^2\right) p x ( 1 − ⟨ ψ x ∣ ψ x ⟩ 2 ) = p x ( 1 − ∣ ⟨ ψ x ∣ q α ⟩ ∣ 2 )
(by Eq. (23) )
= p x − α ^ † B x α ^ =p_x-\widehat{\alpha}^{\dagger}B_x\widehat{\alpha} = p x − α † B x α
(by Lemma 5.6)
= p x − α † B x α + α † B x α − α ^ † B x α ^ = p x − α † B x α + α † B ^ x α − α † E x α − α ^ † B x α ^ ≤ p x − α † B x α + α ^ † B ^ x α ^ − α † E x α − α ^ † B x α ^ (by maximality of α ^ ) = p x − α † B x α + α ^ † E x α ^ − α † E x α ≤ p x − α † B x α + 2 ∥ E x ∥ o p (since ∥ α ∥ 2 = ∥ α ^ ∥ 2 = 1 ) = ∑ b ∈ { 0 , 1 } p x b ( 1 − ∣ ⟨ ψ x b ∣ ψ ^ x b ⟩ ∣ 2 ) + 2 ∥ B ^ x − B x ∥ o p . (by Corollary 5.7) \begin{aligned}
= p_x-\alpha^\dagger B_x\alpha+\alpha^\dagger B_x\alpha-\widehat{\alpha}^\dagger B_x\widehat{\alpha} \\
&= p_x-\alpha^\dagger B_x\alpha+\alpha^\dagger\widehat{B}_x\alpha-\alpha^\dagger E_x\alpha-\widehat{\alpha}^\dagger B_x\widehat{\alpha} \\
&\le p_x-\alpha^\dagger B_x\alpha+\widehat{\alpha}^\dagger\widehat{B}_x\widehat{\alpha}-\alpha^\dagger E_x\alpha-\widehat{\alpha}^\dagger B_x\widehat{\alpha}\qquad\text{(by maximality of }\widehat{\alpha}\text{)} \\
&= p_x-\alpha^\dagger B_x\alpha+\widehat{\alpha}^\dagger E_x\widehat{\alpha}-\alpha^\dagger E_x\alpha\\
&\le p_x-\alpha^\dagger B_x\alpha+2\lVert E_x\rVert_{\mathrm{op}}\qquad\text{(since }\lVert\alpha\rVert_2=\lVert\widehat{\alpha}\rVert_2=1\text{)} \\
&= \sum_{b\in\{0,1\}}p_{xb}\left(1-\left|\langle\psi_{xb}\mid\widehat{\psi}_{xb}\rangle\right|^2\right)+2\lVert\widehat{B}_x-B_x\rVert_{\mathrm{op}}.
\qquad\text{(by Corollary 5.7)}
\end{aligned} = p x − α † B x α + α † B x α − α † B x α = p x − α † B x α + α † B x α − α † E x α − α † B x α ≤ p x − α † B x α + α † B x α − α † E x α − α † B x α (by maximality of α ) = p x − α † B x α + α † E x α − α † E x α ≤ p x − α † B x α + 2 ∥ E x ∥ op (since ∥ α ∥ 2 = ∥ α ∥ 2 = 1 ) = b ∈ { 0 , 1 } ∑ p x b ( 1 − ⟨ ψ x b ∣ ψ x b ⟩ 2 ) + 2 ∥ B x − B x ∥ op . (by Corollary 5.7)
Lemma 5.12. For every node x ∈ { 0 , 1 } ℓ x\in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ and fixed child estimates, the expectation over the independent measurement data at level ℓ \ell ℓ satisfies
E [ B ^ x ] = B x \mathbb{E}[\widehat{B}_x]=B_x E [ B x ] = B x and
E [ ∥ B ^ x − B x ∥ F 2 ] ≤ 4 C N ℓ ( p x 2 + p x S ℓ ) . \mathbb{E}\left[\lVert\widehat{B}_x-B_x\rVert_F^2\right]\le\frac{4C}{N_\ell}\left(p_x^2+\frac{p_x}{S_\ell}\right). E [ ∥ B x − B x ∥ F 2 ] ≤ N ℓ 4 C ( p x 2 + S ℓ p x ) .
Proof. With the child estimates held fixed, the observables O 0 , … , O 3 O_0,\ldots,O_3 O 0 , … , O 3 are fixed and satisfy ∥ O j ∥ F = 1 \lVert O_j\rVert_F=1 ∥ O j ∥ F = 1 . By the definitions of B x B_x B x and B ^ x \widehat{B}_x B x , Corollary 5.10 applied entrywise gives E [ B ^ x ] = B x \mathbb{E}[\widehat{B}_x]=B_x E [ B x ] = B x . Moreover,
E [ ∥ B ^ x − B x ∥ F 2 ] = ∑ j = 0 3 E [ ∣ o ^ ( O j ) − p x Tr ( O j ψ x ) ∣ 2 ] ≤ C N ℓ ( p x 2 + p x S ℓ ) ∑ j = 0 3 ∥ O j ∥ F 2 (by Corollary 5.10) = 4 C N ℓ ( p x 2 + p x S ℓ ) . \begin{aligned}
\mathbb{E}\left[\lVert\widehat{B}_x-B_x\rVert_F^2\right]
=\sum_{j=0}^{3}\mathbb{E}\left[\left|\widehat{o}(O_j)-p_x\operatorname{Tr}(O_j\psi_x)\right|^2\right] \\
&\le\frac{C}{N_\ell}\left(p_x^2+\frac{p_x}{S_\ell}\right)\sum_{j=0}^{3}\lVert O_j\rVert_F^2
\qquad\text{(by Corollary 5.10)} \\
&=\frac{4C}{N_\ell}\left(p_x^2+\frac{p_x}{S_\ell}\right).
\end{aligned} E [ ∥ B x − B x ∥ F 2 ] = j = 0 ∑ 3 E [ ∣ o ( O j ) − p x Tr ( O j ψ x ) ∣ 2 ] ≤ N ℓ C ( p x 2 + S ℓ p x ) j = 0 ∑ 3 ∥ O j ∥ F 2 (by Corollary 5.10) = N ℓ 4 C ( p x 2 + S ℓ p x ) .
Corollary 5.13 (Expected reconstruction error). For the recursive reconstruction above,
E [ 1 − ∣ ⟨ ψ ∣ ψ ^ ∅ ⟩ ∣ 2 ] ≤ 4 C ∑ ℓ = 0 n − 1 ( 1 N ℓ + 2 ℓ N ℓ S ℓ ) . \mathbb{E}\left[1-\left|\langle\psi\mid\widehat{\psi}_{\emptyset}\rangle\right|^2\right]
\le4\sqrt{C}\sum_{\ell=0}^{n-1}\left(\frac{1}{\sqrt{N_\ell}}+\sqrt{\frac{2^\ell}{N_\ell S_\ell}}\right). E [ 1 − ⟨ ψ ∣ ψ ∅ ⟩ 2 ] ≤ 4 C ℓ = 0 ∑ n − 1 N ℓ 1 + N ℓ S ℓ 2 ℓ .
Proof. For each level ℓ \ell ℓ , summing Lemma 5.11 over x ∈ { 0 , 1 } ℓ x\in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ gives
∑ x ∈ { 0 , 1 } ℓ p x ( 1 − ∣ ⟨ ψ x ∣ ψ ^ x ⟩ ∣ 2 ) ≤ ∑ x ∈ { 0 , 1 } ℓ ∑ b ∈ { 0 , 1 } p x b ( 1 − ∣ ⟨ ψ x b ∣ ψ ^ x b ⟩ ∣ 2 ) + 2 ∑ x ∈ { 0 , 1 } ℓ ∥ B ^ x − B x ∥ o p = ∑ y ∈ { 0 , 1 } ℓ + 1 p y ( 1 − ∣ ⟨ ψ y ∣ ψ ^ y ⟩ ∣ 2 ) + 2 ∑ x ∈ { 0 , 1 } ℓ ∥ B ^ x − B x ∥ o p . \begin{aligned}
\sum_{x\in\{0,1\}^{\ell}}p_x\left(1-\left|\langle\psi_x\mid\widehat{\psi}_x\rangle\right|^2\right) \\
&\le\sum_{x\in\{0,1\}^{\ell}}\sum_{b\in\{0,1\}}p_{xb}\left(1-\left|\langle\psi_{xb}\mid\widehat{\psi}_{xb}\rangle\right|^2\right)
+2\sum_{x\in\{0,1\}^{\ell}}\lVert\widehat{B}_x-B_x\rVert_{\mathrm{op}} \\
&=\sum_{y\in\{0,1\}^{\ell+1}}p_y\left(1-\left|\langle\psi_y\mid\widehat{\psi}_y\rangle\right|^2\right)
+2\sum_{x\in\{0,1\}^{\ell}}\lVert\widehat{B}_x-B_x\rVert_{\mathrm{op}}.
\end{aligned} x ∈ { 0 , 1 } ℓ ∑ p x ( 1 − ⟨ ψ x ∣ ψ x ⟩ 2 ) ≤ x ∈ { 0 , 1 } ℓ ∑ b ∈ { 0 , 1 } ∑ p x b ( 1 − ⟨ ψ x b ∣ ψ x b ⟩ 2 ) + 2 x ∈ { 0 , 1 } ℓ ∑ ∥ B x − B x ∥ op = y ∈ { 0 , 1 } ℓ + 1 ∑ p y ( 1 − ⟨ ψ y ∣ ψ y ⟩ 2 ) + 2 x ∈ { 0 , 1 } ℓ ∑ ∥ B x − B x ∥ op .
Summing over ℓ = 0 , … , n − 1 \ell=0,\ldots,n-1 ℓ = 0 , … , n − 1 gives a telescoping sum, in which the errors at levels 1 , … , n − 1 1,\ldots,n-1 1 , … , n − 1 cancel. At the leaves (ℓ = n \ell=n ℓ = n ), no qubits remain to be reconstructed, so their errors are zero. At the root (ℓ = 0 \ell=0 ℓ = 0 ), p ∅ = 1 p_{\varnothing}=1 p ∅ = 1 and ∣ ψ ∅ ⟩ = ∣ ψ ⟩ |\psi_{\varnothing}\rangle=|\psi\rangle ∣ ψ ∅ ⟩ = ∣ ψ ⟩ . We therefore obtain
1 − ∣ ⟨ ψ ∣ ψ ^ ∅ ⟩ ∣ 2 ≤ 2 ∑ ℓ = 0 n − 1 ∑ x ∈ { 0 , 1 } ℓ ∥ B ^ x − B x ∥ o p . 1-\left|\langle\psi|\widehat{\psi}_{\varnothing}\rangle\right|^2\le2\sum_{\ell=0}^{n-1}\sum_{x\in\{0,1\}^{\ell}}\|\widehat{B}_x-B_x\|_{\mathrm{op}}. 1 − ⟨ ψ ∣ ψ ∅ ⟩ 2 ≤ 2 ℓ = 0 ∑ n − 1 x ∈ { 0 , 1 } ℓ ∑ ∥ B x − B x ∥ op .
Taking expectations and applying Lemmas 3.10 and 5.12 , together with ∑ x p x = 1 \sum_x p_x=1 ∑ x p x = 1 , we obtain
E [ 1 − ∣ ⟨ ψ ∣ ψ ^ ∅ ⟩ ∣ 2 ] ≤ 2 ∑ ℓ = 0 n − 1 ∑ x ∈ { 0 , 1 } ℓ E ∥ B ^ x − B x ∥ o p ≤ 2 ∑ ℓ = 0 n − 1 ∑ x ∈ { 0 , 1 } ℓ E ∥ B ^ x − B x ∥ F 2 (by xref‘Lemma 3.10‘) ≤ 4 C ∑ ℓ = 0 n − 1 1 N ℓ ∑ x ∈ { 0 , 1 } ℓ p x 2 + p x S ℓ ≤ 4 C ∑ ℓ = 0 n − 1 ( 1 N ℓ + ∑ x ∈ { 0 , 1 } ℓ p x N ℓ S ℓ ) ≤ 4 C ∑ ℓ = 0 n − 1 ( 1 N ℓ + 2 ℓ N ℓ S ℓ ) . ( by ∑ x ∈ { 0 , 1 } ℓ p x ≤ 2 ℓ / 2 ) \begin{aligned}
\mathbb{E}\left[1-\left|\langle\psi|\widehat{\psi}_{\varnothing}\rangle\right|^2\right]
&\le2\sum_{\ell=0}^{n-1}\sum_{x\in\{0,1\}^{\ell}}\mathbb{E}\|\widehat{B}_x-B_x\|_{\mathrm{op}}\\
&\le2\sum_{\ell=0}^{n-1}\sum_{x\in\{0,1\}^{\ell}}\sqrt{\mathbb{E}\|\widehat{B}_x-B_x\|_{\mathrm{F}}^2}
\qquad\text{(by {xref}`Lemma 3.10`)}\\
&\le4\sqrt{C}\sum_{\ell=0}^{n-1}\frac{1}{\sqrt{N_\ell}}\sum_{x\in\{0,1\}^{\ell}}\sqrt{p_x^2+\frac{p_x}{S_\ell}}\\
&\le4\sqrt{C}\sum_{\ell=0}^{n-1}\left(\frac{1}{\sqrt{N_\ell}}+\frac{\sum_{x\in\{0,1\}^{\ell}}\sqrt{p_x}}{\sqrt{N_\ell S_\ell}}\right)\\
&\le4\sqrt{C}\sum_{\ell=0}^{n-1}\left(\frac{1}{\sqrt{N_\ell}}+\sqrt{\frac{2^\ell}{N_\ell S_\ell}}\right).
\qquad\left(\text{by }\sum_{x\in\{0,1\}^{\ell}}\sqrt{p_x}\le2^{\ell/2}\right)
\end{aligned} E [ 1 − ⟨ ψ ∣ ψ ∅ ⟩ 2 ] ≤ 2 ℓ = 0 ∑ n − 1 x ∈ { 0 , 1 } ℓ ∑ E ∥ B x − B x ∥ op ≤ 2 ℓ = 0 ∑ n − 1 x ∈ { 0 , 1 } ℓ ∑ E ∥ B x − B x ∥ F 2 (by xref ‘Lemma 3.10‘) ≤ 4 C ℓ = 0 ∑ n − 1 N ℓ 1 x ∈ { 0 , 1 } ℓ ∑ p x 2 + S ℓ p x ≤ 4 C ℓ = 0 ∑ n − 1 ( N ℓ 1 + N ℓ S ℓ ∑ x ∈ { 0 , 1 } ℓ p x ) ≤ 4 C ℓ = 0 ∑ n − 1 N ℓ 1 + N ℓ S ℓ 2 ℓ . by x ∈ { 0 , 1 } ℓ ∑ p x ≤ 2 ℓ /2
We now combine the preceding bounds to prove Theorem 5.1 .
Proof of Theorem 5.1 . Let K > 0 K>0 K > 0 be a constant to be chosen later, and set
N ℓ : = ⌈ K n 2 ⌉ , S ℓ : = ⌈ K d 2 2 ℓ / 3 N ℓ ⌉ , ℓ = 0 , … , n − 1. N_\ell:=\lceil K n^2\rceil,\qquad S_\ell:=\left\lceil\frac{K d^2 2^{\ell/3}}{N_\ell}\right\rceil,\qquad\ell=0,\ldots,n-1. N ℓ := ⌈ K n 2 ⌉ , S ℓ := ⌈ N ℓ K d 2 2 ℓ /3 ⌉ , ℓ = 0 , … , n − 1.
Let ∣ σ 0 ⟩ : = ∣ ψ ^ ∅ ⟩ |\sigma_0\rangle:=|\widehat{\psi}_{\varnothing}\rangle ∣ σ 0 ⟩ := ∣ ψ ∅ ⟩ . By Corollary 5.13,
E [ 1 − ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ] ≤ 4 C K ( 1 + d − 1 / 3 ∑ ℓ = 0 n − 1 2 ℓ / 3 ) \mathbb{E}\left[1-\left|\langle\psi|\sigma_0\rangle\right|^2\right]\le4\sqrt{\frac{C}{K}}\left(1+d^{-1/3}\sum_{\ell=0}^{n-1}2^{\ell/3}\right) E [ 1 − ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ] ≤ 4 K C ( 1 + d − 1/3 ℓ = 0 ∑ n − 1 2 ℓ /3 )
≤ 4 C K ( 1 + 1 2 1 / 3 − 1 ) ≤ 1 24 , \le4\sqrt{\frac{C}{K}}\left(1+\frac{1}{2^{1/3}-1}\right)\le\frac{1}{24}, ≤ 4 K C ( 1 + 2 1/3 − 1 1 ) ≤ 24 1 ,
where the last inequality holds for a sufficiently large constant K = O ( C ) K=O(C) K = O ( C ) . Applying Lemma 3.9 gives
Pr [ 1 − ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 > 1 2 ] ≤ 2 E [ 1 − ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ] ≤ 1 12 . \Pr\left[1-\left|\langle\psi|\sigma_0\rangle\right|^2>\frac{1}{2}\right]\le2\mathbb{E}\left[1-\left|\langle\psi|\sigma_0\rangle\right|^2\right]\le\frac{1}{12}. Pr [ 1 − ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 > 2 1 ] ≤ 2 E [ 1 − ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ] ≤ 12 1 .
Thus the required overlap holds with probability at least 11 12 \frac{11}{12} 12 11 , and the output is normalized by construction.
The number of sampled bases is ∑ ℓ = 0 n − 1 N ℓ = O ( n 3 ) \sum_{\ell=0}^{n-1}N_\ell=O(n^3) ∑ ℓ = 0 n − 1 N ℓ = O ( n 3 ) and the total copy count is
∑ ℓ = 0 n − 1 N ℓ S ℓ = O ( d 2 / 3 ∑ ℓ = 0 n − 1 2 ℓ / 3 ) = O ( d ) . \sum_{\ell=0}^{n-1}N_\ell S_\ell=O\left(d^{2/3}\sum_{\ell=0}^{n-1}2^{\ell/3}\right)=O(d). ℓ = 0 ∑ n − 1 N ℓ S ℓ = O ( d 2/3 ℓ = 0 ∑ n − 1 2 ℓ /3 ) = O ( d ) .
All bases and shot counts are chosen before observing any outcomes, so the protocol is nonadaptive and single-copy. Its depth is O ( log n ) O(\log n) O ( log n ) by the assumed properties of the suffix unitary ensembles.
Classical post–processing
We assume that the experimental measurement results are provided as an outcome histogram for each measurement basis. Given these histograms, both initialization of ∣ σ 0 ⟩ |\sigma_0\rangle ∣ σ 0 ⟩ and shadow bootstrapping can be performed in O ~ ( d ) \widetilde{O}(d) O ( d ) time and working memory. We first establish the computational primitives used by both procedures.
Lemma 6.1 (Clifford circuit application). For a measurement circuit U U U in our two-layer Clifford ensemble and any x ∈ C d x\in\mathbb{C}^d x ∈ C d , both U x Ux U x and U † x U^\dagger x U † x can be computed in O ( d n log n ) O(dn\log n) O ( d n log n ) time and O ( d ) O(d) O ( d ) working storage.
Proof. We implement each k k k -qubit Clifford block by an O ( k ) O(k) O ( k ) -depth circuit over { H , S , C X } \{H,S,\mathrm{CX}\} { H , S , CX } . Each circuit layer contains at most k k k gates, so each block uses O ( k 2 ) O(k^2) O ( k 2 ) gates [28 ] . The two-layer ensemble has n / k n/k n / k blocks per layer. With our choice k = Θ ( log n ) k=\Theta(\log n) k = Θ ( log n ) , the total gate count is
2 n k O ( k 2 ) = O ( n k ) = O ( n log n ) . \frac{2n}{k}O(k^2)=O(nk)=O(n\log n). k 2 n O ( k 2 ) = O ( nk ) = O ( n log n ) . For a dense vector x ∈ C d x\in\mathbb{C}^d x ∈ C d , an H H H gate applies a fixed 2 × 2 2\times2 2 × 2 transformation to each of d / 2 d/2 d /2 amplitude pairs differing only in the target bit. An S S S gate multiplies the d / 2 d/2 d /2 amplitudes whose target bit is 1 by i i i . A C X \mathrm{CX} CX gate swaps d / 4 d/4 d /4 amplitude pairs whose control bit is 1 and whose target bits differ. Each gate therefore costs O ( d ) O(d) O ( d ) arithmetic operations. Applying all O ( n log n ) O(n\log n) O ( n log n ) gates costs O ( d n log n ) O(dn\log n) O ( d n log n ) . The same argument applies to the inverse circuit U † U^\dagger U † . All updates can be performed in place, so O ( d ) O(d) O ( d ) working storage suffices.
Lemma 6.2 (Exact visibility evaluation). For a measurement circuit U U U in our two-layer Clifford ensemble and a Pauli operator P P P , the visibility m U † P U m_{U^\dagger P U} m U † P U can be computed in O ( n log n ) O(n\log n) O ( n log n ) time and O ( n ) O(n) O ( n ) working storage.
Proof. Our two-layer Clifford circuit contains O ( n log n ) O(n\log n) O ( n log n ) gates from { H , S , C X } \{H,S,\mathrm{CX}\} { H , S , CX } . Conjugation by H H H or S S S updates one Pauli factor, while conjugation by C X \mathrm{CX} CX updates at most two. Each update therefore takes O ( 1 ) O(1) O ( 1 ) time, and the same holds for the adjoint gates. Thus, the Pauli label of U † P U U^\dagger P U U † P U can be computed in O ( n log n ) O(n\log n) O ( n log n ) time and O ( n ) O(n) O ( n ) working storage. We ignore the overall sign since it does not affect the visibility.
Next, by Lemma 3.3 , the support of a Pauli string on the blocks of the first layer can be determined in O ( n ) O(n) O ( n ) time. Its visibility is then obtained by multiplying n / k n/k n / k matrices of size 2 × 2 2\times2 2 × 2 , requiring O ( n / k ) O(n/k) O ( n / k ) arithmetic operations. Together with the Pauli conjugation step, this gives O ( n log n ) O(n\log n) O ( n log n ) time and O ( n ) O(n) O ( n ) working memory.
Lemma 6.3 (Shadow action). Let M \mathcal{M} M be the shadow channel of our two-layer Clifford ensemble. Given a measurement circuit U U U and vectors h = ( h z ) z , x ∈ C d h=(h_z)_z,x\in\mathbb{C}^d h = ( h z ) z , x ∈ C d , the vector
[ ∑ z h z M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) ] x ∈ C d \left[\sum_z h_z\mathcal{M}^{-1}\left(U^\dagger|z\rangle\langle z|U\right)\right]x\in\mathbb{C}^d [ z ∑ h z M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) ] x ∈ C d
can be computed in O ~ ( d ) \widetilde{O}(d) O ( d ) time and O ~ ( d ) \widetilde{O}(d) O ( d ) working memory. Proof. For a ∈ { 0 , 1 } n a \in\{0,1\}^{n} a ∈ { 0 , 1 } n , write Z a : = ⨂ j = 1 n Z a j Z^{a} := \bigotimes_{j=1}^{n} Z^{a_j} Z a := ⨂ j = 1 n Z a j and Z : = { Z a : a ∈ { 0 , 1 } n } \mathcal{Z} := \{Z^{a} : a \in\{0,1\}^{n}\} Z := { Z a : a ∈ { 0 , 1 } n } . Since Z a ∣ z ⟩ = ( − 1 ) a ⋅ z ∣ z ⟩ Z^{a}|z\rangle= (-1)^{a\cdot z}|z\rangle Z a ∣ z ⟩ = ( − 1 ) a ⋅ z ∣ z ⟩ , for any v ∈ C d v \in\mathbb{C}^{d} v ∈ C d ,
∑ a v a Z a = ∑ z ( ∑ a ( − 1 ) a ⋅ z v a ) ∣ z ⟩ ⟨ z ∣ = diag ( W H − 1 ( v ) ) , \sum_{a} v_a Z^a = \sum_z \left(\sum_a (-1)^{a\cdot z}v_a\right)|z\rangle\langle z| = \operatorname{diag}(\mathrm{WH}^{-1}(v)), a ∑ v a Z a = z ∑ ( a ∑ ( − 1 ) a ⋅ z v a ) ∣ z ⟩ ⟨ z ∣ = diag ( WH − 1 ( v )) ,
where diag ( v ) \operatorname{diag}(v) diag ( v ) denotes the diagonal matrix whose diagonal entries are the components of v v v . Using the Pauli expansion and M − 1 ( P ) = m P − 1 P \mathcal{M}^{-1}(P) = m_P^{-1}P M − 1 ( P ) = m P − 1 P , we obtain
∑ z h z M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) = 1 d ∑ z ∑ P h z m P − 1 Tr ( U P U † ∣ z ⟩ ⟨ z ∣ ) P = 1 d ∑ z ∑ P : U P U † = ± Z a h z m P − 1 Tr ( U P U † ∣ z ⟩ ⟨ z ∣ ) P = 1 d ∑ z ∑ a h z m U † Z a U − 1 ( − 1 ) a ⋅ z U † Z a U = U † ( ∑ a m U † Z a U − 1 U † Z a U [ 1 d ∑ z ( − 1 ) a ⋅ z h z ] Z a ) U = U † ( ∑ a m U † Z a U − 1 W H ( h ) a Z a ) U = U † ( ∑ a μ a Z a ) U = U † diag ( W H − 1 ( μ ) ) U , \begin{aligned}
\sum_z h_z\mathcal{M}^{-1}\left(U^\dagger|z\rangle\langle z|U\right)
&= \frac{1}{d}\sum_z\sum_P h_zm_P^{-1}\operatorname{Tr}\left(UPU^\dagger|z\rangle\langle z|\right)P\\
&= \frac{1}{d}\sum_z\sum_{P:UPU^\dagger=\pm Z^a}h_zm_P^{-1}\operatorname{Tr}\left(UPU^\dagger|z\rangle\langle z|\right)P\\
&= \frac{1}{d}\sum_z\sum_a h_zm_{U^\dagger Z^aU}^{-1}(-1)^{a\cdot z}U^\dagger Z^aU\\
&= U^\dagger\left(\sum_a m_{U^\dagger Z^aU}^{-1}U^\dagger Z^aU\left[\frac{1}{d}\sum_z(-1)^{a\cdot z}h_z\right]Z^a\right)U\\
&= U^\dagger\left(\sum_a m_{U^\dagger Z^aU}^{-1}\mathrm{WH}(h)_aZ^a\right)U\\
&= U^\dagger\left(\sum_a\mu_aZ^a\right)U\\
&= U^\dagger\operatorname{diag}(\mathrm{WH}^{-1}(\mu))U,
\end{aligned} z ∑ h z M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) = d 1 z ∑ P ∑ h z m P − 1 Tr ( U P U † ∣ z ⟩ ⟨ z ∣ ) P = d 1 z ∑ P : U P U † = ± Z a ∑ h z m P − 1 Tr ( U P U † ∣ z ⟩ ⟨ z ∣ ) P = d 1 z ∑ a ∑ h z m U † Z a U − 1 ( − 1 ) a ⋅ z U † Z a U = U † ( a ∑ m U † Z a U − 1 U † Z a U [ d 1 z ∑ ( − 1 ) a ⋅ z h z ] Z a ) U = U † ( a ∑ m U † Z a U − 1 WH ( h ) a Z a ) U = U † ( a ∑ μ a Z a ) U = U † diag ( WH − 1 ( μ )) U ,
where μ a : = m U † Z a U − 1 W H ( h ) a \mu_a := m_{U^\dagger Z^aU}^{-1}\mathrm{WH}(h)_a μ a := m U † Z a U − 1 WH ( h ) a . Here P P P ranges over unsigned Pauli operators, and we use m − P = m P m_{-P}=m_P m − P = m P . When U P U † = ± Z a UPU^\dagger=\pm Z^a U P U † = ± Z a , the signs in the trace coefficient and in P = ± U † Z a U P=\pm U^\dagger Z^aU P = ± U † Z a U cancel. First, we compute W H − 1 ( μ ) \mathrm{WH}^{-1}(\mu) WH − 1 ( μ ) . Reading h h h and performing the two fast Walsh–Hadamard transforms costs O ( d log d ) O(d\log d) O ( d log d ) time. The d d d visibility evaluations take O ~ ( d ) \widetilde{O}(d) O ( d ) total time by Lemma 6.2 . These computations use O ~ ( d ) \widetilde{O}(d) O ( d ) working memory. The required vector is
U † diag ( W H − 1 ( μ ) ) U x . (24) U^\dagger\operatorname{diag}(\mathrm{WH}^{-1}(\mu))Ux. \tag*{(24)} U † diag ( WH − 1 ( μ )) U x . (24)
By Lemma 6.1 , computing U x Ux U x and applying U † U^\dagger U † costs O ( d n log n ) O(dn\log n) O ( d n log n ) time and O ( d ) O(d) O ( d ) storage. Multiplication by the diagonal matrix uses only its d d d diagonal entries and takes O ( d ) O(d) O ( d ) time. The total time and working memory are therefore O ~ ( d ) \widetilde{O}(d) O ( d ) .
Initialization
For each x ∈ { 0 , 1 } ℓ x \in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ , we reconstruct
∣ ψ ^ x ⟩ = α ^ x 0 ∣ 0 ⟩ ⊗ ∣ ψ ^ x 0 ⟩ + α ^ x 1 ∣ 1 ⟩ ⊗ ∣ ψ ^ x 1 ⟩ . |\widehat{\psi}_x\rangle= \widehat{\alpha}_{x0}|0\rangle\otimes|\widehat{\psi}_{x0}\rangle+\widehat{\alpha}_{x1}|1\rangle\otimes|\widehat{\psi}_{x1}\rangle. ∣ ψ x ⟩ = α x 0 ∣0 ⟩ ⊗ ∣ ψ x 0 ⟩ + α x 1 ∣1 ⟩ ⊗ ∣ ψ x 1 ⟩ .
The coefficients are obtained by estimating the 2 × 2 2\times2 2 × 2 matrix B ^ x \widehat{B}_x B x and computing a normalized eigenvector corresponding to its largest eigenvalue. Each histogram has at most d d d entries, so grouping them by prefix x x x takes O ( d ) O(d) O ( d ) time. There are O ( n ℓ ) O(n^\ell) O ( n ℓ ) histograms, giving O ~ ( d ) \widetilde{O}(d) O ( d ) total time. Applying the construction of Lemma 6.3 to the inverse shadow channel M − 1 \mathcal{M}^{-1} M − 1 on the suffix, followed by inner products with ∣ q 0 ⟩ |q_0\rangle ∣ q 0 ⟩ and ∣ q 1 ⟩ |q_1\rangle ∣ q 1 ⟩ , estimates each entry of B x B_x B x in O ~ ( N ℓ 2 n − ℓ ) \widetilde{O}(N_\ell2^{n-\ell}) O ( N ℓ 2 n − ℓ ) time. Since N ℓ = O ( n 2 ) N_\ell= O(n^2) N ℓ = O ( n 2 ) , estimating and diagonalizing B ^ x \widehat{B}_x B x and constructing ∣ ψ ^ x ⟩ |\widehat{\psi}_x\rangle ∣ ψ x ⟩ take O ~ ( 2 n − ℓ ) \widetilde{O}(2^{n-\ell}) O ( 2 n − ℓ ) time per node. There are 2 ℓ 2^\ell 2 ℓ nodes at level ℓ \ell ℓ , so each level costs O ~ ( 2 n ) \widetilde{O}(2^n) O ( 2 n ) time. Repeating over ℓ = n − 1 , … , 0 \ell= n-1,\ldots,0 ℓ = n − 1 , … , 0 therefore takes O ~ ( 2 n ) = O ~ ( d ) \widetilde{O}(2^n) = \widetilde{O}(d) O ( 2 n ) = O ( d ) total time, including histogram processing.
The state vectors at each level have total length 2 ℓ 2 n − ℓ = d 2^\ell2^{n-\ell} = d 2 ℓ 2 n − ℓ = d . After reconstructing all states at level ℓ \ell ℓ , we delete the estimates at level ℓ + 1 \ell+1 ℓ + 1 from memory. Thus, only two adjacent levels need to be stored at a time, and O ~ ( d ) \widetilde{O}(d) O ( d ) working memory suffices.
Shadow Bootstrapping
At stage t t t , we compute
∣ σ ~ t ⟩ = ( σ t − 1 + 1 N t ∑ i = 1 N t Δ t , i ) ∣ σ 0 ⟩ . (25) \left|\widetilde{\sigma}_t\right\rangle= \left(\sigma_{t-1} + \frac{1}{N_t}\sum_{i=1}^{N_t}\Delta_{t,i}\right)|\sigma_0\rangle. \tag*{(25)} ∣ σ t ⟩ = ( σ t − 1 + N t 1 i = 1 ∑ N t Δ t , i ) ∣ σ 0 ⟩ . (25)
For each basis U t , i U_{t,i} U t , i , computing the predicted probabilities p z : = Tr ( U t , i σ t − 1 U t , i † ∣ z ⟩ ⟨ z ∣ ) p_z := \operatorname{Tr}(U_{t,i}\sigma_{t-1}U_{t,i}^{\dagger}|z\rangle\langle z|) p z := Tr ( U t , i σ t − 1 U t , i † ∣ z ⟩ ⟨ z ∣ ) for all z z z takes O ~ ( d ) \widetilde{O}(d) O ( d ) time by Lemma 6.1 . We then compute the weights h z : = f ^ t , i ( z ) − p z h_z := \widehat{f}_{t,i}(z) - p_z h z := f t , i ( z ) − p z in O ( d ) O(d) O ( d ) additional time. Lemma 6.3 then computes Δ t , i ∣ σ 0 ⟩ \Delta_{t,i}|\sigma_0\rangle Δ t , i ∣ σ 0 ⟩ in O ~ ( d ) \widetilde{O}(d) O ( d ) time. Computing σ t − 1 ∣ σ 0 ⟩ = ∣ σ t − 1 ⟩ ⟨ σ t − 1 ∣ σ 0 ⟩ \sigma_{t-1}|\sigma_0\rangle= |\sigma_{t-1}\rangle\langle\sigma_{t-1}|\sigma_0\rangle σ t − 1 ∣ σ 0 ⟩ = ∣ σ t − 1 ⟩ ⟨ σ t − 1 ∣ σ 0 ⟩ takes O ( d ) O(d) O ( d ) time.
The choice N t = O ( 1 ) N_t = O(1) N t = O ( 1 ) in the proof of Corollary 4.5 therefore gives O ~ ( N t d ) = O ~ ( d ) \widetilde{O}(N_t d) = \widetilde{O}(d) O ( N t d ) = O ( d ) time per stage. Since the same corollary uses J = O ( log ( 1 / ϵ ) ) J = O(\log(1/\epsilon)) J = O ( log ( 1/ ϵ )) stages, the total time is O ~ ( J d ) = O ~ ( d ) \widetilde{O}(Jd) = \widetilde{O}(d) O ( J d ) = O ( d ) .
We process the measurement bases one at a time and reuse the same memory for each basis. Only a constant number of length-d d d vectors need to be stored, so the working memory is O ~ ( d ) \widetilde{O}(d) O ( d ) .
Full Algorithm
Algorithm 1 Nonadaptive measurement schedule
Input: Copy access to an unknown n n n -qubit pure state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ ; target infidelity ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) .
Output: Initialization data D i n i t \mathcal{D}_{\mathrm{init}} D init and refinement data D r e f \mathcal{D}_{\mathrm{ref}} D ref , including circuit descriptions, shot counts, and per-basis outcome histograms.
d ← 2 n d \leftarrow2^n d ← 2 n .
Choose sufficiently large constant K K K as in the proof of Theorem 5.1 .
J ← ⌈ log 2 ( 6 / ϵ ) ⌉ J \leftarrow\lceil\log_2(6/\epsilon) \rceil J ← ⌈ log 2 ( 6/ ϵ )⌉ ▷ Corollary 4.6
for ℓ = 0 , … , n − 1 \ell= 0,\ldots,n-1 ℓ = 0 , … , n − 1 do
N ℓ ← ⌈ K n 2 ⌉ N_\ell\leftarrow\lceil K n^2\rceil N ℓ ← ⌈ K n 2 ⌉ , S ℓ ← ⌈ K d 2 / 3 2 ℓ / 3 / N ℓ ⌉ S_\ell\leftarrow\lceil K d^{2/3}2^{\ell/3}/N_\ell\rceil S ℓ ← ⌈ K d 2/3 2 ℓ /3 / N ℓ ⌉ ▷ Theorem 5.1
for i = 1 , … , N ℓ i=1,\ldots,N_\ell i = 1 , … , N ℓ do
Independently sample U ℓ , i ∼ E ℓ U_{\ell,i} \sim\mathcal{E}_\ell U ℓ , i ∼ E ℓ .
Schedule S ℓ S_\ell S ℓ shots using I 2 ℓ ⊗ U ℓ , i I_{2^\ell}\otimes U_{\ell,i} I 2 ℓ ⊗ U ℓ , i .
end for
end for
for t = 1 , … , J t=1,\ldots,J t = 1 , … , J do
N t ← ⌈ 16 ( C + 1 ) ⌉ N_t \leftarrow\lceil16(C+1)\rceil N t ← ⌈ 16 ( C + 1 )⌉ , S t ← d 2 t − 1 S_t \leftarrow d\,2^{t-1} S t ← d 2 t − 1 ▷ Corollary 4.5
for i = 1 , … , N t i=1,\ldots,N_t i = 1 , … , N t do
Independently sample U t , i ∼ E U_{t,i}\sim\mathcal{E} U t , i ∼ E .
Schedule S t S_t S t shots using U t , i U_{t,i} U t , i .
end for
end for
Execute all scheduled measurements on disjoint copies, with computational-basis readout after each circuit.
Store the initialization circuits, shot counts, and histograms f ^ ℓ , i ( x , b ) \widehat{f}_{\ell,i}(x,b) f ℓ , i ( x , b ) in D i n i t \mathcal{D}_{\mathrm{init}} D init .
Store the refinement circuits, shot counts, and histograms f ^ t , i ( z ) \widehat{f}_{t,i}(z) f t , i ( z ) in D r e f \mathcal{D}_{\mathrm{ref}} D ref .
return D i n i t , D r e f \mathcal{D}_{\mathrm{init}},\mathcal{D}_{\mathrm{ref}} D init , D ref .
Algorithm 2 Weighted shadow action
Input: A measurement circuit U U U ; weights h = ( h z ) z h=(h_z)_z h = ( h z ) z ; a vector x x x on the same register; the matched shadow channel M \mathcal{M} M .
Output: ∑ z h z M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) x \sum_z h_z\mathcal{M}^{-1}(U^\dagger|z\rangle\langle z|U)x ∑ z h z M − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) x (Lemma 6.3 ).
function ShadowAction( U , h , x , M ) (U,h,x,\mathcal{M}) ( U , h , x , M )
μ ← WH ( h ) \mu\leftarrow\operatorname{WH}(h) μ ← WH ( h ) .
for each bit string a a a on the register of U U U do
μ a ← μ a / m U † Z a U \mu_a\leftarrow\mu_a/m_{U^\dagger Z^aU} μ a ← μ a / m U † Z a U ▷ Lemma 6.2
end for
λ ← WH − 1 ( μ ) \lambda\leftarrow\operatorname{WH}^{-1}(\mu) λ ← WH − 1 ( μ ) .
y ← U x y\leftarrow Ux y ← U x .
y z ← λ z y z y_z\leftarrow\lambda_z y_z y z ← λ z y z for every z z z .
return U † y U^\dagger y U † y .
end function
Algorithm 3 Initialization
Input: Initialization data D i n i t \mathcal{D}_{\mathrm{init}} D init from Algorithm 1; suffix shadow channels { M ℓ } ℓ = 0 n − 1 \{\mathcal{M}_{\ell}\}_{\ell=0}^{n-1} { M ℓ } ℓ = 0 n − 1 (Lemma 5.4 ).
Output: A normalized initial estimate ∣ σ 0 ⟩ |\sigma_0\rangle ∣ σ 0 ⟩ (Theorem 5.1 ).
function Initialization(D i n i t , { M ℓ } ℓ = 0 n − 1 \mathcal{D}_{\mathrm{init}},\{\mathcal{M}_{\ell}\}_{\ell=0}^{n-1} D init , { M ℓ } ℓ = 0 n − 1 )
Read n n n , N ℓ N_{\ell} N ℓ , S ℓ S_{\ell} S ℓ , the circuits, and the histograms from D i n i t \mathcal{D}_{\mathrm{init}} D init .
∣ ψ ^ x ⟩ ← 1 ∈ C |\widehat{\psi}_x\rangle\leftarrow1 \in\mathbb{C} ∣ ψ x ⟩ ← 1 ∈ C for every leaf x ∈ { 0 , 1 } n x \in\{0,1\}^n x ∈ { 0 , 1 } n .
for ℓ = n − 1 , … , 0 \ell=n-1,\ldots,0 ℓ = n − 1 , … , 0 do
for x ∈ { 0 , 1 } ℓ x \in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ do
∣ q 0 ⟩ ← ∣ 0 ⟩ ⊗ ∣ ψ ^ x 0 ⟩ |q_0\rangle\leftarrow|0\rangle\otimes|\widehat{\psi}_{x0}\rangle ∣ q 0 ⟩ ← ∣0 ⟩ ⊗ ∣ ψ x 0 ⟩ , ∣ q 1 ⟩ ← ∣ 1 ⟩ ⊗ ∣ ψ ^ x 1 ⟩ |q_1\rangle\leftarrow|1\rangle\otimes|\widehat{\psi}_{x1}\rangle ∣ q 1 ⟩ ← ∣1 ⟩ ⊗ ∣ ψ x 1 ⟩ .
h i ← ( f ^ ℓ , i ( x , b ) ) b ∈ { 0 , 1 } n − ℓ h_i \leftarrow(\widehat{f}_{\ell,i}(x,b))_{b\in\{0,1\}^{n-\ell}} h i ← ( f ℓ , i ( x , b ) ) b ∈ { 0 , 1 } n − ℓ for i = 1 , … , N ℓ i=1,\ldots,N_{\ell} i = 1 , … , N ℓ .
( B ^ x ) r s ← 1 N ℓ ∑ i = 1 N ℓ ⟨ q r ∣ ShadowAction ( U ℓ , i , h i , ∣ q s ⟩ , M ℓ ) (\widehat{B}_x)_{rs} \leftarrow\frac{1}{N_{\ell}}\sum_{i=1}^{N_{\ell}}\langle q_r|\operatorname{ShadowAction}(U_{\ell,i},h_i,|q_s\rangle,\mathcal{M}_{\ell}) ( B x ) r s ← N ℓ 1 ∑ i = 1 N ℓ ⟨ q r ∣ ShadowAction ( U ℓ , i , h i , ∣ q s ⟩ , M ℓ ) for r , s ∈ { 0 , 1 } r,s\in\{0,1\} r , s ∈ { 0 , 1 } .
Choose any normalized eigenvector α ^ \widehat{\alpha} α corresponding to the largest eigenvalue of B ^ x \widehat{B}_x B x .
∣ ψ ^ x ⟩ ← α ^ 0 ∣ q 0 ⟩ + α ^ 1 ∣ q 1 ⟩ |\widehat{\psi}_x\rangle\leftarrow\widehat{\alpha}_0|q_0\rangle+\widehat{\alpha}_1|q_1\rangle ∣ ψ x ⟩ ← α 0 ∣ q 0 ⟩ + α 1 ∣ q 1 ⟩ .
end for
end for
return ∣ σ 0 ⟩ ← ∣ ψ ^ ∅ ⟩ |\sigma_0\rangle\leftarrow|\widehat{\psi}_{\varnothing}\rangle ∣ σ 0 ⟩ ← ∣ ψ ∅ ⟩ .
end function
Algorithm 4 Shadow bootstrapping
Input: Data D i n i t , D r e f \mathcal{D}_{\mathrm{init}},\mathcal{D}_{\mathrm{ref}} D init , D ref from Algorithm 1; shadow channels { M ℓ } ℓ = 0 n − 1 \{\mathcal{M}_{\ell}\}_{\ell=0}^{n-1} { M ℓ } ℓ = 0 n − 1 and M \mathcal{M} M .
Output: A normalized estimate ∣ ψ ^ ⟩ |\widehat{\psi}\rangle ∣ ψ ⟩ .
Read J J J , N t N_t N t , S t S_t S t , the circuits, and the histograms from D r e f \mathcal{D}_{\mathrm{ref}} D ref .
∣ σ 0 ⟩ ← Initialization ( D i n i t , { M ℓ } ℓ = 0 n − 1 ) |\sigma_0\rangle\leftarrow\operatorname{Initialization}(\mathcal{D}_{\mathrm{init}},\{\mathcal{M}_{\ell}\}_{\ell=0}^{n-1}) ∣ σ 0 ⟩ ← Initialization ( D init , { M ℓ } ℓ = 0 n − 1 ) .
for t = 1 , … , J t=1,\ldots,J t = 1 , … , J do
∣ σ ~ t ⟩ ← ⟨ σ t − 1 ∣ σ 0 ⟩ ∣ σ t − 1 ⟩ |\widetilde{\sigma}_t\rangle\leftarrow\langle\sigma_{t-1}|\sigma_0\rangle|\sigma_{t-1}\rangle ∣ σ t ⟩ ← ⟨ σ t − 1 ∣ σ 0 ⟩ ∣ σ t − 1 ⟩ .
for i = 1 , … , N t i=1,\ldots,N_t i = 1 , … , N t do
h z ← f ^ t , i ( z ) − Tr ( U t , i σ t − 1 U t , i † ∣ z ⟩ ⟨ z ∣ ) h_z \leftarrow\widehat{f}_{t,i}(z)-\operatorname{Tr}(U_{t,i}\sigma_{t-1}U_{t,i}^{\dagger}|z\rangle\langle z|) h z ← f t , i ( z ) − Tr ( U t , i σ t − 1 U t , i † ∣ z ⟩ ⟨ z ∣ ) for every z ∈ { 0 , 1 } n z\in\{0,1\}^n z ∈ { 0 , 1 } n .
∣ σ ~ t ⟩ ← ∣ σ ~ t ⟩ + 1 N t ShadowAction ( U t , i , h , ∣ σ 0 ⟩ , M ) |\widetilde{\sigma}_t\rangle\leftarrow|\widetilde{\sigma}_t\rangle+\frac{1}{N_t}\operatorname{ShadowAction}(U_{t,i},h,|\sigma_0\rangle,\mathcal{M}) ∣ σ t ⟩ ← ∣ σ t ⟩ + N t 1 ShadowAction ( U t , i , h , ∣ σ 0 ⟩ , M ) .
end for
if ∥ σ ~ t ∥ 2 > 0 \|\widetilde{\sigma}_t\|_2>0 ∥ σ t ∥ 2 > 0 then
∣ σ t ⟩ ← ∣ σ ~ t ⟩ / ∥ σ ~ t ∥ 2 |\sigma_t\rangle\leftarrow|\widetilde{\sigma}_t\rangle/\|\widetilde{\sigma}_t\|_2 ∣ σ t ⟩ ← ∣ σ t ⟩ /∥ σ t ∥ 2 .
else
∣ σ t ⟩ ← ∣ σ t − 1 ⟩ |\sigma_t\rangle\leftarrow|\sigma_{t-1}\rangle ∣ σ t ⟩ ← ∣ σ t − 1 ⟩ .
end if
end for
return ∣ ψ ^ ⟩ ← ∣ σ J ⟩ |\widehat{\psi}\rangle\leftarrow|\sigma_J\rangle ∣ ψ ⟩ ← ∣ σ J ⟩ .
Theorem 7.1 (Full algorithm at constant confidence). For any n n n -qubit pure state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ and ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) , Algorithms 1 and 4 output a unit vector ∣ ψ ^ ⟩ |\widehat{\psi}\rangle ∣ ψ ⟩ satisfying
Pr [ 1 − ∣ ⟨ ψ ∣ ψ ^ ⟩ ∣ 2 ≤ ϵ ] ≥ 5 6 . \Pr\left[1-|\langle\psi|\widehat{\psi}\rangle|^2\le\epsilon\right]\ge\frac{5}{6}. Pr [ 1 − ∣ ⟨ ψ ∣ ψ ⟩ ∣ 2 ≤ ϵ ] ≥ 6 5 .
The protocol uses nonadaptive single-copy Clifford measurements of depth O ( log n ) O(\log n) O ( log n ) , with
T = O ( d / ϵ ) , N = O ( n 3 + log ( 2 / ϵ ) ) . T = O(d/\epsilon), \qquad N = O(n^3 + \log(2/\epsilon)). T = O ( d / ϵ ) , N = O ( n 3 + log ( 2/ ϵ )) .
Given per-basis outcome histograms, classical post-processing takes O ~ ( d log ( 2 / ϵ ) ) \widetilde{O}(d\log(2/\epsilon)) O ( d log ( 2/ ϵ )) time and O ~ ( d ) \widetilde{O}(d) O ( d ) working memory.
Proof. By Theorem 5.1 , initialization outputs a normalized vector ∣ σ 0 ⟩ |\sigma_0\rangle ∣ σ 0 ⟩ with ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ≥ 1 / 2 |\langle\psi|\sigma_0\rangle|^2 \ge1/2 ∣ ⟨ ψ ∣ σ 0 ⟩ ∣ 2 ≥ 1/2 except with probability at most 1 / 12 1/12 1/12 . Conditional on any such initial estimate, the refinement data remain independent of initialization. Corollary 4.6 therefore gives
Pr [ 1 − ∣ ⟨ ψ ∣ ψ ^ ⟩ ∣ 2 > ϵ ] ≤ 1 12 + 1 12 = 1 6 . \Pr\left[1-|\langle\psi|\widehat{\psi}\rangle|^2>\epsilon\right]\leq\frac{1}{12}+\frac{1}{12}=\frac{1}{6}. Pr [ 1 − ∣ ⟨ ψ ∣ ψ ⟩ ∣ 2 > ϵ ] ≤ 12 1 + 12 1 = 6 1 .
Theorem 5.1 and Corollary 4.5 give
T = ∑ ℓ = 0 n − 1 N ℓ S ℓ + ∑ t = 1 J N t S t = O ( d ) + O ( d / ϵ ) = O ( d / ϵ ) , T=\sum_{\ell=0}^{n-1}N_\ell S_\ell+\sum_{t=1}^{J}N_tS_t=O(d)+O(d/\epsilon)=O(d/\epsilon), T = ℓ = 0 ∑ n − 1 N ℓ S ℓ + t = 1 ∑ J N t S t = O ( d ) + O ( d / ϵ ) = O ( d / ϵ ) ,
N ≤ ∑ ℓ = 0 n − 1 N ℓ + ∑ t = 1 J N t = O ( n 3 + log ( 1 / ϵ ) ) . N\leq\sum_{\ell=0}^{n-1}N_\ell+\sum_{t=1}^{J}N_t=O(n^3+\log(1/\epsilon)). N ≤ ℓ = 0 ∑ n − 1 N ℓ + t = 1 ∑ J N t = O ( n 3 + log ( 1/ ϵ )) .
All bases and shot counts are chosen before observing any outcomes, and each measurement acts on one copy. The measurement depth is O ( log n ) O(\log n) O ( log n ) by the construction of the measurement ensembles. Lemma 6.3 ensures that the pseudocode computes the initialization matrices and residual updates analyzed above. The preceding classical post-processing analysis gives the stated time and working-memory bounds, including histogram processing, normalization, and state-vector output.
We use the following standard confidence-amplification lemma.
Lemma 7.2 (Confidence amplification [17 Proposition 2.4] ). Let A \mathcal{A} A estimate an unknown point x ⋆ x_\star x ⋆ in a metric space ( X , D ) (\mathcal{X},D) ( X , D ) with efficiently computable distances. Suppose its output X X X satisfies Pr [ D ( X , x ⋆ ) ≤ r ] ≥ 2 / 3 \Pr[D(X,x_\star)\leq r]\geq2/3 Pr [ D ( X , x ⋆ ) ≤ r ] ≥ 2/3 . For any 0 < δ < 1 / 2 0<\delta<1/2 0 < δ < 1/2 , running A \mathcal{A} A independently O ( log ( 1 / δ ) ) O(\log(1/\delta)) O ( log ( 1/ δ )) times and selecting one output using pairwise distances yields an estimate X ^ \widehat{X} X satisfying
Pr [ D ( X ^ , x ⋆ ) ≤ 3 r ] ≥ 1 − δ . \Pr[D(\widehat{X},x_\star)\leq3r]\geq1-\delta. Pr [ D ( X , x ⋆ ) ≤ 3 r ] ≥ 1 − δ .
Theorem 7.3 (Arbitrary confidence). For any ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) and δ ∈ ( 0 , 1 / 2 ) \delta\in(0,1/2) δ ∈ ( 0 , 1/2 ) , there is a nonadaptive single-copy tomography algorithm that outputs a unit vector ∣ ψ ^ ⟩ |\widehat{\psi}\rangle ∣ ψ ⟩ satisfying
Pr [ 1 − ∣ ⟨ ψ ∣ ψ ^ ⟩ ∣ 2 ≤ ϵ ] ≥ 1 − δ . \Pr\left[1-|\langle\psi|\widehat{\psi}\rangle|^2\leq\epsilon\right]\geq1-\delta. Pr [ 1 − ∣ ⟨ ψ ∣ ψ ⟩ ∣ 2 ≤ ϵ ] ≥ 1 − δ . Each measurement has Clifford depth O ( log n ) O(\log n) O ( log n ) , and
T = O ( d ϵ log 1 δ ) , N = O ( [ n 3 + log 1 ϵ ] log 1 δ ) . T=O\left(\frac{d}{\epsilon}\log\frac{1}{\delta}\right), \qquad N=O\left(\left[n^3+\log\frac{1}{\epsilon}\right]\log\frac{1}{\delta}\right). T = O ( ϵ d log δ 1 ) , N = O ( [ n 3 + log ϵ 1 ] log δ 1 ) . Given per-basis outcome histograms, classical post-processing takes
O ~ ( d [ log 1 ϵ log 1 δ + log 2 1 δ ] ) \widetilde{O}\left(d\left[\log\frac{1}{\epsilon}\log\frac{1}{\delta}+\log^2\frac{1}{\delta}\right]\right) O ( d [ log ϵ 1 log δ 1 + log 2 δ 1 ] ) time and O ~ ( d log ( 1 / δ ) ) \widetilde{O}(d\log(1/\delta)) O ( d log ( 1/ δ )) working memory.
Proof. Run the entire algorithm of Theorem 7.1 , including initialization, independently R = O ( log ( 1 / δ ) ) R = O(\log(1/\delta)) R = O ( log ( 1/ δ )) times with target infidelity ϵ / 9 \epsilon/9 ϵ /9 . In Lemma 7.2 , take D D D to be the trace distance between pure states:
D ( ϕ , ψ ) : = 1 2 ∥ ∣ ϕ ⟩ ⟨ ϕ ∣ − ∣ ψ ⟩ ⟨ ψ ∣ ∥ t r = 1 − ∣ ⟨ ϕ ∣ ψ ⟩ ∣ 2 . D(\phi, \psi) := \frac{1}{2}\left\lVert|\phi\rangle\langle\phi| - |\psi\rangle\langle\psi| \right\rVert_{\mathrm{tr}} = \sqrt{1 - |\langle\phi|\psi\rangle|^2}. D ( ϕ , ψ ) := 2 1 ∥ ∣ ϕ ⟩ ⟨ ϕ ∣ − ∣ ψ ⟩ ⟨ ψ ∣ ∥ tr = 1 − ∣ ⟨ ϕ ∣ ψ ⟩ ∣ 2 .
By Eq. (1) , each output has distance at most ϵ / 3 \sqrt{\epsilon}/3 ϵ /3 from ψ \psi ψ with probability at least 5 / 6 5/6 5/6 . The lemma therefore selects an output with trace distance at most ϵ \sqrt{\epsilon} ϵ , and hence infidelity at most ϵ \epsilon ϵ , with probability at least 1 − δ 1-\delta 1 − δ .
The bounds on sample complexity T T T and the number of sampled measurement bases N N N follow by multiplying the corresponding bounds in Theorem 7.1 by R R R . All measurements can be scheduled in advance, preserving nonadaptivity and depth. Each pairwise distance costs O ( d ) O(d) O ( d ) time to compute. Candidate selection thus adds O ( d R 2 ) O(dR^2) O ( d R 2 ) time and O ( d R ) O(dR) O ( d R ) memory, with no additional measurements. Together with the R R R executions, this gives the stated computational bounds. This also proves Theorem 1.1 .
Acknowledgments
This work was supported by grants from the National Research Foundation of Korea (NRF) funded by the Korean Government [Ministry of Science and ICT (MSIT)] (Grants RS-2023-00283291, RS-2023-NR077112, RS-2024-00413957, and Quantum Technology R&D Leading Program (Quantum Computing) (Grant RS-2024-00442994)), and a core center program grant funded by the Ministry of Education (No. 2021R1A6C101B418). This research was conducted as part of an R&D project supported by SDT Inc. and SAIT.
AI Disclosure
GPT-5.6 and GPT-6 were used throughout the research to discuss technical ideas, examine proofs, analyze prior work, and assist with manuscript preparation. The authors alternated between discussions with these models and their own checks and revisions of the arguments. These exchanges helped clarify and simplify parts of the analysis, including coefficient recovery using the reconstruction matrix B x B_x B x and the allocation of measurement bases and shots during initialization. They also contributed to the runtime analysis of computing U x U_x U x for shallow circuits and histogram-based post-processing with the inverse shadow channel. The authors reviewed the resulting material and take responsibility for the mathematical claims, references, and writing in the final manuscript.
Deferred Proofs
Lemma 3.5. Let M \mathcal{M} M be the invertible shadow channel of a Clifford ensemble E \mathcal{E} E . For every U ∈ E U \in\mathcal{E} U ∈ E and A ∈ C d × d A \in\mathbb{C}^{d \times d} A ∈ C d × d ,
∑ b Tr ( A U † ∣ b ⟩ ⟨ b ∣ U ) M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) = ∑ b Tr ( A M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) U † ∣ b ⟩ ⟨ b ∣ U . \sum_b \operatorname{Tr}\left(AU^\dagger|b\rangle\langle b|U\right)\mathcal{M}^{-1}\left(U^\dagger|b\rangle\langle b|U\right)
=
\sum_b \operatorname{Tr}\left(A\mathcal{M}^{-1}\left(U^\dagger|b\rangle\langle b|U\right)\right)U^\dagger|b\rangle\langle b|U. b ∑ Tr ( A U † ∣ b ⟩ ⟨ b ∣ U ) M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) = b ∑ Tr ( A M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) ) U † ∣ b ⟩ ⟨ b ∣ U .
Proof. Let P P P range over { I , X , Y , Z } ⊗ n \{I,X,Y,Z\}^{\otimes n} { I , X , Y , Z } ⊗ n , and let Z : = { I , Z } ⊗ n \mathcal{Z}:=\{I,Z\}^{\otimes n} Z := { I , Z } ⊗ n . Since U U U is Clifford,
∑ b Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) U † ∣ b ⟩ ⟨ b ∣ U = { P , U P U † ∈ ± Z , 0 , U P U † ∉ ± Z . \sum_b \operatorname{Tr}\left(PU^\dagger|b\rangle\langle b|U\right)U^\dagger|b\rangle\langle b|U
=
\begin{cases}
P, & UPU^\dagger\in\pm\mathcal{Z},\\
0, & UPU^\dagger\notin\pm\mathcal{Z}.
\end{cases} b ∑ Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) U † ∣ b ⟩ ⟨ b ∣ U = { P , 0 , U P U † ∈ ± Z , U P U † ∈ / ± Z .
Using M − 1 ( P ) = m P − 1 P \mathcal{M}^{-1}(P)=m_P^{-1}P M − 1 ( P ) = m P − 1 P in Eq. (5) , we obtain
∑ b Tr ( A U † ∣ b ⟩ ⟨ b ∣ U ) M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) = 1 d ∑ b ∑ P m P − 1 Tr ( A U † ∣ b ⟩ ⟨ b ∣ U ) Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) P = 1 d ∑ P m P − 1 Tr [ A ∑ b Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) U † ∣ b ⟩ ⟨ b ∣ U ] P = 1 d ∑ P : U P U † ∈ ± Z m P − 1 Tr ( A P ) P \begin{aligned}
\sum_b \operatorname{Tr}\left(AU^\dagger|b\rangle\langle b|U\right)\mathcal{M}^{-1}\left(U^\dagger|b\rangle\langle b|U\right)
&= \frac{1}{d}\sum_b\sum_P m_P^{-1}\operatorname{Tr}\left(AU^\dagger|b\rangle\langle b|U\right)\operatorname{Tr}\left(PU^\dagger|b\rangle\langle b|U\right)P\\
&= \frac{1}{d}\sum_P m_P^{-1}\operatorname{Tr}\left[A\sum_b\operatorname{Tr}\left(PU^\dagger|b\rangle\langle b|U\right)U^\dagger|b\rangle\langle b|U\right]P\\
&= \frac{1}{d}\sum_{P:UPU^\dagger\in\pm\mathcal{Z}}m_P^{-1}\operatorname{Tr}(AP)P
\end{aligned} b ∑ Tr ( A U † ∣ b ⟩ ⟨ b ∣ U ) M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) = d 1 b ∑ P ∑ m P − 1 Tr ( A U † ∣ b ⟩ ⟨ b ∣ U ) Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) P = d 1 P ∑ m P − 1 Tr [ A b ∑ Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) U † ∣ b ⟩ ⟨ b ∣ U ] P = d 1 P : U P U † ∈ ± Z ∑ m P − 1 Tr ( A P ) P
= 1 d ∑ b ∑ P m P − 1 Tr ( A P ) Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) U † ∣ b ⟩ ⟨ b ∣ U = ∑ b Tr [ A ( 1 d ∑ P m P − 1 Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) P ) U † ∣ b ⟩ ⟨ b ∣ U ] = ∑ b Tr ( A M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) U † ∣ b ⟩ ⟨ b ∣ U ) . \begin{aligned}
&= \frac{1}{d}\sum_b\sum_P m_P^{-1}\operatorname{Tr}(AP)\operatorname{Tr}(PU^\dagger|b\rangle\langle b|U)U^\dagger|b\rangle\langle b|U\\
&= \sum_b\operatorname{Tr}\left[A\left(\frac{1}{d}\sum_Pm_P^{-1}\operatorname{Tr}(PU^\dagger|b\rangle\langle b|U)P\right)U^\dagger|b\rangle\langle b|U\right]\\
&= \sum_b\operatorname{Tr}\left(A\mathcal{M}^{-1}(U^\dagger|b\rangle\langle b|U)U^\dagger|b\rangle\langle b|U\right).
\end{aligned} = d 1 b ∑ P ∑ m P − 1 Tr ( A P ) Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) U † ∣ b ⟩ ⟨ b ∣ U = b ∑ Tr [ A ( d 1 P ∑ m P − 1 Tr ( P U † ∣ b ⟩ ⟨ b ∣ U ) P ) U † ∣ b ⟩ ⟨ b ∣ U ] = b ∑ Tr ( A M − 1 ( U † ∣ b ⟩ ⟨ b ∣ U ) U † ∣ b ⟩ ⟨ b ∣ U ) .
Corollary 5.10 (Complex observables). Fix x ∈ { 0 , 1 } ℓ x \in\{0,1\}^{\ell} x ∈ { 0 , 1 } ℓ . For any observable O ∈ L ( H 2 n − ℓ ) O \in\mathcal{L}(\mathcal{H}^{2^{n-\ell}}) O ∈ L ( H 2 n − ℓ ) on the suffix, the estimator in Eq. (21) satisfies E [ o ^ ] = p x Tr ( O ψ x ) \mathbb{E}[\widehat{o}]=p_x\operatorname{Tr}(O\psi_x) E [ o ] = p x Tr ( O ψ x ) and
E [ ∣ o ^ − p x Tr ( O ψ x ) ∣ 2 ] ≤ C ∥ O ∥ F 2 N ℓ ( p x 2 + p x S ℓ ) . \mathbb{E}\left[\left|\widehat{o}-p_x\operatorname{Tr}(O\psi_x)\right|^2\right]\leq\frac{C\lVert O\rVert_F^2}{N_\ell}\left(p_x^2+\frac{p_x}{S_\ell}\right). E [ ∣ o − p x Tr ( O ψ x ) ∣ 2 ] ≤ N ℓ C ∥ O ∥ F 2 ( p x 2 + S ℓ p x ) .
Proof. Write O = O R + i O I O=O_R+iO_I O = O R + i O I , where O R = ( O + O † ) / 2 O_R=(O+O^\dagger)/2 O R = ( O + O † ) /2 and O I = ( O − O † ) / ( 2 i ) O_I=(O-O^\dagger)/(2i) O I = ( O − O † ) / ( 2 i ) are Hermitian. By linearity of the estimator and Lemma 5.9 , E [ o ^ ( O ) ] = p x Tr ( O ψ x ) \mathbb{E}[\widehat{o}(O)]=p_x\operatorname{Tr}(O\psi_x) E [ o ( O )] = p x Tr ( O ψ x ) . Moreover,
E [ ∣ o ^ ( O ) − p x Tr ( O ψ x ) ∣ 2 ] = E [ ( o ^ ( O R ) − p x Tr ( O R ψ x ) ) 2 ] + E [ ( o ^ ( O I ) − p x Tr ( O I ψ x ) ) 2 ] ≤ C ( ∥ O R ∥ F 2 + ∥ O I ∥ F 2 ) N ℓ ( p x 2 + p x S ℓ ) (by xref‘Lemma 5.9‘) = C ∥ O ∥ F 2 N ℓ ( p x 2 + p x S ℓ ) . \begin{aligned}
\mathbb{E}\left[\left|\widehat{o}(O)-p_x\operatorname{Tr}(O\psi_x)\right|^2\right]
&=\mathbb{E}\left[\left(\widehat{o}(O_R)-p_x\operatorname{Tr}(O_R\psi_x)\right)^2\right]\\
&\quad+\mathbb{E}\left[\left(\widehat{o}(O_I)-p_x\operatorname{Tr}(O_I\psi_x)\right)^2\right]\\
&\leq\frac{C\left(\lVert O_R\rVert_F^2+\lVert O_I\rVert_F^2\right)}{N_\ell}\left(p_x^2+\frac{p_x}{S_\ell}\right)\qquad\text{(by {xref}`Lemma 5.9`)}\\
&= \frac{C\lVert O\rVert_F^2}{N_\ell}\left(p_x^2+\frac{p_x}{S_\ell}\right).
\end{aligned} E [ ∣ o ( O ) − p x Tr ( O ψ x ) ∣ 2 ] = E [ ( o ( O R ) − p x Tr ( O R ψ x ) ) 2 ] + E [ ( o ( O I ) − p x Tr ( O I ψ x ) ) 2 ] ≤ N ℓ C ( ∥ O R ∥ F 2 + ∥ O I ∥ F 2 ) ( p x 2 + S ℓ p x ) (by xref ‘Lemma 5.9‘) = N ℓ C ∥ O ∥ F 2 ( p x 2 + S ℓ p x ) .
Lemma A.1 (Extension from [8 Lemma 25] ). Let E A \mathcal{E}_A E A and E B \mathcal{E}_B E B be independent unitary ensembles on n A n_A n A and n B n_B n B qubits, respectively, with invertible shadow channels. Suppose that, for every state ρ A \rho_A ρ A and Hermitian observable O A O_A O A on A A A , and every state ρ B \rho_B ρ B and Hermitian observable O B O_B O B on B B B , the matched shadow estimators satisfy
Var [ Tr ( O A ρ ^ A ) ] ≤ C A ∥ O A ∥ F 2 , Var [ Tr ( O B ρ ^ B ) ] ≤ C B ∥ O B ∥ F 2 . \operatorname{Var}[\operatorname{Tr}(O_A\widehat{\rho}_A)]\leq C_A\lVert O_A\rVert_F^2,\qquad
\operatorname{Var}[\operatorname{Tr}(O_B\widehat{\rho}_B)]\leq C_B\lVert O_B\rVert_F^2. Var [ Tr ( O A ρ A )] ≤ C A ∥ O A ∥ F 2 , Var [ Tr ( O B ρ B )] ≤ C B ∥ O B ∥ F 2 . Then, for every joint state ρ A B \rho_{AB} ρ A B and Hermitian observable O A B O_{AB} O A B , the matched shadow estimator for E A ⊗ E B \mathcal{E}_A\otimes\mathcal{E}_B E A ⊗ E B satisfies
Var [ Tr ( O A B ρ ^ A B ) ] ≤ ( C A + 1 ) ( C B + 1 ) ∥ O A B ∥ F 2 . \operatorname{Var}[\operatorname{Tr}(O_{AB}\widehat{\rho}_{AB})]\leq(C_A+1)(C_B+1)\lVert O_{AB}\rVert_F^2. Var [ Tr ( O A B ρ A B )] ≤ ( C A + 1 ) ( C B + 1 ) ∥ O A B ∥ F 2 . Proof. By unbiasedness and ∥ ρ A ∥ F ≤ 1 \lVert\rho_A\rVert_F\leq1 ∥ ρ A ∥ F ≤ 1 , the assumed variance bound implies
E [ Tr ( O A ρ ^ A ) 2 ] ≤ ( C A + 1 ) ∥ O A ∥ F 2 . \mathbb{E}\left[\operatorname{Tr}(O_A\widehat{\rho}_A)^2\right]\leq(C_A+1)\lVert O_A\rVert_F^2. E [ Tr ( O A ρ A ) 2 ] ≤ ( C A + 1 ) ∥ O A ∥ F 2 . The analogous bound on B B B holds with constant C B + 1 C_B+1 C B + 1 . Write
O = ∑ P P ⊗ X P , O=\sum_P P\otimes X_P, O = P ∑ P ⊗ X P , where P P P ranges over the Pauli operators on A A A , and each X P = 2 − n A Tr A ( O ( P ⊗ I ) ) X_P=2^{-n_A}\operatorname{Tr}_A(O(P\otimes I)) X P = 2 − n A Tr A ( O ( P ⊗ I )) is a Hermitian operator on B B B . Pauli orthogonality gives
∥ O ∥ F 2 = 2 n A ∑ P ∥ X P ∥ F 2 . \lVert O\rVert_F^2=2^{n_A}\sum_P\lVert X_P\rVert_F^2. ∥ O ∥ F 2 = 2 n A P ∑ ∥ X P ∥ F 2 .
The shadow channel factorizes M A B = M A ⊗ M B \mathcal{M}_{AB}=\mathcal{M}_A\otimes\mathcal{M}_B M A B = M A ⊗ M B , so ρ ^ A B = ρ ^ A ⊗ ρ ^ B \widehat{\rho}_{AB}=\widehat{\rho}_A\otimes\widehat{\rho}_B ρ A B = ρ A ⊗ ρ B . Then
Tr ( O ρ ^ A B ) = ∑ P Tr ( P ρ ^ A ) Tr ( X P ρ ^ B ) = ∑ P Tr ( P ρ ^ A ) α P = Tr ( O ~ A ρ ^ A ) , \begin{aligned}
\operatorname{Tr}(O\widehat{\rho}_{AB})=\sum_P\operatorname{Tr}(P\widehat{\rho}_A)\operatorname{Tr}(X_P\widehat{\rho}_B) \\
&=\sum_P\operatorname{Tr}(P\widehat{\rho}_A)\alpha_P \\
&=\operatorname{Tr}\left(\widetilde{O}_A\widehat{\rho}_A\right),
\end{aligned} Tr ( O ρ A B ) = P ∑ Tr ( P ρ A ) Tr ( X P ρ B ) = P ∑ Tr ( P ρ A ) α P = Tr ( O A ρ A ) ,
where α P : = Tr ( X P ρ ^ B ) \alpha_P:=\operatorname{Tr}(X_P\widehat{\rho}_B) α P := Tr ( X P ρ B ) and O ~ A : = ∑ P α P P \widetilde{O}_A:=\sum_P\alpha_PP O A := ∑ P α P P are auxiliary observables on A A A . By Pauli orthogonality,
∥ O ~ A ∥ F 2 = 2 n A ∑ P α P 2 = 2 n A ∑ P Tr ( X P ρ ^ B ) 2 . (26) \|\widetilde{O}_A\|_F^2=2^{n_A}\sum_P\alpha_P^2=2^{n_A}\sum_P\operatorname{Tr}(X_P\widehat{\rho}_B)^2. \tag*{(26)} ∥ O A ∥ F 2 = 2 n A P ∑ α P 2 = 2 n A P ∑ Tr ( X P ρ B ) 2 . (26)
The conditional state on A A A is independent of U A U_A U A . We can therefore apply the assumed second-moment bound on A A A with ( U B , z B ) (U_B,z_B) ( U B , z B ) held fixed.
E A , B [ Tr ( O ρ ^ A B ) 2 ] = E B [ E A [ Tr ( O ~ A ρ ^ A ) 2 ∣ U B , z B ] ] ≤ ( C A + 1 ) E B [ ∥ O ~ A ∥ F 2 ] = 2 n A ( C A + 1 ) ∑ P E B [ Tr ( X P ρ ^ B ) 2 ] \begin{aligned}
\mathbb{E}_{A,B}\left[\operatorname{Tr}(O\widehat{\rho}_{AB})^2\right]
=\mathbb{E}_B\left[\mathbb{E}_A\left[\operatorname{Tr}(\widetilde{O}_A\widehat{\rho}_A)^2\mid U_B,z_B\right]\right] \\
&\leq(C_A+1)\mathbb{E}_B\left[\|\widetilde{O}_A\|_F^2\right] \\
&=2^{n_A}(C_A+1)\sum_P\mathbb{E}_B\left[\operatorname{Tr}(X_P\widehat{\rho}_B)^2\right]
\end{aligned} E A , B [ Tr ( O ρ A B ) 2 ] = E B [ E A [ Tr ( O A ρ A ) 2 ∣ U B , z B ] ] ≤ ( C A + 1 ) E B [ ∥ O A ∥ F 2 ] = 2 n A ( C A + 1 ) P ∑ E B [ Tr ( X P ρ B ) 2 ]
≤ 2 n A ( C A + 1 ) ( C B + 1 ) ∑ P ∥ X P ∥ F 2 = ( C A + 1 ) ( C B + 1 ) ∥ O ∥ F 2 . \begin{aligned}
\leq2^{n_A}(C_A+1)(C_B+1)\sum_P\|X_P\|_F^2 \\
&=(C_A+1)(C_B+1)\|O\|_F^2.
\end{aligned} ≤ 2 n A ( C A + 1 ) ( C B + 1 ) P ∑ ∥ X P ∥ F 2 = ( C A + 1 ) ( C B + 1 ) ∥ O ∥ F 2 .
Since variance is bounded by the second moment, the claim follows.
Lemma A.2 (Shallow ensembles for all suffix sizes). Let k : = max { 8 , 2 ⌈ log 2 n ⌉ } k:=\max\{8,2\lceil\log_2 n\rceil\} k := max { 8 , 2 ⌈ log 2 n ⌉} . For each ℓ = 0 , … , n − 1 \ell=0,\ldots,n-1 ℓ = 0 , … , n − 1 , write n − ℓ = m k + r n-\ell=mk+r n − ℓ = mk + r , where m = ⌊ n − ℓ k ⌋ m=\left\lfloor\frac{n-\ell}{k}\right\rfloor m = ⌊ k n − ℓ ⌋ and 0 ≤ r ≤ k − 1 0\leq r\leq k-1 0 ≤ r ≤ k − 1 . Define unitary ensemble
E ℓ : = E 2 L ( k m ) ⊗ Cl ( r ) , \mathcal{E}_{\ell}:=\mathcal{E}_{2L}(km)\otimes\operatorname{Cl}(r), E ℓ := E 2 L ( k m ) ⊗ Cl ( r ) , where E 2 L \mathcal{E}_{2L} E 2 L is the cyclic two-layer Clifford ensemble with block size k k k . Let M ℓ \mathcal{M}_{\ell} M ℓ be its shadow channel. For every ( n − ℓ ) (n-\ell) ( n − ℓ ) -qubit suffix state ρ \rho ρ and Hermitian observable O ∈ L ( H 2 n − ℓ ) O\in\mathcal{L}(H^{2^{n-\ell}}) O ∈ L ( H 2 n − ℓ ) ,
Var [ Tr ( O ρ ^ ) ] ≤ C ℓ ∥ O ∥ F 2 , C ℓ = O ( 1 ) , \operatorname{Var}[\operatorname{Tr}(O\widehat{\rho})]\leq C_{\ell}\|O\|_F^2,\qquad C_{\ell}=O(1), Var [ Tr ( O ρ )] ≤ C ℓ ∥ O ∥ F 2 , C ℓ = O ( 1 ) , where ρ ^ : = M ℓ − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) \widehat{\rho}:=\mathcal{M}_{\ell}^{-1}(U^\dagger|z\rangle\langle z|U) ρ := M ℓ − 1 ( U † ∣ z ⟩ ⟨ z ∣ U ) , U ∼ E ℓ U\sim\mathcal{E}_{\ell} U ∼ E ℓ , and z ∈ { 0 , 1 } n − ℓ z\in\{0,1\}^{n-\ell} z ∈ { 0 , 1 } n − ℓ is a measurement outcome.
Proof. Factors acting on zero qubits are omitted. If m = 0 m=0 m = 0 , the ensemble is simply Cl ( r ) \operatorname{Cl}(r) Cl ( r ) , whose variance constant is at most 3 [18 ] . For m ≥ 1 m\geq1 m ≥ 1 , our choice of k k k gives
m 2 k / 2 ≤ n k 2 k / 2 ≤ 1 k ≤ 1. \frac{m}{2^{k/2}}\leq\frac{n}{k2^{k/2}}\leq\frac{1}{k}\leq1. 2 k /2 m ≤ k 2 k /2 n ≤ k 1 ≤ 1.
The variance bound for the two-layer Clifford ensemble therefore applies to E 2 L ( k m ) \mathcal{E}_{2L}(km) E 2 L ( k m ) , with coefficient 8 e 45 m / 2 k / 2 = O ( 1 ) 8e^{45m/2^{k/2}}=O(1) 8 e 45 m / 2 k /2 = O ( 1 ) multiplying ∥ O ∥ F 2 \|O\|_F^2 ∥ O ∥ F 2 (see [8 Theorem 7] for the derivation). The global Clifford factor Cl ( r ) \operatorname{Cl}(r) Cl ( r ) , when present, has variance constant at most 3. Applying Lemma A.1, we obtain
Var [ Tr ( O ρ ^ ) ] ≤ ( 3 + 1 ) ( 8 e 45 m / 2 k / 2 + 1 ) ∥ O ∥ F 2 . \operatorname{Var}[\operatorname{Tr}(O\widehat{\rho})]\leq(3+1)\left(8e^{45m/2^{k/2}}+1\right)\|O\|_F^2. Var [ Tr ( O ρ )] ≤ ( 3 + 1 ) ( 8 e 45 m / 2 k /2 + 1 ) ∥ O ∥ F 2 .
Thus we may take C ℓ : = 4 ( 8 e 45 n / ( 2 k / 2 k ) + 1 ) = O ( 1 ) C_{\ell}:=4(8e^{45n/(2^{k/2}k)}+1)=O(1) C ℓ := 4 ( 8 e 45 n / ( 2 k /2 k ) + 1 ) = O ( 1 ) . When r = 0 r=0 r = 0 , the same bound follows directly from the two-layer estimate. The matched shadow channel is invertible because the component channels are invertible. Finally, each Clifford block in the two-layer Clifford circuit has depth O ( k ) O(k) O ( k ) . Since r < k r<k r < k , the Clifford circuit from Cl ( r ) \operatorname{Cl}(r) Cl ( r ) also has depth at most O ( k ) O(k) O ( k ) . Hence the total depth is O ( k ) = O ( log ( n ) ) O(k)=O(\log(n)) O ( k ) = O ( log ( n )) .
Low-Rank Tomography with Nearly Minimal Measurement Settings
The shadow bootstrapping method developed in the main text also extends to nonadaptive single-copy tomography of low-rank quantum states. For states of rank at most r r r , our protocol uses O ~ ( r ) \widetilde{O}(r) O ( r ) measurement settings and O ~ ( d r 2 / ϵ 2 ) \widetilde{O}(dr^{2}/\epsilon^{2}) O ( d r 2 / ϵ 2 ) copies to achieve trace-norm error ϵ \epsilon ϵ with failure probability at most δ \delta δ . The number of sampled measurement bases matches the Ω ( r ) \Omega(r) Ω ( r ) lower bound up to polylogarithmic factors [20 , 2 ] . The sample complexity likewise matches the Ω ( d r 2 / ϵ 2 ) \Omega(dr^{2}/\epsilon^{2}) Ω ( d r 2 / ϵ 2 ) lower bound for nonadaptive single-copy tomography up to polylogarithmic factors [27 ] .
Preliminaries
Lemma B.1 (Matrix Bernstein inequality with spectral clipping [8 Lemma 4] ). Let X ^ 1 , … , X ^ N \widehat{X}_{1},\ldots,\widehat{X}_{N} X 1 , … , X N be independent copies of a Hermitian random matrix X ^ ∈ C d × d \widehat{X}\in\mathbb{C}^{d\times d} X ∈ C d × d satisfying E [ X ^ ] = X \mathbb{E}[\widehat{X}]=X E [ X ] = X and ∥ E [ X ^ 2 ] ∥ o p ≤ V \lVert\mathbb{E}[\widehat{X}^{2}]\rVert_{\mathrm{op}}\le V ∥ E [ X 2 ] ∥ op ≤ V . For 0 < δ < 1 0<\delta<1 0 < δ < 1 , set K : = V N / log ( 2 d / δ ) K:=\sqrt{VN/\log(2d/\delta)} K := V N / log ( 2 d / δ ) . Then, with probability at least 1 − δ 1-\delta 1 − δ ,
∥ 1 N ∑ i = 1 N clip K ( X ^ i ) − X ∥ o p ≤ C 0 V log ( 2 d / δ ) N , \left\lVert\frac{1}{N}\sum_{i=1}^{N}\operatorname{clip}_{K}(\widehat{X}_{i})-X\right\rVert_{\mathrm{op}}\le C_{0}\sqrt{\frac{V\log(2d/\delta)}{N}}, N 1 i = 1 ∑ N clip K ( X i ) − X op ≤ C 0 N V log ( 2 d / δ ) ,
where C 0 > 0 C_{0}>0 C 0 > 0 is a universal constant and clip K ( x ) = max { − K , min { x , K } } \operatorname{clip}_{K}(x)=\max\{-K,\min\{x,K\}\} clip K ( x ) = max { − K , min { x , K }} .
Lemma B.2 (Rank-r r r spectral truncation). Let A , B ∈ C d × d A,B\in\mathbb{C}^{d\times d} A , B ∈ C d × d be Hermitian, with rank ( B ) ≤ r \operatorname{rank}(B)\le r rank ( B ) ≤ r . Let proj r ( A ) : = argmin rank ( X ) ≤ r ∥ A − X ∥ o p \operatorname{proj}_{r}(A):=\underset{\operatorname{rank}(X)\le r}{\operatorname{argmin}}\lVert A-X\rVert_{\mathrm{op}} proj r ( A ) := rank ( X ) ≤ r argmin ∥ A − X ∥ op retain the r r r eigenvalues of A A A with largest absolute value and their corresponding eigenvectors. Then
∥ proj r ( A ) − B ∥ F 2 ≤ 8 r ∥ A − B ∥ o p 2 . \lVert\operatorname{proj}_{r}(A)-B\rVert_{F}^{2}\le8r\lVert A-B\rVert_{\mathrm{op}}^{2}. ∥ proj r ( A ) − B ∥ F 2 ≤ 8 r ∥ A − B ∥ op 2 .
Proof.
∥ proj r ( A ) − B ∥ F 2 ≤ rank ( proj r ( A ) − B ) ∥ proj r ( A ) − B ∥ o p 2 ≤ 2 r ∥ proj r ( A ) − B ∥ o p 2 ≤ 2 r ( ∥ proj r ( A ) − A ∥ o p + ∥ A − B ∥ o p ) 2 ≤ 8 r ∥ A − B ∥ o p 2 (by ∥ A − proj r ( A ) ∥ o p ≤ ∥ A − B ∥ o p ) . \begin{aligned}
\lVert\operatorname{proj}_{r}(A)-B\rVert_{F}^{2}
&\le\operatorname{rank}(\operatorname{proj}_{r}(A)-B)\lVert\operatorname{proj}_{r}(A)-B\rVert_{\mathrm{op}}^{2}\\
&\le2r\lVert\operatorname{proj}_{r}(A)-B\rVert_{\mathrm{op}}^{2}\\
&\le2r\bigl(\lVert\operatorname{proj}_{r}(A)-A\rVert_{\mathrm{op}}+\lVert A-B\rVert_{\mathrm{op}}\bigr)^{2}\\
&\le8r\lVert A-B\rVert_{\mathrm{op}}^{2}\qquad\text{(by }\lVert A-\operatorname{proj}_{r}(A)\rVert_{\mathrm{op}}\le\lVert A-B\rVert_{\mathrm{op}}\text{)}.
\end{aligned} ∥ proj r ( A ) − B ∥ F 2 ≤ rank ( proj r ( A ) − B ) ∥ proj r ( A ) − B ∥ op 2 ≤ 2 r ∥ proj r ( A ) − B ∥ op 2 ≤ 2 r ( ∥ proj r ( A ) − A ∥ op + ∥ A − B ∥ op ) 2 ≤ 8 r ∥ A − B ∥ op 2 (by ∥ A − proj r ( A ) ∥ op ≤ ∥ A − B ∥ op ) .
Lemma B.3 (Projection onto quantum states). Let A ∈ C d × d A\in\mathbb{C}^{d\times d} A ∈ C d × d be Hermitian with at least one positive eigenvalue. Let A + A_{+} A + be obtained by replacing the negative eigenvalues of A A A by zero, and define
Π ( A ) : = A + Tr ( A + ) . \Pi(A):=\frac{A_{+}}{\operatorname{Tr}(A_{+})}. Π ( A ) := Tr ( A + ) A + .
Then Π ( A ) \Pi(A) Π ( A ) is a quantum state of rank at most rank ( A ) \operatorname{rank}(A) rank ( A ) . Moreover, for every quantum state ρ \rho ρ ,
∥ Π ( A ) − ρ ∥ t r ≤ 2 ∥ A − ρ ∥ t r . \lVert\Pi(A)-\rho\rVert_{\mathrm{tr}}\le2\lVert A-\rho\rVert_{\mathrm{tr}}. ∥ Π ( A ) − ρ ∥ tr ≤ 2 ∥ A − ρ ∥ tr .
Proof. Positivity, unit trace, and the rank bound follow directly from the definition. Suppose first that Tr ( A + ) > 0 \operatorname{Tr}(A_+)>0 Tr ( A + ) > 0 . Since A + ⪰ 0 A_+ \succeq0 A + ⪰ 0 and A + − A ⪰ 0 A_+ - A \succeq0 A + − A ⪰ 0 have orthogonal supports,
∥ Π ( A ) − A ∥ t r = ∥ ( 1 Tr ( A + ) − 1 ) A + + ( A + − A ) ∥ t r = ∣ 1 − Tr ( A + ) ∣ + Tr ( A + − A ) = max { 1 − Tr ( A ) , ∥ A ∥ t r − 1 } (by ∥ A ∥ t r = 2 Tr ( A + ) − Tr ( A ) ) = max { Tr ( ρ − A ) , ∥ A ∥ t r − ∥ ρ ∥ t r } (by Tr ( ρ ) = ∥ ρ ∥ t r = 1 ) ≤ ∥ A − ρ ∥ t r . \begin{aligned}
\left\|\Pi(A)-A\right\|_{\mathrm{tr}}=\left\|\left(\frac{1}{\operatorname{Tr}(A_+)}-1\right)A_+ +(A_+-A)\right\|_{\mathrm{tr}} \\
&=|1-\operatorname{Tr}(A_+)|+\operatorname{Tr}(A_+-A) \\
&=\max\{1-\operatorname{Tr}(A),\|A\|_{\mathrm{tr}}-1\}\qquad\text{(by }\|A\|_{\mathrm{tr}}=2\operatorname{Tr}(A_+)-\operatorname{Tr}(A)\text{)} \\
&=\max\{\operatorname{Tr}(\rho-A),\|A\|_{\mathrm{tr}}-\|\rho\|_{\mathrm{tr}}\}\qquad\text{(by }\operatorname{Tr}(\rho)=\|\rho\|_{\mathrm{tr}}=1\text{)} \\
&\leq\|A-\rho\|_{\mathrm{tr}}.
\end{aligned} ∥ Π ( A ) − A ∥ tr = ( Tr ( A + ) 1 − 1 ) A + + ( A + − A ) tr = ∣1 − Tr ( A + ) ∣ + Tr ( A + − A ) = max { 1 − Tr ( A ) , ∥ A ∥ tr − 1 } (by ∥ A ∥ tr = 2 Tr ( A + ) − Tr ( A ) ) = max { Tr ( ρ − A ) , ∥ A ∥ tr − ∥ ρ ∥ tr } (by Tr ( ρ ) = ∥ ρ ∥ tr = 1 ) ≤ ∥ A − ρ ∥ tr .
Then the triangle inequality gives
∥ Π ( A ) − ρ ∥ t r ≤ ∥ Π ( A ) − A ∥ t r + ∥ A − ρ ∥ t r ≤ 2 ∥ A − ρ ∥ t r . \|\Pi(A)-\rho\|_{\mathrm{tr}}\leq\|\Pi(A)-A\|_{\mathrm{tr}}+\|A-\rho\|_{\mathrm{tr}}\leq2\|A-\rho\|_{\mathrm{tr}}. ∥Π ( A ) − ρ ∥ tr ≤ ∥Π ( A ) − A ∥ tr + ∥ A − ρ ∥ tr ≤ 2∥ A − ρ ∥ tr .
Theoretical Guarantees
Theorem B.4 (Low-rank shadow bootstrapping). Let ρ ∈ C d × d \rho\in\mathbb{C}^{d\times d} ρ ∈ C d × d be an n n n -qubit quantum state of rank at most r r r , where d = 2 n d=2^n d = 2 n . For every 0 < ϵ , δ < 1 0<\epsilon,\delta<1 0 < ϵ , δ < 1 , there is a nonadaptive single-copy shallow-depth protocol whose reconstruction outputs an estimate ρ ^ \widehat{\rho} ρ satisfying Pr [ ∥ ρ ^ − ρ ∥ t r ≤ ϵ ] ≥ 1 − δ \Pr[\|\widehat{\rho}-\rho\|_{\mathrm{tr}}\leq\epsilon]\geq1-\delta Pr [ ∥ ρ − ρ ∥ tr ≤ ϵ ] ≥ 1 − δ . The protocol uses N N N measurement settings and T T T copies, where
N = O ~ ( r ) , T = O ~ ( d r 2 ϵ 2 ) . N=\widetilde{O}(r),\qquad T=\widetilde{O}\left(\frac{dr^2}{\epsilon^2}\right). N = O ( r ) , T = O ( ϵ 2 d r 2 ) .
Proof. Let J : = ⌈ log 2 ( 4 r / ϵ 2 ) ⌉ J:=\lceil\log_2(4r/\epsilon^2)\rceil J := ⌈ log 2 ( 4 r / ϵ 2 )⌉ , and start from any fixed quantum state σ 0 \sigma_0 σ 0 .
For t = 1 , … , J t=1,\ldots,J t = 1 , … , J , choose
N t : = ⌈ 24 C 0 2 ( C + 1 ) r log 2 d J δ ⌉ , S t : = d 2 t − 1 . N_t:=\left\lceil24C_0^2(C+1)r\log\frac{2dJ}{\delta}\right\rceil,\qquad S_t:=d2^{t-1}. N t := ⌈ 24 C 0 2 ( C + 1 ) r log δ 2 dJ ⌉ , S t := d 2 t − 1 .
where C 0 C_0 C 0 is the constant in Lemma B.1. Let Δ t , i \Delta_{t,i} Δ t , i be the residual estimator in Definition 4.1, with reference σ t − 1 \sigma_{t-1} σ t − 1 , using independent measurement data at each stage.
The proof of Lemma 4.2 also applies to Hermitian reference matrices σ t − 1 \sigma_{t-1} σ t − 1 and gives
E [ Δ t , i ∣ σ t − 1 ] = ρ − σ t − 1 , \mathbb{E}[\Delta_{t,i}\mid\sigma_{t-1}]=\rho-\sigma_{t-1}, E [ Δ t , i ∣ σ t − 1 ] = ρ − σ t − 1 ,
∥ E [ Δ t , i 2 ∣ σ t − 1 ] ∥ o p ≤ ( C + 1 ) ( ∥ ρ − σ t − 1 ∥ F 2 + d S t ) . \left\|\mathbb{E}[\Delta_{t,i}^2\mid\sigma_{t-1}]\right\|_{\mathrm{op}}\leq(C+1)\left(\|\rho-\sigma_{t-1}\|_F^2+\frac{d}{S_t}\right). E [ Δ t , i 2 ∣ σ t − 1 ] op ≤ ( C + 1 ) ( ∥ ρ − σ t − 1 ∥ F 2 + S t d ) .
Set
K t : = ( C + 1 ) ( 2 / 2 t − 1 + d / S t ) N t log ( 2 d J / δ ) , K_t:=\sqrt{\frac{(C+1)(2/2^{t-1}+d/S_t)N_t}{\log(2dJ/\delta)}}, K t := log ( 2 dJ / δ ) ( C + 1 ) ( 2/ 2 t − 1 + d / S t ) N t ,
and define
σ t : = proj r ( σ t − 1 + 1 N t ∑ i = 1 N t clip K t ( Δ t , i ) ) . \sigma_t:=\operatorname{proj}_r\left(\sigma_{t-1}+\frac{1}{N_t}\sum_{i=1}^{N_t}\operatorname{clip}_{K_t}(\Delta_{t,i})\right). σ t := proj r ( σ t − 1 + N t 1 i = 1 ∑ N t clip K t ( Δ t , i ) ) .
Suppose that ∥ ρ − σ t − 1 ∥ F 2 ≤ 2 / 2 t − 1 \|\rho-\sigma_{t-1}\|_F^2\leq2/2^{t-1} ∥ ρ − σ t − 1 ∥ F 2 ≤ 2/ 2 t − 1 . Applying Lemmas B.1 and B.2 gives
∥ σ t − ρ ∥ F 2 ≤ 8 r ∥ 1 N t ∑ i = 1 N t clip K t ( Δ t , i ) − ( ρ − σ t − 1 ) ∥ o p 2 ≤ 8 C 0 2 ( C + 1 ) r log ( 2 d J / δ ) N t ( 2 2 t − 1 + d S t ) ≤ 2 2 t , \begin{aligned}
\|\sigma_t-\rho\|_F^2\leq8r\left\|\frac{1}{N_t}\sum_{i=1}^{N_t}\operatorname{clip}_{K_t}(\Delta_{t,i})-(\rho-\sigma_{t-1})\right\|_{\mathrm{op}}^2 \\
&\le\frac{8C_{0}^{2}(C+1)r\log(2dJ/\delta)}{N_t}\left(\frac{2}{2^{t-1}}+\frac{d}{S_t}\right) \\
&\le\frac{2}{2^t},
\end{aligned} ∥ σ t − ρ ∥ F 2 ≤ 8 r N t 1 i = 1 ∑ N t clip K t ( Δ t , i ) − ( ρ − σ t − 1 ) op 2 ≤ N t 8 C 0 2 ( C + 1 ) r log ( 2 dJ / δ ) ( 2 t − 1 2 + S t d ) ≤ 2 t 2 ,
with conditional probability at least 1 − δ / J 1-\delta/J 1 − δ / J .
Since ρ \rho ρ and σ 0 \sigma_0 σ 0 are quantum states, ∥ ρ − σ 0 ∥ F 2 ≤ 2 \lVert\rho-\sigma_0\rVert_F^2\le2 ∥ ρ − σ 0 ∥ F 2 ≤ 2 . Induction and a union bound therefore show that these bounds hold at every stage with probability at least 1 − δ 1-\delta 1 − δ . On this event, rank ( σ J − ρ ) ≤ 2 r \operatorname{rank}(\sigma_J-\rho)\le2r rank ( σ J − ρ ) ≤ 2 r implies
∥ ρ − σ J ∥ t r ≤ 2 r ∥ ρ − σ J ∥ F ≤ 4 r 2 J ≤ ϵ . \lVert\rho-\sigma_J\rVert_{\mathrm{tr}}\le\sqrt{2r}\lVert\rho-\sigma_J\rVert_F\le\sqrt{\frac{4r}{2^J}}\le\epsilon. ∥ ρ − σ J ∥ tr ≤ 2 r ∥ ρ − σ J ∥ F ≤ 2 J 4 r ≤ ϵ .
Finally, 2 J = O ( r / ϵ 2 ) 2^J=O(r/\epsilon^2) 2 J = O ( r / ϵ 2 ) gives
N = ∑ t = 1 J N t = O ( r J log 2 d J δ ) = O ~ ( r ) , N=\sum_{t=1}^{J}N_t=O\left(rJ\log\frac{2dJ}{\delta}\right)=\widetilde{O}(r), N = t = 1 ∑ J N t = O ( r J log δ 2 dJ ) = O ( r ) ,
T = ∑ t = 1 J N t S t = O ( r d 2 J log 2 d J δ ) = O ~ ( d r 2 ϵ 2 ) . T=\sum_{t=1}^{J}N_tS_t=O\left(rd\,2^J\log\frac{2dJ}{\delta}\right)=\widetilde{O}\left(\frac{dr^2}{\epsilon^2}\right). T = t = 1 ∑ J N t S t = O ( r d 2 J log δ 2 dJ ) = O ( ϵ 2 d r 2 ) .
On the success event, ∥ σ J − ρ ∥ t r ≤ ϵ \lVert\sigma_J-\rho\rVert_{\mathrm{tr}}\le\epsilon ∥ σ J − ρ ∥ tr ≤ ϵ ensures that σ J \sigma_J σ J has at least one positive eigenvalue. By Lemma B.3, replacing ϵ \epsilon ϵ by ϵ / 2 \epsilon/2 ϵ /2 and projecting the final estimate onto the set of quantum states gives a positive semidefinite, unit-trace output with error at most ϵ \epsilon ϵ , without changing the asymptotic bounds on N N N and T T T . All measurement bases and shot counts are chosen in advance, and each measurement circuit has depth O ( log n ) O(\log n) O ( log n ) by Lemma A.2.