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

Bulletin of the American Physical Society

Quantum Algorithm for Solving an NP-Complete Problem

Hefeng Wang, Fuli Li

Published Jun 21, 2012• 0 citations
OpenAlex

Abstract

When a probe qubit is coupled to a quantum register that represents a physical system, the probe qubit will exhibit a dynamical response only when it is resonant with a transition in the system. Using this principle, we propose a quantum algorithm for solving discrete mathematical problems based on the circuit model. Our algorithm has favorable scaling properties in solving some discrete mathematical problems.

Related papers

Quantum algorithm for solving some discrete mathematical problems by probing their energy spectra

Hefeng Wang, Heng Fan, Fuli Li

When a probe qubit is coupled to a quantum register that represents a physical system, the probe qubit will exhibit a dynamical response only when it is resonant with a transition in the system. Using this principle, we propose a quantum algorithm for solving discrete mathematical problems based on the circuit model. Our algorithm has favorable scaling properties in solving some discrete mathematical problems.

arXiv:1206.4747•Physical Review A•Jan 6, 2014•3 citations

Quantum algorithm for obtaining the eigenstates of a physical system

Hefeng Wang

We propose a quantum algorithm for solving the following problem: given the Hamiltonian of a physical system and one of its eigenvalues, how do we obtain the corresponding eigenstate? The algorithm is based on the resonance phenomenon. For a probe qubit coupled to a quantum system, the system exhibits resonance dynamics when the frequency of the probe qubit matches a transition frequency in the system. Therefore the system can be guided to evolve to the eigenstate with a known eigenvalue by inducing the resonance between the probe qubit and a designed transition in the system. This algorithm can also be used to obtain the energy spectrum of a physical system and can achieve even quadratic speedup over the phase estimation algorithm.

arXiv:1510.00820•Physical Review A•May 25, 2016•20 citations

New quantum algorithm for studying NP-complete problems

Masanori Ohya, Igor Vasil'evich Volovich

Ordinary approach to quantum algorithm is based on quantum Turing machine or quantum circuits. It is known that this approach is not powerful enough to solve NP-complete problems. In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm. keywords: Quantum Algorithm, NP-complete problem, Chaotic Dynamics 1

•Jan 1, 2003•37 citations

A Quantum Computing Based Solution Approach for NP-Complete Problems

Seda Nur Gungor, Mehmet Karaköse

Although NP-complete problems have solutions that can be verified in polynomial time, their exponential computational complexity presents significant challenges for classical computing methods. This study focuses on transferring various NP-complete problems into the quantum computing framework. The application of specific quantum computing algorithms is proposed for solving these problems. Within the scope of this study, a reusable quantum component with problem-specific constraints is designed, and a quantum circuit model is introduced to adapt the Quantum Feasibility Labeling algorithm for solving the Maximum Clique problem. Additionally, the Quick Quantum Search algorithm, which performs a search with a single oracle call, is integrated into the solution of the Maximum Independent Set problem. The proposed quantum circuits provide illustrative examples of how the components of an NP-complete problem can be represented in a quantum computing environment and how problem-specific constraints can be implemented within a quantum circuit. The utilization of modular circuit designs effectively demonstrates the applicability of larger and more complex problems in quantum environments. These approaches not only enable more efficient use of computational resources compared to traditional methods but also lead to significant reductions in solution times. This study provides a comprehensive framework that not only demonstrates the practicality of quantum circuits for small-scale NP-complete problems but also lays the groundwork for addressing larger and more complex challenges in future quantum computing applications.

•Feb 19, 2025•4 citations

A quantum algorithm for obtaining the energy spectrum of a physical system without guessing its eigenstates

Hefeng Wang

