Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Applicable Algebra in Engineering Communication and Computing

Nested Quantum Search and NP-Hard Problems

Nicolas J. Cerf, Lov K. Grover, Colin P. Williams

Published May 1, 2000• 21 citations
Publisher
DOI
10.1007/s002000050134

Related papers

Experimental study on Quantum heuristic search in an NP-hard problem

Mohamed El-fiky, Satoshi Ono, Shigeru Nakayama

•Jan 1, 2008•0 citations

Solving NP-Complete Problems with Quantum Search

Martin Fürer

Springer eBooks•Apr 3, 2008•20 citations

Topological Dynamics and Quantum Spatial Interference (QSI) for NP-Hard Problems

Ahmed Salemkour

"We introduce a continuous topological framework for NP-hard problems using Quantum Spatial Interference (QSI) and energy-based dynamics. The model replaces discrete combinatorial search with continuous geometric evolution."

•Apr 3, 2026•0 citations

Solving Chromatic Number with Quantum Search and Quantum Counting

David Lutze

This thesis presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2n/2n2(log2n)2). This is an improvement over the best known algorithm, with a run time of 2nnO(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can be framed as NP-Hard problems, so any speed-up in the solution of these problems is highly sought after. A bulk of this thesis consists of a review of the underlying principles of quantum mechanics and quantum computing, building to the Quantum Search and Quantum Counting algorithms. The review is written with the assumption that the reader has no prior knowledge on quantum computing. This culminates with a presentation of algorithms for generating the quantum circuits required to solve K-Coloring and Chromatic Number.

•Jun 1, 2021•3 citations

Quantum Computation and NP-Complete Problems

Tetsuro Nishino

•Jul 1, 2000•0 citations

Quantum computation and NP-complete problems

Takashi Mihara, Tetsuro Nishino

Lecture notes in computer science•Jan 1, 1994•1 citation
This thesis presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2n/2n2(log2n)2). This is an improvement over the best known algorithm, with a run time of 2nnO(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can be framed as NP-Hard problems, so any speed-up in the solution of these problems is highly sought after. A bulk of this thesis consists of a review of the underlying principles of quantum mechanics and quantum computing, building to the Quantum Search and Quantum Counting algorithms. The review is written with the assumption that the reader has no prior knowledge on quantum computing. This culminates with a presentation of algorithms for generating the quantum circuits required to solve K-Coloring and Chromatic Number.