Quantum computing, postselection, and probabilistic polynomial-time

被引:151
作者
Aaronson, S [1 ]
机构
[1] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON N2L 3G1, Canada
来源
PROCEEDINGS OF THE ROYAL SOCIETY A-MATHEMATICAL PHYSICAL AND ENGINEERING SCIENCES | 2005年 / 461卷 / 2063期
关键词
quantum computers; computational complexity; Born's rule;
D O I
10.1098/rspa.2005.1546
中图分类号
O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];
学科分类号
07 ; 0710 ; 09 ;
摘要
I study the class of problems efficiently solvable by a quantum computer, given the ability to 'postselect' on the outcomes of measurements. I prove that this class coincides with a classical complexity class called PP, or probabilistic polynomial-time. Using this result, I show that several simple changes to the axioms of quantum mechanics would let us Solve PP-complete problems efficiently. The result also implies, as an easy corollary, a celebrated theorem of Beigel, Reingold and Spielman that PP is closed under intersection, as well as a generalization of that theorem due to Fortnow and Reingold. This illustrates that quantum computing can yield new and simpler proofs of major results about classical computation.
引用
收藏
页码:3473 / 3482
页数:10
相关论文
共 34 条
[1]  
AARONSON S, 2004, P VAXJ C QUANT THEOR
[2]  
AARONSON S, 2004, P 36 ANN ACM S THEOR, P465
[3]  
Aaronson S., 2005, Theory of Computing, V1, P1
[4]  
AARONSON S, 2005, THESIS U CALIFORNIA
[5]   Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems [J].
Abrams, DS ;
Lloyd, S .
PHYSICAL REVIEW LETTERS, 1998, 81 (18) :3992-3995
[6]   Quantum computability [J].
Adleman, LM ;
Demarrais, J ;
Huang, MDA .
SIAM JOURNAL ON COMPUTING, 1997, 26 (05) :1524-1540
[7]   PRIMES is in P [J].
Agrawal, M ;
Kayal, N ;
Saxena, N .
ANNALS OF MATHEMATICS, 2004, 160 (02) :781-793
[8]   Lattice problems in NP∧coNP [J].
Aharonov, D ;
Regev, O .
45TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2004, :362-371
[9]  
AHARONOV D, 2002, QUANTUM NP SURVEY
[10]   PP IS CLOSED UNDER INTERSECTION [J].
BEIGEL, R ;
REINGOLD, N ;
SPIELMAN, D .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1995, 50 (02) :191-202