Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems

DOI10.1088/1367-2630/18/7/073003zbMath1456.81147arXiv1512.00859OpenAlexW3101715799MaRDI QIDQ5855059

G. G. Guerreschi, Salvatore Mandrà, Alán Aspuru-Guzik

Publication date: 12 March 2021

Published in: New Journal of Physics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum gates (81P65)

Related Items (1)

Quantum branch-and-bound algorithm and its application to the travelling salesman problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Quantum pattern matching fast on average
• Algorithms for four variants of the exact satisfiability problem
• The complexity of computing the permanent
• New algorithms for exact satisfiability
• Exact 3-satisfiability is decidable in time \(O(2^{0.16254 n})\)
• An upper bound \(O(2^{0.16254n})\) for exact 3-satisfiability: a simpler proof
• On the hardness of approximate reasoning
• The Worst-Case Upper Bound for Exact 3-Satisfiability with the Number of Clauses as the Parameter
• NEW WORST-CASE UPPER BOUND FOR COUNTING EXACT SATISFIABILITY
• Search via Quantum Walk
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• A Dynamic Programming Approach to Sequencing Problems
• Properties of sparse random matrices over finite fields
• Exponential algorithmic speedup by a quantum walk
• An Improved Exact Algorithm for Cubic Graph TSP
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Reducibility among Combinatorial Problems
• The Traveling Salesman Problem for Cubic Graphs
• Gibbs states and the set of solutions of random constraint satisfaction problems
• The complexity of satisfiability problems
• The computational complexity of linear optics
• Quantum Walk Algorithm for Element Distinctness
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving

This page was built for publication: Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems