QIP = PSPACE

DOI10.1145/2049697.2049704MaRDI QIDQ5395673zbMATH OpenOpenAlexFDO

Authors Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous

Publication date 17 February 2014

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

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)

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.

Recommendations

• \(\mathrm{QIP} = \mathrm{PSPACE}\)
• IP = PSPACE
• IP = SPACE
• \(Q_p\)-spaces
• scientific article; zbMATH DE number 2134878
• \(Q\)-binary spaces
• \(L_p [0,1] \setminus \underset {q>p} \bigcup L_q [0,1]\) is spaceable for every \(p > 0\)
• scientific article; zbMATH DE number 1489953
• On the Space l^p+ = ∩l^q_q>p
• \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)

Cited in

(18)

• Constant-space quantum interactive proofs against multiple provers
• QPCF: higher-order languages and quantum circuits
• Stronger methods of making quantum interactive proofs perfectly complete
• scientific article; zbMATH DE number 7651209 (Why is no real title available?)
• On the complexity of approximating the diamond norm
• \(\text{NQP}_\mathbb{C}=\text{co-C}_=\text{P}\)
• PSPACE has constant-round quantum interactive proof systems
• Quantum interactive proofs with weak error bounds
• Measuring 4-local qubit observables could probabilistically solve PSPACE
• IP = SPACE
• Generalized quantum Arthur-Merlin games
• \(\mathrm{QIP} = \mathrm{PSPACE}\)
• Parallel approximation of min-max problems
• Accelerated extra-gradient descent: a novel accelerated first-order method
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• scientific article; zbMATH DE number 7561520 (Why is no real title available?)
• Nearly linear-time packing and covering LP solvers. Nearly linear-time packing and covering LP solvers, achieving width-independence and =(1/)-convergence
• Bounds on the power of proofs and advice in general physical theories

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)