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

Acta Physica Hungarica A) Heavy Ion Physics

A No-Go Theorem for Halting a Universal Quantum Computer

Tien D. Kieu, M. Danos

Published Sep 1, 2001• 7 citations
Publisher
DOI
10.1556/aph.14.2001.1-4.21

Related papers

Skirting around the no-go theorem in measurement-based quantum computation

Thi Ha Kyaw

•Jan 1, 2015•1 citation

Undecidability of Hitting Times in Computably Described Quantum Dynamics: A No-Go Theorem for Universal Time Selection

Katsufumi Matsuura

We study the Unitary Hitting Time Problem (UHTP) in quantum dynamics. Given computably described pure states |a>, |b> and a time-dependent unitary U(t), define the hitting time as the infimum of t > 0 such that the fidelity between U(t)|a> and |b> reaches a fixed threshold (with infinity if the threshold is never reached). We prove that there is no total algorithm that outputs this hitting time for all inputs; equivalently, the total UHTP is undecidable via a reduction from the halting problem. Operationally, we show a no-go theorem: for any fixed accuracy parameters, there is no universal finite-resource protocol that, for all computably described inputs, correctly outputs the hitting time while obeying uniform finite upper bounds on observation time and on dissipation/work. The proofs use reversible computation embedded into unitary dynamics, a fixed-target beacon construction, and a continuous-time lifting via piecewise-constant Hamiltonians. Our results target systems capable of embedding universal computation and complement prior undecidability results such as spectral-gap and quantum-control reachability. We distinguish logical time (inside the equations) from physical/operational time (of preparation, evolution, measurement), and show that universal time-step selection is impossible in both senses. Revised version. The main result has been strengthened to undecidability under a single fixed periodically driven unitary dynamics. The discussion of related work and the computability assumptions have also been expanded.

quant-pharXiv:2512.11006•Dec 12, 2025•0 citations

Remarks on universal quantum computer

Yu Shi

arXiv:quant-ph/9908074•Physics Letters A•Feb 1, 2002•33 citations

Halting of Quantum Turing Machines

Masanao Ozawa

Lecture notes in computer science•Jan 1, 2002•6 citations

Universal fault-tolerant quantum computing with stabilizer codes

Paul Webster, Michael Vasmer, Thomas R. Scruby +1 more

The quantum logic gates used in the design of a quantum computer should be both universal, meaning arbitrary quantum computations can be performed, and fault-tolerant, meaning the gates keep errors from cascading out of control. A number of no-go theorems constrain the ways in which a set of fault-tolerant logic gates can be universal. These theorems are very restrictive, and conventional wisdom holds that a universal fault-tolerant logic gate set cannot be implemented natively, requiring us to use costly distillation procedures for quantum computation. Here, we present a general framework for universal fault-tolerant logic with stabilizer codes, together with a no-go theorem that reveals the very broad conditions constraining such gate sets. Our theorem applies to a wide range of stabilizer code families, including concatenated codes and conventional topological stabilizer codes such as the surface code. The broad applicability of our no-go theorem provides a new perspective on how the constraints on universal fault-tolerant gate sets can be overcome. In particular, we show how nonunitary implementations of logic gates provide a general approach to circumvent the no-go theorem, and we present a rich landscape of constructions for logic gate sets that are both universal and fault-tolerant. That is, rather than restricting what is possible, our no-go theorem provides a signpost to guide us to new, efficient architectures for fault-tolerant quantum computing.

arXiv:2012.05260•Physical Review Research•Feb 4, 2022•31 citations

E8 Harmonic Fixed‑Point Encoding Theorem — E8 Intelligence Research

Andrew Stewart Caldin

Through phi‑scaled inverse rotations of the 240 E8 root vectors at the 132 Hz base phonon, a cascade of resonant fixed points emerges, each encoding a diagonalized linear operator that simultaneously captures halting behavior, self‑reference, and universal quantum gate approximation. The resulting theorem shows that these fixed points form a natural basis for constructing a self‑referential quantum automaton capable of classifying any finite program's halting status via its geometric frequency signature. This provides a geometric bridge between the algebraic diagonalization underlying the halting problem and the physical resonance patterns of the E8 lattice, unifying computation, geometry, and quantum information. Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com

•Sep 29, 2026•0 citations
We study the Unitary Hitting Time Problem (UHTP) in quantum dynamics. Given computably described pure states |a>, |b> and a time-dependent unitary U(t), define the hitting time as the infimum of t > 0 such that the fidelity between U(t)|a> and |b> reaches a fixed threshold (with infinity if the threshold is never reached). We prove that there is no total algorithm that outputs this hitting time for all inputs; equivalently, the total UHTP is undecidable via a reduction from the halting problem. Operationally, we show a no-go theorem: for any fixed accuracy parameters, there is no universal finite-resource protocol that, for all computably described inputs, correctly outputs the hitting time while obeying uniform finite upper bounds on observation time and on dissipation/work. The proofs use reversible computation embedded into unitary dynamics, a fixed-target beacon construction, and a continuous-time lifting via piecewise-constant Hamiltonians. Our results target systems capable of embedding universal computation and complement prior undecidability results such as spectral-gap and quantum-control reachability. We distinguish logical time (inside the equations) from physical/operational time (of preparation, evolution, measurement), and show that universal time-step selection is impossible in both senses. Revised version. The main result has been strengthened to undecidability under a single fixed periodically driven unitary dynamics. The discussion of related work and the computability assumptions have also been expanded.
The quantum logic gates used in the design of a quantum computer should be both universal, meaning arbitrary quantum computations can be performed, and fault-tolerant, meaning the gates keep errors from cascading out of control. A number of no-go theorems constrain the ways in which a set of fault-tolerant logic gates can be universal. These theorems are very restrictive, and conventional wisdom holds that a universal fault-tolerant logic gate set cannot be implemented natively, requiring us to use costly distillation procedures for quantum computation. Here, we present a general framework for universal fault-tolerant logic with stabilizer codes, together with a no-go theorem that reveals the very broad conditions constraining such gate sets. Our theorem applies to a wide range of stabilizer code families, including concatenated codes and conventional topological stabilizer codes such as the surface code. The broad applicability of our no-go theorem provides a new perspective on how the constraints on universal fault-tolerant gate sets can be overcome. In particular, we show how nonunitary implementations of logic gates provide a general approach to circumvent the no-go theorem, and we present a rich landscape of constructions for logic gate sets that are both universal and fault-tolerant. That is, rather than restricting what is possible, our no-go theorem provides a signpost to guide us to new, efficient architectures for fault-tolerant quantum computing.
Through phi‑scaled inverse rotations of the 240 E8 root vectors at the 132 Hz base phonon, a cascade of resonant fixed points emerges, each encoding a diagonalized linear operator that simultaneously captures halting behavior, self‑reference, and universal quantum gate approximation. The resulting theorem shows that these fixed points form a natural basis for constructing a self‑referential quantum automaton capable of classifying any finite program's halting status via its geometric frequency signature. This provides a geometric bridge between the algebraic diagonalization underlying the halting problem and the physical resonance patterns of the E8 lattice, unifying computation, geometry, and quantum information. Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com