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

Computational complexity versus physics: what each physical resource would compute — from finite automata to closed time loops

Jarek Duda

Published Oct 3, 2026• 0 citations
Publisher

Abstract

Large review of computational capabilities allowed by our physics, also potential e.g. hypothetical NP-solver.Written by Opus 5.5+Sol 6.1, reviewed by Gemini, Qwen, Kimi.
DOI
10.5281/zenodo.23125605

Related papers

The Complexity of Probabilistic versus Quantum Finite Automata

Gatis Midrijānis

arXiv:quant-ph/0309080•Lecture notes in computer science•Jan 1, 2002•0 citations

Computational Complexity for Physicists

Stephan Mertens

These lecture notes are an informal introduction to the theory of computational complexity and its links to quantum computing and statistical mechanics.

arXiv:cond-mat/0012185•Dec 11, 2000•6 citations

Non-Hermitian quantum mechanics and two-way quantum computing: one fork, one test

Jarek Duda

Discussed connections between non-Hermitian quantum mechanics and two-way quantum computers.Written by Opus with help of Sol, Geminim, Qwen, Kimi

•Oct 8, 2026•0 citations

Is the future open? Final-boundary tests of quantum mechanics: is the Feynman path ensemble open at its final end?

Jarek Duda

Proposed missing basic experimental test: of uniform weigths in Feynman ensembles.Part of 2WQC project ( https://zenodo.org/records/23089597 ), prepared by Opus with help and review by Sol, Gemini and Qwen.

•Oct 2, 2026•0 citations

Aspects Of Computability In Physics

Joseph Shipman

This paper reviews connections between physics and computation, and explores their implications. The main topics are computational "hardness" of physical systems, computational status of fundamental theories, quantum computation, and the Universe as a computer.

arXiv:math/9711204•Workshop on Physics and Computation (PhysComp)•Aug 24, 2005•4 citations

Photonic Ising machines for combinatorial optimization problems

Yuan Gao, Guanyu Chen, Qi Luo +3 more

The demand for efficient solvers of complicated combinatorial optimization problems, especially those classified as NP-complete or NP-hard, has recently led to increased exploration of novel computing architectures. One prominent collective state computing paradigm embodied in the so-called Ising machines has recently attracted considerable research attention due to its ability to optimize complex problems with large numbers of interacting variables. Ising model-inspired solvers, thus named due to mathematical similarities to the well-known model from solid-state physics, represent a promising alternative to traditional von Neumann computer architectures due to their high degree of inherent parallelism. While there are many possible physical realizations of Ising solvers, just as there are many possible implementations of any binary computer, photonic Ising machines (PIMs) use primarily optical components for computation, taking advantage of features like lower power consumption, fast calculation speeds, the leveraging of physical optics to perform the calculations themselves, possessing decent scalability and noise tolerance. Photonic computing in the form of PIMs may offer certain computational advantages that are not easily achieved with non-photonic approaches and is nonetheless an altogether fascinating application of photonics to computing. In this review, we provide an overview of Ising machines generally, introducing why they are useful, what types of problems they can tackle, and how different Ising solvers can be compared and benchmarked. We delineate their various operational mechanisms, advantages, and limitations vis-à-vis non-photonic Ising machines. We describe their scalability, interconnectivity, performance, and physical dimensions. As research in PIMs continues to progress, there is a potential that photonic computing could well emerge as a way to handle large and challenging optimization problems across diverse domains. This review serves as a comprehensive resource for researchers and practitioners interested in understanding capabilities and potential of PIMs in addressing such complex optimization problems.

Applied Physics Reviews•Oct 14, 2024•40 citations
The demand for efficient solvers of complicated combinatorial optimization problems, especially those classified as NP-complete or NP-hard, has recently led to increased exploration of novel computing architectures. One prominent collective state computing paradigm embodied in the so-called Ising machines has recently attracted considerable research attention due to its ability to optimize complex problems with large numbers of interacting variables. Ising model-inspired solvers, thus named due to mathematical similarities to the well-known model from solid-state physics, represent a promising alternative to traditional von Neumann computer architectures due to their high degree of inherent parallelism. While there are many possible physical realizations of Ising solvers, just as there are many possible implementations of any binary computer, photonic Ising machines (PIMs) use primarily optical components for computation, taking advantage of features like lower power consumption, fast calculation speeds, the leveraging of physical optics to perform the calculations themselves, possessing decent scalability and noise tolerance. Photonic computing in the form of PIMs may offer certain computational advantages that are not easily achieved with non-photonic approaches and is nonetheless an altogether fascinating application of photonics to computing. In this review, we provide an overview of Ising machines generally, introducing why they are useful, what types of problems they can tackle, and how different Ising solvers can be compared and benchmarked. We delineate their various operational mechanisms, advantages, and limitations vis-à-vis non-photonic Ising machines. We describe their scalability, interconnectivity, performance, and physical dimensions. As research in PIMs continues to progress, there is a potential that photonic computing could well emerge as a way to handle large and challenging optimization problems across diverse domains. This review serves as a comprehensive resource for researchers and practitioners interested in understanding capabilities and potential of PIMs in addressing such complex optimization problems.