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

arXiv:2009.11518

Sample optimal Quantum identity testing via Pauli Measurements

Nengkun Yu

Published Sep 24, 2020• 3 citations
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2009.11518

Related papers

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

Nengkun Yu

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.

IEEE Transactions on Information Theory•Apr 27, 2023•3 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•7 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•16 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

Testing identity of collections of quantum states: sample complexity analysis

Marco Fanizza, Raffaele Salvia, Vittorio Giovannetti

We study the problem of testing identity of a collection of unknown quantum states given sample access to this collection, each state appearing with some known probability. We show that for a collection of d -dimensional quantum states of cardinality N , the sample complexity is O(Nd/ϵ2) , with a matching lower bound, up to a multiplicative constant. The test is obtained by estimating the mean squared Hilbert-Schmidt distance between the states, thanks to a suitable generalization of the estimator of the Hilbert-Schmidt distance between two unknown states by Bădescu, O'Donnell, and Wright \cite{Badescu2019}.

arXiv:2103.14511•Quantum•Sep 11, 2023•1 citation

Quantum Closeness Testing: A Streaming Algorithm and Applications

Nengkun Yu

In this paper, we study the quantum identity testing problem, i.e., testing whether two given quantum states are identical, and quantum independence testing problem, i.e., testing whether a given multipartite quantum state is in tensor product form. For the quantum identity testing problem of 𝒟(ℂ^d) system, we provide a deterministic measurement scheme that uses 𝒪(d²/ε²) copies via independent measurements with d being the dimension of the state and ε being the additive error. For the independence testing problem 𝒟(ℂ^d₁⊗ℂ^{d₂}⊗⋯⊗ℂ^{d_m}) system, we show that the sample complexity is Θ̃((Π_{i = 1}^m d_i)/ε²) via collective measurements, and 𝒪((Π_{i = 1}^m d_i²)/ε²) via independent measurements. If randomized choice of independent measurements are allowed, the sample complexity is Θ(d^{3/2}/ε²) for the quantum identity testing problem, and Θ̃((Π_{i = 1}^m d_i^{3/2})/ε²) for the quantum independence testing problem.

arXiv:1904.03218•Leibniz international proceedings in informatics•Apr 5, 2019•14 citations
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.
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 andandand\sigma ,areidenticalor, are identical or,areidenticalor\epsilon −farintracedistanceusingPaulimeasurements,using-far in trace distance using Pauli measurements, using−farintracedistanceusingPaulimeasurements,usingO\left({\min \{n^{4},n^{3}+\log ^{3}(1/\epsilon)\}\cdot \frac {4^{n}}{\epsilon ^{2}}}\right)copiesofcopies ofcopiesof\rho andandand\sigma .Interestingly,. Interestingly,.Interestingly,\mathcal {O}\left({\frac {4^{n}}{\epsilon ^{2}}}\right)$copies are not sufficient under this setting.
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 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.
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ε.
We study the problem of testing identity of a collection of unknown quantum states given sample access to this collection, each state appearing with some known probability. We show that for a collection of d -dimensional quantum states of cardinality N , the sample complexity is O(Nd/ϵ2) , with a matching lower bound, up to a multiplicative constant. The test is obtained by estimating the mean squared Hilbert-Schmidt distance between the states, thanks to a suitable generalization of the estimator of the Hilbert-Schmidt distance between two unknown states by Bădescu, O'Donnell, and Wright \cite{Badescu2019}.
In this paper, we study the quantum identity testing problem, i.e., testing whether two given quantum states are identical, and quantum independence testing problem, i.e., testing whether a given multipartite quantum state is in tensor product form. For the quantum identity testing problem of 𝒟(ℂ^d) system, we provide a deterministic measurement scheme that uses 𝒪(d²/ε²) copies via independent measurements with d being the dimension of the state and ε being the additive error. For the independence testing problem 𝒟(ℂ^d₁⊗ℂ^{d₂}⊗⋯⊗ℂ^{d_m}) system, we show that the sample complexity is Θ̃((Π_{i = 1}^m d_i)/ε²) via collective measurements, and 𝒪((Π_{i = 1}^m d_i²)/ε²) via independent measurements. If randomized choice of independent measurements are allowed, the sample complexity is Θ(d^{3/2}/ε²) for the quantum identity testing problem, and Θ̃((Π_{i = 1}^m d_i^{3/2})/ε²) for the quantum independence testing problem.