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

Complexity of self-consistent entanglement certification

Yujie Zhang

quant-phSubmitted Oct 6, 2026• Announced Oct 7, 2026• 0 citations
arXivHTMLPDF

Abstract

In recent work Phys. Rev. X 16, 031057 (2026), we proposed a self-consistent approach to entanglement certification based on generalized noncontextuality. It requires no prior characterization of the measurement devices and, given access to all local measurements, can certify every entangled state in a Bell circuit. Here, we study the complexity of this protocol in a finite experiment. At fixed local dimension $d$, we show that the optimal number of distinct local effects needed to reach a trace-distance \textit{entanglement resolution} $γ$ is $Θ_d(γ^{-(d-1)})$. This scaling is necessary even when the measurements are tailored to the target state. Independent Haar-random projective measurements instead require $Θ_d(γ^{-(d-1)}\log(1/γ))$ effects. Finally, we show that, once the exact operational identities are known, $Θ_d(γ^{-2}\log(1/δ))$ copies of the target state are necessary and sufficient for certification with error probability at most $δ$. Determining the optimal sample complexity when those identities must instead be inferred from the same finite target-state data remains open.

AI Summary

The paper asks how finite measurement resources limit a previously proposed entanglement-certification protocol based on generalized noncontextuality. The protocol uses a Bell circuit without prior measurement calibration, testing statistics against models that preserve all local operational identities. With all local measurements available, it can certify every entangled state. At fixed local dimension $d$, the paper proves that the optimal number of distinct local effects per party, counted up to positive rescaling, needed to certify every state at trace distance at least $\gamma$ from the separable set is $\Theta_d(\gamma^{-(d-1)})$. No finite measurement family is universal. The lower bound also applies to worst-case targets when measurements can be tailored to the state. Independent Haar-random projective measurements require $\Theta_d(\gamma^{-(d-1)}\log(1/\gamma))$ effects instead. The central step relates the largest uncertified entanglement to the effects’ pure-state covering infidelity $\epsilon$, proving $\epsilon/[16d(d+1)]\leq\gamma^{\rm tr}\leq2d\epsilon$ for sufficiently small $\epsilon$. Local depolarization establishes the upper bound; measurement-independent Werner states establish the lower bound. Pure-state covering estimates then give the effect counts. If exact operational identities are supplied independently, the optimal target-copy complexity is $\Theta_d(\gamma^{-2}\log(1/\delta))$ for error probability $\delta$. The upper bound samples only $d^4$ product probabilities; quantum hypothesis testing gives the lower bound even for collective measurements. This excludes the cost of learning identities. Sample complexity when identities are inferred from the same finite target data remains open, as do optimal dimension dependence and computational-complexity comparisons with other separability approximations.

Little sign of AI-generated textAI use disclosedStrong assumptions
The optimal effect complexity and the Haar-random complexity were subsequently established through interactions with OpenAI Codex (using models 5.6 and later 6).

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
Preliminary version for upcoming talks

Related papers

Instance-Optimal Quantum State Certification with Entangled Measurements

Ryan O’Donnell, Chirag Wadhwa

We consider the task of quantum state certification: given a description of a hypothesis state σ and multiple copies of an unknown state ρ, a tester aims to determine whether the two states are equal or є-far in trace distance. It is known that Θ(d/є2) copies of ρ are necessary and sufficient for this task, assuming the tester can make entangled measurements over all copies. However, these bounds are for a worst-case σ, and it is not known what the optimal copy complexity is for this problem on an instance-by-instance basis. While such instance-optimal bounds have previously been shown for quantum state certification when the tester is limited to measurements unentangled across copies, they remained open when testers are unrestricted in the kind of measurements they can perform.

arXiv:2507.06010•ACM Symposium on Theory of Computing (STOC)•Jun 9, 2026•13 citations

Certifying Localizable Quantum Properties with Constant Sample Complexity

Zhenyu Du, Jinchang Liu, Elias X. Huber +2 more

