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.

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•0 citations

Entanglement Certification Using Noncontextuality Inequalities

Yujie Zhang, Jonah Spodek, David Schmid +5 more

By combining the assumptions of Bell locality with those of generalized noncontextuality, we define classes of noncontextuality inequalities for correlations arising in a bipartite Bell circuit. These classes are distinguished by which subsets of the full set of operational identities are taken as input to the principle of noncontextuality; certain natural subsets form a hierarchy that provides a way of understanding and classifying different forms of quantum correlations, including entanglement, steering, and nonlocality. Each level of this hierarchy gives rise to a corresponding class of noncontextuality inequalities whose violation witnesses one of these forms of bipartite quantum resourcefulness, thereby yielding different sufficient conditions for entanglement. The resulting entanglement certification paradigm requires no prior characterization of the measurements, delivers a verdict independent of tomographic gauge freedom, and can certify any entangled state without auxiliary entangled sources. To illustrate the power of this paradigm, we show that noncontextuality inequalities can certify entanglement for families of two-qubit isotropic states for which certification by Bell or steering inequalities is known to be impossible. We also show that, compared with the Bell test, this approach certifies a much larger fraction of entangled states, while the associated membership problem is computationally more tractable. On the experimental side, we describe techniques to ensure nontrivial operational identities in the presence of noisy and imperfect implementations. We also identify the sufficient condition under which these techniques are valid, namely, a particular notion of of the implemented Bell circuit, which ensures that the operational identities are independent of tomographic gauge. Finally, we provide an experimental demonstration of the superior performance of this entanglement certification technique using polarization-entangled photons.

arXiv:2507.01122•Physical Review X•Jul 21, 2026•0 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•77 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

Optimal strategy to certify quantum nonlocality

Santiago Gómez, Daniel Uzcátegui Contreras, I. Machuca +4 more

Certification of quantum nonlocality plays a central role in practical applications like device-independent quantum cryptography and random number generation protocols. These applications entail the challenging problem of certifying quantum nonlocality, something that is hard to achieve when the target quantum state is only weakly entangled, or when the source of errors is high, e.g. when photons propagate through the atmosphere or a long optical fiber. Here we introduce a technique to find a Bell inequality with the largest possible gap between the quantum prediction and the classical local hidden variable limit for a given set of measurement frequencies. Our method represents an efficient strategy to certify quantum nonlocal correlations from experimental data without requiring extra measurements, in the sense that there is no Bell inequality with a larger gap than the one provided. Furthermore, we also reduce the photodetector efficiency required to close the detection loophole. We illustrate our technique by improving the detection of quantum nonlocality from experimental data obtained with weakly entangled photons.

Scientific Reports•Oct 14, 2021•1 citation

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•71 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.
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.
By combining the assumptions of Bell locality with those of generalized noncontextuality, we define classes of noncontextuality inequalities for correlations arising in a bipartite Bell circuit. These classes are distinguished by which subsets of the full set of operational identities are taken as input to the principle of noncontextuality; certain natural subsets form a hierarchy that provides a way of understanding and classifying different forms of quantum correlations, including entanglement, steering, and nonlocality. Each level of this hierarchy gives rise to a corresponding class of noncontextuality inequalities whose violation witnesses one of these forms of bipartite quantum resourcefulness, thereby yielding different sufficient conditions for entanglement. The resulting entanglement certification paradigm requires no prior characterization of the measurements, delivers a verdict independent of tomographic gauge freedom, and can certify any entangled state without auxiliary entangled sources. To illustrate the power of this paradigm, we show that noncontextuality inequalities can certify entanglement for families of two-qubit isotropic states for which certification by Bell or steering inequalities is known to be impossible. We also show that, compared with the Bell test, this approach certifies a much larger fraction of entangled states, while the associated membership problem is computationally more tractable. On the experimental side, we describe techniques to ensure nontrivial operational identities in the presence of noisy and imperfect implementations. We also identify the sufficient condition under which these techniques are valid, namely, a particular notion of of the implemented Bell circuit, which ensures that the operational identities are independent of tomographic gauge. Finally, we provide an experimental demonstration of the superior performance of this entanglement certification technique using polarization-entangled photons.
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.
Certification of quantum nonlocality plays a central role in practical applications like device-independent quantum cryptography and random number generation protocols. These applications entail the challenging problem of certifying quantum nonlocality, something that is hard to achieve when the target quantum state is only weakly entangled, or when the source of errors is high, e.g. when photons propagate through the atmosphere or a long optical fiber. Here we introduce a technique to find a Bell inequality with the largest possible gap between the quantum prediction and the classical local hidden variable limit for a given set of measurement frequencies. Our method represents an efficient strategy to certify quantum nonlocal correlations from experimental data without requiring extra measurements, in the sense that there is no Bell inequality with a larger gap than the one provided. Furthermore, we also reduce the photodetector efficiency required to close the detection loophole. We illustrate our technique by improving the detection of quantum nonlocality from experimental data obtained with weakly entangled photons.
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.