This paper proves that BQP (Bounded-error Quantum Polynomial time) does not contain NP, using the TTCC language introduced in Work XIII (DOI: 10.5281/zenodo.20726838) and the topological obstacle o(L) established in Work XII (DOI: 10.5281/zenodo.20726572). The proof proceeds through four lemmas. Lemma 1: homology groups are invariant under triangulation. Lemma 2: computing Betti numbers of simplicial complexes is QMA1-hard (Cade, Crichigno et al., 2022). Lemma 3: the obstacle o(L) for NP problems is QMA1-hard via Lemma 1. Lemma 4: no quantum algorithm computes o(L) in polynomial time. The main theorem follows by contraposition. This result completes a trilogy: neither classical (Work XII) nor quantum (Work XIV) computers can overcome the topological obstacle for NP problems. Practical implications include the security of post-quantum cryptography based on NP-hard problems against quantum attacks.
This paper proves that BQP (Bounded-error Quantum Polynomial time) does not contain NP, using the TTCC language introduced in Work XIII (DOI: 10.5281/zenodo.20726838) and the topological obstacle o(L) established in Work XII (DOI: 10.5281/zenodo.20726572). The proof proceeds through four lemmas. Lemma 1: homology groups are invariant under triangulation. Lemma 2: computing Betti numbers of simplicial complexes is QMA1-hard (Cade, Crichigno et al., 2022). Lemma 3: the obstacle o(L) for NP problems is QMA1-hard via Lemma 1. Lemma 4: no quantum algorithm computes o(L) in polynomial time. The main theorem follows by contraposition. This result completes a trilogy: neither classical (Work XII) nor quantum (Work XIV) computers can overcome the topological obstacle for NP problems. Practical implications include the security of post-quantum cryptography based on NP-hard problems against quantum attacks.
Quantum computers are widely believed have an advantage over classical computers, and some have even published some empirical evidence that this is the case. However, these publications do not include a rigorous proof of this advantage, which would have to minimally state that the class of problems decidable by a quantum computer in polynomial time, BQP, contains problems that are not in the class of problems decidable by a classical computer with similar time bounds, P. Here, I provide the proof of a stronger result that implies this result: BQP contains problems that lie beyond the much larger classical computing class NP. This proves that quantum computation is able to efficiently solve problems which are far beyond the capabilities of classical computers.
A celebrated important result due to Freedman et al (2002 Commun. Math. Phys. 227 605–22) states that providing additive approximations of the Jones polynomial at the k th root of unity, for constant k =5 and k ⩾7, is BQP-hard. Together with the algorithmic results of Aharonov et al (2005) and Freedman et al (2002 Commun. Math. Phys. 227 587–603), this gives perhaps the most natural BQP-complete problem known today and motivates further study of the topic. In this paper, we focus on the universality proof; we extend the result of Freedman et al (2002) to k s that grow polynomially with the number of strands and crossings in the link, thus extending the BQP-hardness of Jones polynomial approximations to all values to which the AJL algorithm applies (Aharonov et al 2005), proving that for all those values, the problems are BQP-complete. As a side benefit, we derive a fairly elementary proof of the Freedman et al density result, without referring to advanced results from Lie algebra representation theory, making this important result accessible to a wider audience in the computer science research community. We make use of two general lemmas we prove, the bridge lemma and the decoupling lemma , which provide tools for establishing the density of subgroups in SU( n ). Those tools seem to be of independent interest in more general contexts of proving the quantum universality. Our result also implies a completely classical statement, that the multiplicative approximations of the Jones polynomial, at exactly the same values, are #P-hard, via a recent result due to Kuperberg (2009 arXiv:0908.0512). Since the first publication of those results in their preliminary form (Aharonov and Arad 2006 arXiv:quant-ph/0605181), the methods we present here have been used in several other contexts (Aharonov and Arad 2007 arXiv:quant-ph/0702008; Peter and Stephen 2008 Quantum Inf. Comput. 8 681). The present paper is an improved and extended version of the results presented by Aharonov and Arad (2006) and includes discussions of the developments since then.
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 O~(N^{1/3}) time, but no faster than Ω(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.
I will discuss the now-ancient question of where BQP, Bounded-Error Quantum Polynomial-Time, fits in among classical complexity classes. After reviewing some basics from the 90s, I will discuss the Forrelation problem that I introduced in 2009 to yield an oracle separation between BQP and PH, and the dramatic completion of that program by Ran Raz and Avishay Tal in 2018. I will then discuss very recent work, with William Kretschmer and DeVon Ingram, which leverages the Raz-Tal theorem, along with a new "quantum-aware" random restriction method, to obtain results that illustrate just how differently BQP can behave from BPP. These include oracles relative to which NP^{BQP} ̸ ⊂ BQP^{PH} - solving a 2005 open problem of Lance Fortnow - and conversely, relative to which BQP^{NP} ̸ ⊂ PH^{BQP}; an oracle relative to which 𝖯 = NP and yet BQP ≠ QCMA; an oracle relative to which NP ⊆ BQP yet PH is infinite; an oracle relative to which 𝖯 = NP≠ BQP = PP; and an oracle relative to which PP = PostBQP ̸ ⊂ QMA^{QMA^{…}}. By popular demand, I will also speculate about the status of BQP in the unrelativized world.
We explore the space "just above" BQP by defining a complexity class naCQP (non-adaptive Collapse-free 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 (non-adaptive) 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 Õ(N1/3) time, but no faster than Ω(N1/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. This is surprising as most modifications of BQP increase the power of quantum computation to NP or beyond.
The aim of the paper is to answer a long-standing open problem on the relationship between NP and BQP. The paper shows that BQP contains NP by proposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a fundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the MAX-E3-SAT problem is to find the variable assignment that maximizes the number of satisfied clauses. The proposed algorithm runs in O(m2) for an E3-CNF Boolean formula with m clauses and in the worst case runs in O(n6) for an E3-CNF Boolean formula with n inputs. The proposed algorithm maximizes the set of satisfied clauses using a novel iterative partial negation and partial measurement technique. The algorithm is shown to achieve an arbitrary high probability of success of 1−ε for small ε>0 using a polynomial resources. In addition to solving the MAX-E3-SAT problem, the proposed algorithm can also be used to decide if an E3-CNF Boolean formula is satisfiable or not, which is an NP-complete problem, based on the maximum number of satisfied clauses.