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

arXiv:2409.08342 · Monatshefte für Mathematik

Undecidability and incompleteness in quantum information theory and operator algebras

Isaac Goldbring

Published May 8, 2025• 0 citations
arXivHTMLPDF
DOI
10.1007/s00605-025-02080-3

Related papers

The mathematics of quantum information theory

Guillaume Aubrun, Stanisław Szarek

Mathematical surveys and monographs•Aug 30, 2017•0 citations

Quantum recursion theory

Karl Svozil

Incompleteness and undecidability theorems have to be revised in view of quantum information and computation theory. qrt.tex 1 As has already been pointed out in Gödel’s centennial paper on the incompleteness af arithmetic [1], the classical undecidability theorems of formal logic [2] and the theory of computable functions [4, 5] are based on semantical pardoxes such as the liar [6] or Richard’s paradox. The method of diagonalization, which was first applied by Cantor for a proof of the undenumerability of real numbers [7], has been applied by Turing for a proof of the recursive undecidability of the halting problem [8]. The halting problem is the problem of whether or not an arbitrary algorithm terminates or produces a particular output and terminates. Assume that the halting problem is decidable. Turing [8] proved that this assumption yields a contradiction. To construct the contradiction, consider

arXiv:hep-th/9412048•Dec 6, 1994•4 citations

Algebraic Quantum Information Theory

Keye Martin

•Oct 30, 2017•0 citations

Quantum Measurement Problem and Systems Selfdescription in Operators Algebras Formalism

Sergey Nikolaevich Mayburov

Quantum Measurement problem studied in Information Theory approach of systems selfdescription which exploits the information acquisition incompleteness for the arbitrary information system. The studied model of measuring system (MS) consist of measured state S environment E and observer $O$ processing input S signal. $O$ considered as the quantum object which interaction with S,E obeys to Schrodinger equation (SE). MS incomplete or restricted states for $O$ derived by the algebraic QM formalism which exploits Segal and $C^*$-algebras. From Segal theorem for systems subalgebras it's shown that such restricted states $V^O=|O_j> < O_j|$ describes the classical random 'pointer' outcomes $O_j$ observed by $O$ in the individual events. The 'preferred' basis $|O_j>$ defined by $O$ state decoherence via $O$ - E interactions.

arXiv:quant-ph/0212099•Dec 17, 2002•1 citation

Undecidability Theorem and Quantum Randomness

Alexander A. Berezin

Bulletin of the American Physical Society•Apr 17, 2005•0 citations

A Quantum Gate as a Physical Model of an Universal Arithmetical Algorithm without Church's Undecidability and Godel's Incompleteness

Vladan Panković, Milan Predojević

In this work we define an universal arithmetical algorithm, by means of the standard quantum mechanical formalism, called universal qm-arithmetical algorithm. By universal qm-arithmetical algorithm any decidable arithmetical formula (operation) can be decided (realized, calculated. Arithmetic defined by universal qm-arithmetical algorithm called qm-arithmetic one-to-one corresponds to decidable part of the usual arithmetic. We prove that in the qm-arithmetic the undecidable arithmetical formulas (operations) cannot exist (cannot be consistently defined). Or, we prove that qm-arithmetic has no undecidable parts. In this way we show that qm-arithmetic, that holds neither Church's undecidability nor Godel's incompleteness, is decidable and complete. Finally, we suggest that problems of the foundation of the arithmetic, can be solved by qm-arithmetic.

arXiv:quant-ph/0602009•Feb 1, 2006•0 citations
Incompleteness and undecidability theorems have to be revised in view of quantum information and computation theory. qrt.tex 1 As has already been pointed out in Gödel’s centennial paper on the incompleteness af arithmetic [1], the classical undecidability theorems of formal logic [2] and the theory of computable functions [4, 5] are based on semantical pardoxes such as the liar [6] or Richard’s paradox. The method of diagonalization, which was first applied by Cantor for a proof of the undenumerability of real numbers [7], has been applied by Turing for a proof of the recursive undecidability of the halting problem [8]. The halting problem is the problem of whether or not an arbitrary algorithm terminates or produces a particular output and terminates. Assume that the halting problem is decidable. Turing [8] proved that this assumption yields a contradiction. To construct the contradiction, consider
Quantum Measurement problem studied in Information Theory approach of systems selfdescription which exploits the information acquisition incompleteness for the arbitrary information system. The studied model of measuring system (MS) consist of measured state S environment E and observer OOO processing input S signal. OOO considered as the quantum object which interaction with S,E obeys to Schrodinger equation (SE). MS incomplete or restricted states for OOO derived by the algebraic QM formalism which exploits Segal and C∗C^*C∗-algebras. From Segal theorem for systems subalgebras it's shown that such restricted states VO=∣Oj><Oj∣V^O=|O_j> < O_j|VO=∣Oj​><Oj​∣ describes the classical random 'pointer' outcomes OjO_jOj​ observed by OOO in the individual events. The 'preferred' basis ∣Oj>|O_j>∣Oj​> defined by OOO state decoherence via OOO - E interactions.
In this work we define an universal arithmetical algorithm, by means of the standard quantum mechanical formalism, called universal qm-arithmetical algorithm. By universal qm-arithmetical algorithm any decidable arithmetical formula (operation) can be decided (realized, calculated. Arithmetic defined by universal qm-arithmetical algorithm called qm-arithmetic one-to-one corresponds to decidable part of the usual arithmetic. We prove that in the qm-arithmetic the undecidable arithmetical formulas (operations) cannot exist (cannot be consistently defined). Or, we prove that qm-arithmetic has no undecidable parts. In this way we show that qm-arithmetic, that holds neither Church's undecidability nor Godel's incompleteness, is decidable and complete. Finally, we suggest that problems of the foundation of the arithmetic, can be solved by qm-arithmetic.