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

Entangled protocols and non-local games for testing quantum systems.

Matthew Coudron

Published Jan 1, 2017• 0 citations
OpenAlex

Abstract

The field of quantum computing investigates the extent to which one can design a quantum system that outperforms all known classical hardware at a certain task.But, to what extent can a human being, capable only (perhaps) of classical computation and of observing classical bit-string messages, verify that a quantum device in their possession is performing the task that they wish?This is a fundamental question about the nature of quantum mechanics, and the extent to which humans can harness it in a trustworthy manner.It is also a natural and important consideration when quantum devices may be used to perform sensitive cryptographic tasks which have no known efficient classical witness of correctness (Quantum Key Distribution, and Randomness Expansion are two examples of such tasks).It is remarkable that any quantum behavior at all can be tested by a verifier under such a constraint, without trusting any other quantum mechanical device in the process!But, intriguingly, when there are two or more quantum provers available in an interactive proof, there exist protocols to verify many interesting and useful quantum tasks in this setting.This thesis investigates multi-prover interactive proofs for verifying quantum behavior, and focuses on the stringent testing scenario in which the verifier in the interactive proof is completely classical as described above.It resolves the question of the maximum attainable expansion rate of a randomness expansion protocol by providing an adaptive randomness expansion protocol that achieves an arbitrary, or infinite rate of randomness expansion [29].Secondly it presents a new rigidity result for the parallel repeated magic square game [24], which provides some improvements on previous rigidity results that play a pivotal role in existing interactive proofs for entangled provers, QKD, and randomness expansion results.This new rigidity result may be useful for improving such interactive proofs in the future.The second half of this thesis investigates the problem of bounding the role of quantum The further I go the more I value what my parents' example has taught me, not about science, but about life.I love you Mom and Dad.My deep gratitude goes to my advisor, Peter Shor, for guidance in research throughout graduate school, and for supporting my own research endeavors.During a PhD a student's mind is full of many different considerations, both scientific and logistical.Peter's advice is an invaluable way to refocus on the heart of the research problem at hand and, with stunning consistency, to learn something amazing and new.During my PhD I have had the privilege of collaborating with many talented researchers and good friends.What would the exploration process be without people share ideas with, and fellow researchers with which to share the thrill of discovery?Many thanks to my collaborators (listed here in no particular order)!I can only hope to continue to have such great collaborations again in the future:

Related papers

Non-local correlations and interactive games

Umesh V. Vazirani, Daniel Preda

Quantum entanglement, and the resulting peculiar non-classical correlations are one of the most counter-intuitive aspects of quantum mechanics. The formalism of interactive games from computational complexity theory provides a useful framework in which to understand the power of entanglement. In an interactive game, a verifier interacts with a number of infinitely powerful provers who are allowed to share quantum entanglement but otherwise can't communicate. The ability of the verifier to extract useful information from the provers, whom he does not trust, provides an interesting measure of the ability of the provers to coordinate using their shared entanglement. Two particular interactive games we'll look at are Magic Square and 3SAT. The Magic Square game is the iconic example of a game where two classical provers cannot perfectly coordinate their strategies using shared randomness, but quantum provers with shared entanglement can win with probability 1. We show that by adding an extra prover, we disallow perfect cheating. For 3SAT with three provers we also show that perfect cheating is not possible. We then generalize the results for Magic Square and 3SAT by looking at non-commuting provers, a superset of entangled provers (communication is allowed, but operators applied by different provers must commute). Using this method, we obtain a generalized Tsirelson inequality that we apply to the Magic Square. Hence, we are able to give provably optimal strategies for the general Magic Square with n players. We also recover a similar result for 3SAT as with entangled provers, and we improve on it by showing that the gap is inverse exponential in the input size. The no-signaling principle, which forbids faster than light communication, is a fundamental constraint on the non-local correlations resulting from quantum entanglement. However, no-signaling allows distributions that are more general than those arising from quantum mechanics. In particular, using a specific unit of general non-local correlation (the Popescu-Rohlich box), we show that there are classes that are equal to NEXP classically, but collapse to AM once such correlations are allowed. We also show that MIP where the verifier only looks at the XOR of the answers collapses to PSPACE. For the second approach, we show that by writing general non-local correlations as linear constraints, MIP is included in EXP under such correlations (vs NEXP classically). We can extend these results to entangled quantum provers, by formulating an artificial MIP-like class built on a promise problem, that classically is equal to NEXP, but that also collapses to AM when quantum correlations are present.

