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:2602.11616

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, Ellen Wu

quant-phSubmitted Feb 12, 2026• Announced Feb 13, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Comments
22 + 6 pages

Related papers

The Power of Two Bases: Robust and Copy-Optimal Certification of Nearly All Quantum States with Few-Qubit Measurements

Andrea Coladangelo, Jerry Zheng 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. 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.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•0 citations

Robust quantum state certification and uncertainty principles for total influence

Andrea Coladangelo, Jerry Li, Joseph Slote

We show that nonadaptive single-qubit Pauli measurements suffice to test whether an unknown $n$-qubit state $ρ$ is $\varepsilon$-close to or $O(\varepsilon)$-far from an ideal target state $|ψ\rangle$, for all but a $2^{-Ω(n)}$ fraction of target states. The test uses $O(\varepsilon^{-2}\log(1/δ))$ copies of $ρ$ to achieve confidence $1-δ$, which is information-theoretically optimal even among protocols with arbitrary joint measurements. The main technical innovation is an uncertainty principle for weighted generalizations of the total influence of Boolean functions. As a simple example, the unweighted variant states that $\mathbf{Inf}[f]+\mathbf{Inf}[\widehat{f}] = Ω(n)$, which is a natural hypercube analogue of the Heisenberg uncertainty principle (here $\widehat{\,\cdot\,}$ denotes the $2^{-n/2}$-normalized Fourier transform). The weighted case generalizes $\mathbf{Inf}[\,\cdot\,]$ and $\mathbf{Inf}[\,\widehat{\,\cdot\,}\,]$ to Dirichlet energies associated with Glauber dynamics for certain dual measures on the cube.

quant-pharXiv:2607.27184•Jul 30, 2026•0 citations

Optimal Quantum State Testing Even with Limited Entanglement

Chirag Wadhwa, Sitan Chen

In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state $ρ$, test whether it matches some target state $σ$ or is $ε$-far from it. For certifying $d$-dimensional states, $Θ(d/ε^2)$ copies of $ρ$ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all $O(d/ε^2)$ copies of $ρ$. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on $t$ copies at once, for some $1 < t \ll d/ε^2$. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements. Our main result is a smooth copy complexity upper bound for state certification as a function of $t$, which achieves a near-optimal rate at $t = d^2$. In the high-precision regime, i.e., for $ε< \frac{1}{\sqrt{d}}$, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at $t = d^2$ as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our testing upper bounds with a (nearly) matching lower bound that holds in the high-precision regime, implying that one must take $t \geq Ω(d^2)$ to achieve the optimal rate for certification.

quant-pharXiv:2604.07460•Apr 10, 2026•0 citations

Few Single-Qubit Measurements Suffice to Certify Any Quantum State

Meghal Gupta, William He, Ryan O'Donnell

A fundamental task in quantum information science is state certification: testing whether a lab-prepared n-qubit state is close to a given hypothesis state. In this work, we show that every pure hypothesis state can be certified using only O(n^2) single-qubit measurements applied to O(n) copies of the lab state. Prior to our work, it was not known whether even subexponentially many single-qubit measurements could suffice to certify arbitrary states. This resolves the main open question of Huang, Preskill, and Soleimanifar (FOCS 2024, QIP 2024).

arXiv:2506.11355•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•2 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

Certifying unknown-basis pure-state entanglement dimensionality with few measurement settings

Changhao Yi

We introduce a basis-independent algorithm that only uses single-copy measurements to certify the Schmidt number of $2n$-qubit bipartite pure states. Assuming the local system dimension is $d = 2^n$, the Schmidt number $χ$ is $O(1)$, and the non-zero Schmidt coefficients are bounded below by $Ω(1)$, our protocol achieves a total sample complexity of $\widetilde{O}(d^2χ^2)$ with only $\widetilde{O}(χ^4)$ measurement settings. This work establishes a measurement-setting-efficient approach to high-dimensional entanglement certification.

