The space ``just above BQP

DOI10.1145/2840728.2840739zbMATH Open1334.68075arXiv1412.6507OpenAlexW1575325906MaRDI QIDQ2800575FDOQ2800575

Adam Bouland, Mitchell Lee, Scott Aaronson, Joseph Fitzsimons

Publication date: 15 April 2016

Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Abstract: We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the wavefunction. This (non-physical) model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in $ildeO$(N^{1/3}) time, but no faster than {Omega}(N^{1/4}), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. Our work is inspired by previous work of Aaronson on the power of sampling the histories of hidden variables. However Aaronson's work contains an error in its proof of the lower bound for search, and hence it is unclear whether or not his model allows for search in logarithmic time. Our work can be viewed as a conceptual simplification of Aaronson's approach, with a provable polynomial lower bound for search.

Full work available at URL: https://arxiv.org/abs/1412.6507

zbMATH Keywords

lower boundquantum computingBQPoracle separationstatistical zero knowledge

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cited In (3)

• Oracles and query lower bounds in generalised probabilistic theories
• Deriving Grover's lower bound from simple physical principles
• On the Power of Statistical Zero Knowledge

This page was built for publication: The space ``just above BQP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2800575)