Characterizing increasingly complex quantum systems is a central task in quantum information science, yet experimental costs often scale prohibitively with system size. Certifying key properties using simple local measurements is highly desirable but challenging. In this work, we introduce a highly general certification framework based on a physical phenomenon that we call localizable quantumness: for generic many-body states, essential quantum properties are robustly preserved within the projected ensembles on small subsystems after performing local projective measurements on the rest of the system. Leveraging this insight, we develop protocols to certify global properties—including multipartite entanglement, circuit complexity, and quantum magic—by witnessing them on a small, accessible subsystem. Remarkably, randomizing the local measurement bases extends this capability to certify state fidelity. Relying solely on local Pauli measurements, these protocols achieve constant sample complexity and robustness for almost all quantum states, including a wide range of physically relevant states. For certifying the fidelity of n -qubit states, this O ( 1 ) scaling dramatically improves upon state-of-the-art protocols requiring O ( n 4 ) samples. Our unified framework provides both a practical toolkit for large-scale quantum certification and a novel lens into complex many-body systems.

arXiv:2509.17580•Physical Review X•Sep 16, 2026•11 citations

Self-testing of Pauli observables for device-independent entanglement certification

Joseph Bowles, Ivan Šupić, Daniel Cavalcanti +1 more

We present self-testing protocols to certify the presence of tensor products of Pauli measurements on maximally entangled states of local dimension ${2}^{n}$ for $n\ensuremath{\in}\mathbb{N}$. This provides self-tests of sets of informationally complete measurements in arbitrarily high dimension. We then show that this can be used for the device-independent certification of the entanglement of all bipartite entangled states by exploiting a connection to measurement-device-independent entanglement witnesses and quantum networks. This work extends a more compact parallel work on the same subject [Bowles et al., Phys. Rev. Lett. 121, 180503 (2018)] and provides all the required technical proofs.

arXiv:1801.10446•Physical Review A•Oct 29, 2018•88 citations

Quantum Correlations, Certifying Quantum Devices, and the Quest for Infinite Entanglement

Andrea Coladangelo

Quantum information has the potential to disrupt the present computational landscape. Much of this potential rests on the existence of efficient quantum algorithms for classically intractable problems and of quantum cryptographic protocols for tasks that are provably impossible to realize classically. At the heart of many quantum advantages is one of the most counterintuitive features of quantum mechanics, known as entanglement. The central motivating question of this thesis is the following: if quantum devices will perform tasks that are beyond the reach of classical devices, can we hope to certify that they are performing these tasks correctly? Bell's theorem, a landmark result in physics, provides a partial answer to this question: it asserts that measurements on spatially isolated, but entangled, particles can result in outcomes that are correlated in a way that cannot be explained by any local hidden variable theory (such as Newtonian physics). A direct operational consequence of this theorem is that one can devise a statistical test to certify the presence of entanglement (and hence of genuine quantumness). Remarkably, nature allows us to take this certification one step further: in some cases, the correlation of measurement outcomes is sufficient to single out a unique quantum setup compatible with this correlation. This phenomenon is often referred to as self-testing, and is the central topic of this thesis. In the first part of this thesis, we review the basic terminology and results in the theory of self-testing. We then explore a concrete application to the problem of verifiably delegating a quantum computation. Our main technical contribution is a test that robustly certifies products of single-qubit Clifford measurements on many EPR pairs. We employ this test to obtain a protocol which allows a classical user to verifiably delegate her quantum computation to two spatially isolated quantum servers. The overall complexity of our protocol is near-optimal, requiring resources that scale almost linearly in the size of the circuit being delegated. In the second part of this thesis, the driving question is the following: what is the class of quantum states and measurements that can be certified through self-testing? Does self-testing only apply to a few special cases, like EPR pairs or copies of EPR pairs, or are these instances of a more general phenomenon? One of the main results of this thesis is that we settle this question for the case of bipartite states. We show the existence of a self-testing correlation for any pure bipartite entangled state of any finite local dimension. We then move on to explore the multipartite case, and we show that a significantly larger class of states can be self-tested than was previously known. This includes all multipartite partially entangled GHZ states, and more generally all multipartite qudit states which admit a Schmidt decomposition. In the final part of this thesis, we explore connections of the theory of self-testing to basic questions about entanglement and quantum correlation sets. In particular, we set out to understand the expressive power of infinite-dimensional quantum systems. We consider two questions: can spatially isolated quantum systems of infinite dimension produce correlations that are unattainable by finite-dimensional systems? Does there exist a correlation that cannot be attained exactly by spatially isolated quantum systems (not even infinite-dimensional ones), but can be approximated arbitrarily well by a sequence of finite or infinite-dimensional systems? The first question was posed by Tsirelson in 1993, and its answer has been elusive. One of the main results of this thesis is a resolution of this question. The second question is better known as the "non-closure of the set of quantum correlations", and was answered affirmatively in a breakthrough of Slofstra. We give a new elementary proof of this result which leverages one of our self-testing results and a phenomenon known as embezzlement.