•Jan 1, 2011•0 citations

The Complexity of Entangled Games

Thomas Vidick

Entanglement is at the heart of quantum mechanics. The nonlocal correlations that can be obtained from space-time separated measurements on an entangled state are a central feature which provably distinguish it from local theories. This dissertation studies entanglement through a computational viewpoint. We develop new insights into the complex nature of entanglement by studying its role in multiplayer games, in which cooperating, but non-communicating, players interact with a referee in an attempt to win a pre-specified game. On the one hand, the nonlocal correlations that entanglement allows may enable players using it to develop new colluding strategies, defeating previously secure protocols. On the other, the richness of this new resource may also be exploited in order to design new protocols, providing solutions to problems previously deemed impossible. We explore both aspects of this dual nature of entanglement, putting limits on its strength while at the same time showing how it can be put to profit to solve new computational problems. A major unresolved question on the computational complexity of multiplayer entangled games is the power of MIP*, the class of languages having entangled multi-prover interactive proofs: how does it relate to its purely classical analogue MIP, which was completely characterized through the fundamental equation MIP=NEXP? Since the players may use entanglement to increase their odds at colluding against the verifier, MIP* could potentially be a much weaker class than MIP. Indeed, for a long time it has been an open question whether two entangled provers are more useful than a single prover. In this thesis we resolve this question by showing that the class of languages having multiprover interactive proofs with entangled provers is at least as large as its classical counterpart: NEXP is included in MIP*. At the heart of this result is an analysis of the multilinearity test of Babai, Fortnow, and Lund in the presence of entanglement. The fact that this test remains sound gives a systematic way for a verifier to impose strong limits on the ability of entangled provers to collude against the verifier.Gap amplification is a fundamental primitive in the study of classical multiplayer games. While sequential repetition of a game always decreases the prover's maximum success probability at an exponential rate, the fact that parallel repetition also achieves a gap amplification is a highly non-trivial fact. We show that gap amplification can be performed in parallel even in the presence of entanglement between the provers. We adapt a technique which was originally introduced by Feige and Kilian and results in a polynomial rate of amplification.The phenomenon of monogamy of entanglement states, in first approximation, that if two parties are maximally entangled then they cannot simultaneously be entangled with a third party. We use this phenomenon in two distinct results. In the first, we show that the bits generated in our randomness-expansion protocol are certifiably random even from the point of view of a quantum adversary who may share prior entanglement with the provers. In addition, we prove the security against quantum adversaries of a randomness-efficient extractor construction originally due to Trevisan. This lets us transform the high-entropy bits that are generated in our protocol into ones that are almost indistinguishable from uniform by any adversary. More generally, we show how the monogamy of entanglement can be exploited to design multi-prover interactive proof systems that are partially entanglement-resistant. Quantitative bounds on the monogamy of entanglement have generally been elusive, and the analysis of our protocol demonstrates such a bound in a new context. The nonlocal correlations that can be created by entangled players provide a statistical means of differentiating them from classical, unentangled players. This is the main idea behind Bell inequalities, the violation of which demonstrates the nonlocality of quantum mechanics. We show how this phenomenon may be exploited to design a protocol in which the bits produced by successful players necessarily contain a large quantity of fresh randomness. The presence of randomness is guaranteed irrespective of the provers' actual strategy, as long as the sole constraint of no signaling is respected. Hence a statistical certification for the presence of randomness, a feat easily seen to be impossible to achieve classically. In order to manipulate the random bits produced in our protocol, and make them useful in cryptography, we give the first proof of security of a poly-logarithmic seed extractor secure against quantum adversaries. To achieve this we adapt the reconstruction paradigm originally introduced by Trevisan to the quantum setting. We study other ways in which entanglement may be used in interactive proof systems by also allowing a quantum interaction between the referee and the players. We show that, using entanglement, the class of QMIP* proof systems can be parallelized to only three rounds of interaction, and made public-coin, a property that does not hold in the absence of entanglement between the provers.

