research-article

QIP = PSPACE

Authors:

Sarvagya Upadhyay,

John WatrousAuthors Info & Claims

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

Pages 573 - 582

https://doi.org/10.1145/1806689.1806768

Published: 05 June 2010 Publication History

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.

References

[1]

S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009.

Digital Library

[2]

S. Arora, E. Hazan, and S. Kale. Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 339--348, 2005.

Digital Library

[3]

S. Arora and S. Kale. A combinatorial, primal-dual approach to semidefinite programs. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, pages 227--236, 2007.

Digital Library

[4]

L. Babai. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pages 421--429, 1985.

Digital Library

[5]

L. Babai and S. Moran. Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36(2):254--276, 1988.

Digital Library

[6]

M. Ben-Or, E. Feig, D. Kozen, and P. Tiwari. A fast parallel algorithm for determining all roots of a polynomial with real roots. In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, pages 340--349, 1986.

Digital Library

[7]

M. Ben-Or, S. Goldwasser, J. Kilian, and A.Wigderson. Multi-prover interactive proofs: how to remove intractability assumptions. In Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 113--131, 1988.

Digital Library

[8]

R. Bhatia. Matrix Analysis. Springer, 1997.

[9]

D. Bini and V. Pan. Computing matrix eigenvalues and polynomial zeros where the output is real. SIAM Journal on Computing, 27(4):1099--1115, 1998.

Digital Library

[10]

A. Borodin. On relating time and space to size and depth. SIAM Journal on Computing, 6:733--744, 1977.

[11]

A. Borodin, S. Cook, and N. Pippenger. Parallel computation for well-endowed rings and space-bounded probabilistic machines. Information and Control, 58:113--136, 1983.

Digital Library

[12]

Y. Bugeaud. Approximation by Algebraic Numbers, volume 160 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2004.

[13]

L. Csanky. Fast parallel matrix inversion algorithms. SIAM Journal on Computing, 5(4):618--623, 1976.

[14]

D. Dobkin, R. Lipton, and S. Reiss. Linear programming is log-space hard for P. Information Processing Letters, 8(2):96--97, 1979.

[15]

S. Even, A. Selman, and Y. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2):159--173, 1984.

Digital Library

[16]

U. Feige and J. Kilian. Making games short. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing, pages 506--516, 1997.

Digital Library

[17]

P. Feldman. The optimum prover lies in PSPACE. Manuscript, 1986.

[18]

J. von zur Gathen. Parallel linear algebra. In J. Reif, editor, Synthesis of Parallel Algorithms, chapter 13. Morgan Kaufmann Publishers, Inc., 1993.

[19]

O. Goldreich. On promise problems (a survey in memory of Shimon Even {1935--2004}). Electronic Colloquium on Computational Complexity, Report TR05-018, 2005.

[20]

O. Goldreich, S. Micali, and A.Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. Journal of the ACM, 38(1):691--729, 1991.

Digital Library

[21]

S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, pages 291--304, 1985.

Digital Library

[22]

S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186--208, 1989.

Digital Library

[23]

S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pages 73--90. JAI Press, 1989.

[24]

G. Gutoski and J.Watrous. Toward a general theory of quantum games. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 565--574, 2007.

Digital Library

[25]

S. Hallgren, A. Kolla, P. Sen, and S. Zhang. Making classical honest verifier zero knowledge protocols secure against quantum attacks. In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, volume 5126 of Lecture Notes in Computer Science, pages 592--603. Springer, 2008.

Digital Library

[26]

R. Jain, S. Upadhyay, and J.Watrous. Two-message quantum interactive proofs are in PSPACE. In Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, pages 534--543, 2009.

Digital Library

[27]

R. Jain and J.Watrous. Parallel approximation of non-interactive zero-sum quantum games. In Proceedings of the 24th IEEE Conference on Computational Complexity, pages 243--253, 2009.

Digital Library

[28]

S. Kale. Efficient algorithms using the multiplicative weights update method. PhD thesis, Princeton University, 2007.

Digital Library

[29]

J. Kempe, H. Kobayashi, K. Matsumoto, and T. Vidick. Using entanglement in quantum multi-prover interactive proofs. Computational Complexity, 18(2):273--307, 2009.

[30]

A. Kitaev and J.Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof system. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 608--617, 2000.

Digital Library

[31]

H. Kobayashi. General properties of quantum zero-knowledge proofs. In Proceedings of the Fifth IACR Theory of Cryptography Conference, volume 4948 of Lecture Notes in Computer Science, pages 107--124. Springer, 2008.

Digital Library

[32]

H. Kobayashi and K. Matsumoto. Quantum multi-prover interactive proof systems with limited prior entanglement. Journal of Computer and System Sciences, 66(3):429--450, 2003.

Digital Library

[33]

C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4):859--868, 1992.

Digital Library

[34]

K. Mahler. Lectures on Diophantine Approximations, volume 1. Cushing Malloy, 1961.

[35]

C. Marriott and J.Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14(2):122--152, 2005.

Digital Library

[36]

N. Megiddo. A note on approximate linear programming. Information Processing Letters, 42(1):53, 1992.

Digital Library

[37]

C. Moler and C. V. Loan. Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Review, 45(1):3--49, 2003.

Digital Library

[38]

C. A. Neff. Specified precision polynomial root isolation is in NC. Journal of Computer and System Sciences, 48(3):429--463, 1994.

