QIP = PSPACE

DOI10.1145/2049697.2049704zbMATH Open1281.68117arXiv0907.4737OpenAlexW2295995314MaRDI QIDQ5395673FDOQ5395673

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous

Publication date: 17 February 2014

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE. This containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semidefinite programs that captures the computational power of quantum interactive proofs. As the containment of PSPACE in QIP follows immediately from the well-known equality IP = PSPACE, the equality QIP = PSPACE follows.

Full work available at URL: https://arxiv.org/abs/0907.4737

zbMATH Keywords

semidefinite programmingquantum computationinteractive proof systemsmatrix multiplicative weights update method

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (12)

• Constant-space quantum interactive proofs against multiple provers
• QPCF: higher-order languages and quantum circuits
• Generalized Quantum Arthur--Merlin Games
• Title not available (Why is that?)
• Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
• \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
• Accelerated Extra-Gradient Descent: A Novel Accelerated First-Order Method
• IP = SPACE
• \(\mathrm{QIP} = \mathrm{PSPACE}\)
• Parallel approximation of min-max problems
• Title not available (Why is that?)
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and \(=(1/\varepsilon)\)-convergence

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• \(\mathrm{QIP} = \mathrm{PSPACE}\) 👍 👎
• \(Q_p\)-spaces 👍 👎
• IP = PSPACE 👍 👎
• \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\) 👍 👎
• \(L_p [0,1 \setminus \underset {q>p} \bigcup L_q [0,1]\) is spaceable for every \(p > 0\)] 👍 👎
• On the Space l^p+ = ∩l^q_q>p 👍 👎
• \(Q\)-binary spaces 👍 👎
• IP = SPACE 👍 👎

This page was built for publication: QIP = PSPACE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395673)