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

arXiv:2406.16607

An Invitation to Universality in Physics, Computer Science, and Beyond

Tomáš Gonda, Coves, Gemma De les

Published Jun 24, 2024• 0 citations
arXivHTMLPDF

Abstract

A universal Turing machine is a powerful concept - a single device can compute any function that is computable. A universal spin model, similarly, is a class of physical systems whose low energy behavior simulates that of any spin system. Our categorical framework for universality (arXiv:2307.06851) captures these and other examples of universality as instances. In this article, we present an accessible account thereof with a focus on its basic ingredients and ways to use it. Specifically, we show how to identify necessary conditions for universality, compare types of universality within each instance, and establish that universality and negation give rise to unreachability (such as uncomputability).

DOI
10.48550/arxiv.2406.16607

Related papers

Deutsch's Universal Quantum Turing Machine (Revisited)

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

Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.

arXiv:quant-ph/0701108•Jan 16, 2007•4 citations

Towards Observable Quantum Turing Machines: Fundamentals, Computational Power, and Universality

Simon Perdrix

We study the observation of quantum Turing machines by allowing interactions between a quantum machine and its environment during the computation, whereas a quantum Turing machine --original model introduced by Deutsch-- remains isolated. We show that the introduction of observations leads to a weakening of the well formedness conditions of quantum Turing machines such that any (reversible or not) classical Turing machine is a special instance of a quantum machine. Moreover, observation of quantum Turing machines provides a formal solution to the halting process problem: the impossibility to know whether a given quantum Turing machine has actually reached its halting state. It also provides a more realistic abstract architecture of a quantum computer while most of the physical proposals of quantum computers are based on an hybrid classical-quantum architecture. However, we show that a natural formalisation of an observable quantum Turing machines leads to an over-powerful model solving undecidable problems. As a consequence, we introduce a restricted version of observable quantum Turing machines and we show that, under this restriction, any observable quantum Turing machine can be efficiently simulated by a quantum Turing machine. Finally, we discuss the potential application of the observable quantum Turing machine in the quest of a universal quantum Turing machine while recent papers have pointed out that a classical control is a key feature of a universal quantum machine.

•Jan 1, 2011•0 citations

General Conditions for Universality of Quantum Hamiltonians

Tamara Kohler, Stephen Piddock, Johannes Bausch +1 more

Recent work has demonstrated the existence of universal Hamiltonians-simple spin-lattice models that can simulate any other quantum many-body system to any desired level of accuracy.Until now, proofs of universality have relied on explicit constructions, tailored to each specific family of universal Hamiltonians.In this work, we go beyond this approach and completely classify the simulation ability of quantum Hamiltonians by their complexity classes.We do this by deriving necessary and sufficient complexitytheoretic conditions characterizing universal quantum Hamiltonians.Although the result concerns the theory of analog Hamiltonian simulation-a promising application of near-term quantum technology-the proof relies on abstract complexity-theoretic concepts and the theory of quantum computation.As well as providing simplified proofs of previous Hamiltonian universality results and offering a route to new universal constructions, the results in this paper give insight into the origins of universality; for example, finally explaining the previously noted coincidences between families of universal Hamiltonian and classes of Hamiltonians appearing in complexity theory.

arXiv:2101.12319•PRX Quantum•Jan 13, 2022•9 citations

Increasing the Speed of Quantum Logic Gates in Spin Qubits with Inductors

Wolfe, Michael

Universal computing can be dated to 1903 when Alan Turing’s theoretical model of the Turing machine led a large-scale innovative revolution towards digital computing machines.¹ The next milestone is to process and control information at its fundamental level — quantum states of particles. Richard Feynman first pointed out that as certain types of computational problems get more complex, classical bits fail to give efficient answers.² For example, when simulating quantum mechanics, the amount of memory needed to describe a quantum system increases exponentially with the number of its components. A new device — a quantum computer — is therefore highly sought after by physicists.³

•Jan 1, 2016•0 citations

Universal spin models are universal approximators in machine learning

Tobias Reinhart, Gemma De les Coves

One of the theoretical pillars that sustain certain machine learning models are universal approximation theorems, which prove that they can approximate all functions from a function class to arbitrary precision. Independently, classical spin models are termed universal if they can reproduce the behavior of any other spin model in their low energy sector. Universal spin models have been characterized via sufficient and necessary conditions, showing that simple models such as the 2d Ising with fields are universal. In this work, we prove that universal spin models are universal approximators of probability distributions. This enables us to leverage the characterization of the former to reveal conditions which are sufficient for universal approximation. Deriving universal approximation theorems thus amounts to verifying these conditions, yielding a unified recipe for universal approximation theorems applicable to a wide range of models. We explicitly test this recipe for restricted and deep Boltzmann machines, as well as for deep belief networks. This work illustrates that independently discovered universality statements may be intimately related, enabling the transfer of results.

arXiv:2507.07669•Physical review. E•Mar 9, 2026•0 citations

Simple universal models capture all classical spin physics

Gemma De las Cuevas, Toby S. Cubitt

Spin models are used in many studies of complex systems because they exhibit rich macroscopic behavior despite their microscopic simplicity. Here, we prove that all the physics of every classical spin model is reproduced in the low-energy sector of certain "universal models," with at most polynomial overhead. This holds for classical models with discrete or continuous degrees of freedom. We prove necessary and sufficient conditions for a spin model to be universal and show that one of the simplest and most widely studied spin models, the two-dimensional Ising model with fields, is universal. Our results may facilitate physical simulations of Hamiltonians with complex interactions.