•Feb 4, 2020•0 citations

Third-Order Local Randomized Measurements for Finite-size Entanglement Certification

Giovanni Scala, Gniewomir Sarbicki

Randomized measurements access nonlinear functionals without full tomography, yet turning third-order local single-copy data into a strong entanglement test remains difficult. We convert the reduction criterion into an experimentally measurable separability criterion by testing it on squared affine combinations of the identity, the local marginals, and the state itself. This yields a $4\times4$ matrix $\bar{\mathfrak{M}}(ρ)$ built from experimentally accessible second- and third-order local invariants. Entanglement is certified when its minimum eigenvalue $\mathcal{E}_4(ρ)$ becomes negative. We prove that all separable states satisfy $\bar{\mathfrak{M}}(ρ)\succeq0$, and that the sign of $\mathcal{E}_4(ρ)$ can be inferred from single-copy randomized measurements with dimension-independent sample complexity. For isotropic states on $d\times d$, the second-order purity criterion detects entanglement only for $p\sim d^{-1/2}$, whereas our third-order witness reaches $p\sim 2/d$, close to the separability threshold $p\sim 1/d$. A complementary nonisotropic benchmark shows that the affine marginal directions become essential once the local states are not maximally mixed.

quant-pharXiv:2604.13165•Apr 16, 2026•0 citations

Optimal Entanglement Certification from Moments of the Partial Transpose

Xiao‐Dong Yu, Satoya Imai, Otfried Gühne

For the certification and benchmarking of medium-size quantum devices, efficient methods to characterize entanglement are needed. In this context, it has been shown that locally randomized measurements on a multiparticle quantum system can be used to obtain valuable information on the so-called moments of the partially transposed quantum state. This allows one to infer some separability properties of a state, but how to use the given information in an optimal and systematic manner has yet to be determined. We propose two general entanglement detection methods based on the moments of the partially transposed density matrix. The first method is based on the Hankel matrices and provides a family of entanglement criteria, of which the lowest order reduces to the known p_{3}-positive-partial-transpose criterion proposed in A. Elben et al. [Phys. Rev. Lett. 125, 200501 (2020)PRLTAO0031-900710.1103/PhysRevLett.125.200501]. The second method is optimal and gives necessary and sufficient conditions for entanglement based on some moments of the partially transposed density matrix.

