Solving NP-Complete Problems with Quantum Search

DOI10.1007/978-3-540-78773-0_67zbMath1136.68519OpenAlexW1727475799MaRDI QIDQ5458579

Martin Fuerer

Publication date: 15 April 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-78773-0_67

Mathematics Subject Classification ID

Quantum computation (81P68) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Non-Boolean quantum amplitude amplification and quantum mean estimation ⋮ The Road to Quantum Computational Supremacy ⋮ A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing ⋮ Unnamed Item ⋮ Exponential-time quantum algorithms for graph coloring problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Counting models for 2SAT and 3SAT formulae
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• New methods for 3-SAT decision and worst-case analysis
• Algorithms for Sat and upper bounds on their complexity
• Rapid sampling though quantum computing
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• Finding a Maximum Independent Set
• Exact Max 2-Sat: Easier and Faster
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving