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

Studies in big data

QFT + NP = P Quantum Field Theory (QFT): A Possible Way of Solving NP-Complete Problems in Polynomial Time

Владик Крейнович, Luc Longpré, Adriana Espino Beltrán

Published Oct 13, 2017• 0 citations
Publisher
DOI
10.1007/978-3-319-63639-9_10

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

Quantum Phase Transitions and Typical Case, Polynomial Time Solution of Randomly Generated NP-Complete Problems via Adiabatic Quantum Computation

William M. Kaminsky, Seth Lloyd

Bulletin of the American Physical Society•Mar 16, 2006•0 citations

Is quantum field theory a theory

Gerard ’t Hooft

•Jan 1, 1983•0 citations

A recursive definition of quantum polynomial time computability (extended abstract).

Tomoyuki Yamakami

NCMA•Jan 1, 2017•1 citation

Reconfigurable integrated photonic processor for NP-complete problems

Xiao-Yun Xu, Tian-Yu Zhang, Ziwei Wang +2 more

Nondeterministic-polynomial-time (NP)-complete problems are widely involved in various real-life scenarios but are still intractable in being solved efficiently on conventional computers. It is of great practical significance to construct versatile computing architectures that solve NP-complete problems with computational advantage. Here, we present a reconfigurable integrated photonic processor to efficiently solve a benchmark NP-complete problem, the subset sum problem. We show that in the case of successive primes, the photonic processor has genuinely surpassed electronic processors launched recently by taking advantage of the high propagation speed and vast parallelism of photons and state-of-the-art integrated photonic technology. Moreover, we are able to program the photonic processor to tackle different problem instances, relying on the tunable integrated modules, variable split junctions, which can be used to build a fully reconfigurable architecture potentially allowing 2N configurations at most. Our experiments confirm the potential of the photonic processor as a versatile and efficient computing platform, suggesting a possible practical route to solving computationally hard problems at a large scale.

Advanced Photonics•Sep 24, 2024•11 citations

Experimental verification of NP-complete problems via linear optics

Jian Li, Tongjun Liu, Tianlei Hou +4 more

Non-deterministic polynomial (NP)-complete problems are collections of intractable problems for classical computers, but they may be easier to solve for quantum computers. Considering that practical quantum computers and networks are still under development, it is necessary to find alternatives to solve these problems. Simulations with linear optics offer a good choice since much of the research on quantum information is executed with this approach. In this work, based on Aaronson's protocol (Theory Comput, 5, 1, 2009) ad Arrazola et. al.'s linear optics scheme (npj Quantum Inf, 78, 022310, 2018), we present a demonstration of the NP-complete 2-out-of-4 SAT problem for 4 variables. The experimental results show that NP-complete problems can be well simulated through linear optical systems.

International Conference on Wireless Communications and Signal Processing (WCSP)•Oct 20, 2021•1 citation
Nondeterministic-polynomial-time (NP)-complete problems are widely involved in various real-life scenarios but are still intractable in being solved efficiently on conventional computers. It is of great practical significance to construct versatile computing architectures that solve NP-complete problems with computational advantage. Here, we present a reconfigurable integrated photonic processor to efficiently solve a benchmark NP-complete problem, the subset sum problem. We show that in the case of successive primes, the photonic processor has genuinely surpassed electronic processors launched recently by taking advantage of the high propagation speed and vast parallelism of photons and state-of-the-art integrated photonic technology. Moreover, we are able to program the photonic processor to tackle different problem instances, relying on the tunable integrated modules, variable split junctions, which can be used to build a fully reconfigurable architecture potentially allowing 2N configurations at most. Our experiments confirm the potential of the photonic processor as a versatile and efficient computing platform, suggesting a possible practical route to solving computationally hard problems at a large scale.
Non-deterministic polynomial (NP)-complete problems are collections of intractable problems for classical computers, but they may be easier to solve for quantum computers. Considering that practical quantum computers and networks are still under development, it is necessary to find alternatives to solve these problems. Simulations with linear optics offer a good choice since much of the research on quantum information is executed with this approach. In this work, based on Aaronson's protocol (Theory Comput, 5, 1, 2009) ad Arrazola et. al.'s linear optics scheme (npj Quantum Inf, 78, 022310, 2018), we present a demonstration of the NP-complete 2-out-of-4 SAT problem for 4 variables. The experimental results show that NP-complete problems can be well simulated through linear optical systems.