Dorit Aharonov
Skip Abstract Section
Abstract
The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century. In recent years, researchers in quantum computational complexity have tried to identify approaches and develop tools that address the question: does a quantum version of the PCP theorem hold? The story of this study starts with classical complexity and takes unexpected turns providing fascinating vistas on the foundations of quantum mechanics and multipartite entanglement, topology and the so-called phenomenon of topological order, quantum error correction, information theory, and much more; it raises questions that touch upon some of the most fundamental issues at the heart of our understanding of quantum mechanics. At this point, the jury is still out as to whether or not such a theorem holds. This survey aims to provide a snapshot of the status in this ongoing story, tailored to a general theory-of-CS audience.
- S. A. Cook, "The complexity of theorem-proving procedures," in Proceedings of the third annual ACM symposium on Theory of computing, pp. 151--158, ACM, 1971. Google Scholar
Digital Library
- L. A. Levin, "Universal sequential search problems," Problemy Peredachi Informatsii, vol. 9, no. 3, pp. 115--116, 1973.Google Scholar
- S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy, "Proof verification and the hardness of approximation problems," J. ACM, vol. 45, no. 3, pp. 501--555, 1998. Google ScholarDigital Library
- S. Arora and S. Safra, "Probabilistic checking of proofs: A new characterization of NP," J. ACM, vol. 45, no. 1, pp. 70--122, 1998. Google ScholarDigital Library
- I. Dinur, "The PCP theorem by gap amplification," J. ACM, vol. 54, no. 3, 2007. Google ScholarDigital Library
- C. Lund, L. Fortnow, H. Karloff, and N. Nisan, "Algebraic methods for interactive proof systems," J. ACM, vol. 39, pp. 859--868, 1992. Google ScholarDigital Library
- A. Shamir, "IP = PSPACE," J. ACM, vol. 39, no. 4, pp. 869--877, 1992. Google ScholarDigital Library
- L. Babai, L. Fortnow, and C. Lund, "Non-deterministic exponential time has two-prover interactive protocols," Comput. Complexity, vol. 1, pp. 3--40, 1991.Google ScholarCross Ref
- L. Babai, "Trading group theory for randomness," in Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 421--429, ACM, 1985. Google ScholarDigital Library
- S. Goldwasser, S. Micali, and C. Rackoff, "The knowledge complexity of interactive proof systems," SIAM Journal on Computing, vol. 18, no. 1, pp. 186--208, 1989. Google ScholarDigital Library
- S. Arora and B. Barak, Computational complexity: a modern approach. Cambridge University Press Cambridge, 2009. Google ScholarDigital Library
- M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information. Cambridge University Press, October 2000.Google ScholarDigital Library
- A. Kitaev, 1999. Lecture given at the Hebrew University, Jerusalem, Israel.Google Scholar
- A. Kitaev, A. Shen, and M. Vyalyi, Classical and Quantum Computation. American Mathematical Society, 2002. Google ScholarDigital Library
- E. Knill, "Quantum randomness and nondeterminism," arXiv preprint quant-ph/9610012, 1996.Google Scholar
- D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev, "Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation," in Proc. 45th FOCS, vol. 45, pp. 42--53, IEEE, 2004. Google ScholarDigital Library
- J. Kempe, A. Kitaev, and O. Regev, "The complexity of the local Hamiltonian problem," SIAM Journal on Computing, vol. 35, no. 5, pp. 1070--1097, 2006. Google ScholarDigital Library
- R. Oliveira and B. M. Terhal, "The complexity of quantum spin systems on a two-dimensional square lattice," Quantum Information & Computation, vol. 8, no. 10, pp. 900--924, 2008. Google ScholarDigital Library
- D. Aharonov, D. Gottesman, S. Irani, and J. Kempe, "The power of quantum systems on a line," Communications in Mathematical Physics, vol. 287, no. 1, pp. 41--65, 2009.Google ScholarCross Ref
- D. Gottesman and S. Irani, "The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems," in Proc. 50th FOCS, pp. 95--104, IEEE, 2009. Google ScholarDigital Library
- S. Bravyi, D. P. DiVincenzo, D. Loss, and B. M. Terhal, "Quantum simulation of many-body Hamiltonians using perturbation theory with bounded-strength interactions," Phys. Rev. Lett., vol. 101, p. 070503, Aug 2008.Google ScholarCross Ref
- R. M. Karp, "Reducibility Among Combinatorial Problems," in Complexity of Computer Computations (R. E. Miller and J. W. Thatcher, eds.), pp. 85--103, Plenum Press, 1972.Google Scholar
- N. Schuch and F. Verstraete, "Computational complexity of interacting electrons and fundamental limitations of density functional theory," Nature Physics, vol. 5, pp. 732--735, Aug. 2009.Google ScholarCross Ref
- D. Aharonov and T. Naveh, "Quantum NP -- a survey," arXiv preprint quant-ph/0210077, 2002.Google Scholar
- S. Aaronson, "The quantum PCP manifesto." http://www.scottaaronson.com/blog/?p=139, 2006. Blog entry.Google Scholar
- D. Aharonov, I. Arad, Z. Landau, and U. Vazirani, "The detectability lemma and quantum gap amplification," in Proc. 41st STOC, (New York, NY, USA), pp. 417--426, ACM, 2009. Google ScholarDigital Library
- M. B. Hastings, "Topological order at nonzero temperature," Phys. Rev. Lett., vol. 107, p. 210501, Nov 2011.Google ScholarCross Ref
- M. Freedman and M. Hastings, "Quantum systems on non-k-hyperfinite complexes: A generalization of classical statistical mechanics on expander graphs," arXiv preprint arXiv:1301.1363, 2013.Google Scholar
- I. Arad, "A note about a partial no-go theorem for quantum PCP," Quantum Information & Computation, vol. 11, pp. 1019--1027, Nov. 2011. Google ScholarDigital Library
- D. Aharonov and L. Eldar, "On the complexity of commuting local Hamiltonians, and tight conditions for topological order in such systems," in Proc. 52nd FOCS, pp. 334--343, IEEE, 2011. Google ScholarDigital Library
- N. Schuch, "Complexity of commuting Hamiltonians on a square lattice of qubits," Quantum Information & Computation, vol. 11, no. 901, 2011. Google ScholarDigital Library
- M. Hastings, "Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture," Quantum Information & Computation, vol. 13, no. 5 & 6, pp. 393--429, 2013. Google ScholarDigital Library
- S. Gharibian and J. Kempe, "Approximation algorithms for QMA-complete problems," in Computational Complexity (CCC), 2011 IEEE 26th Annual Conference on, pp. 178--188, IEEE, 2011. Google ScholarDigital Library
- T. Vidick, "Three-player entangled XOR games are NP-hard to approximate," arXiv preprint arXiv:1302.1242, 2013.Google Scholar
- F. G. Brandao and A. W. Harrow, "Product-state approximations to quantum ground states," in Proc. 45th STOC, 2013. Google ScholarDigital Library
- D. Aharonov and L. Eldar, "Commuting local Hamiltonians on expanders, locally testable quantum codes, and the qPCP conjecture," arXiv preprint arXiv:1301.3407, 2013.Google Scholar
- M. B. Hastings, "Matrix product operators and central elements: Classical description of a quantum state," arXiv preprint arXiv:1207.1671, 2012.Google Scholar
- V. Guruswami and R. O'Donnell, "A history of the PCP theorem." Available at http://www.cs.washington.edu/education/courses/533/05au/pcp-history.pdf.Google Scholar
- A. Y. Kitaev, "Fault-tolerant quantum computation by anyons," Annals of Physics, vol. 303, no. 1, pp. 2--30, 2003.Google ScholarCross Ref
- S. Bravyi and M. Vyalyi, "Commutative version of the local Hamiltonian problem and common eigenspace problem," Quantum Information & Computation, vol. 5, no. 3, pp. 187--215, 2013. Google ScholarDigital Library
- J. S. Bell, "On the Einstein-Podolsky-Rosen paradox," Physics, vol. 1, pp. 195--200, 1964.Google ScholarCross Ref
- A. Aspect, J. Dalibard, and G. Roger, "Experimental test of Bell's inequalities using timevarying analyzers," Phys. Rev. Lett., vol. 49, pp. 1804--1807, Dec 1982.Google ScholarCross Ref
- R. P. Feynman, "Simulating physics with computers," International journal of theoretical physics, vol. 21, no. 6, pp. 467--488, 1982.Google Scholar
- R. P. Feynman, "Quantum mechanical computers," Foundations of physics, vol. 16, no. 6, pp. 507--531, 1986.Google ScholarCross Ref
- I. Dinur and O. Reingold, "Assignment testers: Towards a combinatorial proof of the PCPtheorem," in Proc. 45th FOCS, pp. 155--164, IEEE, 2004. Google ScholarDigital Library
- E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan, "Robust PCPs of proximity, shorter PCPs and applications to coding," in Proc. 36th STOC, pp. 1--10, ACM, 2004. Google ScholarDigital Library
- W. K. Wootters and W. H. Zurek, "A single quantum cannot be cloned," Nature, vol. 299, no. 5886, pp. 802--803, 1982.Google ScholarCross Ref
- P. Raghavendra and N. Tan, "Approximating CSPs with global cardinality constraints using SDP hierarchies," in Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 373--387, SIAM, 2012. Google ScholarDigital Library
- V. Coffman, J. Kundu, and W. K. Wootters, "Distributed entanglement," Phys. Rev. A, vol. 61, p. 052306, Apr 2000.Google ScholarCross Ref
- S. Hoory, N. Linial, and A. Wigderson, "Expander graphs and their applications," Bulletin of the American Mathematical Society, vol. 43, no. 4, pp. 439--561, 2006.Google ScholarCross Ref
- J. Eisert, M. Cramer, and M. B. Plenio, "Colloquium: Area laws for the entanglement entropy," Rev. Mod. Phys., vol. 82, pp. 277--306, Feb 2010.Google ScholarCross Ref
- S. Bravyi, M. B. Hastings, and F. Verstraete, "Lieb-Robinson bounds and the generation of correlations and topological quantum order," Phys. Rev. Lett., vol. 97, p. 050401, Jul 2006.Google ScholarCross Ref
- E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, "Topological quantum memory," Journal of Mathematical Physics, vol. 43, p. 4452, 2002.Google ScholarCross Ref
- O. Goldreich, S. Micali, and A. Wigderson, "Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems," J. ACM, vol. 38, no. 3, pp. 691--729, 1991. Google ScholarDigital Library
- Y.-K. Liu, "Consistency of local density matrices is QMA-complete," in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 438--449, Springer, 2006. Google ScholarDigital Library
- A. Kitaev and J. Watrous, "Parallelization, amplification, and exponential time simulation of quantum interactive proof systems," in Proc. 32nd STOC, (New York, NY, USA), pp. 608--617, ACM, 2000. Google ScholarDigital Library
- M. Vyalyi, "QMA=PP implies that PP contains PH," tech. rep., Electronic Colloquium on Computational Complexity, Report TR03-021, 2003.Google Scholar
- C. Marriott and J. Watrous, "Quantum Arthur-Merlin games," Comput. Complexity, vol. 14, pp. 122--152, June 2005. Google ScholarDigital Library
- R. Cleve, P. Hoyer, B. Toner, and J. Watrous, "Consequences and limits of nonlocal strategies," in Proc. 19th IEEE Conf. on Computational Complexity (CCC'04), pp. 236--249, IEEE Computer Society, 2004. Google ScholarDigital Library
- B. W. Reichardt, F. Unger, and U. Vazirani, "A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games," in Proceedings of the 4th conference on Innovations in Theoretical Computer Science, ITCS '13, (New York, NY, USA), pp. 321--322, ACM, 2013. Google ScholarDigital Library
- R. Jain, Z. Ji, S. Upadhyay, and J. Watrous, "QIP = PSPACE," in Proc. 42nd STOC, (New York, NY, USA), pp. 573--582, ACM, 2010. Google ScholarDigital Library
- T. Ito and T. Vidick, "A multi-prover interactive proof for NEXP sound against entangled provers," Proc. 53rd FOCS, pp. 243--252, 2012. Google ScholarDigital Library
- L. Valiant and V. Vazirani, "NP is as easy as detecting unique solutions," Theoretical Computer Science, vol. 47, no. 0, pp. 85--93, 1986. Google ScholarDigital Library
- S. Aaronson, "On perfect completeness for QMA," Quantum Information & Computation, vol. 9, no. 1, pp. 81--89, 2009. Google ScholarDigital Library
- M. Aguado and G. Vidal, "Entanglement renormalization and topological order," Phys. Rev. Lett., vol. 100, p. 070404, Feb 2008.Google ScholarCross Ref
Index Terms
- Guest column: the quantum PCP conjecture
Recommendations
Guest Column: Quantum Finite Automata: From Theory to Practice
Quantum computing is a prolific research area, halfway between physics and computer science [27, 29, 52]. Most likely, its origins may be dated back to 70's, when some works on quantum information began to appear (see, e.g., [34, 37]). In early 80's, ...
Guest Column: Adiabatic Quantum Computing Challenges
The paper presents a brief introduction to quantum computing with focus on the adiabatic model which is illustrated with the commercial D-Wave computer. We also include new theory and experimental work done on the D-Wave computer. Finally we discuss a ...
Guest Column: NP-complete problems and physical reality
Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, ...
Comments