link.springer.com

Quantum Computational Complexity

  • Aaronson S (2002) Quantum lower bound for the collision problem. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing. ACM Press, New York

    Google Scholar 

  • Aaronson S (2005) Limitations of quantum advice and one-way communication. Theory Comput 1:1–28

    MathSciNet  Google Scholar 

  • Aaronson S (2006) QMA/qpoly is contained in PSPACE/poly: de-Merlinizing quantum protocols. In: Proceedings of the 21st Annual IEEE Conference on Computational Complexity. IEEE Ceomputer Society Press, Los Alamitos pp 261–273

    Google Scholar 

  • Aaronson S, Kuperberg G (2007) Quantum versus classical proofs and advice. Theory Comput 3:129–157

    MathSciNet  Google Scholar 

  • Aaronson S, Shi Y (2004) Quantum lower bounds for the collision and the element distinctness problems. J ACM 51(4):595–605

    MathSciNet  MATH  Google Scholar 

  • Adleman L (1978) Two theorems on random polynomial time. In: Proceeding of the 19th Annual IEEE Symposium on Foundations of Computer Science. IEEE Ceomputer Society Press, Los Alamitos pp 75–83

    Google Scholar 

  • Adleman L, DeMarrais J, Huang M (1997) Quantum computability. SIAM J Comput 26(5):1524–1540

    MathSciNet  MATH  Google Scholar 

  • Aharonov D, Naveh T (2002) Quantum NP – a survey. Available as arXiv.org e-Print quant-ph/0210077

    Google Scholar 

  • Aharonov D, Kitaev A, Nisan N (1998) Quantum circuits with mixed states. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing. ACM Press, New York, pp 20–30

    Google Scholar 

  • Aharonov D, Gottesman D, Irani S, Kempe J (2007) The power of quantum systems on a line. In: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science. IEEE Ceomputer Society Press, Los Alamitos pp 373–383

    Google Scholar 

  • Aharonov D, van Dam W, Kempe J, Landau Z, Lloyd S, Regev O (2007) Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J Comput 37(1):166–194

    MathSciNet  MATH  Google Scholar 

  • Allender E, Ogihara M (1996) Relationships among PL, #L, and the determinant. RAIRO – Theor Inf Appl 30:1–21

    MathSciNet  MATH  Google Scholar 

  • Arora S, Barak B (2006) Complexity Theory: A Modern Approach. Web draft available at http://www.cs.princeton.edu/theory/complexity/

  • Arora S, Safra S (1998) Probabilistic checking of proofs: a new characterization of NP. J ACM 45(1):70–122

    MathSciNet  MATH  Google Scholar 

  • Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and the hardness of approximation problems. J ACM 45(3):501–555

    MathSciNet  MATH  Google Scholar 

  • Aroya A-B, Shma A-T (2007) Quantum expanders and the quantum entropy difference problem. Available as arXiv.org e-print quant-ph/0702129

    Google Scholar 

  • Babai L (1985) Trading group theory for randomness. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing. ACM Press, New York pp 421–429

    Google Scholar 

  • Babai L (1992) Bounded round interactive proofs in finite groups. SIAM J Discret Math 5(1):88–111

    MathSciNet  MATH  Google Scholar 

  • Babai L, Moran S (1988) Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. J Comput Syst Sci 36(2):254–276

    MathSciNet  MATH  Google Scholar 

  • Babai L, Szemerédi E (1984) On the complexity of matrix group problems I. In: Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science. IEEE Ceomputer Society Press, Los Alamitos pp 229–240

    Google Scholar 

  • Babai L, Fortnow L, Lund C (1991) Non-deterministic exponential time has two-prover interactive protocols. Comput Complex 1(1):3–40

    MathSciNet  MATH  Google Scholar 

  • Beigel R, Reingold N, Spielman D (1995) PP is closed under intersection. J Comput Syst Sci 50(2):191–202

    MathSciNet  MATH  Google Scholar 

  • Beigi S, Shor P (2007) On the complexity of computing zero-error and Holevo capacity of quantum channels. Available as arXiv.org e-Print 0709.2090

    Google Scholar 

  • Bell J (1964) On the Einstein-Podolsky-Rosen paradox. Phys 1(3):195–200

    Google Scholar 

  • Bellare M, Goldreich O, Sudan M (1998) Free bits, PCPs, and non-approximability —towards tight results. SIAM J Comput 27(3):804–915

    MathSciNet  MATH  Google Scholar 

  • Bennett CH (1973) Logical reversibility of computation. IBM J Res Dev 17:525–532

    MATH  Google Scholar 

  • Bennett CH, Bernstein E, Brassard G, Vazirani U (1997) Strengths and weaknesses of quantum computing. SIAM J Comput 26(5):1510–1523

    MathSciNet  MATH  Google Scholar 

  • Bera D, Green F, Homer S (2007) Small depth quantum circuits. ACM SIGACT News 38(2):35–50

    Google Scholar 

  • Bernstein E, Vazirani U (1993) Quantum complexity theory (preliminary abstract). In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing. ACM Press, New York pp 11–20

    Google Scholar 

  • Bernstein E, Vazirani U (1997) Quantum complexity theory. SIAM J Comput 26(5):1411–1473

    MathSciNet  MATH  Google Scholar 

  • Borodin A (1977) On relating time and space to size and depth. SIAM J Comput 6:733–744

    MathSciNet  MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  • Brassard G (2003) Quantum communication complexity. Found Phys 33(11):1593–1616

    MathSciNet  MATH  Google Scholar 

  • Cleve R (2000) An introduction to quantum complexity theory. In: Macchiavello C, Palma GM, Zeilinger A (eds) Collected Papers on Quantum Computation and Quantum Information Theory. World Scientific. Singapore pp 103–127

    Google Scholar 

  • Cleve R, Watrous J (2000) Fast parallel circuits for the quantum Fourier transform. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science. pp 526–536

    Google Scholar 

  • Cleve R, Høyer P, Toner B, Watrous J (2004) Consequences and limits of nonlocal strategies. In: Proceedings of the 19th Annual IEEE Conference on Computational Complexity. pp 236–249

    Google Scholar 

  • Cleve R, Slofstra W, Unger F, Upadhyay S (2007) Perfect parallel repetition theorem for quantum XOR proof systems. In: Proceedings of the 22nd Annual IEEE Conference on Computational Complexity. pp 109–114

    Google Scholar 

  • Cook S (1972) The complexity of theorem proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. ACM Press, New York pp 151–158

    Google Scholar 

  • de Wolf R (2002) Quantum communication and complexity. Theor Comput Sci 287(1):337–353

    MATH  Google Scholar 

  • Deutsch D (1985) Quantum theory, the Church–Turing principle and the universal quantum computer. Proc Roy Soc Lond A 400:97–117

    MathSciNet  ADS  MATH  Google Scholar 

  • Deutsch D (1989) Quantum computational networks. Proc Roy Soc Lond A 425:73–90

    MathSciNet  ADS  MATH  Google Scholar 

  • Dinur I (2007) The PCP theorem by gap amplification. J ACM 54(3)

    MathSciNet  Google Scholar 

  • Du D-Z, Ko K-I (2000) Theory of Computational Complexity. Wiley, New York

    MATH  Google Scholar 

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

    MathSciNet  MATH  Google Scholar 

  • Feige U, Kilian J (1997) Making games short. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing. ACM Press, New York pp 506–516

    Google Scholar 

  • Feige U, Lovász L (1992) Two-prover one-round proof systems: their power and their problems. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing. ACM Press, New York pp 733–744

    Google Scholar 

  • Fenner S, Fortnow L, Kurtz S (1994) Gap-definable counting classes. J Comput Syst Sci 48:116–148

    MathSciNet  MATH  Google Scholar 

  • Fenner S, Green F Homer S, Zhang Y (2005) Bounds on the power of constant-depth quantum circuits. In: Proceedings of the 15th International Symposium on Fundamentals of Computation Theory. Lect Notes Comput Sci 3623:44–55

    Google Scholar 

  • Feynman R (1983) Simulating physics with computers. Int J Theor Phys 21(6/7):467–488

    MathSciNet  Google Scholar 

  • Fortnow L (1997) Counting complexity. In: Hemaspaandra L, Selman A (eds) Complexity Theory Retrospective II. Springer, New York pp 81–107

    Google Scholar 

  • Fortnow L, Rogers J (1999) Complexity limitations on quantum computation. J Comput Syst Sci 59(2):240–252

    MathSciNet  MATH  Google Scholar 

  • Goldreich O (2005) On promise problems (a survey in memory of Shimon Even [1935–2004]). Electronic Colloquium on Computational Complexity; Report TR05-018

    Google Scholar 

  • Goldreich O, Vadhan S (1999) Comparing entropies in statistical zero-knowledge with applications to the structure of SZK. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity. pp 54–73

    Google Scholar 

  • Goldwasser S, Sipser M (1989) Private coins versus public coins in interactive proof systems. In: Micali S (ed) Randomness and Computation, vol 5 of Advances in Computing Research. JAI Press, Greenwich, Conn pp 73–90

    Google Scholar 

  • Goldwasser S, Micali S, Rackoff C (1985) The knowledge complexity of interactive proof systems. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing. ACM Press, New York pp 291–304

    Google Scholar 

  • Goldwasser S, Micali S, Rackoff C (1989) The knowledge complexity of interactive proof systems. SIAM J Comput 18(1):186–208

    MathSciNet  MATH  Google Scholar 

  • Gutoski G, Watrous J (2007) Toward a general theory of quantum games. In: Proceedings of the 39th ACM Symposium on Theory of Computing. ACM Press, New York pp 565–574

    Google Scholar 

  • Håstad J (2001) Some optimal inapproximability results. J ACM 48(4):798–859

    Google Scholar 

  • Janzing D, Wocjan P, Beth T (2005) Non-identity-check is QMA-complete. Int J Quantum Inf 3(2):463–473

    MATH  Google Scholar 

  • Kaye P, Laflamme R, Mosca M (2007) An introduction to quantum computing. Oxford University Press, Oxford

    MATH  Google Scholar 

  • Kempe J, Kitaev A, Regev O (2006) The complexity of the local Hamiltonian problem. SIAM J Comput 35(5):1070–1097

    MathSciNet  MATH  Google Scholar 

  • Kempe J, Kobayashi H, Matsumoto K, Toner B, Vidick T (2007) Entangled games are hard to approximate. Proceedings ot the 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos 2008

    Google Scholar 

  • Kempe J, Regev O, Toner B (2007) The unique games conjecture with entangled provers is false. Proceedings ot the 49th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos 2008

    Google Scholar 

  • Kitaev A (1997) Quantum computations: algorithms and error correction. Russ Math Surv 52(6):1191–1249

    MathSciNet  MATH  Google Scholar 

  • Kitaev A (1999) Quantum NP. Talk at AQIP'99: Second Workshop on Algorithms in Quantum Information Processing. DePaul University, Chicago

    Google Scholar 

  • Kitaev A, Watrous J (2000) Parallelization, amplification, and exponential time simulation of quantum interactive proof system. In: Proceedings of the 32nd ACM Symposium on Theory of Computing. ACM Press, New York pp 608–617

    Google Scholar 

  • Kitaev A, Shen A, Vyalyi M (2002) Classical and Quantum Computation. Graduate Studies in Mathematics, vol 47. American Mathematical Society, Providence

    Google Scholar 

  • Knill E (1995) Approximation by quantum circuits. Technical Report LAUR-95-2225, Los Alamos National Laboratory. Available as arXiv.org e-Print quant-ph/9508006

    Google Scholar 

  • Knill E (1996) Quantum randomness and nondeterminism. Technical Report LAUR-96-2186, Los Alamos National Laboratory. Available as arXiv.org e-Print quant-ph/9610012

    Google Scholar 

  • Kobayashi H, Matsumoto K (2003) Quantum multi-prover interactive proof systems with limited prior entanglement. J Comput Syst Sci 66(3):429–450

    MathSciNet  MATH  Google Scholar 

  • Kobayashi H, Matsumoto K, Yamakami T (2003) Quantum Merlin–Arthur proof systems: Are multiple Merlins more helpful to Arthur? In: Proceedings of the 14th Annual International Symposium on Algorithms and Computation. Lecture Notes in Computer Science, vol 2906. Springer, Berlin

    Google Scholar 

  • Levin L (1973) Universal search problems. Probl Inf Transm 9(3):265–266 (English translation)

    Google Scholar 

  • Liu Y-K (2006) Consistency of local density matrices is QMA-complete. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Springer, Berlin; Lect Notes Comput Sci 4110:438–449

    Google Scholar 

  • Lloyd S (2000) Ultimate physical limits to computation. Nature 406:1047–1054

    Google Scholar 

  • Lund C, Fortnow L, Karloff H, Nisan N (1992) Algebraic methods for interactive proof systems. J ACM 39(4):859–868

    MathSciNet  MATH  Google Scholar 

  • Marriott C, Watrous J (2005) Quantum Arthur-Merlin games. Comput Complex 14(2):122–152

    MathSciNet  Google Scholar 

  • Moore C, Nilsson M (2002) Parallel quantum computation and quantum codes. SIAM J Comput 31(3):799–815

    MathSciNet  Google Scholar 

  • Moore G (1965) Cramming more components onto integrated circuits. Electron 38(8):82–85

    Google Scholar 

  • Nielsen MA, Chuang IL (2000) Quantum Computation and Quantum Information. Cambridge University Press, Cambride

    MATH  Google Scholar 

  • Nishimura H, Yamakami T (2004) Polynomial time quantum computation with advice. Inf Process Lett 90(4):195–204

    MathSciNet  MATH  Google Scholar 

  • Oliveira R, Terhal B (2005) The complexity of quantum spin systems on a two-dimensional square lattice. Available as arXiv.org e-Print quant-ph/0504050

    Google Scholar 

  • Papadimitriou C (1994) Computational Complexity. Addison-Wesley, Readig, Mass

    MATH  Google Scholar 

  • Raz R (2005) Quantum information and the PCP theorem. In: 46th Annual IEEE Symposium on Foundations of Computer Science. pp 459–468

    Google Scholar 

  • Rosgen B (2008) Distinguishing short quantum computations. Proceedings of the 25th Annual Symposium on theoretical Aspects of Computer Science, IBFI, Schloss Dagstuhl, pp 597–608

    Google Scholar 

  • Rosgen B, Watrous J (2005) On the hardness of distinguishing mixed-state quantum computations. In: Proceedings of the 20th Annual Conference on Computational. pp 344–354

    Google Scholar 

  • Sahai A, Vadhan S (2003) A complete promise problem for statistical zero-knowledge. J ACM 50(2):196–249

    MathSciNet  Google Scholar 

  • Shamir A (1992) IP \( { = } \) PSPACE. J ACM 39(4):869–877

    MathSciNet  MATH  Google Scholar 

  • Shor P (1994) Algorithms for quantum computation: discrete logarithms ande factoring. In: Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science. pp 124–134

    Google Scholar 

  • Shor P (1997) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J Comput 26(5):1484–1509

    MathSciNet  MATH  Google Scholar 

  • Stinespring WF (1955) Positive functions on C *-algebras. Proc Am Math Soc 6(2):211–216

    MathSciNet  MATH  Google Scholar 

  • Toda S (1991) PP is as hard as the polynomial-time hierarchy. SIAM J Comput 20(5):865–887

    MathSciNet  MATH  Google Scholar 

  • Toffoli T (1980) Reversible computing. Technical Report MIT/LCS/TM-151, Laboratory for Computer Science, Massachusetts Institute of Technology

    Google Scholar 

  • Vadhan S (2007) The complexity of zero knowledge. In: 27th International Conference on Foundations of Software Technology and Theoretical Computer Science. Lect Notes Comput Sci 4855:52–70

    MathSciNet  Google Scholar 

  • Valiant L (1979) The complexity of computing the permanent. Theor Comput Sci 8:189–201

    MathSciNet  MATH  Google Scholar 

  • Watrous J (1999) Space-bounded quantum complexity. J Comput Syst Sci 59(2):281–326

    MathSciNet  MATH  Google Scholar 

  • Watrous J (2000) Succinct quantum proofs for properties of finite groups. In: Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science. pp 537–546

    Google Scholar 

  • Watrous J (2002) Limits on the power of quantum statistical zero-knowledge. In: Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. pp 459–468

    Google Scholar 

  • Watrous J (2003) On thecomplexity of simulating space-bounded quantum computations. Comput Complex12:48–84

    MathSciNet  MATH  Google Scholar 

  • Watrous J (2003) PSPACE has constant-round quantum interactive proof systems. Theor Comput Sci 292(3):575–588

    MathSciNet  MATH  Google Scholar 

  • Watrous J (2006) Zero-knowledge against quantum attacks. In: Proceedings of the 38th ACM Symposium on Theory of Computing. ACM Press, New York pp 296–305

    Google Scholar 

  • Wehner S (2006) Entanglement in interactive proof systems with binary answers. In: Proceedings of the 23rd Annual Symposium on Theoretical Aspects of Computer Science. Lect Notes Comput Sci 3884:162–171

    MathSciNet  Google Scholar