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

Annual Symposium on Foundations of Computer Science

Certifying Almost All Quantum States with Few Single-Qubit Measurements

Hsin-Yuan Huang, John P. Preskill, Mehdi Soleimanifar

Published Oct 27, 2024• 10 citations
Publisher

Abstract

A fundamental challenge in quantum information science is certifying that an n-qubit state$\rho$prepared in the lab closely matches a target state$\vert \psi\rangle$. Previous approaches to this problem often require deep quantum circuits, exponentially many single-qubit measurements, or are limited to specific state families. In this work, we introduce a new method that leverages a connection between state certification and the mixing time of a random walk, allowing almost all n-qubit target states, including those with exponential circuit complexity, to be certified with only$\mathrm{O}(n^{2})$single-qubit measurements. Our protocol is broadly compatible with various experimental platforms and has applications in benchmarking quantum systems, optimizing quantum circuits, and efficiently learning and verifying representations of quantum states—such as neural networks and tensor networks—using only single-qubit measurements. Moreover, these verified representations enable the efficient prediction of highly non-local properties of$\rho$that would otherwise require an exponential number of measurements.

DOI
10.1109/focs61266.2024.00079

Related papers

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•Feb 13, 2026•0 citations

Certifying almost all quantum states with few single-qubit measurements

Hsin-Yuan Huang, John P. Preskill, Mehdi Soleimanifar

Certifying that an n-qubit state synthesized in the lab is close to the target state is a fundamental task in quantum information science. However, existing rigorous protocols either require deep quantum circuits or exponentially many single-qubit measurements. In this work, we prove that almost all n-qubit target states, including those with exponential circuit complexity, can be certified from only O(n^2) single-qubit measurements. This result is established by a new technique that relates certification to the mixing time of a random walk. Our protocol has applications for benchmarking quantum systems, for optimizing quantum circuits to generate a desired target state, and for learning and verifying neural networks, tensor networks, and various other representations of quantum states using only single-qubit measurements. We show that such verified representations can be used to efficiently predict highly non-local properties that would otherwise require an exponential number of measurements. We demonstrate these applications in numerical experiments with up to 120 qubits, and observe advantage over existing methods such as cross-entropy benchmarking (XEB).

arXiv:2404.07281•Apr 10, 2024•1 citation

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

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

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

Sound and Efficient Certification of High-Quality Qubit Operations: Theory and Experiment

Nikolai Miklin, Jan Nöller, José Martínez +4 more

Can a high-quality quantum gate be certified when uncharacterized state-preparation and measurement errors are dominant? Can this be achieved with low experimental overhead? Here, we introduce a sound black-box certification protocol for a single-qubit gate based on a small set of fixed, deterministic sequences. From the data, the protocol derives finite-sample bounds on the gate's rotation eigenvalue, a gauge-invariant property. Its phase reveals the accuracy of the rotation angle, while its modulus quantifies the loss of coherence under repeated gate applications. We implement the protocol on a $^{40}\mathrm{Ca}^{+}$ trapped-ion processor and certify the $\sqrt{\mathrm{X}}$-gate rotation eigenvalue using $22\,000$ circuit executions, and demonstrate the robustness of certification to state-preparation and measurement errors by deliberately degrading the readout. Finally, we prove that these spectral constraints imply, up to a physically meaningful unitary change of basis, a rigorous average gate-fidelity lower bound for every time-independent qubit model compatible with the data. In both readout settings, the spectral bounds yield the same fidelity certificate of $99.94(3)\%$ with $99\%$ confidence. Our results establish a new standard for quantum-gate certification by combining soundness and experimental efficiency without requiring trusted reference operations, randomized circuits, or model fitting.

quant-pharXiv:2608.17005•Aug 19, 2026•0 citations
A fundamental challenge in quantum information science is certifying that an n-qubit stateρ\rhoρprepared in the lab closely matches a target state∣ψ⟩\vert \psi\rangle∣ψ⟩. Previous approaches to this problem often require deep quantum circuits, exponentially many single-qubit measurements, or are limited to specific state families. In this work, we introduce a new method that leverages a connection between state certification and the mixing time of a random walk, allowing almost all n-qubit target states, including those with exponential circuit complexity, to be certified with onlyO(n2)\mathrm{O}(n^{2})O(n2)single-qubit measurements. Our protocol is broadly compatible with various experimental platforms and has applications in benchmarking quantum systems, optimizing quantum circuits, and efficiently learning and verifying representations of quantum states—such as neural networks and tensor networks—using only single-qubit measurements. Moreover, these verified representations enable the efficient prediction of highly non-local properties ofρ\rhoρthat would otherwise require an exponential number of measurements.
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.
Certifying that an n-qubit state synthesized in the lab is close to the target state is a fundamental task in quantum information science. However, existing rigorous protocols either require deep quantum circuits or exponentially many single-qubit measurements. In this work, we prove that almost all n-qubit target states, including those with exponential circuit complexity, can be certified from only O(n^2) single-qubit measurements. This result is established by a new technique that relates certification to the mixing time of a random walk. Our protocol has applications for benchmarking quantum systems, for optimizing quantum circuits to generate a desired target state, and for learning and verifying neural networks, tensor networks, and various other representations of quantum states using only single-qubit measurements. We show that such verified representations can be used to efficiently predict highly non-local properties that would otherwise require an exponential number of measurements. We demonstrate these applications in numerical experiments with up to 120 qubits, and observe advantage over existing methods such as cross-entropy benchmarking (XEB).
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 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.
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).
Can a high-quality quantum gate be certified when uncharacterized state-preparation and measurement errors are dominant? Can this be achieved with low experimental overhead? Here, we introduce a sound black-box certification protocol for a single-qubit gate based on a small set of fixed, deterministic sequences. From the data, the protocol derives finite-sample bounds on the gate's rotation eigenvalue, a gauge-invariant property. Its phase reveals the accuracy of the rotation angle, while its modulus quantifies the loss of coherence under repeated gate applications. We implement the protocol on a 40Ca+^{40}\mathrm{Ca}^{+}40Ca+ trapped-ion processor and certify the X\sqrt{\mathrm{X}}X​-gate rotation eigenvalue using 22 00022\,00022000 circuit executions, and demonstrate the robustness of certification to state-preparation and measurement errors by deliberately degrading the readout. Finally, we prove that these spectral constraints imply, up to a physically meaningful unitary change of basis, a rigorous average gate-fidelity lower bound for every time-independent qubit model compatible with the data. In both readout settings, the spectral bounds yield the same fidelity certificate of 99.94(3)%99.94(3)\%99.94(3)% with 99%99\%99% confidence. Our results establish a new standard for quantum-gate certification by combining soundness and experimental efficiency without requiring trusted reference operations, randomized circuits, or model fitting.