Digital Library

[39]

M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

Digital Library

[40]

M. Serna. Approximating linear programming is log-space complete for P. Information Processing Letters, 37(4):233--236, 1991.

Digital Library

[41]

A. Shamir. IP = PSPACE. Journal of the ACM, 39(4):869--877, 1992.

Digital Library

[42]

A. Shen. IP = PSPACE: simplified proof. Journal of the ACM, 39(4):878--880, 1992.

Digital Library

[43]

M. Sipser. Introduction to the Theory of Computation. Thomson Course Technology, second edition, 2005.

[44]

M. Warmuth and D. Kuzmin. Online variance minimization. In Proceedings of the 19th Annual Conference on Learning Theory, volume 4005 of Lecture Notes in Computer Science, pages 514--528. Springer, 2006.

Digital Library

[45]

J.Watrous. PSPACE has constant-round quantum interactive proof systems. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, pages 112--119, 1999.

Digital Library

[46]

J.Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing, 39(1):25--58, 2009.

Digital Library

Cited By

Lin WPiliouras GSim RVarvitsiotis A(2024)No-Regret Learning and Equilibrium Computation in Quantum GamesQuantum10.22331/q-2024-12-17-15698(1569)Online publication date: 17-Dec-2024
https://doi.org/10.22331/q-2024-12-17-1569
Jeronimo FWu PSaha BServedio R(2023)The Power of Unentangled Quantum Proofs with Non-negative AmplitudesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585248(1629-1642)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585248
Aharonov DArad IVidick T(2013)Guest columnACM SIGACT News10.1145/2491533.249154944:2(47-79)Online publication date: 3-Jun-2013
https://dl.acm.org/doi/10.1145/2491533.2491549
Show More Cited By

Index Terms

QIP = PSPACE
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes

Recommendations

QIP = PSPACE

The interactive proof system model of computation has been studied extensively in computational complexity theory and theoretical cryptography for more than 25 years, and has driven the development of interesting new techniques and insights in those ...
QIP = PSPACE

This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model’s natural quantum computational analogue. An exact characterization of the expressive power of quantum interactive ...
Two-Message Quantum Interactive Proofs Are in PSPACE
FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer Science

We prove that QIP(2), the class of problems having two-message quantum interactive proof systems, is a subset of PSPACE.This relationship is obtained by means of an efficient parallel algorithm, based on the matrix multiplicative weights update method, ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

June 2010

812 pages

ISBN:9781450300506

DOI:10.1145/1806689

General Chair:
Michael Mitzenmacher
Harvard
,
Program Chair:
Leonard J. Schulman
Caltech

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'10

Sponsor:

SIGACT

STOC'10: Symposium on Theory of Computing

June 5 - 8, 2010

Massachusetts, Cambridge, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
384
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)4

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lin WPiliouras GSim RVarvitsiotis A(2024)No-Regret Learning and Equilibrium Computation in Quantum GamesQuantum10.22331/q-2024-12-17-15698(1569)Online publication date: 17-Dec-2024
https://doi.org/10.22331/q-2024-12-17-1569
Jeronimo FWu PSaha BServedio R(2023)The Power of Unentangled Quantum Proofs with Non-negative AmplitudesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585248(1629-1642)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585248
Aharonov DArad IVidick T(2013)Guest columnACM SIGACT News10.1145/2491533.249154944:2(47-79)Online publication date: 3-Jun-2013
https://dl.acm.org/doi/10.1145/2491533.2491549
Wright A(2013)Proving groundsCommunications of the ACM10.1145/2447976.244798256:5(17-19)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1145/2447976.2447982
Ito TKobayashi HWatrous JGoldwasser S(2012)Quantum interactive proofs with weak error boundsProceedings of the 3rd Innovations in Theoretical Computer Science Conference10.1145/2090236.2090259(266-275)Online publication date: 8-Jan-2012
https://dl.acm.org/doi/10.1145/2090236.2090259
Gutoski GWu X(2012)Parallel Approximation of Min-max Problems with Applications to Classical and Quantum Zero-Sum GamesProceedings of the 2012 IEEE Conference on Computational Complexity (CCC)10.1109/CCC.2012.12(21-31)Online publication date: 26-Jun-2012
https://dl.acm.org/doi/10.1109/CCC.2012.12
Warmuth MKuzmin D(2012)Online variance minimizationMachine Language10.1007/s10994-011-5269-087:1(1-32)Online publication date: 1-Apr-2012
https://dl.acm.org/doi/10.1007/s10994-011-5269-0
Chailloux AKerenidis IRosgen B(2011)Quantum commitments from complexity assumptionsProceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I10.5555/2027127.2027136(73-85)Online publication date: 4-Jul-2011
https://dl.acm.org/doi/10.5555/2027127.2027136
Jain RYao P(2011)A Parallel Approximation Algorithm for Positive Semidefinite ProgrammingProceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science10.1109/FOCS.2011.25(463-471)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1109/FOCS.2011.25
Gharibian SKempe J(2011)Approximation Algorithms for QMA-Complete ProblemsProceedings of the 2011 IEEE 26th Annual Conference on Computational Complexity10.1109/CCC.2011.15(178-188)Online publication date: 8-Jun-2011
https://dl.acm.org/doi/10.1109/CCC.2011.15
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents