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

arXiv:1309.1801

Applying computational complexity to the emergence of classicality

Arkady Bolotin

Published Sep 7, 2013• 1 citation
arXivHTMLPDF

Abstract

Can the computational complexity theory of computer science and mathematics say something new about unresolved problems in quantum physics? Particularly, can the P versus NP question in the computational complexity theory be a factor in the elucidation of the emergency of classicality in quantum mechanics? The paper compares two different ways of deriving classicality from the quantum formalism resulted from two differing hypotheses regarding the P versus NP question -- the approach of the quantum decoherence theory implying that P = NP and the computational complexity approach which assumes that P is not equal to NP.

DOI
10.48550/arxiv.1309.1801

Related papers

The Orthogonality of P and NP: A Quantum-Classical Framework for Dissolving the Millennium Problem

Nguyen, Van Laurie Nguyen

The P versus NP problem has remained unsolved for over fifty years, with some researchers suggesting it may be independent of standard axiom systems (Sipser, 1992; Aaronson, 2003). This paper proposes that the problem resists solution not due to mathematical difficulty, but due to categorical error: P and NP are not comparable quantities within a single dimension, but rather orthogonal constructs operating on different layers of reality. Drawing on established research linking computational complexity to physical theory (Freedman et al., 1998), we argue that P represents quantum- scale reasoning processes while NP represents classical verification. The question "Does P equal NP?" is therefore malformed—analogous to asking whether length equals color. We propose that dissolving rather than solving this problem opens new avenues for understanding the relationship between quantum and classical computation.

•Dec 18, 2025•0 citations

The unity between quantum field computation, real computation, and quantum computation

A. C. Manoharan

It is indicated that principal models of computation are indeed significantly related. The quantum field computation model contains the quantum computation model of Feynman. (The term "quantum field computer" was used by Freedman.) Quantum field computation (as enhanced by Wightman's model of quantum field theory) involves computation over the continuum which is remarkably related to the real computation model of Smale. The latter model was established as a generalization of Turing computation. All this is not surprising since it is well known that the physics of quantum field theory (which includes Einstein's special relativity) contains quantum mechanics which in turn contains classical mechanics. The unity of these computing models, which seem to have grown largely independently, could shed new light into questions of computational complexity, into the central P (Polynomial time) versus NP (Non-deterministic Polynomial time) problem of computer science, and also into the description of Nature by fundamental physics theories.

arXiv:quant-ph/0109015•Sep 4, 2001•2 citations

The Orthogonality of P and NP: A Quantum-Clasical Framework for Dissolving the Millennium Problem

Nguyen, Van Laurie

The P versus NP problem has remained unsolved for over fifty years, with some researchers suggesting it may be independent of standard axiom systems (Sipser, 1992; Aaronson, 2003). This paper proposes that the problem resists solution not due to mathematical difficulty, but due to categorical error: P and NP are not comparable quantities within a single dimension, but rather orthogonal constructs operating on different layers of reality. Drawing on established research linking computational complexity to physical theory (Freedman et al., 1998), we argue that P represents quantum-scale reasoning processes while NP represents classical verification. The question "Does P equal NP?" is therefore malformed—analogous to asking whether length equals color. We propose that dissolving rather than solving this problem opens new avenues for understanding the relationship between quantum and classical computation.

•Dec 19, 2025•0 citations

The P Vs NP Problem: A Method for Solving NP-Complete Problems by use of Graph Embodiment on a Quantum Computation Paradigm using a Relational Database Query

Shadrack Mwanik, Andrew Mwaura Kahonge, Evans Kirimi Miriti

The relationship between the complexity class P and NP is one of the most fascinating and unresolved question in theoretical Computer Science. The classical computational paradigm, hedged on Turing thesis may be by itself the limiting factor. To investigate this relationship, a method for solving a query problem on a relational database on the classical and the quantum computational paradigm has been developed. The method solves queries or database problems through the use of graphs. The results indicate that the solution to the P vs NP cannot be resolved under the current computation paradigms and may requires a new computation paradigm to resolve it.

•Jan 1, 2013•0 citations

Quantum Complexity

Stefan Heinrich

A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.

Cambridge University Press eBooks•Mar 25, 2004•2 citations

P Vs NP as a Physical Problem: From Topological Invariants to Hardware Implementation

Овчинников С. В.

The relevance of the research is determined by the fundamental nature of the P vs NP problem, which has been considered a central unsolved problem in theoretical computer science for more than half a century. In this article, for the first time, it is proved that the problem of solving the P vs NP problem is not a mathematical problem, but a physical problem, the solution of which depends on the physical implementation of the computing system. The aim of this paper is to prove that the solution of the P vs NP problem depends on the type of physical system used for calculations. The leading approach to research is to synthesize three independent paradigms: 1. Algebraic topology that provides invariants for complexity classification. 2. Quantum physics, which provides parallel information processing. 3. Apparat implementation on the GPU that demonstrates the physical limitations of classical computing. Author's results include: A formal proof that P ≠ NP holds in classical physics (Newtonian mechanics, deterministic computations) and a simultaneous proof that P = NP holds in quantum physics (superposition, entanglement). Experimental confirmation of the physical implementation through a series of computational experiments. Development of hybrid system that allows you to switch between modes depending on the available resources. The theoretical significance lies in rethinking the fundamental problem of complexity theory as a physical law. Practical significance is the creation of an adaptive computing system, the efficiency of which is determined by the available physical platform.

