aqora

PDQP/qpoly=ALL

Scott Aaronson

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.

Quantum Information and ComputationSep 1, 20183 citations

Theory of Quantum Computing and its Analog of the Haltingproblem. Extensions of Logic to Nondeterminism, Decidability,And Nonexistence

Andrii Hopanchuk

Jan 1, 20250 citations

Measurement-Based Quantum Computation and Undecidable Logic

Maarten Van den Nest, Hans J. Briegel

arXiv:quant-ph/0610040Foundations of PhysicsMar 13, 200817 citations

PDQP/qpoly = ALL

Scott Aaronson

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.

May 22, 20181 citation

Decision Diagrams for Quantum Computing

Robert Wille, Stefan Hillmich, Lukas Burgholzer

arXiv:2302.04687Springer eBooksAug 13, 202222 citations

PDQP/qpoly = ALL.

Scott Aaronson

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.

Electronic colloquium on computational complexityJan 1, 20180 citations

PDQP/qpoly = All

Abstract

Related papers

PDQP/qpoly = All

Abstract

Related papers