arXiv:1406.5955•Science•Mar 10, 2016•114 citations
A universal Turing machine is a powerful concept - a single device can compute any function that is computable. A universal spin model, similarly, is a class of physical systems whose low energy behavior simulates that of any spin system. Our categorical framework for universality (arXiv:2307.06851) captures these and other examples of universality as instances. In this article, we present an accessible account thereof with a focus on its basic ingredients and ways to use it. Specifically, we show how to identify necessary conditions for universality, compare types of universality within each instance, and establish that universality and negation give rise to unreachability (such as uncomputability).
Deutsch, Feynman, and Manin viewed quantum computing as a kind of universal physical simulation procedure. Much of the writing about quantum Turing machines has shown how these machines can simulate an arbitrary unitary transformation on a finite number of qubits. This interesting problem has been addressed most famously in a paper by Deutsch, and later by Bernstein and Vazirani. Quantum Turing machines form a class closely related to deterministic and probabilistic Turing machines and one might hope to find a universal machine in this class. A universal machine is the basis of a notion of programmability. The extent to which universality has in fact been established by the pioneers in the field is examined and a key notion in theoretical computer science (universality) is scrutinised. In a forthcoming paper, the authors will also consider universality in the quantum gate model.
We study the observation of quantum Turing machines by allowing interactions between a quantum machine and its environment during the computation, whereas a quantum Turing machine --original model introduced by Deutsch-- remains isolated. We show that the introduction of observations leads to a weakening of the well formedness conditions of quantum Turing machines such that any (reversible or not) classical Turing machine is a special instance of a quantum machine. Moreover, observation of quantum Turing machines provides a formal solution to the halting process problem: the impossibility to know whether a given quantum Turing machine has actually reached its halting state. It also provides a more realistic abstract architecture of a quantum computer while most of the physical proposals of quantum computers are based on an hybrid classical-quantum architecture. However, we show that a natural formalisation of an observable quantum Turing machines leads to an over-powerful model solving undecidable problems. As a consequence, we introduce a restricted version of observable quantum Turing machines and we show that, under this restriction, any observable quantum Turing machine can be efficiently simulated by a quantum Turing machine. Finally, we discuss the potential application of the observable quantum Turing machine in the quest of a universal quantum Turing machine while recent papers have pointed out that a classical control is a key feature of a universal quantum machine.
Recent work has demonstrated the existence of universal Hamiltonians-simple spin-lattice models that can simulate any other quantum many-body system to any desired level of accuracy.Until now, proofs of universality have relied on explicit constructions, tailored to each specific family of universal Hamiltonians.In this work, we go beyond this approach and completely classify the simulation ability of quantum Hamiltonians by their complexity classes.We do this by deriving necessary and sufficient complexitytheoretic conditions characterizing universal quantum Hamiltonians.Although the result concerns the theory of analog Hamiltonian simulation-a promising application of near-term quantum technology-the proof relies on abstract complexity-theoretic concepts and the theory of quantum computation.As well as providing simplified proofs of previous Hamiltonian universality results and offering a route to new universal constructions, the results in this paper give insight into the origins of universality; for example, finally explaining the previously noted coincidences between families of universal Hamiltonian and classes of Hamiltonians appearing in complexity theory.
Universal computing can be dated to 1903 when Alan Turing’s theoretical model of the Turing machine led a large-scale innovative revolution towards digital computing machines.¹ The next milestone is to process and control information at its fundamental level — quantum states of particles. Richard Feynman first pointed out that as certain types of computational problems get more complex, classical bits fail to give efficient answers.² For example, when simulating quantum mechanics, the amount of memory needed to describe a quantum system increases exponentially with the number of its components. A new device — a quantum computer — is therefore highly sought after by physicists.³
One of the theoretical pillars that sustain certain machine learning models are universal approximation theorems, which prove that they can approximate all functions from a function class to arbitrary precision. Independently, classical spin models are termed universal if they can reproduce the behavior of any other spin model in their low energy sector. Universal spin models have been characterized via sufficient and necessary conditions, showing that simple models such as the 2d Ising with fields are universal. In this work, we prove that universal spin models are universal approximators of probability distributions. This enables us to leverage the characterization of the former to reveal conditions which are sufficient for universal approximation. Deriving universal approximation theorems thus amounts to verifying these conditions, yielding a unified recipe for universal approximation theorems applicable to a wide range of models. We explicitly test this recipe for restricted and deep Boltzmann machines, as well as for deep belief networks. This work illustrates that independently discovered universality statements may be intimately related, enabling the transfer of results.
Spin models are used in many studies of complex systems because they exhibit rich macroscopic behavior despite their microscopic simplicity. Here, we prove that all the physics of every classical spin model is reproduced in the low-energy sector of certain "universal models," with at most polynomial overhead. This holds for classical models with discrete or continuous degrees of freedom. We prove necessary and sufficient conditions for a spin model to be universal and show that one of the simplest and most widely studied spin models, the two-dimensional Ising model with fields, is universal. Our results may facilitate physical simulations of Hamiltonians with complex interactions.