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

Texts in computer science

Quantum Universality, Computability, & Complexity

Colin P. Williams

Published Dec 6, 2010• 0 citations
Publisher
DOI
10.1007/978-1-84628-887-6_4

Related papers

Universality, Invariance, and the Foundations of Computational Complexity in the Light of the Quantum Computer

Michael E. Cuffaro

Philosophy of engineering and technology•Jan 1, 2018•9 citations

Universal Computers and Computational Complexity

Stefano Olivares

Lecture notes in physics•Jan 1, 2025•0 citations

Universality and programmability of quantum computers

Willem L. Fouché, Johannes Heidema, Glyn Jones +1 more

arXiv:0710.3329•Theoretical Computer Science•May 19, 2008•5 citations

Quantum theory, the Church–Turing principle and the universal quantum computer

David Deutsch

Abstract It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the 'universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett’s. Some of the numerous connections between the quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the ‘complexity’ or ‘knowledge’ in a physical system than does classical complexity theory.

Proceedings of the Royal Society of London A Mathematical and Physical Sciences•Jul 8, 1985•4,778 citations

Non-Hermitian Computers Need No Complex Numbers

Qi Zhang

In traditional quantum computing, it has been established that real quantum computation augmented with non-Clifford gates is as powerful as universal quantum computation. Here we investigate this phenomenon in the non-Hermitian setting. We show that a non-Hermitian quantum computer equipped with the real gate set ${H, \text{CCNOT}, G}$, where $G = \operatorname{diag}(g^{-1}, g)$ with $g > 0$ and $g \neq 1$, can solve problems in $\text{P}^{\sharp\text{P}}$ in polynomial time, matching the capability of its universal non-Hermitian counterpart ${H, T, \text{CNOT}, G}$. This demonstrates that non-unitarity, rather than universality, is the essential resource, and that complex numbers are unnecessary.

quant-pharXiv:2605.28152•May 28, 2026•0 citations

Universe as quantum computer

Seth Lloyd

This article reviews the history of digital computation, and investigates just how far the concept of computation can be taken. In particular, I address the question of whether the universe itself is in fact a giant computer, and if so, just what kind of computer it is. I will show that the universe can be regarded as a giant quantum computer. The quantum computational model of the universe explains a variety of observed phenomena not encompassed by the ordinary laws of physics. In particular, the model shows that the the quantum computational universe automatically gives rise to a mix of randomness and order, and to both simple and complex systems.

arXiv:1312.4455•Complexity•Sep 1, 1997•105 citations
Abstract It is argued that underlying the Church–Turing hypothesis there is an implicit physical assertion. Here, this assertion is presented explicitly as a physical principle: ‘every finitely realizible physical system can be perfectly simulated by a universal model computing machine operating by finite means’. Classical physics and the universal Turing machine, because the former is continuous and the latter discrete, do not obey the principle, at least in the strong form above. A class of model computing machines that is the quantum generalization of the class of Turing machines is described, and it is shown that quantum theory and the 'universal quantum computer’ are compatible with the principle. Computing machines resembling the universal quantum computer could, in principle, be built and would have many remarkable properties not reproducible by any Turing machine. These do not include the computation of non-recursive functions, but they do include ‘quantum parallelism’, a method by which certain probabilistic tasks can be performed faster by a universal quantum computer than by any classical restriction of it. The intuitive explanation of these properties places an intolerable strain on all interpretations of quantum theory other than Everett’s. Some of the numerous connections between the quantum theory of computation and the rest of physics are explored. Quantum complexity theory allows a physically more reasonable definition of the ‘complexity’ or ‘knowledge’ in a physical system than does classical complexity theory.
In traditional quantum computing, it has been established that real quantum computation augmented with non-Clifford gates is as powerful as universal quantum computation. Here we investigate this phenomenon in the non-Hermitian setting. We show that a non-Hermitian quantum computer equipped with the real gate set H,CCNOT,G{H, \text{CCNOT}, G}H,CCNOT,G, where G=diag⁡(g−1,g)G = \operatorname{diag}(g^{-1}, g)G=diag(g−1,g) with g>0g > 0g>0 and g≠1g \neq 1g=1, can solve problems in P♯P\text{P}^{\sharp\text{P}}P♯P in polynomial time, matching the capability of its universal non-Hermitian counterpart H,T,CNOT,G{H, T, \text{CNOT}, G}H,T,CNOT,G. This demonstrates that non-unitarity, rather than universality, is the essential resource, and that complex numbers are unnecessary.
This article reviews the history of digital computation, and investigates just how far the concept of computation can be taken. In particular, I address the question of whether the universe itself is in fact a giant computer, and if so, just what kind of computer it is. I will show that the universe can be regarded as a giant quantum computer. The quantum computational model of the universe explains a variety of observed phenomena not encompassed by the ordinary laws of physics. In particular, the model shows that the the quantum computational universe automatically gives rise to a mix of randomness and order, and to both simple and complex systems.