quant-pharXiv:2601.11040•Jan 19, 2026•0 citations
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.
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. 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.
We show that nonadaptive single-qubit Pauli measurements suffice to test whether an unknown nnn-qubit state ρρρ is ε\varepsilonε-close to or O(ε)O(\varepsilon)O(ε)-far from an ideal target state ∣ψ⟩|ψ\rangle∣ψ⟩, for all but a 2−Ω(n)2^{-Ω(n)}2−Ω(n) fraction of target states. The test uses O(ε−2log⁡(1/δ))O(\varepsilon^{-2}\log(1/δ))O(ε−2log(1/δ)) copies of ρρρ to achieve confidence 1−δ1-δ1−δ, which is information-theoretically optimal even among protocols with arbitrary joint measurements. The main technical innovation is an uncertainty principle for weighted generalizations of the total influence of Boolean functions. As a simple example, the unweighted variant states that Inf[f]+Inf[f^]=Ω(n)\mathbf{Inf}[f]+\mathbf{Inf}[\widehat{f}] = Ω(n)Inf[f]+Inf[f​]=Ω(n), which is a natural hypercube analogue of the Heisenberg uncertainty principle (here  ⋅ ^\widehat{\,\cdot\,}⋅ denotes the 2−n/22^{-n/2}2−n/2-normalized Fourier transform). The weighted case generalizes Inf[ ⋅ ]\mathbf{Inf}[\,\cdot\,]Inf[⋅] and Inf[  ⋅ ^ ]\mathbf{Inf}[\,\widehat{\,\cdot\,}\,]Inf[⋅] to Dirichlet energies associated with Glauber dynamics for certain dual measures on the cube.
In this work, we consider the fundamental task of quantum state certification: given copies of an unknown quantum state ρρρ, test whether it matches some target state σσσ or is εεε-far from it. For certifying ddd-dimensional states, Θ(d/ε2)Θ(d/ε^2)Θ(d/ε2) copies of ρρρ are known to be necessary and sufficient. However, the algorithm achieving this complexity makes fully entangled measurements over all O(d/ε2)O(d/ε^2)O(d/ε2) copies of ρρρ. Often, one is interested in certifying states to a high precision; this makes such joint measurements intractable even for low-dimensional states. Thus, we study whether one can obtain optimal rates for quantum state certification and related testing problems while only performing measurements on ttt copies at once, for some 1<t≪d/ε21 < t \ll d/ε^21<t≪d/ε2. While it is well-understood how to use intermediate entanglement to achieve optimal quantum state learning, the only protocol known to achieve optimal testing is the one using fully entangled measurements. Our main result is a smooth copy complexity upper bound for state certification as a function of ttt, which achieves a near-optimal rate at t=d2t = d^2t=d2. In the high-precision regime, i.e., for ε<1dε< \frac{1}{\sqrt{d}}ε<d​1​, this is a strict improvement over the entanglement used by the aforementioned optimal protocol. We also extend our techniques to develop new algorithms for the related tasks of mixedness testing and purity estimation, and show tradeoffs achieving the optimal rates for these problems at t=d2t = d^2t=d2 as well. Our algorithms are based on novel reductions from testing to learning and leverage recent advances in quantum state tomography in a non-black-box fashion. We complement our testing upper bounds with a (nearly) matching lower bound that holds in the high-precision regime, implying that one must take t≥Ω(d2)t \geq Ω(d^2)t≥Ω(d2) to achieve the optimal rate for certification.
A fundamental task in quantum information science is state certification: testing whether a lab-prepared n-qubit state is close to a given hypothesis state. In this work, we show that every pure hypothesis state can be certified using only O(n^2) single-qubit measurements applied to O(n) copies of the lab state. Prior to our work, it was not known whether even subexponentially many single-qubit measurements could suffice to certify arbitrary states. This resolves the main open question of Huang, Preskill, and Soleimanifar (FOCS 2024, QIP 2024).
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 introduce a basis-independent algorithm that only uses single-copy measurements to certify the Schmidt number of 2n2n2n-qubit bipartite pure states. Assuming the local system dimension is d=2nd = 2^nd=2n, the Schmidt number χχχ is O(1)O(1)O(1), and the non-zero Schmidt coefficients are bounded below by Ω(1)Ω(1)Ω(1), our protocol achieves a total sample complexity of O~(d2χ2)\widetilde{O}(d^2χ^2)O(d2χ2) with only O~(χ4)\widetilde{O}(χ^4)O(χ4) measurement settings. This work establishes a measurement-setting-efficient approach to high-dimensional entanglement certification.