We present a quantum algorithm that provides a general approach for obtaining the energy spectrum of a physical system without making a guess on its eigenstates. In this algorithm, a probe qubit is coupled to a quantum register R which consists of one ancilla qubit and an n-qubit register that represents the system. R is prepared in a general reference state, and a general excitation operator that acts on R is constructed. The probe exhibits a dynamical response only when it is resonant with a transition from the reference state to an excited state of R which contains the eigenstates of the system. By varying the probe's frequency, the energy spectrum and the eigenstates of the system can be obtained.

arXiv:1306.6732•Physical Chemistry Chemical Physics•Jan 1, 2014•3 citations

A New Quantum Algorithm for NP-complete Problems

Makoto Ohya, Masanori Ohya, Igor V. Volovich

An approach to the solution of NP-complete problems based on quantum computing and chaotic dynamics is proposed. We consider the satisfiability problem and argue that the problem, in principle, can be solved in polynomial time if we combine the quantum computer with the chaotic dynamics amplifier based on the logistic map.

•Jan 1, 2002•1 citation
When a probe qubit is coupled to a quantum register that represents a physical system, the probe qubit will exhibit a dynamical response only when it is resonant with a transition in the system. Using this principle, we propose a quantum algorithm for solving discrete mathematical problems based on the circuit model. Our algorithm has favorable scaling properties in solving some discrete mathematical problems.
We propose a quantum algorithm for solving the following problem: given the Hamiltonian of a physical system and one of its eigenvalues, how do we obtain the corresponding eigenstate? The algorithm is based on the resonance phenomenon. For a probe qubit coupled to a quantum system, the system exhibits resonance dynamics when the frequency of the probe qubit matches a transition frequency in the system. Therefore the system can be guided to evolve to the eigenstate with a known eigenvalue by inducing the resonance between the probe qubit and a designed transition in the system. This algorithm can also be used to obtain the energy spectrum of a physical system and can achieve even quadratic speedup over the phase estimation algorithm.
Ordinary approach to quantum algorithm is based on quantum Turing machine or quantum circuits. It is known that this approach is not powerful enough to solve NP-complete problems. In this paper we study a new approach to quantum algorithm which is a combination of the ordinary quantum algorithm with a chaotic dynamical system. We consider the satisfiability problem as an example of NP-complete problems and argue that the problem, in principle, can be solved in polynomial time by using our new quantum algorithm. keywords: Quantum Algorithm, NP-complete problem, Chaotic Dynamics 1
Although NP-complete problems have solutions that can be verified in polynomial time, their exponential computational complexity presents significant challenges for classical computing methods. This study focuses on transferring various NP-complete problems into the quantum computing framework. The application of specific quantum computing algorithms is proposed for solving these problems. Within the scope of this study, a reusable quantum component with problem-specific constraints is designed, and a quantum circuit model is introduced to adapt the Quantum Feasibility Labeling algorithm for solving the Maximum Clique problem. Additionally, the Quick Quantum Search algorithm, which performs a search with a single oracle call, is integrated into the solution of the Maximum Independent Set problem. The proposed quantum circuits provide illustrative examples of how the components of an NP-complete problem can be represented in a quantum computing environment and how problem-specific constraints can be implemented within a quantum circuit. The utilization of modular circuit designs effectively demonstrates the applicability of larger and more complex problems in quantum environments. These approaches not only enable more efficient use of computational resources compared to traditional methods but also lead to significant reductions in solution times. This study provides a comprehensive framework that not only demonstrates the practicality of quantum circuits for small-scale NP-complete problems but also lays the groundwork for addressing larger and more complex challenges in future quantum computing applications.
We present a quantum algorithm that provides a general approach for obtaining the energy spectrum of a physical system without making a guess on its eigenstates. In this algorithm, a probe qubit is coupled to a quantum register R which consists of one ancilla qubit and an n-qubit register that represents the system. R is prepared in a general reference state, and a general excitation operator that acts on R is constructed. The probe exhibits a dynamical response only when it is resonant with a transition from the reference state to an excited state of R which contains the eigenstates of the system. By varying the probe's frequency, the energy spectrum and the eigenstates of the system can be obtained.