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 Reducibility theorem

Sergej Materov

Published Apr 2, 2026• 2 citations
Publisher

Abstract

A Principled Limitation of Wolfram's Computational Irreducibility for Finite Unitary Quantum Systems. The sufficiency of a single slice to predict the entire evolution. After diagonalization, prediction cost is independent of the time horizon. Time is not a fundamental step-by-step process—it emerges from the spectrum of the evolutionary operator. Therefore, the "future" is not ontologically inaccessible: it is already fully encoded in the spectral structure of the present. Computational reducibility is not a trick involving substitution into a formula. It reflects the fact that in Quantumograph, time and spectrum are the same thing, described in different languages.

DOI
10.24108/preprints-3114827

Related papers

Computational Reducibility theorem

Sergej Materov

Computational Reducibility Theorem.Against S. Wolfram's Principle of Computational Irreducibility:The sufficiency of a single slice to predict the entire evolution.Time is not a fundamental step-by-step process—it emerges from the spectrum of the evolutionary operator. Therefore, the "future" is not ontologically inaccessible: it is already fully encoded in the spectral structure of the present. Computational reducibility is not a trick involving substitution into a formula. It reflects the fact that in Quantumograph, time and spectrum are the same thing, described in different languages.A Blow to Cryptography?Implications and Practical Outlook. The main consequence is not a universal cryptanalytic breakthrough, but a precise separation between principled and operational predictability. Exact microstate prediction remains exponentially costly, whereas coarse-grained observables admit polynomial forecasting. This makes the framework relevant for model reduction, spectral inference, and device-level analysis, while the cryptographic threat landscape remains governed by dedicated quantum algorithms and by the ongoing transition to post-quantum cryptography.

•Mar 30, 2023•0 citations

THE COMPUTATIONAL REDUCIBILITY THEOREM

Materov

Abstract Wolfram's Principle of Computational Irreducibility asserts that for most non-trivial discrete systems there exists no analytical shortcut: to determine the state at time T, one must simulate all T steps. For finite-dimensional unitary graph systems, the evolution admits an exact spectral representation for a specific class of systems: finite quantum graphs with unitary evolution. Knowledge of the spectral slice - the quantum state |Ψ(t₀)⟩ and the spectrum of the evolution operator Û - fully and exactly determines the state at any moment T without stepping through intermediate times. The theorem is a principled, not a practical result: algorithmic complexity O( ) remains exponential. Practical significance is achieved in the coarse-graining limit at scale ℓ >> a, where the problem reduces to polynomial complexity. Three conditions - finiteness, unitarity, linearity - constitute the exact domain of applicability.

•Jul 3, 2026•0 citations

Between Computability and Physical Realizability: The Computational Reducibility Theorem and the Fundamental Limit of Quantum Computation

Materov

This note connects two claims in the Quantumograph program. The Computational Reducibility Theorem shows that a finite unitary quantum graph is, in principle, exactly forecastable from one spectral slice: the state at one time together with the spectrum of the evolution operator. The Fundamental Limit of Quantum Computation (FLQC) adds a physical constraint: any realizable quantum device has a finite phase resolution, so exact spectral data and exact phase gates cannot be implemented with arbitrary precision. Realism, in this setting, is the position between these two statements. The universe is computable in principle, but nature imposes a nonzero floor on the precision with which that computability can be instantiated. The note derives the phase floor, compares it with the phase resolution required by QFT- and Shor-type circuits, and gives a concrete experimental signature on superconducting quantum processors.

•Jun 18, 2026•0 citations

The Quantumograph: A Discrete Ontology of Spacetime and the Empirical Accessibility of Quantum Gravity

Sergej Materov

Quantum gravity is traditionally regarded as a domain of mathematical physics devoid of direct empirical access. This paper proposes an alternative research program-the Quantumograph (TQGT) (Materov 2026) - in which spacetime is ontologically identical to a finite quantum graph, while continuum notions (metric, fields, time) are strictly emergent. I argue that this program possesses excess empirical content: its central predictions are testable on existing cryogenic quantum processors, thereby relocating quantum gravity from speculation to experimental science. Philosophical analysis reveals ontological consequences: support for ontic structural realism, the constitutional finitude of the Universe, the dynamic nature of time, and two fundamental theorems on the absence of asymptotic chaos and computational reducibility. A comparison with string theory, loop quantum gravity, and the Fredkin–Wolfram–Lloyd digital-physics tradition locates the program's unique status as a falsifiable digital structuralism.

•Apr 29, 2026•0 citations

Quantum-mechanical computers and uncomputability

Seth Lloyd

The time evolution operator for any quantum-mechanical computer is diagonalizable, but to obtain the diagonal decomposition of a program state of the computer is as hard as actually performing the computation corresponding to the program. In particular, if a quantum-mechanical system is capable of universal computation, then the diagonal decomposition of program states is uncomputable. As a result, in a universe in which local variables support universal computation, a quantum-mechanical theory for that universe that supplies its spectrum cannot supply the spectral decomposition of the computational variables. A ``theory of everything'' can be simultaneously correct and fundamentally incomplete.

