Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

IEEE Transactions on Information Theory

Almost Tight Sample Complexity Analysis of Quantum Identity Testing by Pauli Measurements

Nengkun Yu

Published Apr 27, 2023• 3 citations
Publisher

Abstract

This paper studies the quantum identity testing problem, a quantum analogue of distribution identity testing. The goal is to determine whether a quantum state is identical to another fixed quantum state, using as few state samples as possible. Rather than general entangled measurements, we consider the less powerful but experimentally friendly Pauli measurements. We follow the standard setting where Pauli measurements are regarded as two-outcome measurements, i.e., each$n$-qubit Pauli measurement has a one-bit outcome. We prove that for an$n$-qubit quantum system, the sample complexity of this problem is$\Theta \left({\mathrm {poly}(n)\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)$if only Pauli measurements are allowed. In other words, we provide simple algorithms to determine whether two$n$-qubit quantum states,$\rho $and$\sigma $, are identical or$\epsilon $-far in trace distance using Pauli measurements, using$O\left({\min \{n^{4},n^{3}+\log ^{3}(1/\epsilon)\}\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)$copies of$\rho $and$\sigma $. Interestingly,$\mathcal {O}\left({\frac {4^{n}}{\epsilon ^{2}}}\right)$copies are not sufficient under this setting.

DOI
10.1109/tit.2023.3271206

Related papers

Sample optimal Quantum identity testing via Pauli Measurements

Nengkun Yu

In this paper, we show that $Θ(\mathrm{poly}(n)\cdot\frac{4^n}{ε^2})$ is the sample complexity of testing whether two $n$-qubit quantum states $ρ$ and $σ$ are identical or $ε$-far in trace distance using two-outcome Pauli measurements.

arXiv:2009.11518•Sep 24, 2020•6 citations

Efficient Quantum State Identity Testing

Shih-Han Hung, Ming-Hsien Tsai

We study the following quantum state identity problem: given access to copies of $n$ unknown pure quantum states, the goal is to determine whether every pair has fidelity at least $1-\varepsilon$ or some pair has fidelity at most $\varepsilon$. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter $\varepsilon\in(0,1/4)$, we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes $O(\log(n/δ)\log(2/δ))$ copies of each input state to succeed with probability at least $1-δ$. The second uses the Schur transform to reduce the sample complexity to $O(\log(n/δ))$, through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of $Ω(\log(n/δ))$ for any quantum algorithm with failure probability at most $δ\le 1/2-c$, for any constant $c>0$, establishing that the second algorithm achieves the optimal dependence on both $n$ and $δ$ for fixed $\varepsilon$.

quant-pharXiv:2610.04597•Oct 6, 2026•0 citations

Sample efficient tomography via Pauli Measurements

Nengkun Yu

Pauli Measurements are the most important measurements in both theoretical and experimental aspects of quantum information science. In this paper, we explore the power of Pauli measurements in the state tomography related problems. Firstly, we show that the \textit{quantum state tomography} problem of $n$-qubit system can be accomplished with ${\mathcal{O}}(\frac{10^n}{ε^2})$ copies of the unknown state using Pauli measurements. As a direct application, we studied the \textit{quantum overlapping tomography} problem introduced by Cotler and Wilczek in Ref. \cite{Cotler_2020}. We show that the sample complexity is $\mathcal{O}(\frac{10^k\cdot\log({{n}\choose{k}}/δ))}{ε^{2}})$ for quantum overlapping tomography of $k$-qubit reduced density matrices among $n$ is quantum system, where $1-δ$ is the confidential level, and $ε$ is the trace distance error. This can be achieved using Pauli measurements. Moreover, we prove that $Ω(\frac{\log(n/δ)}{ε^{2}})$ copies are needed. In other words, for constant $k$, joint, highly entangled, measurements are not asymptotically more efficient than Pauli measurements.

arXiv:2009.04610•Sep 10, 2020•19 citations

Near-Optimal Mixedness Testing with Pauli Measurements

Jayadev Acharya, Abhilash Dharmavarapu, Yuhan Liu +1 more

We consider a fundamental problem of \emph{mixedness testing}: Given $n$ copies of an $N$-qubit state $ρ$, determine whether $ρ= \mathbb{I}_d/d$ or $\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon$ with high probability, where $d = 2^N$. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing $n = \tildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)$. To establish our lower bound, we introduce a measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube. In conjunction, we provide lower and upper bounds for mixedness testing with fixed Pauli measurement protocols.

