2015/07/16 by Ahmed Younes, Jonathan E. Rowe, Younes, Ahmed +1 · 1 voice · 1 citation
Computer Science · Mathematics · #Algebra over a field #Algorithm #Boolean expression #Boolean function #Boolean satisfiability problem #Bounded function #Combinatorics #Computability, Logic, AI Algorithms #Computer science #Discrete mathematics #Mathematics #Maximum satisfiability problem #Product term #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Time complexity #True quantified Boolean formula #Two-element Boolean algebra #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1507.05061
published in arXiv (Cornell University) (Cornell University) · 15 pages, 5 figures. arXiv admin note: text overlap with arXiv:1505.06284
openalex publication_date 2015/07/16 · arxiv created 2015/07/27 · arxiv updated 2015/07/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/04
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