arXiv:2103.06897•Physical Review Letters•Aug 4, 2021•79 citations
In recent work Phys. Rev. X 16, 031057 (2026), we proposed a self-consistent approach to entanglement certification based on generalized noncontextuality. It requires no prior characterization of the measurement devices and, given access to all local measurements, can certify every entangled state in a Bell circuit. Here, we study the complexity of this protocol in a finite experiment. At fixed local dimension ddd, we show that the optimal number of distinct local effects needed to reach a trace-distance \textit{entanglement resolution} γγγ is Θd(γ−(d−1))Θ_d(γ^{-(d-1)})Θd​(γ−(d−1)). This scaling is necessary even when the measurements are tailored to the target state. Independent Haar-random projective measurements instead require Θd(γ−(d−1)log⁡(1/γ))Θ_d(γ^{-(d-1)}\log(1/γ))Θd​(γ−(d−1)log(1/γ)) effects. Finally, we show that, once the exact operational identities are known, Θd(γ−2log⁡(1/δ))Θ_d(γ^{-2}\log(1/δ))Θd​(γ−2log(1/δ)) copies of the target state are necessary and sufficient for certification with error probability at most δδδ. Determining the optimal sample complexity when those identities must instead be inferred from the same finite target-state data remains open.
The paper asks how finite measurement resources limit a previously proposed entanglement-certification protocol based on generalized noncontextuality. The protocol uses a Bell circuit without prior measurement calibration, testing statistics against models that preserve all local operational identities. With all local measurements available, it can certify every entangled state.
At fixed local dimension ddd, the paper proves that the optimal number of distinct local effects per party, counted up to positive rescaling, needed to certify every state at trace distance at least γ\gammaγ from the separable set is Θd(γ−(d−1))\Theta_d(\gamma^{-(d-1)})Θd​(γ−(d−1)). No finite measurement family is universal. The lower bound also applies to worst-case targets when measurements can be tailored to the state. Independent Haar-random projective measurements require Θd(γ−(d−1)log⁡(1/γ))\Theta_d(\gamma^{-(d-1)}\log(1/\gamma))Θd​(γ−(d−1)log(1/γ)) effects instead.
The central step relates the largest uncertified entanglement to the effects’ pure-state covering infidelity ϵ\epsilonϵ, proving ϵ/[16d(d+1)]≤γtr≤2dϵ\epsilon/[16d(d+1)]\leq\gamma^{\rm tr}\leq2d\epsilonϵ/[16d(d+1)]≤γtr≤2dϵ for sufficiently small ϵ\epsilonϵ. Local depolarization establishes the upper bound; measurement-independent Werner states establish the lower bound. Pure-state covering estimates then give the effect counts.
If exact operational identities are supplied independently, the optimal target-copy complexity is Θd(γ−2log⁡(1/δ))\Theta_d(\gamma^{-2}\log(1/\delta))Θd​(γ−2log(1/δ)) for error probability δ\deltaδ. The upper bound samples only d4d^4d4 product probabilities; quantum hypothesis testing gives the lower bound even for collective measurements. This excludes the cost of learning identities. Sample complexity when identities are inferred from the same finite target data remains open, as do optimal dimension dependence and computational-complexity comparisons with other separability approximations.
We consider the task of quantum state certification: given a description of a hypothesis state σ and multiple copies of an unknown state ρ, a tester aims to determine whether the two states are equal or є-far in trace distance. It is known that Θ(d/є2) copies of ρ are necessary and sufficient for this task, assuming the tester can make entangled measurements over all copies. However, these bounds are for a worst-case σ, and it is not known what the optimal copy complexity is for this problem on an instance-by-instance basis. While such instance-optimal bounds have previously been shown for quantum state certification when the tester is limited to measurements unentangled across copies, they remained open when testers are unrestricted in the kind of measurements they can perform.
Characterizing increasingly complex quantum systems is a central task in quantum information science, yet experimental costs often scale prohibitively with system size. Certifying key properties using simple local measurements is highly desirable but challenging. In this work, we introduce a highly general certification framework based on a physical phenomenon that we call localizable quantumness: for generic many-body states, essential quantum properties are robustly preserved within the projected ensembles on small subsystems after performing local projective measurements on the rest of the system. Leveraging this insight, we develop protocols to certify global properties—including multipartite entanglement, circuit complexity, and quantum magic—by witnessing them on a small, accessible subsystem. Remarkably, randomizing the local measurement bases extends this capability to certify state fidelity. Relying solely on local Pauli measurements, these protocols achieve constant sample complexity and robustness for almost all quantum states, including a wide range of physically relevant states. For certifying the fidelity of n -qubit states, this O ( 1 ) scaling dramatically improves upon state-of-the-art protocols requiring O ( n 4 ) samples. Our unified framework provides both a practical toolkit for large-scale quantum certification and a novel lens into complex many-body systems.
We present self-testing protocols to certify the presence of tensor products of Pauli measurements on maximally entangled states of local dimension 2n{2}^{n}2n for $n\ensuremath{\in}\mathbb{N}$. This provides self-tests of sets of informationally complete measurements in arbitrarily high dimension. We then show that this can be used for the device-independent certification of the entanglement of all bipartite entangled states by exploiting a connection to measurement-device-independent entanglement witnesses and quantum networks. This work extends a more compact parallel work on the same subject [Bowles et al., Phys. Rev. Lett. 121, 180503 (2018)] and provides all the required technical proofs.
Quantum information has the potential to disrupt the present computational landscape. Much of this potential rests on the existence of efficient quantum algorithms for classically intractable problems and of quantum cryptographic protocols for tasks that are provably impossible to realize classically. At the heart of many quantum advantages is one of the most counterintuitive features of quantum mechanics, known as entanglement. The central motivating question of this thesis is the following: if quantum devices will perform tasks that are beyond the reach of classical devices, can we hope to certify that they are performing these tasks correctly? Bell's theorem, a landmark result in physics, provides a partial answer to this question: it asserts that measurements on spatially isolated, but entangled, particles can result in outcomes that are correlated in a way that cannot be explained by any local hidden variable theory (such as Newtonian physics). A direct operational consequence of this theorem is that one can devise a statistical test to certify the presence of entanglement (and hence of genuine quantumness). Remarkably, nature allows us to take this certification one step further: in some cases, the correlation of measurement outcomes is sufficient to single out a unique quantum setup compatible with this correlation. This phenomenon is often referred to as self-testing, and is the central topic of this thesis. In the first part of this thesis, we review the basic terminology and results in the theory of self-testing. We then explore a concrete application to the problem of verifiably delegating a quantum computation. Our main technical contribution is a test that robustly certifies products of single-qubit Clifford measurements on many EPR pairs. We employ this test to obtain a protocol which allows a classical user to verifiably delegate her quantum computation to two spatially isolated quantum servers. The overall complexity of our protocol is near-optimal, requiring resources that scale almost linearly in the size of the circuit being delegated. In the second part of this thesis, the driving question is the following: what is the class of quantum states and measurements that can be certified through self-testing? Does self-testing only apply to a few special cases, like EPR pairs or copies of EPR pairs, or are these instances of a more general phenomenon? One of the main results of this thesis is that we settle this question for the case of bipartite states. We show the existence of a self-testing correlation for any pure bipartite entangled state of any finite local dimension. We then move on to explore the multipartite case, and we show that a significantly larger class of states can be self-tested than was previously known. This includes all multipartite partially entangled GHZ states, and more generally all multipartite qudit states which admit a Schmidt decomposition. In the final part of this thesis, we explore connections of the theory of self-testing to basic questions about entanglement and quantum correlation sets. In particular, we set out to understand the expressive power of infinite-dimensional quantum systems. We consider two questions: can spatially isolated quantum systems of infinite dimension produce correlations that are unattainable by finite-dimensional systems? Does there exist a correlation that cannot be attained exactly by spatially isolated quantum systems (not even infinite-dimensional ones), but can be approximated arbitrarily well by a sequence of finite or infinite-dimensional systems? The first question was posed by Tsirelson in 1993, and its answer has been elusive. One of the main results of this thesis is a resolution of this question. The second question is better known as the "non-closure of the set of quantum correlations", and was answered affirmatively in a breakthrough of Slofstra. We give a new elementary proof of this result which leverages one of our self-testing results and a phenomenon known as embezzlement.
Randomized measurements access nonlinear functionals without full tomography, yet turning third-order local single-copy data into a strong entanglement test remains difficult. We convert the reduction criterion into an experimentally measurable separability criterion by testing it on squared affine combinations of the identity, the local marginals, and the state itself. This yields a 4×44\times44×4 matrix Mˉ(ρ)\bar{\mathfrak{M}}(ρ)Mˉ(ρ) built from experimentally accessible second- and third-order local invariants. Entanglement is certified when its minimum eigenvalue E4(ρ)\mathcal{E}_4(ρ)E4​(ρ) becomes negative. We prove that all separable states satisfy Mˉ(ρ)⪰0\bar{\mathfrak{M}}(ρ)\succeq0Mˉ(ρ)⪰0, and that the sign of E4(ρ)\mathcal{E}_4(ρ)E4​(ρ) can be inferred from single-copy randomized measurements with dimension-independent sample complexity. For isotropic states on d×dd\times dd×d, the second-order purity criterion detects entanglement only for p∼d−1/2p\sim d^{-1/2}p∼d−1/2, whereas our third-order witness reaches p∼2/dp\sim 2/dp∼2/d, close to the separability threshold p∼1/dp\sim 1/dp∼1/d. A complementary nonisotropic benchmark shows that the affine marginal directions become essential once the local states are not maximally mixed.
For the certification and benchmarking of medium-size quantum devices, efficient methods to characterize entanglement are needed. In this context, it has been shown that locally randomized measurements on a multiparticle quantum system can be used to obtain valuable information on the so-called moments of the partially transposed quantum state. This allows one to infer some separability properties of a state, but how to use the given information in an optimal and systematic manner has yet to be determined. We propose two general entanglement detection methods based on the moments of the partially transposed density matrix. The first method is based on the Hankel matrices and provides a family of entanglement criteria, of which the lowest order reduces to the known p_{3}-positive-partial-transpose criterion proposed in A. Elben et al. [Phys. Rev. Lett. 125, 200501 (2020)PRLTAO0031-900710.1103/PhysRevLett.125.200501]. The second method is optimal and gives necessary and sufficient conditions for entanglement based on some moments of the partially transposed density matrix.