Pauli Measurements Are Near-Optimal for Pure State Tomography Sabee Grewal, Meghal Gupta, William He, Aniruddha Sen, Mihir Singhal Abstract We give an algorithm for pure state tomography with near-optimal copy complexity using single-qubit measurements. Specifically, given O ~ ​ ( 2 n / ε ) \widetilde{O}(2^{n}/\varepsilon) copies of an unknown pure n n -qubit state | ψ ⟩ \lvert\psi\rangle , the algorithm performs only nonadaptive Pauli measurements , runs in time poly ⁡ ( 2 n , 1 / ε ) \mathrm{poly}(2^{n},1/\varepsilon) , and outputs | ψ ^ ⟩ \lvert\widehat{\psi}\rangle that has fidelity 1 − ε 1-\varepsilon with | ψ ⟩ \lvert\psi\rangle with high probability. This improves upon the previous best copy complexity bound of O ~ ​ ( 3 n / ε ) \widetilde{O}(3^{n}/\varepsilon) . 1 Introduction Quantum state tomography is the problem of learning an unknown quantum state from measurement outcomes on independent copies. In this work, we focus on tomography of pure n -qubit states. The learner receives N copies of an unknown state \lvert\psi\rangle\in(\mathbb{C}^{2})^{\otimes n} and must output an estimate \lvert\widehat{\psi}\rangle with high fidelity, e.g., 1-|\langle\widehat{\psi}|\mathopen{}\psi\rangle|^{2}\leq\varepsilon with probability at least 1-\delta . 1 1 1 For pure states, learning with respect to distances such as trace distance, Frobenius distance, and \chi^{2} distance is equivalent, since each is a monotone function of fidelity. If the learner can perform arbitrary measurements, the copy complexity of worst-case pure-state tomography is known to be \Theta(2^{n}/\varepsilon) . This rate is achieved by several procedures and is information-theoretically optimal; see, e.g., [ 9 , 8 , 14 , 7 , 17 , 15 , 16 ] . Moreover, it is well known that the measurements do not need to be entangled across copies to attain this scaling [ 18 , 11 , 8 ] . What remains unclear, however, is whether entanglement is required within each n -qubit copy . Such highly entangled measurements are infeasible in practice, and restricting to simpler measurements would make tomography feasible for larger quantum systems. This motivates the central question of this paper: Can one achieve the optimal \Theta(2^{n}/\varepsilon) copy complexity using only nonadaptive single-qubit (product basis) measurements? An even more ambitious goal is to achieve optimal pure-state tomography using only Pauli basis measurements (i.e. measurements diagonalizing operators \{X,Y,Z\}^{\otimes n} ), a standard and well-studied class of single-qubit measurements. Previously, the strongest guarantee for pure-state tomography using Pauli measurements (and, more generally, any single-qubit measurements) was due to [ 7 ] , who achieved copy complexity \widetilde{O}(3^{n}/\varepsilon) . Their estimator works as follows. First, each copy of the unknown state is measured in a uniformly random Pauli product basis. Each measurement outcome is then converted into a matrix-valued estimate, and these matrices are averaged across samples. 2 2 2 They then apply a projected least-squares step to enforce positivity and unit trace; if one wishes to output a pure state, one may further post-process by taking the eigenvector corresponding to the largest eigenvalue. Neither of these steps has a substantial effect on the accuracy of the estimate. By construction, this average will equal the true state in expectation. However, the number of samples required for this estimator to concentrate is \widetilde{O}(3^{n}/\varepsilon) . Moreover, their variance bound is shown to be tight even for pure product states. Consequently, any approach that follows this paradigm – namely, forming an average of (possibly reweighted) matrices derived from Pauli measurement outcomes and arguing concentration via the matrix Bernstein inequality – cannot asymptotically improve upon the 3^{n} dependence. Our main result shows that the 3^{n} scaling is not a fundamental limitation of all Pauli measurement schemes. We give a different (but still simple) learning algorithm that achieves essentially optimal copy complexity while using only Pauli basis measurements. 3 3 3 The term Pauli measurement can refer to two distinct measurement models. In the first, each qubit is measured independently in one of the X , Y , or Z bases, yielding an n -bit outcome; we refer to this as a Pauli basis measurement . In the second, the two-outcome projective measurement \{(I+P)/2,\,(I-P)/2\} associated with an n -qubit Pauli operator P is applied, yielding a single outcome in \{\pm 1\} ; we refer to this as a Pauli observable measurement . Under the latter model, it is known that \Omega(d^{2}/\varepsilon) samples are necessary for pure state tomography [ 3 , 13 ] . Theorem 1 . There exists an algorithm that, given copies of an unknown n -qubit pure state \lvert\psi\rangle , samples \widetilde{O}(2^{n}\mathrm{poly}(n)\log(1/\delta)/\varepsilon) Pauli product bases, measures one copy of \lvert\psi\rangle in each sampled basis, and outputs an estimate \lvert\widehat{\psi}\rangle satisfying |\langle\widehat{\psi}|\psi\rangle|^{2}\geq 1-\varepsilon with probability at least 1-\delta . The algorithm runs in time \mathrm{poly}(2^{n},1/\varepsilon) . In particular, our copy complexity matches (up to polylogarithmic factors) the \Omega(2^{n}/\varepsilon) lower bound that holds even when the learner is allowed arbitrary measurements. 1.1 Related Work Pauli measurement tomography for mixed states. A direct analogue of our work appear in recent works of Acharya, Dharmavarapu, Liu, and Yu [ 1 , 2 , 19 ] on mixed state tomography using Pauli basis measurements. These works show that (up to polylogarithmic factors) \Theta(10^{n}/\varepsilon) copies are necessary and sufficient for algorithms using nonadaptive Pauli measurements to perform tomography on general mixed states. Interestingly, while nonadaptive Pauli measurements cannot match the copy complexity achieved by general measurement schemes in the mixed-state setting, our work shows that this is not the case for pure state tomography. Additionally, combining our algorithm with the reduction of [ 15 ] yields a sample-optimal (up to polylogarithmic factors) mixed-state tomography algorithm in which all entangling operations are confined to the initial purification step. This is morally similar to settings such as measurement-based quantum computing or magic state distillation, where the more complicated parts of the computation are isolated in an initial preprocessing phase. A separate line of work studies tomography from Pauli observable measurements through the lens of compressed sensing and low-rank matrix recovery, initiated by Gross, Liu, Flammia, Becker, and Eisert [ 5 ] and developed further in, e.g., [ 12 , 3 ] . These works show that a rank- r state in dimension d can be uniquely reconstructed from \widetilde{O}(rd) randomly chosen Pauli observables when their expectation values are known exactly. In the tomography setting, however, we only have noisy empirical estimates of these expectation values. Accounting for this statistical noise gives sample complexity bounds on the order of \widetilde{O}_{\varepsilon}(r^{2}d^{2}) for tomography. This matches the corresponding lower bound of \Omega(r^{2}d^{2}/\varepsilon) samples for tomography from Pauli observable measurements [ 3 , 13 ] . Direct fidelity estimation. We present an algorithm that estimates the Frobenius distance \mathinner{\!\left\lVert\rho-\sigma\right\rVert}_{F} between two (potentially mixed) n -qubit quantum states \rho and \sigma using nonadaptive Pauli measurements; this serves as a key subroutine in our pure-state tomography algorithm. A closely related problem was studied in the direct fidelity estimation (DFE) procedure of Flammia and Liu [ 4 ] , which applies to the special case where both \rho and \sigma are pure (precisely the regime relevant to our algorithm). Their procedure estimates the fidelity between \rho and \sigma to within additive error \pm\gamma^{\prime} , using \tilde{O}(2^{n}/\gamma^{\prime 2}) copies. Since, for pure states, the fidelity is linearly related to the squared Frobenius distance, this yields an estimator for \mathinner{\!\left\lVert\rho-\sigma\right\rVert}_{F} with copy complexity \tilde{O}(2^{n}/\gamma^{\prime 4}) . While this guarantee suffices to obtain a tomography algorithm using \tilde{O}(2^{n}/\mathrm{poly}(\varepsilon)) copies, our stronger Frobenius-distance estimator is required to achieve the optimal dependence on \varepsilon . Quantum state certification. Related to the task of tomography is the task of quantum state certification , in which one is to determine whether an unknown state is close to some hypothesis state given copies of the unknown state. There has been recent work on certifying pure states using single-qubit measurements. See, for example, [ 10 , 6 ] . Interestingly, this line of work shows that to avoid exponentially large copy complexities, adaptivity is necessary. This counters our work, which shows that nonadaptive single-qubit measurements are essentially just as powerful as general measurements for the task of pure state tomography. 2 Technical Overview Our algorithm has two components. First, we show how to perform pure-state tomography assuming access to an estimator that approximates the Frobenius distance between an unknown state and a candidate state \sigma , using only nonadaptive Pauli measurements that do not depend on \sigma . The second component is an implementation of this estimator. 2.1 Tomography via Frobenius Distance Estimation Let \lvert\psi\rangle be a pure n -qubit state. Using \widetilde{O}(2^{n}/\varepsilon) copies, we aim to output \lvert\widehat{\psi}\rangle with |\langle\psi|\mathopen{}\widehat{\psi}\rangle|^{2}\geq 1-\varepsilon . For any x\in\{0,1\}^{\ell} , let p_{x} be the probability of obtaining outcome x when measuring the first \ell qubits of \lvert\psi\rangle in the computational basis, and let \lvert\psi_{x}\rangle be the normalized post-measurement state on the remaining n-\ell qubits conditioned on that outcome. We reconstruct \lvert\psi\rangle recursively along the binary tree of prefixes. At depth k , we maintain estimates \{\lvert\widehat{\psi}_{x}\rangle\mathrel{\mathop{\ordinarycolon}}x\in\{0,1\}^{k}\} . Given estimates at depth k+1 , we will show how to build estimates at depth k . The base case is k=n-1 , where each \lvert\psi_{x}\rangle is a 1 -qubit state (unique up to global phase). Iterating this process up to k=0 will yield \lvert\widehat{\psi}_{\emptyset}\rangle\approx\lvert\psi\rangle . We now describe how to perform this recursive estimation procedure. Fix x\in\{0,1\}^{k} . Given \lvert\widehat{\psi}_{x0}\rangle\approx\lvert\psi_{x0}\rangle and \lvert\widehat{\psi}_{x1}\rangle\approx\lvert\psi_{x1}\rangle , we seek coefficients \widehat{\alpha}_{x0},\widehat{\alpha}_{x1} such that \lvert\widehat{\psi}_{x}\rangle\coloneq\widehat{\alpha}_{x0}\lvert 0\rangle\lvert\widehat{\psi}_{x0}\rangle+\widehat{\alpha}_{x1}\lvert 1\rangle\lvert\widehat{\psi}_{x1}\rangle\approx\lvert\psi_{x}\rangle. By Lemma 4 , there exist coefficients achieving an error (in Frobenius distance) comparable to the weighted errors of the two children, so it suffices to (approximately) solve this 2-parameter optimization problem. We do so by discretizing the coefficient space: let \mathcal{N} be a sufficiently fine net over feasible pairs (\widehat{\alpha}_{x0},\widehat{\alpha}_{x1}) , and output the candidate in \mathcal{N} minimizing its distance to \lvert\psi_{x}\rangle . Thus, for each x we just need to estimate the distance from \lvert\psi_{x}\rangle to every candidate in \mathcal{N} . On each copy of \lvert\psi\rangle we first measure the first k qubits in the computational basis, obtaining some prefix x\in\{0,1\}^{k} with probability p_{x} and leaving the post-selected state \lvert\psi_{x}\rangle on the remaining n-k qubits. With N=\widetilde{O}(2^{n}/\varepsilon) total copies, outcome x appears about Np_{x}=\widetilde{O}(2^{n}p_{x}/\varepsilon) times, giving us that many effective samples from \lvert\psi_{x}\rangle . For each such x , our goal is then to decide which candidate in the net \mathcal{N} is closest to \lvert\psi_{x}\rangle . Concretely, this reduces to estimating (for all \sigma\in\mathcal{N} ) the distance between the unknown state \lvert\psi_{x}\rangle\langle\psi_{x}\rvert and the known candidate \sigma , and picking the minimizer. This is exactly where the Frobenius-distance estimator from Section 2.2 is used: it provides, for any fixed \sigma , an estimate of \|\lvert\psi_{x}\rangle\langle\psi_{x}\rvert-\sigma\|_{F} from appropriate measurements on copies of \lvert\psi_{x}\rangle (and by a union bound, provides such an estimate for all \sigma\in\mathcal{N} ). The only subtlety is that the measurements on the last n-k qubits must be fixed before we learn x : we cannot choose the measurement basis adaptively as a function of the observed prefix. To handle this, fix a probability scale p and consider all prefixes with p_{x}\approx p . It suffices to choose a global list of m=\widetilde{O}(2^{n}p/\varepsilon) measurement settings (independent of x ) that would let the Frobenius estimator compare \lvert\psi_{x}\rangle to any fixed \sigma , which is exactly what Section 2.2 provides; we then repeat each setting \Theta((1/p)\mathrm{poly}(n)) times, always measuring the first k qubits in the computational basis and binning outcomes by the observed x . For any x with p_{x}\approx p , with high probability each setting in the global list is applied at least once within the bin for x , so we obtain exactly the measurement data needed to run the distance estimator for that x . Finally, since the probabilities p_{x} vary with x , we run the above procedure for p\in\{2^{-n},2^{-(n-1)},\dots,1\} ; every p_{x} lies within a constant factor of some dyadic p , so the appropriate run handles it. One point to emphasize is that our approach is only efficient because each node requires optimizing over only two continuous parameters, so |\mathcal{N}| remains small and we can estimate distances to all candidates simultaneously via a union bound. If we had created a net over all the possible states \lvert\psi\rangle from the start without building a binary tree, there would have been \exp(d) candidates, and union bounding over those would introduce an extra factor of d to the sample complexity. This binary-tree structure breaks up the O(d) parameter optimization problem into many 2-parameter optimization problems, which is special to pure states; that is why our method does not work for mixed states. 2.2 Frobenius Distance Estimation Suppose that \rho and \sigma are (potentially mixed) n -qubit states. We are given access to copies of \rho and to a full classical description of \sigma . Our goal is to estimate the quantity \mathinner{\!\left\lVert\rho-\sigma\right\rVert}_{F} up to additive error \gamma , using a fixed (nonadaptive) list of measurements that does not depend on either \rho or \sigma , and using O(d/\gamma^{2}) samples. In the description of our algorithm, we will assume access to samples of both \rho and \sigma , rather than a full description of \sigma . This is more general, because a classical description of \sigma allows us to simulate measurements on it. The first step is to note that \mathinner{\!\left\lVert\rho-\sigma\right\rVert}_{F}=2\sqrt{d}\sqrt{\mathop{{\bf E}\/}_{P}[v_{P}^{2}]} , where v is a real vector of length 4^{n} , indexed by n -qubit Pauli matrices, defined by v_{P}=\frac{1}{2}\mathrm{Tr}(P(\rho-\sigma)) (so that we always have |v_{P}|\leq 1 ). By measuring \rho and \sigma with respect to the observable P , for any fixed P we can draw samples from a Rademacher random variable with mean v_{P} using just one copy each of \rho and \sigma . Therefore, estimating the Frobenius distance using nonadaptive Pauli measurements reduces to the following problem: estimate \sqrt{r}\coloneq\sqrt{\mathop{{\bf E}\/}_{k}[v_{k}^{2}]} to additive error \alpha for vectors v\in[-1,1]^{N} , given the ability to specify a multiset \{k_{1},\dots,k_{T}\} and receive Rademacher samples with means v_{k_{1}},\dots,v_{k_{T}} . We need the number of samples T to be \tilde{O}(1/\alpha^{2}) . To motivate the algorithm, let us imagine that all entries of v are either small (close to 0 ) or big (have absolute value close to 1 ). Write r=r_{\text{small}}+r_{\text{big}} , where r_{\text{small}} and r_{\text{big}} are the contributions to r from small and big indices, respectively. Our goal is to produce an estimator \widehat{r} satisfying |\widehat{r}-r|\lesssim\alpha\sqrt{r}+\alpha^{2} , since such an estimate can be converted into an estimator for \sqrt{r} with additive \alpha error. At a constant factor loss, it suffices to estimate \widehat{r}_{\text{small}} and \widehat{r}_{\text{big}} separately with guarantees \displaystyle|\widehat{r}_{\text{small}}-r_{\text{small}}|\lesssim\alpha\sqrt{r_{\text{small}}}+\alpha^{2},\quad|\widehat{r}_{\text{big}}-r_{\text{big}}|\lesssim\alpha\sqrt{r_{\text{big}}}+\alpha^{2}. (1) 1. To estimate r_{\text{small}} , we sample a small number of indices k_{1},\dots,k_{T_{\text{small}}} , and take many samples of each v_{k_{t}} to get accurate estimates of their values, throwing out the values that are too large. We then output the average of the remaining values v_{k_{i}}^{2} . If r_{\text{small}} is nonnegligible, there must be many small indices, so sampling only T_{\text{small}} indices suffices to hit enough of them. On the other hand, many samples per index are needed to estimate their values accurately enough to satisfy ( 1 ). 2. To estimate r_{\text{big}} , we instead sample a large number T_{\text{big}} of indices k_{1},\dots,k_{T_{\text{big}}} , take a small number of samples of each v_{k_{t}} , discard indices whose empirical averages are too small, and output the average of the corresponding values v_{k_{t}}^{2} . Here, many indices are required to ensure that large entries are encountered if they contribute significantly to r , but only a few samples per index suffice, since we need only a coarse estimate of v_{k_{t}} when v_{k_{t}}^{2} is large. Thresholding based on the empirical values of v_{k_{t}} introduces two issues. First, the resulting estimate of v_{k} is no longer unbiased when conditioned on an index being classified as small or big. Second, for indices whose true values lie near the threshold, the thresholding rule may assign the index to neither or both categories with nonzero probability. Consequently, the probabilities with which an index contributes to the small and big parts may not sum to one, leading to under- or over-counting in expectation. To fix both of these issues at once, before estimating v_{k_{t}} , we run a fixed process that uses the Rademacher samples to classify the index as small or big, so that it only contributes to one of the two categories, and then independently compute the estimate of v_{k_{t}} . To extend our algorithm to a general algorithm, rather than splitting indices into only two categories, we partition them into \log(1/\alpha) level sets, where the j th level consists roughly of indices k with {\left|v_{k}\right|}\in[2^{-j},2^{-j+1}] ). It turns out that to achieve the desired approximation guarantee, we can take T_{j}\approx\alpha^{-2}/4^{j} indices in level j , and take m_{j}\approx 4^{j} samples of each index. Summing over all levels yields a total sample complexity of \widetilde{O}(1/\alpha^{2}) as desired. 3 Preliminaries 3.1 Notation For mixed states \rho and \sigma , let \mathinner{\!\left\lVert\rho-\sigma\right\rVert}_{F} denote the Frobenius distance between the two states. For pure states \lvert\psi\rangle and \lvert\varphi\rangle , let d_{F}(\lvert\psi\rangle,\lvert\varphi\rangle)\coloneq\mathinner{\!\left\lVert\lvert\psi\rangle\!\langle\psi\rvert-\lvert\varphi\rangle\!\langle\varphi\rvert\right\rVert}_{F} be shorthand for the Frobenius distance between two pure states. 3.2 Concentration Bounds We will use the following standard concentration bounds. Lemma 2 (Hoeffding for {[-1,1]} random variables) . Let Y_{1},\dots,Y_{n} be independent random variables with \operatorname{{\bf E}}[Y_{i}]=\mu_{i} and Y_{i}\in[-1,1] almost surely. Let S\coloneqq\sum_{i=1}^{n}(Y_{i}-\mu_{i}). Then for every \gamma\geq 1 , \Pr[|S|>\gamma\sqrt{n}]\leq 2\exp(-\gamma^{2}/8). Lemma 3 (Bernstein for {[0,B]} random variables) . Let X_{1},\dots,X_{m} be independent random variables with X_{i}\in[0,B] and let S\coloneqq\sum_{i=1}^{m}X_{i},\qquad\mu\coloneqq\operatorname{{\bf E}}[S]. Then for every \gamma\geq 1 , \Pr[\lvert S-\mu\rvert>\gamma(\sqrt{B\mu}+B)]\leq 2\exp(-\gamma/2). Proof. If Y_{1},\dots,Y_{m} are independent, mean-zero, and satisfy |Y_{i}|\leq B , and if V\coloneqq\sum_{i=1}^{m}\operatorname{{\bf E}}[Y_{i}^{2}] , then for all t\geq 0 , then by Bernstein’s inequality, \displaystyle\Pr\left[\sum_{i=1}^{m}Y_{i}\geq t\right]\leq\exp\left(-\frac{t^{2}}{2(V+Bt/3)}\right), (2) and the same holds for the lower tail. Now set Y_{i}\coloneq X_{i}-\operatorname{{\bf E}}[X_{i}] , so |Y_{i}|\leq B . Also \operatorname{{\bf E}}[Y_{i}^{2}]\leq\operatorname{{\bf E}}[X_{i}^{2}]\leq B\operatorname{{\bf E}}[X_{i}] since 0\leq X_{i}\leq B , hence V=\sum_{i}\operatorname{{\bf E}}[Y_{i}^{2}]\leq B\sum_{i}\operatorname{{\bf E}}[X_{i}]=B\mu. Use ( 2 ) with V\leq B\mu and take t=\gamma(\sqrt{B\mu}+B) . We check \frac{t^{2}}{2(B\mu+Bt/3)}\geq\gamma/2\qquad(\gamma\geq 1), so \Pr[S-\mu>t]\leq e^{-\gamma/2} and similarly \Pr[\mu-S>t]\leq e^{-\gamma/2} . Using a union bound gives \Pr[|S-\mu|>\gamma(\sqrt{B\mu}+B)]\leq 2e^{-\gamma/2}. ∎ 4 The Algorithm It will be useful to describe \lvert\psi\rangle as a binary tree. Set \lvert\psi_{\emptyset}\rangle\coloneq\lvert\psi\rangle,\qquad p_{\emptyset}\coloneq 1. For any string x\in\{0,1\}^{2^{-b} then 16: return \mathbf{1}[b=j] . 17: end if 18: end for 19: return 0. 20: end function 21: 22: for j=0,\dots,J do 23: T_{j}\leftarrow\alpha^{-2}/4^{j} . 24: for t=1,\dots,T_{j} do 25: U_{j,t}\leftarrow\textsc{Est-v-Squared}(j,t) . 26: \widetilde{U}_{j,t}\leftarrow\min(U_{j,t},16\cdot 4^{-j}) 27: Z_{j,t}\leftarrow\textsc{Level-Check}(j,t) . 28: \widehat{r}_{j,t}\leftarrow\widetilde{U}_{j,t}Z_{j,t} . 29: end for 30: \widehat{r}_{j}\leftarrow\frac{1}{T_{j}}\sum_{t=1}^{T_{j}}\widehat{r}_{j,t} . 31: end for 32: return \widehat{q}=\sqrt{\sum_{j=0}^{J}\widehat{r}_{j}} . Algorithm 4 Build-Estimator (\alpha,\{(k_{j,t},X_{j,t,a})\}) Fix x\in[-1,1] . To define L(x) , consider the following infinite version of Level-Check that has direct access to an i.i.d. stream of Rademacher random variables of mean x . Draw n_{b}=4^{J}n_{0} samples Y^{(b)}_{1},\dots,Y^{(b)}_{n_{b}} with \operatorname{{\bf E}}[Y^{(b)}_{i}]=x , and let \overline{Y_{b}}\coloneqq\frac{1}{n_{b}}\sum_{i=1}^{n_{b}}Y^{(b)}_{i}. If there exists b\leq J with |\overline{Y_{b}}|>2^{-b} , let L(x) be the smallest such b ; otherwise set L(x)=J+1 . By construction, L(x) is the first level at which the empirical mean looks “large” relative to the threshold 2^{-b} . We couple the randomness in \textsc{Level-Check}(j,t) with the randomness in L(\cdot) so that, conditioned on k_{j,t} , the random variable Z_{j,t}=\textsc{Level-Check}(j,t) has the same distribution as \mathbf{1}_{L(v_{k_{j,t}})=j} . In particular, we write z_{j,t}\coloneqq\operatorname{{\bf E}}[Z_{j,t}\mid k_{j,t}]=\Pr[L(v_{k_{j,t}})=j\mid k_{j,t}]. We now prove several concentration lemmas relating v_{k} , L(v_{k}) , and the random variables U_{j,t} and Z_{j,t} . Lemma 12 . For any fixed x\in[-1,1] , with probability 1-O(\alpha^{2}) over the randomness defining L(x) , the following holds: • If L(x)=j\in\{0,\dots,J\} then 0.9\cdot 2^{-j}\leq\text{len}(x)\leq 2.2\cdot 2^{-j}. • If L(x)=J+1 then \text{len}(x)\leq 2.2\cdot 2^{-J}=O(\alpha). Proof. For each b=0,\dots,J , let \overline{X}_{b} be the empirical mean of the 4^{b}n_{0} Rademacher samples (of mean x ) used at level b . By the Hoeffding bound ( Lemma 2 ), we have \Pr[|\overline{X}_{b}-x|>0.1\cdot 2^{-b}]\leq O(\alpha^{10}), using n_{0}=1000\log(1/\alpha^{2}) . By a union bound over b=0,\dots,J=O(\log(1/\alpha^{2})) , with probability 1-O(\alpha^{2}) we have |\overline{X}_{b}-x|\leq 0.1\cdot 2^{-b}\qquad\text{for all }b. (8) Assuming ( 8 ) holds for every b , the conclusion immediately follows by the definition of L(x) . ∎ Lemma 13 . For each j\leq J and t , conditioned on k_{j,t} , with probability 1-O(\alpha^{2}) we have |\mu^{(1)}-v_{k_{j,t}}|\leq 0.05\cdot 2^{-j}\quad\text{and}\quad|\mu^{(2)}-v_{k_{j,t}}|\leq 0.05\cdot 2^{-j}, where \mu^{(1)},\mu^{(2)} are the quantities computed in Est-v-Squared . Proof. Condition on k_{j,t} , each \mu^{(\ell)} is the average of m_{j}/4=4^{j-1}m_{0} i.i.d. Rademacher variables with mean v_{k_{j,t}} and range in [-1,1] . Thus, the conclusion again follows directly from a Hoeffding bound ( Lemma 2 ). ∎ Lemma 14 . For each j\leq J and t , conditioned on k_{j,t} , with probability 1-O(\alpha^{2}) we have U_{j,t}Z_{j,t}=\tilde{U}_{j,t}Z_{j,t}. Proof. Fix j,t and condition on k_{j,t} , writing x\coloneq v_{k_{j,t}} . If Z_{j,t}=0 then both sides are 0 , so we will study what happens when Z_{j,t}=1 . Recall that by how we defined L(x) (running the same Level-Check procedure to all levels), we can couple so that Z_{j,t}=1 if and only if L(x)=j , while having failure probability O(\alpha^{2}) . Therefore, by Lemma 12 applied to x , with probability 1-O(\alpha^{2}) we have Z_{j,t}=1\implies\text{len}(x)\leq 2.2\cdot 2^{-j}. By Lemma 13 (for the same j,t ), with probability 1-O(\alpha^{2}) we have |\mu^{(1)}-x|\leq 0.05\cdot 2^{-j}\quad\text{and}\quad|\mu^{(2)}-x|\leq 0.05\cdot 2^{-j}. Combining these, we have with probability 1-O(\alpha^{2}) that Z_{j,t}=1\implies|\mu^{(1)}|,\ |\mu^{(2)}|\leq 2.25\cdot 2^{-j}, and therefore Z_{j,t}=1\implies|U_{j,t}|<16\cdot 4^{-j}. Thus, except with probability 1-O(\alpha^{2}) , we have either Z_{j,t}=0 or |U_{j,t}|<16\cdot 4^{-j} (which implies that U(j,t)=\tilde{U}(j,t) ), and thus we are done. ∎ Lemma 15 . For each j\leq J and t , conditioned on k_{j,t} we have \operatorname{{\bf E}}[\widehat{r}_{j,t}]=v_{k_{j,t}}^{2}\cdot z_{j,t}+O(\alpha^{2}), where z_{j,t}=\Pr[L(v_{k_{j,t}})=j\mid k_{j,t}] (as defined above). Proof. Fix j,t and condition on k_{j,t} for the entire proof of this lemma. For brevity we write U\coloneq U_{j,t} , Z\coloneq Z_{j,t} and \widetilde{U}\coloneq\tilde{U}_{j,t} . By Lemma 14 , \Pr[\widetilde{U}Z\neq UZ]=O(\alpha^{2}), and |\widetilde{U}Z|,|UZ|\leq 1 , so \bigl|\operatorname{{\bf E}}[\widetilde{U}Z]-\operatorname{{\bf E}}[UZ]\bigr|\leq 2\Pr[\widetilde{U}Z\neq UZ]=O(\alpha^{2}). Now, note that UZ=\mu^{(1)}\mu^{(2)}Z , and \mu^{(1)},\mu^{(2)} , Z are independent given k_{j,t} , since they are computed from disjoint samples. Since \operatorname{{\bf E}}[\mu^{(1)}]=\operatorname{{\bf E}}[\mu^{(2)}]=v_{k_{j,t}} , and \operatorname{{\bf E}}[Z]=z_{j,t} , the conclusion follows. ∎ Corollary 16 . For each j , we have \operatorname{{\bf E}}[\widehat{r}_{j}]=\operatorname{{\bf E}}_{k\sim[N]}[v_{k}^{2}\mathbf{1}_{L(v_{k})=j}]+O(\alpha^{2}). Proof. Recall \widehat{r}_{j}=\frac{1}{T_{j}}\sum_{t=1}^{T_{j}}\widehat{r}_{j,t} and that each k_{j,t} is independent and uniform in [N] . Thus, this follows directly from the previous lemma. ∎ Now, define r_{j}=\operatorname{{\bf E}}_{k\sim[N]}[v_{k}^{2}\mathbf{1}_{L(v_{k})=j}] . Lemma 17 . For each j\leq J , with probability 1-O(\alpha^{2}) we have |\widehat{r}_{j}-r_{j}|\leq\tilde{O}\big(\alpha\sqrt{r_{j}}+\alpha^{2}\big), where r_{j}=\operatorname{{\bf E}}_{k\sim[N]}[v_{k}^{2}\mathbf{1}_{L(v_{k})=j}] . Proof. Fix j . Note that the random variables \widehat{r}_{j,1},\dots,\widehat{r}_{j,T_{j}} are independent, nonnegative, and bounded: 0\leq\widehat{r}_{j,t}\leq B_{j}\coloneqq 16\cdot 4^{-j}. Recall that \widehat{r}_{j}=\frac{1}{T_{j}}\sum_{t=1}^{T_{j}}\widehat{r}_{j,t}, and let \mu_{j}=\operatorname{{\bf E}}[\widehat{r}_{j}] . Note that \mu_{j}=r_{j}+O(\alpha^{2}) by Corollary 16 . By a Chernoff bound ( Lemma 3 ) on T_{j}\widehat{r}_{j}=\sum\widehat{r}_{j,t} , with B=B_{j} and \gamma=\Theta(\log(1/\alpha)) , we have with probability at least 1-O(\alpha^{2}) that |\widehat{r}_{j}-\mu_{j}|\leq\frac{\gamma}{T_{j}}\bigl(\sqrt{B_{j}T_{j}\mu_{j}}+B_{j}\bigr). We have B_{j}/T_{j}=16\alpha^{2} , so substituting this into the above expression gives |\widehat{r}_{j}-\mu_{j}|\leq\gamma(4\alpha\sqrt{\mu_{j}}+16\alpha^{2})=\tilde{O}(\alpha\sqrt{\mu_{j}}+\alpha^{2}). By Corollary 16 , we have \mu_{j}=r_{j}+O(\alpha^{2}) , so \alpha\sqrt{\mu_{j}}=\alpha\sqrt{r_{j}+O(\alpha^{2})}=\tilde{O}\big(\alpha\sqrt{r_{j}}+\alpha^{2}\big), and |\mu_{j}-r_{j}|=O(\alpha^{2}). Combining these bounds, we get |\widehat{r}_{j}-r_{j}|\leq\tilde{O}(\alpha\sqrt{r_{j}}+\alpha^{2}), except with probability O(\alpha^{2}) , as desired. ∎ Now, write r\coloneq\operatorname{{\bf E}}_{k\sim[N]}[v_{k}^{2}],. We wish to show that |\widehat{q}-\sqrt{r}|=\tilde{O}(\alpha) with probability at least 2/3 . Recall that we had earlier defined r_{j}=\operatorname{{\bf E}}_{k\sim[N]}[v_{k}^{2}\mathbf{1}_{L(v_{k})=j}]. Thus we have r=\sum_{j=0}^{J}r_{j}+r_{J+1}. By the first lemma, whenever L(v_{k})=J+1 we have |v_{k}|=O(\alpha) except with probability O(\alpha^{2}) over the randomness defining L , so r_{J+1}=O(\alpha^{2}). By Lemma 17 and a union bound over j , with probability 1-\tilde{O}(\alpha^{2}) we have |\widehat{r}_{j}-r_{j}|\leq\tilde{O}\big(\alpha\sqrt{r_{j}}+\alpha^{2}\big),\quad\text{for all $0\leq j\leq J$}. Assuming (for the rest of the proof) that this holds, we have \displaystyle|\widehat{q}^{2}-r| \displaystyle=\left|\sum_{j=0}^{J}\widehat{r}_{j}-\sum_{j=0}^{J}r_{j}-r_{J+1}\right|\leq\sum_{j=0}^{J}\tilde{O}\big(\alpha\sqrt{r_{j}}+\alpha^{2}\big)+O(\alpha^{2})=\tilde{O}\big(\alpha\sqrt{r}+\alpha^{2}\big), using \sum_{j}r_{j}\leq r and J=\tilde{O}(1) . Finally, we bound the error in \widehat{q} . If r\geq c\alpha^{2} for a suitable constant c>0 , then |\widehat{q}-\sqrt{r}|=\frac{|\widehat{q}^{2}-r|}{\widehat{q}+\sqrt{r}}\leq\frac{\tilde{O}(\alpha\sqrt{r}+\alpha^{2})}{\sqrt{r}}=\tilde{O}(\alpha). If instead r\leq c\alpha^{2} , then we also have |\widehat{q}^{2}|\leq r+|\widehat{q}^{2}-r|=O(\alpha^{2}) , so |\widehat{q}-\sqrt{r}|\leq\widehat{q}+\sqrt{r}=O(\alpha). Thus in all cases |\widehat{q}-\sqrt{r}|=\tilde{O}(\alpha), and for small enough absolute constants in the algorithm the overall success probability is at least 2/3 , completing the proof of Theorem 11 (noting that we can reduce \alpha by a logarithmic factor to make the approximation error actually \alpha ).