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

Physical Review Letters

Quantum-mechanical computers and uncomputability

Seth Lloyd

Published Aug 9, 1993• 32 citations
Publisher

Abstract

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.

DOI
10.1103/physrevlett.71.943

Related papers

Necessary and Sufficient Conditions for Quantum Computation

Seth Lloyd

Necessary and sufficient conditions are given for a quantummechanical system to possess a coordinate system with respect to which its behaviour at discrete times is that of a universal digital computer. The form of the diagonal representation for the unitary time evolution operator for quantum universal computers is derived; aspects of the transformation between the diagonal representation and the computational representation are shown to be uncomputable. A quantum-mechanical treatment of macroscopic, dissipative computers is given.

Journal of Modern Optics•Dec 1, 1994•19 citations

On the uncomputability of the spectral gap

Seth Lloyd

This paper reviews the 1994 proof that the spectral gap of Hamiltonian quantum systems capable of universal computation is uncomputable.

arXiv:1602.05924•Feb 18, 2016•7 citations

Spectral Structure of Physical Propagation: Modes, structural selection, and organization of dynamics

Jonatan P. camargo

We present a structural formulation of physical propagation in which dynamics are described by a unitary operator $\hat W=f(\hat H)$, associated with a self-adjoint structural operator $\hat H$, and by its bilocal representation $W(x,y)$. Time evolution is formulated as the iterative application of this operator, without assuming differential equations as a fundamental starting point. It is shown that the spectral decomposition of $\hat H$ induces a complete organization of the evolution into independent eigenmodes, each governed by a spectral factor $f(\lambda_n)$. From this structure, it is demonstrated that the bilocal propagation kernel is entirely reconstructed from the spectrum and the eigenvector basis of the structural operator. In the regime of translational homogeneity, it is proven that the propagation operator is diagonalizable in a basis compatible with translations, resulting in the absence of mixing between spectral modes. Outside this regime, it is shown that the support of the kernel $W(x,y)$ completely determines the connectivity of propagation, while its off-diagonal structure encodes relations between distinct nodal states. Additionally, it is established that quantities defined as functions of the structural operator can be evaluated directly in the spectral basis, providing an intrinsic characterization of the dynamics in terms of the spectrum of $\hat H$. The results obtained do not constitute a complete physical theory nor do they establish a direct identification between the operator's spectrum and specific empirical observables. The objective of this work is to make explicit the structural level at which propagation is organized by unitary operators and by their spectral decomposition, providing a coherent basis for further developments.

•Apr 13, 2026•0 citations

Undecidable, Unrecognizable, and Quantum Computing

Michael Siomau

Quantum computing allows us to solve some problems much faster than existing classical algorithms. Yet, the quantum computer has been believed to be no more powerful than the most general computing model—the Turing machine. Undecidable problems, such as the halting problem, and unrecognizable inputs, such as the real numbers, are beyond the theoretical limit of the Turing machine. I suggest a model for a quantum computer, which is less general than the Turing machine, but may solve the halting problem for any task programmable on it. Moreover, inputs unrecognizable by the Turing machine can be recognized by the model, thus breaking the theoretical limit for a computational task. A quantum computer is not just a successful design of the Turing machine as it is widely perceived now, but is a different, less general but more powerful model for computing, the practical realization of which may need different strategies than those in use now.

Quantum Reports•Jul 1, 2020•3 citations

Physical Propagation as Spectral Dynamics of Unitary Operators Foundations of a spectral description of propagation

Jonatan P. camargo

We present a structural formulation of physical dynamics based on discrete unitary propagation, in which the time evolution is directly described by a unitary operator $\hat W=f(\hat H)$ associated with a self-adjoint structural operator $\hat H$. Starting from the relationship between action and phase, $\phi=S/\hbar$, and the variational construction of structural operators, we show that the propagation can be written exactly as the action of a bilocal kernel $W(x,y)$ on the state, in continuity with recent developments of the Action-Phase program. We show that the spectral decomposition of $\hat H$ induces a diagonalization of the unitary propagation, in which the state evolution becomes multiplicative in the eigenvector basis of the structural operator. Consequently, the spectral structure organizes the propagation modes of the system, providing a description in which the dynamics is expressed in a decoupled manner between modes. It is evidenced that the distinction between nodal representation and spectral representation emerges naturally from the operator structure, corresponding to different decompositions of the same state in distinct bases of the same Hilbert space. In the case of translational invariance, the decomposition into Fourier modes is recovered as a particular situation. The results presented do not constitute a complete reconstruction of quantum mechanics nor a general gravitational theory. In particular, aspects of measurement, multiparticle structures, or complete covariant formulations are not treated. The objective of this work is more restricted and precise: to establish a formulation in which the dynamics is determined by the propagation operator and organized by its spectral decomposition, providing a structural layer from which more complete physical descriptions can be developed.

•Apr 9, 2026•0 citations

Quantum Uncomputation of Clean and Dirty Ancilla Qubits

Chenke Liu, Li Zhou, Boning Meng

