TY - GEN
T1 - The quantum moment problem and bounds on entangled multi-prover games
AU - Doherty, Andrew C.
AU - Toner, Ben
AU - Liang, Yeong Cherng
AU - Wehner, Stephanie
PY - 2008
Y1 - 2008
N2 - We study the quantum moment problem: Given a conditional probability distribution together with some polynomial constraints, does there exist a quantum state p and a collection of measurement operators such that (i) the probability of obtaining a particular outcome when a particular measurement is performed on p 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 Navascués, Pironio and Acín /Phys. Rev. Lett., 98:010401, 2007] converges to the entangled value of the game. Under this conjecture, it would follow that the languages recognized by a multi-prover interactive proof system where the provers share entanglement are recursive.
AB - We study the quantum moment problem: Given a conditional probability distribution together with some polynomial constraints, does there exist a quantum state p and a collection of measurement operators such that (i) the probability of obtaining a particular outcome when a particular measurement is performed on p 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 Navascués, Pironio and Acín /Phys. Rev. Lett., 98:010401, 2007] converges to the entangled value of the game. Under this conjecture, it would follow that the languages recognized by a multi-prover interactive proof system where the provers share entanglement are recursive.
UR - http://www.scopus.com/inward/record.url?scp=51749083986&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51749083986&partnerID=8YFLogxK
U2 - 10.1109/CCC.2008.26
DO - 10.1109/CCC.2008.26
M3 - Conference contribution
AN - SCOPUS:51749083986
SN - 9780769531694
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 199
EP - 210
BT - Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
T2 - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Y2 - 23 June 2008 through 26 June 2008
ER -