Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe quantum moment problem and bounds on entangled multi-prover games
225
0
0.0
(
0
)
Authors
Andrew C. Doherty
Ask ChatGPT about the research
No Arabic abstract
We study the quantum moment problem: Given a conditional probability distribution together with some polynomial constraints, does there exist a quantum state rho and a collection of measurement operators such that (i) the probability of obtaining a particular outcome when a particular measurement is performed on rho is specified by the conditional probability distribution, and (ii) the measurement operators satisfy the constraints. For example, the constraints might specify that some measurement operators must commute. We show that if an instance of the quantum moment problem is unsatisfiable, then there exists a certificate of a particular form proving this. Our proof is based on a recent result in algebraic geometry, the noncommutative Positivstellensatz of Helton and McCullough [Trans. Amer. Math. Soc., 356(9):3721, 2004]. A special case of the quantum moment problem is to compute the value of one-round multi-prover games with entangled provers. Under the conjecture that the provers need only share states in finite-dimensional Hilbert spaces, we prove that a hierarchy of semidefinite programs similar to the one given by Navascues, Pironio and Acin [Phys. Rev. Lett., 98:010401, 2007] converges to the entangled value of the game. It follows that the class of languages recognized by a multi-prover interactive proof system where the provers share entanglement is recursive.
rate research
Read More
We present a protocol that transforms any quantum multi-prover interactive proof into a nonlocal game in which questions consist of logarithmic number of bits and answers of constant number of bits. As a corollary, this proves that the promise problem corresponding to the approximation of the nonlocal value to inverse polynomial accuracy is complete for QMIP*, and therefore NEXP-hard. This establishes that nonlocal games are provably harder than classical games without any complexity theory assumptions. Our result also indicates that gap amplification for nonlocal games may be impossible in general and provides a negative evidence for the possibility of the gap amplification approach to the multi-prover variant of the quantum PCP conjecture.
We prove an explicit upper bound on the amount of entanglement required by any strategy in a two-player cooperative game with classical questions and quantum answers. Specifically, we show that every strategy for a game with n-bit questions and n-qubit answers can be implemented exactly by players who share an entangled state of no more than 5n qubits--a bound which is optimal to within a factor of 5/2. Previously, no upper bound at all was known on the amount of entanglement required even to approximate such a strategy. It follows that the problem of computing the value of these games is in NP, whereas previously this problem was not known to be computable.
The behavior of games repeated in parallel, when played with quantumly entangled players, has received much attention in recent years. Quantum analogues of Razs classical parallel repetition theorem have been proved for many special classes of games. However, for general entangled games no parallel repetition theorem was known. We prove that the entangled value of a two-player game $G$ repeated $n$ times in parallel is at most $c_G n^{-1/4} log n$ for a constant $c_G$ depending on $G$, provided that the entangled value of $G$ is less than 1. In particular, this gives the first proof that the entangled value of a parallel repeated game must converge to 0 for all games whose entangled value is less than 1. Central to our proof is a combination of both classical and quantum correlated sampling.
Multi Prover Interactive Proof systems (MIPs)were first presented in a cryptographic context, but ever since they were used in various fields. Understanding the power of MIPs in the quantum context raises many open problems, as there are several interesting models to consider. For example, one can study the question when the provers share entanglement or not, and the communication between the verifier and the provers is quantum or classical. While there are several partial results on the subject, so far no one presented an efficient scheme for recognizing NEXP (or NP with logarithmic communication), except for [KM03], in the case there is no entanglement (and of course no communication between the provers). We introduce another variant of Quantum MIP, where the provers do not share entanglement, the communication between the verifier and the provers is quantum, but the provers are unlimited in the classical communication between them. At first, this model may seem very weak, as provers who exchange information seem to be equivalent in power to a simple prover. This in fact is not the case - we show that any language in NEXP can be recognized in this model efficiently, with just two provers and two rounds of communication, with a constant completeness-soundness gap.
We prove lower bounds on the error probability of a quantum algorithm for searching through an unordered list of N items, as a function of the number T of queries it makes. In particular, if T=O(sqrt{N}) then the error is lower bounded by a constant. If we want error <1/2^N then we need T=Omega(N) queries. We apply this to show that a quantum computer cannot do much better than a classical computer when amplifying the success probability of an RP-machine. A classical computer can achieve error <=1/2^k using k applications of the RP-machine, a quantum computer still needs at least ck applications for this (when treating the machine as a black-box), where c>0 is a constant independent of k. Furthermore, we prove a lower bound of Omega(sqrt{log N}/loglog N) queries for quantum bounded-error search of an ordered list of N items.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
