2011/06/03 by Joseph Bebel, Henry Yuen, Bebel, Joseph +1
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.1106.0572
This paper has been withdrawn by the authors due to the fact that strong error reduction for BQP_p problems is significantly more subtle than demonstrated, which compromises the main result
openalex publication_date 2011/06/03 · arxiv created 2011/06/22 · arxiv updated 2011/06/23 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
There's something really strange about quantum mechanics. It's not just that cats can be dead and alive at the same time, and that entanglement seems to violate the principle of locality; quantum mechanics seems to be what Aaronson calls "an island in theoryspace", because even slight perturbations to the theory of quantum mechanics seem to generate absurdities. In [Aar 04] and [Aar 05], he explores these perturbations and the corresponding absurdities in the context of computation. In particular, he shows that a quantum theory where the measurement probabilities are computed using p-norm instead of the standard 2-norm has the effect of blowing up the class BQP (the class of problems that can be efficiently solved on a quantum computer) to at least PP (the class of problems that can be solved in probabilistic polynomial time). He showed that PP ⊆ BQPp ⊆ PSPACE for all constants p != 2, and that BQPp = PP for even integers p > 2. Here, we show that this equality holds for all integers p > 2.