quant-pharXiv:2608.18839•Aug 20, 2026•0 citations

Optimal Tradeoffs for Estimating Pauli Observables

Sitan Chen, Weiyuan Gong, Qi Ye

We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum state$\rho$, estimate Tr$(P\rho)$for some set of Pauli operators$F$to within additive error$\epsilon$. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate$\vert \text{Tr}(P\rho)$for all$P$using$O(n/\epsilon^{4})$copies, but with$k\leq n$qubits of memory,$\Omega(2^{(n-k)/3})$copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence on$\epsilon ?$What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subset$A$of Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up to$\log\vert A\vert$factors. •We show any protocol that makes poly$(n)$-copy measure-ments must make$\Omega(1/\epsilon^{4})$measurements. •For any protocol that makes poly$(n)$-copy measurements and only has$k < n$qubits of memory, we show that$\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})$copies are necessary and sufficient. The protocols we propose can also estimate the actual values$\text{Tr}(P\rho)$, rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.

arXiv:2404.19105•Annual Symposium on Foundations of Computer Science•Oct 27, 2024•48 citations

The Power of Two Bases: Robust and copy-optimal certification of nearly all quantum states with few-qubit measurements

Andrea Coladangelo, Jerry Li, Joseph Slote +1 more

A central task in quantum information science is state certification: testing whether an unknown state is $ε_1$-close to a fixed target state, or $ε_2$-far. Recent work has shown that surprisingly simple measurement protocols--comprising only single-qubit measurements--suffice to certify arbitrary $n$-qubit states [Huang, Preskill, Soleimanifar '25; Gupta, He, O'Donnell '25]. However, these certification protocols are not robust: rather than allowing constant $ε_1$, they can only positively certify states within $ε_1=O(1/n)$ trace distance of the target. In many experimental settings, the appropriate error tolerance is constant as the system size grows, so this lack of robustness renders existing tests inapplicable at scale, no matter how many times the test is repeated. Here we present robust certification protocols based on few-qubit measurements that apply to all but a $O(2^{-n})$-fraction of pure target states. Our first protocol achieves constant robustness, i.e. $ε_1=Θ(1)$, using a single $O(\log n)$-qubit measurement along with single-qubit measurements in the $Z$ or $X$ basis on the other qubits. As a corollary of its robustness, this protocol also achieves constant (in $n$) copy complexity, which is optimal. Our second protocol uses exclusively single-qubit measurements and is nearly robust: $ε_1=Ω(1/\log n)$. Our tests are based on a new uncertainty principle for conditional fidelities, which may be of independent interest.

quant-pharXiv:2602.11616•ACM Symposium on Theory of Computing (STOC)•Feb 13, 2026•7 citations
This paper studies the quantum identity testing problem, a quantum analogue of distribution identity testing. The goal is to determine whether a quantum state is identical to another fixed quantum state, using as few state samples as possible. Rather than general entangled measurements, we consider the less powerful but experimentally friendly Pauli measurements. We follow the standard setting where Pauli measurements are regarded as two-outcome measurements, i.e., eachnnn-qubit Pauli measurement has a one-bit outcome. We prove that for annnn-qubit quantum system, the sample complexity of this problem isΘ(poly(n)⋅4nϵ2)\Theta \left({\mathrm {poly}(n)\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)Θ(poly(n)⋅ϵ24n​)if only Pauli measurements are allowed. In other words, we provide simple algorithms to determine whether twonnn-qubit quantum states,ρ\rho ρandσ\sigma σ, are identical orϵ\epsilon ϵ-far in trace distance using Pauli measurements, usingO(min⁡{n4,n3+log⁡3(1/ϵ)}⋅4nϵ2)O\left({\min \{n^{4},n^{3}+\log ^{3}(1/\epsilon)\}\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)O(min{n4,n3+log3(1/ϵ)}⋅ϵ24n​)copies ofρ\rho ρandσ\sigma σ. Interestingly,O(4nϵ2)\mathcal {O}\left({\frac {4^{n}}{\epsilon ^{2}}}\right)O(ϵ24n​)copies are not sufficient under this setting.
In this paper, we show that Θ(poly(n)⋅4nε2)Θ(\mathrm{poly}(n)\cdot\frac{4^n}{ε^2})Θ(poly(n)⋅ε24n​) is the sample complexity of testing whether two nnn-qubit quantum states ρρρ and σσσ are identical or εεε-far in trace distance using two-outcome Pauli measurements.
We study the following quantum state identity problem: given access to copies of nnn unknown pure quantum states, the goal is to determine whether every pair has fidelity at least 1−ε1-\varepsilon1−ε or some pair has fidelity at most ε\varepsilonε. This problem relaxes the identical-or-orthogonal promise considered in previous work. For any fixed overlap parameter ε∈(0,1/4)\varepsilon\in(0,1/4)ε∈(0,1/4), we present two quantum algorithms with complementary guarantees on circuit depth and sample complexity. The first runs in constant depth using parallel swap tests and takes O(log⁡(n/δ)log⁡(2/δ))O(\log(n/δ)\log(2/δ))O(log(n/δ)log(2/δ)) copies of each input state to succeed with probability at least 1−δ1-δ1−δ. The second uses the Schur transform to reduce the sample complexity to O(log⁡(n/δ))O(\log(n/δ))O(log(n/δ)), through an analysis relating Jucys--Murphy elements to Schur sampling. We also prove a matching sample complexity lower bound of Ω(log⁡(n/δ))Ω(\log(n/δ))Ω(log(n/δ)) for any quantum algorithm with failure probability at most δ≤1/2−cδ\le 1/2-cδ≤1/2−c, for any constant c>0c>0c>0, establishing that the second algorithm achieves the optimal dependence on both nnn and δδδ for fixed ε\varepsilonε.
Pauli Measurements are the most important measurements in both theoretical and experimental aspects of quantum information science. In this paper, we explore the power of Pauli measurements in the state tomography related problems. Firstly, we show that the \textit{quantum state tomography} problem of nnn-qubit system can be accomplished with O(10nε2){\mathcal{O}}(\frac{10^n}{ε^2})O(ε210n​) copies of the unknown state using Pauli measurements. As a direct application, we studied the \textit{quantum overlapping tomography} problem introduced by Cotler and Wilczek in Ref. \cite{Cotler_2020}. We show that the sample complexity is O(10k⋅log⁡((nk)/δ))ε2)\mathcal{O}(\frac{10^k\cdot\log({{n}\choose{k}}/δ))}{ε^{2}})O(ε210k⋅log((kn​)/δ))​) for quantum overlapping tomography of kkk-qubit reduced density matrices among nnn is quantum system, where 1−δ1-δ1−δ is the confidential level, and εεε is the trace distance error. This can be achieved using Pauli measurements. Moreover, we prove that Ω(log⁡(n/δ)ε2)Ω(\frac{\log(n/δ)}{ε^{2}})Ω(ε2log(n/δ)​) copies are needed. In other words, for constant kkk, joint, highly entangled, measurements are not asymptotically more efficient than Pauli measurements.
We consider a fundamental problem of \emph{mixedness testing}: Given nnn copies of an NNN-qubit state ρρρ, determine whether ρ=Id/dρ= \mathbb{I}_d/dρ=Id​/d or ∥ρ−Id/d∥1≥ε\|ρ-\mathbb{I}_d/d\|_1 \geq \varepsilon∥ρ−Id​/d∥1​≥ε with high probability, where d=2Nd = 2^Nd=2N. In particular, we focus on performing this task in the practical setting of single-qubit measurements, where measurements are prepared independently on each qubit. We provide a nearly complete picture of single-qubit mixedness tesing by showing n=Θ~(10N/ε2)n = \tildeΘ\left(\sqrt{10}^N/\varepsilon^2\right)n=Θ~(10​N/ε2). To establish our lower bound, we introduce a measurement-dependent lower bound framework for adaptive single-copy state certification. For the upper bound, we present a randomized Pauli basis measurement protocol, which relies on a new primitive for computationally efficient uniformity testing of correlation-concentrated distributions on the Boolean hypercube. In conjunction, we provide lower and upper bounds for mixedness testing with fixed Pauli measurement protocols.
We revisit the problem of Pauli shadow tomography: given copies of an unknown n-qubit quantum stateρ\rhoρ, estimate Tr(Pρ)(P\rho)(Pρ)for some set of Pauli operatorsFFFto within additive errorϵ\epsilonϵ. This has been a popular testbed for exploring the advantage of protocols with quantum memory over those without: with enough memory to measure two copies at a time, one can use Bell sampling to estimate∣Tr(Pρ)\vert \text{Tr}(P\rho)∣Tr(Pρ)for allPPPusingO(n/ϵ4)O(n/\epsilon^{4})O(n/ϵ4)copies, but withk≤nk\leq nk≤nqubits of memory,Ω(2(n−k)/3)\Omega(2^{(n-k)/3})Ω(2(n−k)/3)copies are needed. These results leave open several natural questions. How does this picture change in the physically relevant setting where one only needs to estimate a certain subset of Paulis? What is the optimal dependence onϵ?\epsilon ?ϵ?What is the optimal tradeoff between quantum memory and sample complexity? We answer all of these questions: •For any subsetAAAof Paulis and any family of measurement strategies, we completely characterize the optimal sample complexity, up tolog⁡∣A∣\log\vert A\vertlog∣A∣factors. •We show any protocol that makes poly(n)(n)(n)-copy measure-ments must makeΩ(1/ϵ4)\Omega(1/\epsilon^{4})Ω(1/ϵ4)measurements. •For any protocol that makes poly(n)(n)(n)-copy measurements and only hask<nk < nk<nqubits of memory, we show thatΘ~(min⁡{2n/ϵ2,2n−k/ϵ4})\tilde{\Theta}(\min\{2^{n}/\epsilon^{2},2^{n-k}/\epsilon^{4}\})Θ~(min{2n/ϵ2,2n−k/ϵ4})copies are necessary and sufficient. The protocols we propose can also estimate the actual valuesTr(Pρ)\text{Tr}(P\rho)Tr(Pρ), rather than just their absolute values as in prior work. Additionally, as a byproduct of our techniques, we establish tight bounds for the task of purity testing and show that it exhibits an intriguing phase transition not present in the memory-sample tradeoff for Pauli shadow tomography.
A central task in quantum information science is state certification: testing whether an unknown state is ε1ε_1ε1​-close to a fixed target state, or ε2ε_2ε2​-far. Recent work has shown that surprisingly simple measurement protocols--comprising only single-qubit measurements--suffice to certify arbitrary nnn-qubit states [Huang, Preskill, Soleimanifar '25; Gupta, He, O'Donnell '25]. However, these certification protocols are not robust: rather than allowing constant ε1ε_1ε1​, they can only positively certify states within ε1=O(1/n)ε_1=O(1/n)ε1​=O(1/n) trace distance of the target. In many experimental settings, the appropriate error tolerance is constant as the system size grows, so this lack of robustness renders existing tests inapplicable at scale, no matter how many times the test is repeated. Here we present robust certification protocols based on few-qubit measurements that apply to all but a O(2−n)O(2^{-n})O(2−n)-fraction of pure target states. Our first protocol achieves constant robustness, i.e. ε1=Θ(1)ε_1=Θ(1)ε1​=Θ(1), using a single O(log⁡n)O(\log n)O(logn)-qubit measurement along with single-qubit measurements in the ZZZ or XXX basis on the other qubits. As a corollary of its robustness, this protocol also achieves constant (in nnn) copy complexity, which is optimal. Our second protocol uses exclusively single-qubit measurements and is nearly robust: ε1=Ω(1/log⁡n)ε_1=Ω(1/\log n)ε1​=Ω(1/logn). Our tests are based on a new uncertainty principle for conditional fidelities, which may be of independent interest.