Automatic uncomputation aims to provide programming-language-level support to facilitate the correct and safe use of ancilla qubits in quantum computing, but efforts have only been made for clean ancillas, leaving dirty ancillas unexplored. We present a unified formalization of the uncomputation of both clean and dirty ancillas. For the first time, we prove that checking the existence of uncomputation is coNP-hard. We introduce two complementary synthesis-oriented existence checking methods: a syntax-directed static reasoning system and a rewrite-based normalization procedure (\RwUnx), together forming a top-down pipeline. We implement \RwUnx in Qiskit. Compared with the state-of-the-art \Reqompx, \RwUnx handles practical benchmarks with complex dependencies where \Reqompx does not, and achieves higher success rates in random-circuit experiments.

cs.PLCross-listedarXiv:2608.09578•Proceedings of the ACM on Programming Languages•Aug 11, 2026•1 citation
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.
Necessary and sufficient conditions are given for a quantummechanical system to possess a coordinate system with respect to which its behaviour at discrete times is that of a universal digital computer. The form of the diagonal representation for the unitary time evolution operator for quantum universal computers is derived; aspects of the transformation between the diagonal representation and the computational representation are shown to be uncomputable. A quantum-mechanical treatment of macroscopic, dissipative computers is given.
We present a structural formulation of physical propagation in which dynamics are described by a unitary operator W^=f(H^)\hat W=f(\hat H)W^=f(H^), associated with a self-adjoint structural operator H^\hat HH^, and by its bilocal representation W(x,y)W(x,y)W(x,y). Time evolution is formulated as the iterative application of this operator, without assuming differential equations as a fundamental starting point. It is shown that the spectral decomposition of H^\hat HH^ induces a complete organization of the evolution into independent eigenmodes, each governed by a spectral factor f(λn)f(\lambda_n)f(λn​). From this structure, it is demonstrated that the bilocal propagation kernel is entirely reconstructed from the spectrum and the eigenvector basis of the structural operator. In the regime of translational homogeneity, it is proven that the propagation operator is diagonalizable in a basis compatible with translations, resulting in the absence of mixing between spectral modes. Outside this regime, it is shown that the support of the kernel W(x,y)W(x,y)W(x,y) completely determines the connectivity of propagation, while its off-diagonal structure encodes relations between distinct nodal states. Additionally, it is established that quantities defined as functions of the structural operator can be evaluated directly in the spectral basis, providing an intrinsic characterization of the dynamics in terms of the spectrum of H^\hat HH^. The results obtained do not constitute a complete physical theory nor do they establish a direct identification between the operator's spectrum and specific empirical observables. The objective of this work is to make explicit the structural level at which propagation is organized by unitary operators and by their spectral decomposition, providing a coherent basis for further developments.
Quantum computing allows us to solve some problems much faster than existing classical algorithms. Yet, the quantum computer has been believed to be no more powerful than the most general computing model—the Turing machine. Undecidable problems, such as the halting problem, and unrecognizable inputs, such as the real numbers, are beyond the theoretical limit of the Turing machine. I suggest a model for a quantum computer, which is less general than the Turing machine, but may solve the halting problem for any task programmable on it. Moreover, inputs unrecognizable by the Turing machine can be recognized by the model, thus breaking the theoretical limit for a computational task. A quantum computer is not just a successful design of the Turing machine as it is widely perceived now, but is a different, less general but more powerful model for computing, the practical realization of which may need different strategies than those in use now.
We present a structural formulation of physical dynamics based on discrete unitary propagation, in which the time evolution is directly described by a unitary operator W^=f(H^)\hat W=f(\hat H)W^=f(H^) associated with a self-adjoint structural operator H^\hat HH^. Starting from the relationship between action and phase, ϕ=S/ℏ\phi=S/\hbarϕ=S/ℏ, and the variational construction of structural operators, we show that the propagation can be written exactly as the action of a bilocal kernel W(x,y)W(x,y)W(x,y) on the state, in continuity with recent developments of the Action-Phase program. We show that the spectral decomposition of H^\hat HH^ induces a diagonalization of the unitary propagation, in which the state evolution becomes multiplicative in the eigenvector basis of the structural operator. Consequently, the spectral structure organizes the propagation modes of the system, providing a description in which the dynamics is expressed in a decoupled manner between modes. It is evidenced that the distinction between nodal representation and spectral representation emerges naturally from the operator structure, corresponding to different decompositions of the same state in distinct bases of the same Hilbert space. In the case of translational invariance, the decomposition into Fourier modes is recovered as a particular situation. The results presented do not constitute a complete reconstruction of quantum mechanics nor a general gravitational theory. In particular, aspects of measurement, multiparticle structures, or complete covariant formulations are not treated. The objective of this work is more restricted and precise: to establish a formulation in which the dynamics is determined by the propagation operator and organized by its spectral decomposition, providing a structural layer from which more complete physical descriptions can be developed.
Automatic uncomputation aims to provide programming-language-level support to facilitate the correct and safe use of ancilla qubits in quantum computing, but efforts have only been made for clean ancillas, leaving dirty ancillas unexplored. We present a unified formalization of the uncomputation of both clean and dirty ancillas. For the first time, we prove that checking the existence of uncomputation is coNP-hard. We introduce two complementary synthesis-oriented existence checking methods: a syntax-directed static reasoning system and a rewrite-based normalization procedure (\RwUnx), together forming a top-down pipeline. We implement \RwUnx in Qiskit. Compared with the state-of-the-art \Reqompx, \RwUnx handles practical benchmarks with complex dependencies where \Reqompx does not, and achieves higher success rates in random-circuit experiments.