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

Computational complexity for physicists

Stephan Mertens

The theory of computational complexity has some interesting links to physics, in particular to quantum computing and statistical mechanics. The article contains an informal introduction to this theory and its links to physics.

Computing in Science & Engineering•Jan 1, 2002•63 citations