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.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.40590Oct 29, 20260 citations

ON QUANTUM RANDOMNESS

WORLD SCIENTIFIC eBooksApr 1, 19980 citations

Mathematical undecidability and quantum randomness

Tomasz Paterek, Časlav Brukner, Robert Prevedel +4 more

We propose a new link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms and show that quantum measurements are capable of revealing whether a given proposition is decidable or not within the axiomatic system. Whenever a mathematical proposition is undecidable within the axioms encoded in the state, the measurement associated with the proposition gives random outcomes. Our results support the view that quantum randomness is irreducible and a manifestation of mathematical undecidability. Whenever a proposition and a given set of axioms together contain more information than the axioms themselves, the proposition can neither be proved nor disproved from the axioms { it is mathematically undecidable [1, 2]. Here we propose a novel link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms. Quantum mechanics imposes an upper limit on how much information can be encoded in a quantum state [3, 4], thus limiting the information content of the set of axioms. We show that quantum measurements are capable of revealing whether a given proposition is decidable or not. Whenever a mathematical proposition is undecidable within the system of axioms encoded in the state, the measurement associated with the proposition gives random outcomes. This allows for an experimental test of mathematical undecidability by realizing in the laboratory both the actual quantum states and the required quantum measurements. (To illustrate these ideas, we conducted experiments using the polarization of photons.) Our results support the view that quantum randomness is irreducible [5, 6] and a manifestation of mathematical undecidability. Any formal system is based on axioms, which are propositions that are dened to be true. A proposition is logically independent from a given set of axioms if it can neither be proved nor disproved from the axioms. If a proposition is independent from the axioms, neither the proposition itself nor its negation creates an inconsistency together with the axiomatic system. ^We propose a new link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms and show that quantum measurements are capable of revealing whether a given proposition is decidable or not within the axiomatic system. Whenever a mathematical proposition is undecidable within the axioms encoded in the state, the measurement associated with the proposition gives random outcomes. Our results support the view that quantum randomness is irreducible and a manifestation of mathematical undecidability. Whenever a proposition and a given set of axioms together contain more information than the axioms themselves, the proposition can neither be proved nor disproved from the axioms { it is mathematically undecidable [1, 2]. Here we propose a novel link between mathematical undecidability and quantum physics. We demonstrate that the states of elementary quantum systems are capable of encoding mathematical axioms. Quantum mechanics imposes an upper limit on how much information can be encoded in a quantum state [3, 4], thus limiting the information content of the set of axioms. We show that quantum measurements are capable of revealing whether a given proposition is decidable or not. Whenever a mathematical proposition is undecidable within the system of axioms encoded in the state, the measurement associated with the proposition gives random outcomes. This allows for an experimental test of mathematical undecidability by realizing in the laboratory both the actual quantum states and the required quantum measurements. (To illustrate these ideas, we conducted experiments using the polarization of photons.) Our results support the view that quantum randomness is irreducible [5, 6] and a manifestation of mathematical undecidability. Any formal system is based on axioms, which are propositions that are dened to be true. A proposition is logically independent from a given set of axioms if it can neither be proved nor disproved from the axioms. If a proposition is independent from the axioms, neither the proposition itself nor its negation creates an inconsistency together with the axiomatic system. ^

Dec 1, 20081 citation

Analysis of Quantum Computers and Randomness

Deepak Chahal, Preethi Ravichandran Kumar

Apr 21, 20200 citations

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.