Physical Review Letters•Aug 9, 1993•31 citations

COMPUTATIONAL REDUCIBILITY OF FINITE UNITARY QUANTUM SYSTEMS (technical note)

Materov

COMPUTATIONAL REDUCIBILITY OF FINITE UNITARY QUANTUM SYSTEMS (technical note). A Theory-Independent Result.

•Aug 10, 2026•0 citations
A Principled Limitation of Wolfram's Computational Irreducibility for Finite Unitary Quantum Systems. The sufficiency of a single slice to predict the entire evolution. After diagonalization, prediction cost is independent of the time horizon. Time is not a fundamental step-by-step process—it emerges from the spectrum of the evolutionary operator. Therefore, the "future" is not ontologically inaccessible: it is already fully encoded in the spectral structure of the present. Computational reducibility is not a trick involving substitution into a formula. It reflects the fact that in Quantumograph, time and spectrum are the same thing, described in different languages.
Computational Reducibility Theorem.Against S. Wolfram's Principle of Computational Irreducibility:The sufficiency of a single slice to predict the entire evolution.Time is not a fundamental step-by-step process—it emerges from the spectrum of the evolutionary operator. Therefore, the "future" is not ontologically inaccessible: it is already fully encoded in the spectral structure of the present. Computational reducibility is not a trick involving substitution into a formula. It reflects the fact that in Quantumograph, time and spectrum are the same thing, described in different languages.A Blow to Cryptography?Implications and Practical Outlook. The main consequence is not a universal cryptanalytic breakthrough, but a precise separation between principled and operational predictability. Exact microstate prediction remains exponentially costly, whereas coarse-grained observables admit polynomial forecasting. This makes the framework relevant for model reduction, spectral inference, and device-level analysis, while the cryptographic threat landscape remains governed by dedicated quantum algorithms and by the ongoing transition to post-quantum cryptography.
Abstract Wolfram's Principle of Computational Irreducibility asserts that for most non-trivial discrete systems there exists no analytical shortcut: to determine the state at time T, one must simulate all T steps. For finite-dimensional unitary graph systems, the evolution admits an exact spectral representation for a specific class of systems: finite quantum graphs with unitary evolution. Knowledge of the spectral slice - the quantum state |Ψ(t₀)⟩ and the spectrum of the evolution operator Û - fully and exactly determines the state at any moment T without stepping through intermediate times. The theorem is a principled, not a practical result: algorithmic complexity O( ) remains exponential. Practical significance is achieved in the coarse-graining limit at scale ℓ >> a, where the problem reduces to polynomial complexity. Three conditions - finiteness, unitarity, linearity - constitute the exact domain of applicability.
This note connects two claims in the Quantumograph program. The Computational Reducibility Theorem shows that a finite unitary quantum graph is, in principle, exactly forecastable from one spectral slice: the state at one time together with the spectrum of the evolution operator. The Fundamental Limit of Quantum Computation (FLQC) adds a physical constraint: any realizable quantum device has a finite phase resolution, so exact spectral data and exact phase gates cannot be implemented with arbitrary precision. Realism, in this setting, is the position between these two statements. The universe is computable in principle, but nature imposes a nonzero floor on the precision with which that computability can be instantiated. The note derives the phase floor, compares it with the phase resolution required by QFT- and Shor-type circuits, and gives a concrete experimental signature on superconducting quantum processors.
Quantum gravity is traditionally regarded as a domain of mathematical physics devoid of direct empirical access. This paper proposes an alternative research program-the Quantumograph (TQGT) (Materov 2026) - in which spacetime is ontologically identical to a finite quantum graph, while continuum notions (metric, fields, time) are strictly emergent. I argue that this program possesses excess empirical content: its central predictions are testable on existing cryogenic quantum processors, thereby relocating quantum gravity from speculation to experimental science. Philosophical analysis reveals ontological consequences: support for ontic structural realism, the constitutional finitude of the Universe, the dynamic nature of time, and two fundamental theorems on the absence of asymptotic chaos and computational reducibility. A comparison with string theory, loop quantum gravity, and the Fredkin–Wolfram–Lloyd digital-physics tradition locates the program's unique status as a falsifiable digital structuralism.
The time evolution operator for any quantum-mechanical computer is diagonalizable, but to obtain the diagonal decomposition of a program state of the computer is as hard as actually performing the computation corresponding to the program. In particular, if a quantum-mechanical system is capable of universal computation, then the diagonal decomposition of program states is uncomputable. As a result, in a universe in which local variables support universal computation, a quantum-mechanical theory for that universe that supplies its spectrum cannot supply the spectral decomposition of the computational variables. A ``theory of everything'' can be simultaneously correct and fundamentally incomplete.