Few Single-Qubit Measurements Suffice to Certify Any Quantum State
Meghal Gupta, William He, Ryan O’Donnell · 2025
Read Few Single-Qubit Measurements Suffice to Certify Any Quantum State by Meghal Gupta, William He, Ryan O’Donnell (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-11355.txt.
Introduction
Meghal Gupta, William He, and Ryan O'Donnell show that a few single-qubit checks can certify any pure quantum state. Certification asks whether a lab-made state truly matches a target, a basic chore as quantum devices grow. Before this work, no one knew whether less than an exponential count of simple checks could ever do the job for all states.
Their 2025 paper gives an algorithm that uses on the order of n squared single-qubit measures spread over n copies. Each copy's later checks bend to its earlier outcomes, and that adaptivity is the engine. The team proves nonadaptive plans need exponentially many copies, a hard wall that marks the power of feedback.
Catalog record
| CREATOR | Meghal Gupta, William He, Ryan O’Donnell |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-11355
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Few Single-Qubit Measurements Suffice to Certify Any Quantum State Meghal Gupta, William He, Ryan O’Donnell Abstract A fundamental task in quantum information science is state certification : testing whether a lab-prepared n 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 ) O(n^{2}) single-qubit measurements applied to O ( n ) O(n) copies of the lab state. Prior to our work, it was not known whether even sub-exponentially 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). 1 Introduction A fundamental task in quantum information science is to test whether an unknown n -qubit state \rho_{\mathsf{lab}} prepared in the lab is equal (or close) to a known target state \ket{\tar} . This task is known as quantum state certification . It is essential for benchmarking quantum devices, validating the outcomes of quantum experiments, and verifying the correctness of practical implementations of quantum algorithms and protocols. See e.g. [ BOW19 , ZH19b , KR21 , HPS24 ] for in-depth discussions of the importance and applications of quantum state certification. More formally, we are given a classical description of (or some form of access to) a known pure state \ket{\tar} , along with copies of an unknown (possibly mixed) lab state \rho_{\mathsf{lab}} . Our goal is to decide whether the fidelity \bra{\tar}\rho_{\mathsf{lab}}\ket{\tar} is close to 1 , in which case we Accept , or significantly smaller than 1 , in which case we Reject . If we ignore measurement complexity, the optimal-copy-complexity approach is straightforward: measure each copy of \rho_{\mathsf{lab}} using the POVM (\outerproduct{\tar}{\tar},\mathrm{Id}-\outerproduct{\tar}{\tar}) , and accept if the first outcome occurs frequently enough. This requires only \Theta(1/\varepsilon) copies to distinguish \bra{\tar}\rho_{\mathsf{lab}}\ket{\tar}<1-\varepsilon from \bra{\tar}\rho_{\mathsf{lab}}\ket{\tar}=1 (or even \geq 1-\varepsilon/2 ). However, actually implementing this n -qubit measurement is roughly as hard as preparing the state \ket{\tar} . Given that the main use of certification is to certify that we can in fact prepare \ket{\tar} , this renders this certification algorithm pretty useless. What we’d actually like is a much simpler algorithm for certifying states—ideally something that’s polynomially complex even when preparing \ket{\tar} is exponentially complex (as it is for most states). These considerations motivate certification algorithms based solely on single-qubit measurements: This would allow for efficient certification even when preparation is more complex and unreliable. Prior to this work, it was unknown whether all pure states \ket{\tar} could be certified using only few single-qubit measurements. 1 1 1 We remark that if \ket{\tar} is allowed to be a mixed state, it is known that certification in general requires exponentially many copies, even when arbitrarily complex measurements are allowed [ CHW07 , OW21 ] . Several algorithms had been developed for this task, but each required some significant concession. For example, some algorithms require exponentially many copies of \rho_{\mathsf{lab}} : [ FL11 , SLP11 , AGKE15 ] . Others apply only to restricted classes of hypothesis states or restricted noise models: [ HMT06 , FL11 , AGKE15 , HM15 , MNS16 , MTH17 , TM18 , GKEA18 , HT19 , LHZ19 , LYS+19 , YSG19 , ZH19a , LHS+21 , HPS24 ] . Indeed, given each of these prior results comes with caveats, it was natural to suspect that fully general certification using only polynomially many single-qubit measurements might be impossible. Even after Huang, Preskill, and Soleimanifar [ HPS24 ] gave such an algorithm for Haar-random target states \ket{\tar} (which are typically highly entangled), they left it open to identify an explicit state \ket{\tar} for which certification with single-qubit measurements requires super-polynomially many copies. Perhaps surprisingly, this work shows that there is no such state: Efficient certification with single-qubit measurements is possible for all quantum states. We present a simple, general quantum state certification algorithm that works for every pure hypothesis state \ket{\tar} , and which uses only single-qubit measurements applied to O(n/\varepsilon) copies of \rho_{\mathsf{lab}} : Main Theorem . There exists an algorithm that given parameters \delta,\varepsilon>0 , oracle access to a pure state \ket{\tar} via the model in Definition 5 , and O(n\varepsilon^{-1}\ln(1/\delta)) copies of \rho_{\mathsf{lab}} , makes only single-qubit measurements to the copies of \rho_{\mathsf{lab}} and outputs: • Accept with probability at least 1-\delta if \bra{\tar}\rho_{\mathsf{lab}}\ket{\tar}\geq 1-\frac{\varepsilon}{2n} . • Reject with probability at least 1-\delta if \bra{\tar}\rho_{\mathsf{lab}}\ket{\tar}\leq 1-\varepsilon . Moreover, the algorithm runs in time linear in the number of measurements. This theorem follows directly from Theorem 1 below, and repetition: Theorem 1 . There exists an algorithm that given oracle access to a pure state \ket{\tar} via the model in Definition 5 and 1 copy of a mixed state \rho_{\mathsf{lab}} , makes only single-qubit measurements to \rho_{\mathsf{lab}} and outputs: • Accept with probability at least \bra{\tar}\rho_{\mathsf{lab}}\ket{\tar} . • Reject with probability at least \frac{1-\bra{\tar}\rho_{\mathsf{lab}}\ket{\tar}}{n} . Future directions. Several natural questions remain open for future work. We state two of them below: First, a basic information-theoretic argument shows that any certification algorithm for a pure target state \ket{\tar} must use at least \Omega(1/\varepsilon) copies of \rho_{\mathsf{lab}} , even without restricting to single-qubit measurements. Can stronger lower bounds be proven for algorithms limited to single-qubit measurements? In particular, our algorithm uses O(n/\varepsilon) copies — is this dependence on n necessary? Second, our algorithm is only 1/n -tolerant: To guarantee \rho_{\mathsf{lab}} is accepted with high probability, it needs to satisfy \bra{\tar}\rho_{\mathsf{lab}}\ket{\tar}\geq 1-O(\varepsilon/n) , rather than 1-O(\varepsilon) . Can this dependence on n be improved or even eliminated? For instance, is it possible to design a test that distinguishes between the cases \bra{\tar}\rho_{\mathsf{lab}}\ket{\tar}\geq 1-\varepsilon/2 and \bra{\tar}\rho_{\mathsf{lab}}\ket{\tar}\leq 1-\varepsilon ? 1.1 Algorithm Overview In this section, we informally describe our algorithm to test whether a candidate state \ket{\lab} is equal to \ket{\smash\tar} or has overlap at most 1-\varepsilon with \ket{\smash\tar} . We can decompose \ket{\smash\tar} as \displaystyle\ket{\smash\tar}=\frac{1}{\sqrt{2}}\ket{e_0}\ket{\smash{\tar^0}}+\frac{1}{\sqrt{2}}\ket{e_1}\ket{\smash{\tar^1}}, for some orthonormal basis \{\ket{e_0},\ket{e_1}\} , where \ket{\smash{\tar^0}} and \ket{\smash{\tar^1}} are (n-1) -qubit states. 2 2 2 We do this only for simplicity of our calculations; we could have stuck with the \{\ket{0},\ket{1}\} basis at the expense of introducing variable coefficients in the analysis. Let U be any unitary operator satisfying U\ket{\smash{\tar^1}}=\ket{\smash{\tar^0}} . If \ket{\smash\lab}=\ket{\smash\tar} , then if we similarly write \displaystyle\ket{\smash\lab}=\gamma_{0}\ket{e_0}\ket{\smash{\lab^0}}+\gamma_{1}\ket{e_1}\ket{\smash{\lab^1}}, it must be true that \gamma_{0}\ket{\smash{\lab^0}}=\gamma_{1}U\ket{\smash{\lab^1}} . The first step of our algorithm ( Algorithm 1 with k=1 ) essentially checks how much this relation is violated for some specific U . Now we will pick U such that we can indeed check this relation with an algorithm that uses only single-qubit measurements. To do this, we select a particular basis \mathcal{B} for (\mathbb{C}^{2})^{\otimes n-1} such that: 1. \ket{\smash{\tar^0}} and \ket{\smash{\tar^1}} , when written in this basis, have coefficients with equal magnitudes. 3 3 3 It is also possible to have both of these magnitudes equal to \frac{1}{\sqrt{2}} , and we will make this choice to simplify our calculations. 2. One can implement measurements in this basis by adaptively measuring single qubits at a time. The existence of such a basis is shown in Lemma 4 . The unitary U is then defined as the unique diagonal operator in \mathcal{B} mapping \ket{\smash{\tar^1}} to \ket{\smash{\tar^0}} . Our algorithm first measures the