DOI: 10.14704/nq.2014.12.4.789

The P versus NP Problem in Quantum Physics

Daegene Song


Motivated by the fact that information is encoded and processed by physical systems, the P versus NP problem is examined in terms of physical processes. In particular, we consider P as a class of deterministic, and NP as nondeterministic, polynomial-time physical processes. Based on these identifications, we review a self-reference physical process in quantum theory, which belongs to NP but cannot be contained in P.


NP problem; polynomial

Full Text:

Full Text PDF


Goldreich O. Computational complexity: a conceptual perspective, Cambridge University Press, 2008.

Cook S. The complexity of theorem proving procedures, Proceedings Third Annual ACM Symposium on Theory of Computing, 1971; p.151.

Fortnow F. The status of the P versus NP problem, Comm. ACM 2009; 52: 78.

Landauer R. Information is physical. Phys Tod 1991; May, 23.

Landauer R. Physical nature of information, Phy Lett A 1996; 217: 188.

Deutsch D, Ekert A and Lupacchini R. Machines, logic and quantum physics. Bull Symbolic Logic 2000; 6 (3): 265.

Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer. Proc R Soc London A 1985; 400: 97.

Bell JS. On the Einstein-Podolsky-Rosen paradox. Physics 1964; 1, 195.

Bennett CH and Brassard G. Quantum cryptography: public key distribution and coin tossing, Proceedings of IEEE International Conference on Computers, Systems and Signal Processing, Bangalore, India, December, 1984; p.175.

Ekert AK. Quantum cryptography based on Bell's theorem. Phys Rev Lett 1991; 67: 661.

Deutsch D and Jozsa R. Rapid solution of problems by quantum computation. Proc R Soc Lond A 1992; 439: 553.

Shor P. Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings of the 35th Annual Symposium on the Foundations of Computer Science, edited by S. Goldwasser (IEEE Computer Society, Los Alamitos, CA), 1996; p.124. arXiv:quant-ph/9508027.

Grover LK. Quantum mechanics helps in searching for a needle in a haystack. Phys Rev Lett 1997; 79: 325; arXiv:quant-ph/9706033.

Bennett CH, Bernstein E, Brassard G and Vazirani U. Strengths and weaknesses of quantum computing, SIAM J Comp 1997; 26: 1510. arXiv:quant-ph/9701001.

Vazirani U. A survey of quantum complexity theory. Proc Sympos Appl Math 2002; 58.

Tusarova T. Quantum complexity classes. arXiv:cs/0409051 [cs.CC].

Aaronson S. NP-complete problems and physical reality, ACM SIGACT News Complexity Theory Column, March. ECCC TR05-026. 2005. arXiv:quant-ph/0502072.

Church A. An unsolvable problem in elementary number theory. Am J Math 1936; 58: 345.

Turing AM. On computable numbers, with an application to the Entscheidungsproblem. Proc London Math Soc 1936; (2) 442: 230.

Yao A. Quantum circuit complexity, Proceedings 34th Annual Symposium on Foundations of Computer Science (FOCS) 1993; 352.

Ekert AK and Jozsa R. Quantum computation and Shor's factoring algorithm. Rev Mod Phys 1996; 68: 733.

Gottesman D. The Heisenberg representation of quantum computers. 1998. arXiv:quant-ph/9807006v1.

Deutsch D and Hayden P. Information flow in entangled quantum systems. Proc R Soc Lond A 1999; 456: 1759. arXiv:quant-ph/9906007.

Hewitt-Horsman C and Vedral V. Developing the Deutsch-Hayden approach to quantum mechanics. New J Phys 2007; 9: 135. arXiv:quant-ph/0609085.

Song D. Non-computability of consciousness. NeuroQuantology 2007; 5: 382. arXiv:0705.1617 [quant-ph].

Supporting Agencies

The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

| NeuroScience + QuantumPhysics> NeuroQuantology :: Copyright 2001-2019