2015/07/16 by Ahmed Younes, Jonathan E. Rowe, Younes, Ahmed +1 · 1 voice
Computer Science · #Computability, Logic, AI Algorithms #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1507.05061
openalex publication_date 2015/07/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The aim of the paper is to answer a long-standing open problem on the\nrelationship between NP and BQP. The paper shows that BQP contains NP by\nproposing a BQP quantum algorithm for the MAX-E3-SAT problem which is a\nfundamental NP-hard problem. Given an E3-CNF Boolean formula, the aim of the\nMAX-E3-SAT problem is to find the variable assignment that maximizes the number\nof satisfied clauses. The proposed algorithm runs in O(m2) for an E3-CNF\nBoolean formula with m clauses and in the worst case runs in O(n6) for an\nE3-CNF Boolean formula with n inputs. The proposed algorithm maximizes the\nset of satisfied clauses using a novel iterative partial negation and partial\nmeasurement technique. The algorithm is shown to achieve an arbitrary high\nprobability of success of 1-\ε for small \ε>0 using a\npolynomial resources. In addition to solving the MAX-E3-SAT problem, the\nproposed algorithm can also be used to decide if an E3-CNF Boolean formula is\nsatisfiable or not, which is an NP-complete problem, based on the maximum\nnumber of satisfied clauses.\n