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

Physical Review A

Quantum computers and intractable (NP-complete) computing problems

V. Černý

Published Jul 1, 1993• 38 citations
Publisher

Abstract

In this paper we discuss physical aspects of intractable (NP-complete) computing problems. We show, using a specific model, that a quantum-mechanical computer can in principle solve an NP-complete problem in polynomial time; however, it would use an exponentially large energy for that computation. We conjecture that our model reflects a complementarity principle concerning the time and the energy needed to perform an NP-complete computation.

DOI
10.1103/physreva.48.116

Related papers

Copying quantum computer makes NP-complete problems tractable.

Mika Hirvensalo

Under the assumption that a quantum computer can exactly copy quantum superpositions, we show that NP-complete problems can be solved probabilistically in polynomial time. We also propose two methods that could potentially allow to avoid the use of a quantum copymachine. Supported by the Academy of Finland under grant 14047. To be presented at MCU'98, March 1998, Metz, France. TUCS Research Group Theory Group: Mathematical Methods in Computer Science 1 Introduction It was conjectured by R. Feynman [5] in 1982 that it may be impossible to simulate quantum physical phenomena by an ordinary computer without an exponential slowdown in the efficiency of the simulation. In his work, Feynman also suggested that the slowdown could be avoided by allowing the computer run according to rules of quantum mechanics, thus introducing the idea of quantum computer. However, quantum computation remained quite a marginal phenomenon in the theory of computing until 1994, when Peter W. Shor discovered ...

Machines, Computations, and Universality•Jan 1, 1998•1 citation

P/NP , and the quantum field computer

Michael Hartley Freedman

The central problem in computer science is the conjecture that two complexity classes, P (polynomial time) and NP (nondeterministic polynomial time-roughly those decision problems for which a proposed solution can be checked in polynomial time), are distinct in the standard Turing model of computation: P not equal NP. As a generality, we propose that each physical theory supports computational models whose power is limited by the physical theory. It is well known that classical physics supports a multitude of implementation of the Turing machine. Non-Abelian topological quantum field theories exhibit the mathematical features necessary to support a model capable of solving all #P problems, a computationally intractable class, in polynomial time. Specifically, Witten [Witten, E. (1989) Commun. Math. Phys. 121, 351-391] has identified expectation values in a certain SU(2)-field theory with values of the Jones polynomial [Jones, V. (1985) Bull. Am. Math. Soc. 12, 103-111] that are #P-hard [Jaeger, F., Vertigen, D. & Welsh, D. (1990) Math. Proc. Comb. Philos. Soc. 108, 35-53]. This suggests that some physical system whose effective Lagrangian contains a non-Abelian topological term might be manipulated to serve as an analog computer capable of solving NP or even #P-hard problems in polynomial time. Defining such a system and addressing the accuracy issues inherent in preparation and measurement is a major unsolved problem.

Proceedings of the National Academy of Sciences•Jan 6, 1998•222 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

NP-complete Problems and Physical Reality

Scott Aaronson

Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and "anthropic computing." The section on soap bubbles even includes some "experimental" results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.

arXiv:quant-ph/0502072•Feb 12, 2005•153 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

Quantum simulated annealing

Steve Huntsman

The question of whether or not quantum computers can efficiently solve NP-complete problems is open, although indications are that BQP does not contain NP. Still, many of these problems are natural candidates for solution on quantum computers. We outline a thermodynamical formalism for the traveling salesman problem which allows for its expected polytime solution on a quantum computer with probability arbitrarily close to unity, given sufficient energy resources and subject to a weak nondegeneracy constraint on the distances. Applications to other problems are also discussed.

arXiv:quant-ph/0012112•Dec 20, 2000•1 citation
In this paper we discuss physical aspects of intractable (NP-complete) computing problems. We show, using a specific model, that a quantum-mechanical computer can in principle solve an NP-complete problem in polynomial time; however, it would use an exponentially large energy for that computation. We conjecture that our model reflects a complementarity principle concerning the time and the energy needed to perform an NP-complete computation.
Under the assumption that a quantum computer can exactly copy quantum superpositions, we show that NP-complete problems can be solved probabilistically in polynomial time. We also propose two methods that could potentially allow to avoid the use of a quantum copymachine. Supported by the Academy of Finland under grant 14047. To be presented at MCU'98, March 1998, Metz, France. TUCS Research Group Theory Group: Mathematical Methods in Computer Science 1 Introduction It was conjectured by R. Feynman [5] in 1982 that it may be impossible to simulate quantum physical phenomena by an ordinary computer without an exponential slowdown in the efficiency of the simulation. In his work, Feynman also suggested that the slowdown could be avoided by allowing the computer run according to rules of quantum mechanics, thus introducing the idea of quantum computer. However, quantum computation remained quite a marginal phenomenon in the theory of computing until 1994, when Peter W. Shor discovered ...
The central problem in computer science is the conjecture that two complexity classes, P (polynomial time) and NP (nondeterministic polynomial time-roughly those decision problems for which a proposed solution can be checked in polynomial time), are distinct in the standard Turing model of computation: P not equal NP. As a generality, we propose that each physical theory supports computational models whose power is limited by the physical theory. It is well known that classical physics supports a multitude of implementation of the Turing machine. Non-Abelian topological quantum field theories exhibit the mathematical features necessary to support a model capable of solving all #P problems, a computationally intractable class, in polynomial time. Specifically, Witten [Witten, E. (1989) Commun. Math. Phys. 121, 351-391] has identified expectation values in a certain SU(2)-field theory with values of the Jones polynomial [Jones, V. (1985) Bull. Am. Math. Soc. 12, 103-111] that are #P-hard [Jaeger, F., Vertigen, D. & Welsh, D. (1990) Math. Proc. Comb. Philos. Soc. 108, 35-53]. This suggests that some physical system whose effective Lagrangian contains a non-Abelian topological term might be manipulated to serve as an analog computer capable of solving NP or even #P-hard problems in polynomial time. Defining such a system and addressing the accuracy issues inherent in preparation and measurement is a major unsolved problem.
Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and "anthropic computing." The section on soap bubbles even includes some "experimental" results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics.
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.
The question of whether or not quantum computers can efficiently solve NP-complete problems is open, although indications are that BQP does not contain NP. Still, many of these problems are natural candidates for solution on quantum computers. We outline a thermodynamical formalism for the traveling salesman problem which allows for its expected polytime solution on a quantum computer with probability arbitrarily close to unity, given sufficient energy resources and subject to a weak nondegeneracy constraint on the distances. Applications to other problems are also discussed.