One of the most fundamental and counterintuitive features of quantum me- chanics is entanglement, which is central to many demonstrations of the quantum advantage. Studying quantum correlations generated by local measurements on an entangled physical system is one of the direct ways to gain insights into en- tanglement. The focus of this dissertation is to get better understanding of the hardness of determining if a given correlation is quantum, which is also known as the membership problem of quantum correlations. Previous work has shown that the general membership problem is computationally undecidable. Where does the hardness come from? Is it just because the size of a quantum correlation (i.e., the number of real values in the description of the correlation) can be arbitrarily large? We would like to understand the role played by the varying sizes of correlations in the hardness of the membership problem. It has been shown that certain quantum correlations require the measured quantum system to be maximally entangled with a certain dimension. This is a unique phenomenon of quantum correlations and it is known as self-testing. The first step towards answering the hardness of the membership problem of quantum correlations is to get deeper understandings about self-testing, and more specifically, about the size of a correlation that can self-test a maximally entangled state of arbitrarily large dimension. If correlations of a fixed size can self- test entangled states of unbounded dimension, this phenomenon is a strong evidence suggesting that deciding membership of fixed-sized correlations can be very hard. We first show that there exists an infinite subset of the set of all the prime numbers such that, for each prime p in this set, a maximally entangled state of local dimension (p − 1) can be self-tested by a correlation of a fixed size. Since this set is infinite, this result implies that constant-sized correlations are sufficient to self-test maximally entangled states of unbounded dimension. Building on the self-testing result, we show that the varying sizes of correlations are not the only root of the hardness. Specifically, we show that the membership problem of fixed finite-sized correlations is still computationally undecidable when the fixed size is sufficiently large. That is, the hardness of the membership problem of quantum correlations is independent of the varying sizes of correlations. In fact, the hardness arises from the fact that the structure of some set of correlations of a particular size is so complicated that no finite description of this set can allow a Turing machine to decide if a correlation is quantum or not.
One of the most fundamental and counterintuitive features of quantum me- chanics is entanglement, which is central to many demonstrations of the quantum advantage. Studying quantum correlations generated by local measurements on an entangled physical system is one of the direct ways to gain insights into en- tanglement. The focus of this dissertation is to get better understanding of the hardness of determining if a given correlation is quantum, which is also known as the membership problem of quantum correlations. Previous work has shown that the general membership problem is computationally undecidable. Where does the hardness come from? Is it just because the size of a quantum correlation (i.e., the number of real values in the description of the correlation) can be arbitrarily large? We would like to understand the role played by the varying sizes of correlations in the hardness of the membership problem. It has been shown that certain quantum correlations require the measured quantum system to be maximally entangled with a certain dimension. This is a unique phenomenon of quantum correlations and it is known as self-testing. The first step towards answering the hardness of the membership problem of quantum correlations is to get deeper understandings about self-testing, and more specifically, about the size of a correlation that can self-test a maximally entangled state of arbitrarily large dimension. If correlations of a fixed size can self- test entangled states of unbounded dimension, this phenomenon is a strong evidence suggesting that deciding membership of fixed-sized correlations can be very hard. We first show that there exists an infinite subset of the set of all the prime numbers such that, for each prime p in this set, a maximally entangled state of local dimension (p − 1) can be self-tested by a correlation of a fixed size. Since this set is infinite, this result implies that constant-sized correlations are sufficient to self-test maximally entangled states of unbounded dimension. Building on the self-testing result, we show that the varying sizes of correlations are not the only root of the hardness. Specifically, we show that the membership problem of fixed finite-sized correlations is still computationally undecidable when the fixed size is sufficiently large. That is, the hardness of the membership problem of quantum correlations is independent of the varying sizes of correlations. In fact, the hardness arises from the fact that the structure of some set of correlations of a particular size is so complicated that no finite description of this set can allow a Turing machine to decide if a correlation is quantum or not.
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.
Let p be an odd prime and let r be the smallest generator of the multiplicative group Z p ∗ . We show that there exists a correlation of size Θ ( r 2 ) that self-tests a maximally entangled state of local dimension p − 1 . The construction of the correlation uses the embedding procedure proposed by Slofstra ( Forum of Mathematics, Pi. ( 2019 )). Since there are infinitely many prime numbers whose smallest multiplicative generator is in the set { 2 , 3 , 5 } (D.R. Heath-Brown The Quarterly Journal of Mathematics ( 1986 ) and M. Murty The Mathematical Intelligencer ( 1988 )), our result implies that constant-sized correlations are sufficient for self-testing of maximally entangled states with unbounded local dimension.
Completely determining the relationship between quantum correlation sets is a long-standing open problem, known as Tsirelson's problem. Following recent progress by Slofstra [arXiv:1606.03140 (2016), arXiv:1703.08618 (2017)] only two instances of the problem remain open. One of them is the question of whether the set of finite-dimensional quantum correlations is strictly contained in the set of infinite-dimensional ones (i.e. whether Cq=Cqs). The usual formulation of the question assumes finite question and answer sets. In this work, we show that, when one allows for either infinite answer sets (and finite question sets) or infinite question sets (and finite answer sets), there exist correlations that are achievable using an infinite-dimensional quantum strategy, but not a finite-dimensional one. For the former case, our proof exploits a recent result [Nat. Comm. 8, 15485 (2017)], which shows self-testing of any pure bipartite entangled state of arbitrary local dimension d, using question sets of size 3 and 4 and answer sets of size d. For the latter case, a key step in our proof is to show a novel self-test, inspired by [Nat. Comm. 8, 15485 (2017)], of all bipartite entangled states of any local dimension d, using question sets of size O(d), and answer sets of size 4 and 3 respectively.
In device-independent quantum information, correlations between local measurement outcomes observed by spatially separated parties in a Bell test play a fundamental role. Even though it is long-known that the set of correlations allowed in quantum theory lies strictly between the Bell-local set and the no-signaling set, many questions concerning the geometry of the quantum set remain unanswered. Here, we revisit the problem of when the boundary of the quantum set coincides with the no-signaling set in the simplest Bell scenario. In particular, for each Class of these common boundaries containing k zero probabilities, we provide a (5−k) -parameter family of quantum strategies realizing these (extremal) correlations. We further prove that self-testing is possible in all nontrivial Classes beyond the known examples of Hardy-type correlations, and provide numerical evidence supporting the robustness of these self-testing results. Candidates of one-parameter families of self-testing correlations from some of these Classes are identified. As a byproduct of our investigation, if the qubit strategies leading to an extremal nonlocal correlation are local-unitarily equivalent, a self-testing statement provably follows. Interestingly, all these self-testing correlations found on the no-signaling boundary are provably non-exposed. An analogous characterization for the set M of quantum correlations arising from finite-dimensional maximally entangled states is also provided. En route to establishing this last result, we show that all correlations of M in the simplest Bell scenario are attainable as convex combinations of those achievable using a Bell pair and projective measurements. In turn, we obtain the maximal Clauser-Horne-Shimony-Holt Bell inequality violation by any maximally entangled two-qudit state and a no-go theorem regarding the self-testing of such states.
Abstract Self-testing was originally introduced as a device-independent method of certification of entangled quantum states and local measurements performed on them. Recently, in (Baccari et al 2020 Phys. Rev. Lett. 125 260507) the notion of state self-testing has been generalized to entangled subspaces and the first self-testing strategies for exemplary genuinely entangled subspaces have been given. The main aim of our work is to pursue this line of research and to address the question how ‘large’ (in terms of dimension) are genuinely entangled subspaces that can be self-tested, concentrating on the multiqubit stabilizer formalism. To this end, we first introduce a framework allowing to efficiently check whether a given stabilizer subspace is genuinely entangled. Building on it, we then determine the maximal dimension of genuinely entangled subspaces that can be constructed within the stabilizer subspaces and provide an exemplary construction of such maximally-dimensional subspaces for any number of qubits. Third, we construct Bell inequalities that are maximally violated by any entangled state from those subspaces and thus also any mixed states supported on them, and we show these inequalities to be useful for self-testing. Interestingly, our Bell inequalities allow for identification of higher-dimensional face structures in the boundaries of the sets of quantum correlations in the simplest multipartite Bell scenarios in which every observer performs two dichotomic measurements.
Self-testing is a powerful certification of quantum systems relying on measured, classical statistics. This paper considers self-testing in bipartite Bell scenarios with small number of inputs and outputs, but with quantum states and measurements of arbitrarily large dimension. The contributions are twofold. Firstly, it is shown that every maximally entangled state can be self-tested with four binary measurements per party. This result extends the earlier work of Mančinska-Prakash-Schafhauser (2021), which applies to maximally entangled states of odd dimensions only. Secondly, it is shown that every single binary projective measurement can be self-tested with five binary measurements per party. A similar statement holds for self-testing of projective measurements with more than two outputs. These results are enabled by the representation theory of quadruples of projections that add to a scalar multiple of the identity. Structure of irreducible representations, analysis of their spectral features and post-hoc self-testing are the primary methods for constructing the new self-tests with small number of inputs and outputs.