2018/05/22 by Scott Aaronson, Aaronson, Scott
Medicine · #Chronic Myeloid Leukemia Treatments #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.1805.08577
openalex publication_date 2018/05/22 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
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.