•Jan 1, 2011•10 citations

Robust verification of quantum computation

Alexandru Gheorghiu

Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.

•Nov 29, 2018•0 citations

Verifying quantum proofs with entangled games

Anand Natarajan

A team of students has been given a challenging physics exam: find the ground energy of a complicated, n-spin system. Even if they succeed, how can the examiners be sure that their answer is correct without physically measuring all n spins of the ground state, or worse, having to read a description of the 2n components of its wavefunction? The main result of this thesis is a protocol such that, if the examiners are allowed to separately interrogate multiple students, they can be confident that the students possess the n-spin ground state as well as learn its energy to high precision, after exchanging just O(log(n)) bits of classical communication with the students! The protocol and its analysis combine classical computer science techniques for efficiently checking proofs with Bell inequalities. Stated more formally, the main result of this thesis is a multi-prover interactive proof protocol, in which a classical verifier exchanging only O(log(n)) bits of classical communication with 7 untrusted, entangled provers can certify that they share between them an encoding of an n-qubit quantum state Ib), and estimate its energy under a local Hamiltonian H to high (1/ poly(n)) precision. As a consequence, we show that, under poly-time randomized reductions, it is QMA-hard to estimate the entangled value of a nonlocal game up to constant error, proving the quantum entangled games PCP conjecture of Fitzsimons and Vidick. Our main technical innovations are two constructions of robust self-tests for entanglement: two-player nonlocal games where to succeed with probability E-close to 1, the players must share a state that is [delta] = poly([epsilon])-close in trace distance to n EPR pairs. These tests are robust in that [delta] is independent of the number n of EPR pairs being tested. Our techniques draw heavily on the original, "algebraic" proof of the PCP theorem in classical complexity theory, and in particular, each of our robust self-tests is based on a classical locally-testable error correcting code: the first on the Hadamard code and the associated linearity test of Blum, Luby, and Rubinfeld, and the second on Reed-Muller code and the associated low-degree test of Raz and Safra.

•Jan 1, 2018•0 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

Quantum computing by interrogation

Ivan Šupić

Quantum information theory forms a bridge between the foundations of quantum mechanics and its promising practical potentials.The extensive theoretical research has been conducted during the last decades and the applications such as quantum key distribution and quantum computing promise to provide real technological breakthroughs.Many experimental groups worldwide are working on the practical implementation of the concepts from the quantum information theory.In the recent years a lot of attention has been paid to the certification of truly quantum behavior of some device, claimed to be quantum.This certification can be done by using some established interactive proof in which classical user just by commanding to a quantum device (prover) can make himself sure that the device works as advertised and moreover can actually use it for some particular task.When it comes to quantum computing one has to be sure that a machine uses quantum mechanics for the computational process.Two interesting interactive proofs are developed so far.One of them uses specific computation model, Measurement-based quantum computing, which is performed on a class of highly entangled states, graph states.The difficulty with the implementation of this interactive proof is a big number of provers required for the process.In this thesis we present some initial results of the attempts to construct interactive proof that would use smaller number of provers.Difficulties of the two-prover interactive proof and guidelines for the future research are presented as well as the new three-prover interactive proof for quantum device performing computation by doing single qubit unitary operations.After finishing my master program I have to thank to some people for having their part in making it as good as it has been.On the first part I would like to thank to my master thesis supervisors Antonio Acin and Matty Hoban.Thanks to prof.Acin for letting me do my thesis in his group in ICFO, for good will and useful discussions on the topic.There are not enough words to express gratitude to Matty Hoban.During these last months I had this great opportunity to learn so much from him.Thanks for this exciting project, for the enthusiasm, invested time, the patience, everything.I had a great reference for the future research.I am also grateful to the whole Quantum information theory group in ICFO, for the pleasant and very motivating atmosphere they have created.Particularly I would like to thank to my office-mate Paul Skrzypczyk for answering my questions "out of nowhere" and help with SDP and to Ariel Bendersky for the help with the last part of

