Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR18-099 | 19th May 2018 04:08

PDQP/qpoly = ALL

RSS-Feed




TR18-099
Authors: Scott Aaronson
Publication: 19th May 2018 04:08
Downloads: 954
Keywords: 


Abstract:

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable codes.



ISSN 1433-8092 | Imprint