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

If Space-Time Is Discrete, We May Be Able to Solve NP-Hard Problems in Polynomial Time

Ricardo O. de Alba Alvarez, Nick Sims, Christian Servín, Martine C. Ceberio, Владик Крейнович

Published Jan 1, 2019• 0 citations
OpenAlex

Abstract

Traditional physics assumes that space and time are continuous. However, this reasonable model leads to some serious problems. One the approaches that physicists follow to solve these problems is to assume that the space-time is actually discrete. In this paper, we analyze possible computational consequences of this discreteness. It turns out that in a discrete space-time, we may be able to solve NP-hard problems in polynomial time.

Related papers

If Space-Time Is Discrete, It Could Be Possible to Solve NP-Complete Problems in Polynomial Time.

Ricardo O. de Alba Alvarez, Nick Sims, Christian Servín +2 more

International journal of unconventional computing•Jan 1, 2020•0 citations

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

The Space "Just Above" BQP

Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons +1 more

We explore the space "just above" BQP by defining a complexity class naCQP (non-adaptive Collapse-free Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform (non-adaptive) measurements that do not collapse the wavefunction. This non-physical model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in Õ(N1/3) time, but no faster than Ω(N1/4), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. This is surprising as most modifications of BQP increase the power of quantum computation to NP or beyond.

Conference on Innovations in Theoretical Computer Science•Jan 5, 2016•15 citations

The space "just above" BQP

Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons +1 more

We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the wavefunction. This (non-physical) model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in $\tilde O$(N^{1/3}) time, but no faster than Ω(N^{1/4}), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. Our work is inspired by previous work of Aaronson on the power of sampling the histories of hidden variables. However Aaronson's work contains an error in its proof of the lower bound for search, and hence it is unclear whether or not his model allows for search in logarithmic time. Our work can be viewed as a conceptual simplification of Aaronson's approach, with a provable polynomial lower bound for search.

arXiv:1412.6507•Electronic colloquium on computational complexity•Dec 19, 2014•0 citations

Mathematical Structure of Discrete Space-time

An-Wei Zhang

In this letter we briefly investigate the mathematical structure of space-time in the framework of discretization. It is shown that the discreteness of space-time may result in a new mechanical system which differ from the usual quantum mechanics (QM).

arXiv:0910.1417•Oct 8, 2009•1 citation

Computational phase transition in Quantum Approximate Optimization Algorithm -- the difference between hard and easy

Bingzhi Zhang, Quntao Zhuang

Quantum Approximate Optimization algorithm (QAOA) is one of the candidates to achieve a near-term quantum advantage. As QAOA seems only capable of solving optimization problems, there is a folklore that QAOA cannot see the difference between easy problems such as 2-SAT and hard problems such as 3-SAT -- although 2-SAT is in the polynomial-time (P) class, its optimization version is also nondeterministic polynomial-time (NP)-hard. In this paper, we show that the folklore is not true. We find a computational phase transition in QAOA when solving a variant of 3-SAT -- the amplitude of gradient and the success probability achieve their minimum at the well-known SAT-UNSAT phase transition. On the contrary, for 2-SAT, such a phenomenon is absent at SAT-UNSAT phase transition and the success probability is unity for a reasonable circuit depth. We connect the gradient transition to the dynamical Lie algebra of the QAOA circuit. In solving the NP-hard optimization versions of SAT, we identify quantum advantages over a classical approximate algorithm at quite a shallow depth of $p=4$ for the problem size of $n=10$.

•Sep 27, 2021•0 citations
Traditional physics assumes that space and time are continuous. However, this reasonable model leads to some serious problems. One the approaches that physicists follow to solve these problems is to assume that the space-time is actually discrete. In this paper, we analyze possible computational consequences of this discreteness. It turns out that in a discrete space-time, we may be able to solve NP-hard problems in polynomial time.
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.
We explore the space "just above" BQP by defining a complexity class naCQP (non-adaptive Collapse-free Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform (non-adaptive) measurements that do not collapse the wavefunction. This non-physical model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in Õ(N1/3) time, but no faster than Ω(N1/4), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. This is surprising as most modifications of BQP increase the power of quantum computation to NP or beyond.
We explore the space "just above" BQP by defining a complexity class PDQP (Product Dynamical Quantum Polynomial time) which is larger than BQP but does not contain NP relative to an oracle. The class is defined by imagining that quantum computers can perform measurements that do not collapse the wavefunction. This (non-physical) model of computation can efficiently solve problems such as Graph Isomorphism and Approximate Shortest Vector which are believed to be intractable for quantum computers. Furthermore, it can search an unstructured N-element list in O~\tilde OO~(N^{1/3}) time, but no faster than Ω(N^{1/4}), and hence cannot solve NP-hard problems in a black box manner. In short, this model of computation is more powerful than standard quantum computation, but only slightly so. Our work is inspired by previous work of Aaronson on the power of sampling the histories of hidden variables. However Aaronson's work contains an error in its proof of the lower bound for search, and hence it is unclear whether or not his model allows for search in logarithmic time. Our work can be viewed as a conceptual simplification of Aaronson's approach, with a provable polynomial lower bound for search.
Quantum Approximate Optimization algorithm (QAOA) is one of the candidates to achieve a near-term quantum advantage. As QAOA seems only capable of solving optimization problems, there is a folklore that QAOA cannot see the difference between easy problems such as 2-SAT and hard problems such as 3-SAT -- although 2-SAT is in the polynomial-time (P) class, its optimization version is also nondeterministic polynomial-time (NP)-hard. In this paper, we show that the folklore is not true. We find a computational phase transition in QAOA when solving a variant of 3-SAT -- the amplitude of gradient and the success probability achieve their minimum at the well-known SAT-UNSAT phase transition. On the contrary, for 2-SAT, such a phenomenon is absent at SAT-UNSAT phase transition and the success probability is unity for a reasonable circuit depth. We connect the gradient transition to the dynamical Lie algebra of the QAOA circuit. In solving the NP-hard optimization versions of SAT, we identify quantum advantages over a classical approximate algorithm at quite a shallow depth of p=4p=4p=4 for the problem size of n=10n=10n=10.