•Sep 9, 2014•0 citations
The field of quantum computing investigates the extent to which one can design a quantum system that outperforms all known classical hardware at a certain task.But, to what extent can a human being, capable only (perhaps) of classical computation and of observing classical bit-string messages, verify that a quantum device in their possession is performing the task that they wish?This is a fundamental question about the nature of quantum mechanics, and the extent to which humans can harness it in a trustworthy manner.It is also a natural and important consideration when quantum devices may be used to perform sensitive cryptographic tasks which have no known efficient classical witness of correctness (Quantum Key Distribution, and Randomness Expansion are two examples of such tasks).It is remarkable that any quantum behavior at all can be tested by a verifier under such a constraint, without trusting any other quantum mechanical device in the process!But, intriguingly, when there are two or more quantum provers available in an interactive proof, there exist protocols to verify many interesting and useful quantum tasks in this setting.This thesis investigates multi-prover interactive proofs for verifying quantum behavior, and focuses on the stringent testing scenario in which the verifier in the interactive proof is completely classical as described above.It resolves the question of the maximum attainable expansion rate of a randomness expansion protocol by providing an adaptive randomness expansion protocol that achieves an arbitrary, or infinite rate of randomness expansion [29].Secondly it presents a new rigidity result for the parallel repeated magic square game [24], which provides some improvements on previous rigidity results that play a pivotal role in existing interactive proofs for entangled provers, QKD, and randomness expansion results.This new rigidity result may be useful for improving such interactive proofs in the future.The second half of this thesis investigates the problem of bounding the role of quantum The further I go the more I value what my parents' example has taught me, not about science, but about life.I love you Mom and Dad.My deep gratitude goes to my advisor, Peter Shor, for guidance in research throughout graduate school, and for supporting my own research endeavors.During a PhD a student's mind is full of many different considerations, both scientific and logistical.Peter's advice is an invaluable way to refocus on the heart of the research problem at hand and, with stunning consistency, to learn something amazing and new.During my PhD I have had the privilege of collaborating with many talented researchers and good friends.What would the exploration process be without people share ideas with, and fellow researchers with which to share the thrill of discovery?Many thanks to my collaborators (listed here in no particular order)!I can only hope to continue to have such great collaborations again in the future:
Quantum entanglement, and the resulting peculiar non-classical correlations are one of the most counter-intuitive aspects of quantum mechanics. The formalism of interactive games from computational complexity theory provides a useful framework in which to understand the power of entanglement. In an interactive game, a verifier interacts with a number of infinitely powerful provers who are allowed to share quantum entanglement but otherwise can't communicate. The ability of the verifier to extract useful information from the provers, whom he does not trust, provides an interesting measure of the ability of the provers to coordinate using their shared entanglement. Two particular interactive games we'll look at are Magic Square and 3SAT. The Magic Square game is the iconic example of a game where two classical provers cannot perfectly coordinate their strategies using shared randomness, but quantum provers with shared entanglement can win with probability 1. We show that by adding an extra prover, we disallow perfect cheating. For 3SAT with three provers we also show that perfect cheating is not possible. We then generalize the results for Magic Square and 3SAT by looking at non-commuting provers, a superset of entangled provers (communication is allowed, but operators applied by different provers must commute). Using this method, we obtain a generalized Tsirelson inequality that we apply to the Magic Square. Hence, we are able to give provably optimal strategies for the general Magic Square with n players. We also recover a similar result for 3SAT as with entangled provers, and we improve on it by showing that the gap is inverse exponential in the input size. The no-signaling principle, which forbids faster than light communication, is a fundamental constraint on the non-local correlations resulting from quantum entanglement. However, no-signaling allows distributions that are more general than those arising from quantum mechanics. In particular, using a specific unit of general non-local correlation (the Popescu-Rohlich box), we show that there are classes that are equal to NEXP classically, but collapse to AM once such correlations are allowed. We also show that MIP where the verifier only looks at the XOR of the answers collapses to PSPACE. For the second approach, we show that by writing general non-local correlations as linear constraints, MIP is included in EXP under such correlations (vs NEXP classically). We can extend these results to entangled quantum provers, by formulating an artificial MIP-like class built on a promise problem, that classically is equal to NEXP, but that also collapses to AM when quantum correlations are present.
Entanglement is at the heart of quantum mechanics. The nonlocal correlations that can be obtained from space-time separated measurements on an entangled state are a central feature which provably distinguish it from local theories. This dissertation studies entanglement through a computational viewpoint. We develop new insights into the complex nature of entanglement by studying its role in multiplayer games, in which cooperating, but non-communicating, players interact with a referee in an attempt to win a pre-specified game. On the one hand, the nonlocal correlations that entanglement allows may enable players using it to develop new colluding strategies, defeating previously secure protocols. On the other, the richness of this new resource may also be exploited in order to design new protocols, providing solutions to problems previously deemed impossible. We explore both aspects of this dual nature of entanglement, putting limits on its strength while at the same time showing how it can be put to profit to solve new computational problems. A major unresolved question on the computational complexity of multiplayer entangled games is the power of MIP*, the class of languages having entangled multi-prover interactive proofs: how does it relate to its purely classical analogue MIP, which was completely characterized through the fundamental equation MIP=NEXP? Since the players may use entanglement to increase their odds at colluding against the verifier, MIP* could potentially be a much weaker class than MIP. Indeed, for a long time it has been an open question whether two entangled provers are more useful than a single prover. In this thesis we resolve this question by showing that the class of languages having multiprover interactive proofs with entangled provers is at least as large as its classical counterpart: NEXP is included in MIP*. At the heart of this result is an analysis of the multilinearity test of Babai, Fortnow, and Lund in the presence of entanglement. The fact that this test remains sound gives a systematic way for a verifier to impose strong limits on the ability of entangled provers to collude against the verifier.Gap amplification is a fundamental primitive in the study of classical multiplayer games. While sequential repetition of a game always decreases the prover's maximum success probability at an exponential rate, the fact that parallel repetition also achieves a gap amplification is a highly non-trivial fact. We show that gap amplification can be performed in parallel even in the presence of entanglement between the provers. We adapt a technique which was originally introduced by Feige and Kilian and results in a polynomial rate of amplification.The phenomenon of monogamy of entanglement states, in first approximation, that if two parties are maximally entangled then they cannot simultaneously be entangled with a third party. We use this phenomenon in two distinct results. In the first, we show that the bits generated in our randomness-expansion protocol are certifiably random even from the point of view of a quantum adversary who may share prior entanglement with the provers. In addition, we prove the security against quantum adversaries of a randomness-efficient extractor construction originally due to Trevisan. This lets us transform the high-entropy bits that are generated in our protocol into ones that are almost indistinguishable from uniform by any adversary. More generally, we show how the monogamy of entanglement can be exploited to design multi-prover interactive proof systems that are partially entanglement-resistant. Quantitative bounds on the monogamy of entanglement have generally been elusive, and the analysis of our protocol demonstrates such a bound in a new context. The nonlocal correlations that can be created by entangled players provide a statistical means of differentiating them from classical, unentangled players. This is the main idea behind Bell inequalities, the violation of which demonstrates the nonlocality of quantum mechanics. We show how this phenomenon may be exploited to design a protocol in which the bits produced by successful players necessarily contain a large quantity of fresh randomness. The presence of randomness is guaranteed irrespective of the provers' actual strategy, as long as the sole constraint of no signaling is respected. Hence a statistical certification for the presence of randomness, a feat easily seen to be impossible to achieve classically. In order to manipulate the random bits produced in our protocol, and make them useful in cryptography, we give the first proof of security of a poly-logarithmic seed extractor secure against quantum adversaries. To achieve this we adapt the reconstruction paradigm originally introduced by Trevisan to the quantum setting. We study other ways in which entanglement may be used in interactive proof systems by also allowing a quantum interaction between the referee and the players. We show that, using entanglement, the class of QMIP* proof systems can be parallelized to only three rounds of interaction, and made public-coin, a property that does not hold in the absence of entanglement between the provers.
Quantum computers promise to offer a considerable speed-up in solving certain problems, compared to the best classical algorithms. In many instances, the gap between quantum and classical running times is conjectured to be exponential. While this is great news for those applications where quantum computers would provide such an advantage, it also raises a significant challenge: how can classical computers verify the correctness of quantum computations? In attempting to answer this question, a number of protocols have been developed in which a classical client (referred to as verifier) can interact with one or more quantum servers (referred to as provers) in order to certify the correctness of a quantum computation performed by the server(s). These protocols are of one of two types: either there are multiple non-communicating provers, sharing entanglement, and the verifier is completely classical; or, there is a single prover and the classical verifier has a device for preparing or measuring quantum states. The latter type of protocols are, arguably, more relevant to near term quantum computers, since having multiple quantum computers that share a large amount of entanglement is, from a technological standpoint, extremely challenging. Before the realisation of practical single-prover protocols, a number of challenges need to be addressed: how robust are these protocols to noise on the verifier's device? Can the protocols be made fault-tolerant without significantly increasing the requirements of the verifier? How do we know that the verifier's device is operating correctly? Could this device be eliminated completely, thus having a protocol with a fully classical verifier and a single quantum prover? Our work attempts to provide answers to these questions. First, we consider a single-prover verification protocol developed by Fitzsimons and Kashefi and show that this protocol is indeed robust with respect to deviations on the quantum state prepared by the verifier. We show that this is true even if those deviations are the result of a correlation with the prover's system. We then use this result to give a verification protocol which is device- independent. The protocol consists of a verifier with a measurement device and a single prover. Device-independence means that the verifier need not trust the measurement device (nor the prover) which can be assumed to be fully malicious (though not communicating with the prover). A key element in realising this protocol is a robust technique of Reichardt, Unger and Vazirani for testing, using non-local correlations, that two untrusted devices share a large number of entangled states. This technique is referred to as rigidity of non-local correlations. Our second result is to prove a rigidity result for a type of quantum correlations known as steering correlations. To do this, we first show that steering correlations can be used in order to certify maximally entangled states, in a setting in which each test is independent of the previous one. We also show that the fidelity with which we characterise the state, in this specific test, is optimal. We then improve the previous result by removing the independence assumption. This then leads to our desired rigidity result. We make use of it, in a similar fashion to the device-independent case, in order to give a verification protocol that is one-sided device-independent. The importance of this application is to show how different trust assumptions affect the efficiency of the protocol. Next, we describe a protocol for fault-tolerantly verifying quantum computations, with minimal "quantum requirements" for the verifier. Specifically, the verifier only requires a device for measuring single-qubit states. Both this device, and the prover's operations are assumed to be prone to errors. We show that under standard assumptions about the error model, it is possible to achieve verification of quantum computation using fault-tolerant principles. As a proof of principle, and to better illustrate the inner workings of the protocol, we describe a toy implementation of the protocol in a quantum simulator, and present the results we obtained, when running it for a small computation. Finally, we explore the possibility of having a verification protocol, with a classical verifier and a single prover, such that the prover is blind with respect to the verifier's computation. We give evidence that this is not possible. In fact, our result is only concerned with blind quantum computation with a classical client, and uses complexity theoretic results to argue why it is improbable for such a protocol to exist. We then use these complexity theoretic techniques to show that a client, with the ability to prepare and send quantum states to a quantum server, would not be able to delegate arbitrary NP problems to that server. In other words, even a client with quantum capabilities cannot exploit those capabilities to delegate the computation of NP problems, while keeping the input, to that computation, private. This is again true, provided certain complexity theoretic conjectures are true.
A team of students has been given a challenging physics exam: find the ground energy of a complicated, n-spin system. Even if they succeed, how can the examiners be sure that their answer is correct without physically measuring all n spins of the ground state, or worse, having to read a description of the 2n components of its wavefunction? The main result of this thesis is a protocol such that, if the examiners are allowed to separately interrogate multiple students, they can be confident that the students possess the n-spin ground state as well as learn its energy to high precision, after exchanging just O(log(n)) bits of classical communication with the students! The protocol and its analysis combine classical computer science techniques for efficiently checking proofs with Bell inequalities. Stated more formally, the main result of this thesis is a multi-prover interactive proof protocol, in which a classical verifier exchanging only O(log(n)) bits of classical communication with 7 untrusted, entangled provers can certify that they share between them an encoding of an n-qubit quantum state Ib), and estimate its energy under a local Hamiltonian H to high (1/ poly(n)) precision. As a consequence, we show that, under poly-time randomized reductions, it is QMA-hard to estimate the entangled value of a nonlocal game up to constant error, proving the quantum entangled games PCP conjecture of Fitzsimons and Vidick. Our main technical innovations are two constructions of robust self-tests for entanglement: two-player nonlocal games where to succeed with probability E-close to 1, the players must share a state that is [delta] = poly([epsilon])-close in trace distance to n EPR pairs. These tests are robust in that [delta] is independent of the number n of EPR pairs being tested. Our techniques draw heavily on the original, "algebraic" proof of the PCP theorem in classical complexity theory, and in particular, each of our robust self-tests is based on a classical locally-testable error correcting code: the first on the Hadamard code and the associated linearity test of Blum, Luby, and Rubinfeld, and the second on Reed-Muller code and the associated low-degree test of Raz and Safra.
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.
Quantum information theory forms a bridge between the foundations of quantum mechanics and its promising practical potentials.The extensive theoretical research has been conducted during the last decades and the applications such as quantum key distribution and quantum computing promise to provide real technological breakthroughs.Many experimental groups worldwide are working on the practical implementation of the concepts from the quantum information theory.In the recent years a lot of attention has been paid to the certification of truly quantum behavior of some device, claimed to be quantum.This certification can be done by using some established interactive proof in which classical user just by commanding to a quantum device (prover) can make himself sure that the device works as advertised and moreover can actually use it for some particular task.When it comes to quantum computing one has to be sure that a machine uses quantum mechanics for the computational process.Two interesting interactive proofs are developed so far.One of them uses specific computation model, Measurement-based quantum computing, which is performed on a class of highly entangled states, graph states.The difficulty with the implementation of this interactive proof is a big number of provers required for the process.In this thesis we present some initial results of the attempts to construct interactive proof that would use smaller number of provers.Difficulties of the two-prover interactive proof and guidelines for the future research are presented as well as the new three-prover interactive proof for quantum device performing computation by doing single qubit unitary operations.After finishing my master program I have to thank to some people for having their part in making it as good as it has been.On the first part I would like to thank to my master thesis supervisors Antonio Acin and Matty Hoban.Thanks to prof.Acin for letting me do my thesis in his group in ICFO, for good will and useful discussions on the topic.There are not enough words to express gratitude to Matty Hoban.During these last months I had this great opportunity to learn so much from him.Thanks for this exciting project, for the enthusiasm, invested time, the patience, everything.I had a great reference for the future research.I am also grateful to the whole Quantum information theory group in ICFO, for the pleasant and very motivating atmosphere they have created.Particularly I would like to thank to my office-mate Paul Skrzypczyk for answering my questions "out of nowhere" and help with SDP and to Ariel Bendersky for the help with the last part of