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

Bulletin of the American Physical Society

Undecidability Theorem and Quantum Randomness

Alexander A. Berezin

Published Apr 17, 2005• 0 citations
OpenAlex

Related papers

Undecidability and the Problem of Outcomes in Quantum Measurements

Rodolfo Gambini, Luis Pedro García-Pintos, Jorge A. Pullin

arXiv:0905.4222•Foundations of Physics•Nov 16, 2009•12 citations

Undecidability and incompleteness in quantum information theory and operator algebras

Isaac Goldbring

arXiv:2409.08342•Monatshefte für Mathematik•May 8, 2025•0 citations

ON QUANTUM RANDOMNESS

WORLD SCIENTIFIC eBooks•Apr 1, 1998•0 citations

Uncertainty, Incompleteness, Chance, and Design

Fernando Sols

The 20th century has revealed two important limitations of scientific knowledge. On the one hand, the combination of Poincaré's nonlinear dynamics and Heisenberg's uncertainty principle leads to a world picture where physical reality is, in many respects, intrinsically undetermined. On the other hand, Gödel's incompleteness theorems reveal us the existence of mathematical truths that cannot be demonstrated. More recently, Chaitin has proved that, from the incompleteness theorems, it follows that the random character of a given mathematical sequence cannot be proved in general (it is 'undecidable'). I reflect here on the consequences derived from the indeterminacy of the future and the undecidability of randomness, concluding that the question of the presence or absence of finality in nature is fundamentally outside the scope of the scientific method.

arXiv:1301.7036•WORLD SCIENTIFIC eBooks•Oct 28, 2013•6 citations

Analysis of Quantum Computers and Randomness

Deepak Chahal, Preethi Ravichandran Kumar

•Apr 21, 2020•0 citations

An Adian-Rabin theorem for quantum automorphism groups of graphs

Josse van Dobben de Bruyn, William Slofstra

Given a graph $G$, does it have quantum symmetries, or in other words, is the algebra of the quantum automorphism group non-commutative? In the world of ordinary groups, determining whether a finitely presented group is commutative is undecidable. This is an immediate consequence of the Adian-Rabin theorem, which shows that many natural properties of finitely presented groups are undecidable. In this paper, we prove an Adian-Rabin theorem for quantum automorphism groups of graphs, showing that many natural properties of the quantum automorphism group of a graph (including having quantum symmetries) are undecidable. We also show that it's undecidable to determine if the discrete quantum automorphism group is non-trivial. Our methods are based on solution groups of linear system nonlocal games, and we also prove an Adian-Rabin theorem in this context.

arXiv:2610.40590•Oct 29, 2026•0 citations
The 20th century has revealed two important limitations of scientific knowledge. On the one hand, the combination of Poincaré's nonlinear dynamics and Heisenberg's uncertainty principle leads to a world picture where physical reality is, in many respects, intrinsically undetermined. On the other hand, Gödel's incompleteness theorems reveal us the existence of mathematical truths that cannot be demonstrated. More recently, Chaitin has proved that, from the incompleteness theorems, it follows that the random character of a given mathematical sequence cannot be proved in general (it is 'undecidable'). I reflect here on the consequences derived from the indeterminacy of the future and the undecidability of randomness, concluding that the question of the presence or absence of finality in nature is fundamentally outside the scope of the scientific method.
Given a graph GGG, does it have quantum symmetries, or in other words, is the algebra of the quantum automorphism group non-commutative? In the world of ordinary groups, determining whether a finitely presented group is commutative is undecidable. This is an immediate consequence of the Adian-Rabin theorem, which shows that many natural properties of finitely presented groups are undecidable. In this paper, we prove an Adian-Rabin theorem for quantum automorphism groups of graphs, showing that many natural properties of the quantum automorphism group of a graph (including having quantum symmetries) are undecidable. We also show that it's undecidable to determine if the discrete quantum automorphism group is non-trivial. Our methods are based on solution groups of linear system nonlocal games, and we also prove an Adian-Rabin theorem in this context.