Solving NP-Complete Problems with Quantum Search

DOI10.1007/978-3-540-78773-0_67MaRDI QIDQ5458579zbMATH OpenOpenAlexFDO

Authors Martin Fürer

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

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

Recommendations

• scientific article; zbMATH DE number 1285153
• scientific article; zbMATH DE number 1555956
• Quantum computation and NP-complete problems
• Nested quantum search and NP-hard problems
• scientific article; zbMATH DE number 1530002
• New quantum algorithm solving the NP complete problem
• New quantum algorithm for studying NP-complete problems
• scientific article; zbMATH DE number 1406118
• Quantum search on structured problems
• Quantum advantage in deciding NP-complete problems

Cites work

• A Computing Procedure for Quantification Theory
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.
• A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs
• A machine program for theorem-proving
• Algorithms for Sat and upper bounds on their complexity
• Counting models for 2SAT and 3SAT formulae
• Exact Max 2-Sat: Easier and Faster
• Finding a Maximum Independent Set
• scientific article; zbMATH DE number 1305487 (Why is no real title available?)
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• scientific article; zbMATH DE number 1775388 (Why is no real title available?)
• scientific article; zbMATH DE number 1796835 (Why is no real title available?)
• scientific article; zbMATH DE number 1929929 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction.
• New methods for 3-SAT decision and worst-case analysis
• Rapid sampling though quantum computing

Cited in

(22)

• Nested quantum search and NP-hard problems
• New quantum algorithm solving the NP complete problem
• The Sturm-Liouville eigenvalue problem and NP-complete problems in the quantum setting with queries
• An \(R||C_{\max}\) quantum scheduling algorithm
• Quantum advantage in deciding NP-complete problems
• Quantum computation and NP-complete problems
• Different adiabatic quantum optimization algorithms for the NP-complete exact cover and 3SAT problems
• The road to quantum computational supremacy
• A Quantum Algorithm for Finding a Hamilton Circuit
• scientific article; zbMATH DE number 1285153 (Why is no real title available?)
• Strengths and Weaknesses of Quantum Computing
• scientific article; zbMATH DE number 2013817 (Why is no real title available?)
• scientific article; zbMATH DE number 1530002 (Why is no real title available?)
• Quantum-walk speedup of backtracking algorithms
• A Stochastic Limit Approach to the SAT Problem
• A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing
• Quantum speedups for exponential-time dynamic programming algorithms
• Exponential-time quantum algorithms for graph coloring problems
• Non-Boolean quantum amplitude amplification and quantum mean estimation
• Quantum algorithms for graph coloring and other partitioning, covering, and packing problems
• Using quantum switches to mitigate noise in Grover's search algorithm
• Quantum cooperative search algorithm for 3-sat

This page was built for publication: Solving NP-Complete Problems with Quantum Search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458579)