•Jan 22, 2026•0 citations
Can the computational complexity theory of computer science and mathematics say something new about unresolved problems in quantum physics? Particularly, can the P versus NP question in the computational complexity theory be a factor in the elucidation of the emergency of classicality in quantum mechanics? The paper compares two different ways of deriving classicality from the quantum formalism resulted from two differing hypotheses regarding the P versus NP question -- the approach of the quantum decoherence theory implying that P = NP and the computational complexity approach which assumes that P is not equal to NP.
The P versus NP problem has remained unsolved for over fifty years, with some researchers suggesting it may be independent of standard axiom systems (Sipser, 1992; Aaronson, 2003). This paper proposes that the problem resists solution not due to mathematical difficulty, but due to categorical error: P and NP are not comparable quantities within a single dimension, but rather orthogonal constructs operating on different layers of reality. Drawing on established research linking computational complexity to physical theory (Freedman et al., 1998), we argue that P represents quantum- scale reasoning processes while NP represents classical verification. The question "Does P equal NP?" is therefore malformed—analogous to asking whether length equals color. We propose that dissolving rather than solving this problem opens new avenues for understanding the relationship between quantum and classical computation.
It is indicated that principal models of computation are indeed significantly related. The quantum field computation model contains the quantum computation model of Feynman. (The term "quantum field computer" was used by Freedman.) Quantum field computation (as enhanced by Wightman's model of quantum field theory) involves computation over the continuum which is remarkably related to the real computation model of Smale. The latter model was established as a generalization of Turing computation. All this is not surprising since it is well known that the physics of quantum field theory (which includes Einstein's special relativity) contains quantum mechanics which in turn contains classical mechanics. The unity of these computing models, which seem to have grown largely independently, could shed new light into questions of computational complexity, into the central P (Polynomial time) versus NP (Non-deterministic Polynomial time) problem of computer science, and also into the description of Nature by fundamental physics theories.
The P versus NP problem has remained unsolved for over fifty years, with some researchers suggesting it may be independent of standard axiom systems (Sipser, 1992; Aaronson, 2003). This paper proposes that the problem resists solution not due to mathematical difficulty, but due to categorical error: P and NP are not comparable quantities within a single dimension, but rather orthogonal constructs operating on different layers of reality. Drawing on established research linking computational complexity to physical theory (Freedman et al., 1998), we argue that P represents quantum-scale reasoning processes while NP represents classical verification. The question "Does P equal NP?" is therefore malformed—analogous to asking whether length equals color. We propose that dissolving rather than solving this problem opens new avenues for understanding the relationship between quantum and classical computation.
The relationship between the complexity class P and NP is one of the most fascinating and unresolved question in theoretical Computer Science. The classical computational paradigm, hedged on Turing thesis may be by itself the limiting factor. To investigate this relationship, a method for solving a query problem on a relational database on the classical and the quantum computational paradigm has been developed. The method solves queries or database problems through the use of graphs. The results indicate that the solution to the P vs NP cannot be resolved under the current computation paradigms and may requires a new computation paradigm to resolve it.
A challenging question in the overlap of computer science, mathematics, and physics, is the exploration of potential capabilities of quantum computers. Milestones were the factoring algorithm of Shor (1994) and the search algorithm of Grover (1996). So far, major research was concentrated on discrete and algebraic problems. Much less was known about computational problems of analysis, including such a prominent example as high dimensional numerical integration, which is well-studied in the classical settings. We seek to understand how efficiently this and related problems can be solved in the quantum model of computation (i.e., on a quantum computer) and how the outcome compares to the efficiency of deterministic or randomized algorithms on a classical (i.e. non-quantum) computer. In this paper we give a survey of the state of the art in this field, including also a brief introduction to the general ideas of quantum computing. Introduction A quantum computer is a computing device based on quantum mechanical laws of the (sub)atomic world. The idea of such a computer was developed by Feynman [8] in 1982. He emphasized that simulating quantum mechanics on a classical computer is extremely hard, probably infeasible. So why not try to simulate quantum mechanics using quantum devices themselves. (Thoughts in this direction were also expressed by Manin [21] in 1980, see also [22].) In 1985 Deutsch [6] presented a formal model of computation for quantum computing.
The relevance of the research is determined by the fundamental nature of the P vs NP problem, which has been considered a central unsolved problem in theoretical computer science for more than half a century. In this article, for the first time, it is proved that the problem of solving the P vs NP problem is not a mathematical problem, but a physical problem, the solution of which depends on the physical implementation of the computing system. The aim of this paper is to prove that the solution of the P vs NP problem depends on the type of physical system used for calculations. The leading approach to research is to synthesize three independent paradigms: 1. Algebraic topology that provides invariants for complexity classification. 2. Quantum physics, which provides parallel information processing. 3. Apparat implementation on the GPU that demonstrates the physical limitations of classical computing. Author's results include: A formal proof that P ≠ NP holds in classical physics (Newtonian mechanics, deterministic computations) and a simultaneous proof that P = NP holds in quantum physics (superposition, entanglement). Experimental confirmation of the physical implementation through a series of computational experiments. Development of hybrid system that allows you to switch between modes depending on the available resources. The theoretical significance lies in rethinking the fundamental problem of complexity theory as a physical law. Practical significance is the creation of an adaptive computing system, the efficiency of which is determined by the available physical platform.