-
The Structure of Emulations in Classical Spin Models: Modularity and Universality
Authors:
Tobias Reinhart,
Benjamin Engel,
Gemma De les Coves
Abstract:
The theory of spin models intersects with condensed matter physics, complex systems, graph theory, combinatorial optimization, computational complexity and neural networks. Many ensuing applications rely on the fact that complicated spin models can be transformed to simpler ones. What is the structure of such transformations? Here, we provide a framework to study and construct emulations between s…
▽ More
The theory of spin models intersects with condensed matter physics, complex systems, graph theory, combinatorial optimization, computational complexity and neural networks. Many ensuing applications rely on the fact that complicated spin models can be transformed to simpler ones. What is the structure of such transformations? Here, we provide a framework to study and construct emulations between spin models. A spin model is a set of spin systems, and emulations are efficiently computable simulations with arbitrary energy cut-off, where a source spin system simulates a target system if, below the cut-off, the target Hamiltonian is encoded in the source Hamiltonian. We prove that emulations preserve important properties, as they induce reductions between computational problems such as computing ground states, approximating partition functions and approximate sampling from Boltzmann distributions. Emulations are modular (they can be added, scaled and composed), and allow for universality, i.e. certain spin models have maximal reach. We prove that a spin model is universal if and only if it is scalable, closed and functional complete. Because the characterization is constructive, it provides a step-by-step guide to construct emulations. We prove that the 2d Ising model with fields is universal, for which we also provide two new crossing gadgets. Finally, we show that simulations can be computed by linear programs. While some ideas of this work are contained in [1], we provide new definitions and theorems. This framework provides a toolbox for applications involving emulations of spin models.
△ Less
Submitted 1 August, 2024; v1 submitted 18 July, 2024;
originally announced July 2024.
-
Epistemic Horizons From Deterministic Laws: Lessons From a Nomic Toy Theory
Authors:
Johannes Fankhauser,
Tomáš Gonda,
Gemma De les Coves
Abstract:
Quantum theory has an epistemic horizon, i.e. exact values cannot be assigned simultaneously to incompatible physical quantities. As shown by Spekkens' toy theory, positing an epistemic horizon akin to Heisenberg's uncertainty principle in a classical mechanical setting also leads to a plethora of quantum phenomena. We introduce a deterministic theory - nomic toy theory - in which information gath…
▽ More
Quantum theory has an epistemic horizon, i.e. exact values cannot be assigned simultaneously to incompatible physical quantities. As shown by Spekkens' toy theory, positing an epistemic horizon akin to Heisenberg's uncertainty principle in a classical mechanical setting also leads to a plethora of quantum phenomena. We introduce a deterministic theory - nomic toy theory - in which information gathering agents are explicitly modelled as physical systems. Our main result shows the presence of an epistemic horizon for such agents. They can only simultaneously learn the values of observables whose Poisson bracket vanishes. Therefore, nomic toy theory has incompatible measurements and the complete state of a physical system cannot be known. The best description of a system by an agent is via an epistemic state of Spekkens' toy theory. Our result reconciles us to measurement uncertainty as an aspect of the inseparability of subjects and objects. Significantly, the claims follow even though nomic toy theory is essentially classical. This work invites further investigations of epistemic horizons, such as the one of (full) quantum theory.
△ Less
Submitted 28 June, 2024; v1 submitted 25 June, 2024;
originally announced June 2024.
-
An Invitation to Universality in Physics, Computer Science, and Beyond
Authors:
Tomáš Gonda,
Gemma De les Coves
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 acce…
▽ More
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).
△ Less
Submitted 24 June, 2024;
originally announced June 2024.
-
Positive Moments Forever: Undecidable and Decidable Cases
Authors:
Gemma De les Coves,
Joshua Graf,
Andreas Klingler,
Tim Netzer
Abstract:
Is there an algorithm to determine attributes such as positivity or non-zeroness of linear recurrence sequences? This long-standing question is known as Skolem's problem. In this paper, we study the complexity of an equivalent problem, namely the (generalized) moment membership problem for matrices. We show that this problem is decidable for orthogonal, unitary and real eigenvalue matrices, and un…
▽ More
Is there an algorithm to determine attributes such as positivity or non-zeroness of linear recurrence sequences? This long-standing question is known as Skolem's problem. In this paper, we study the complexity of an equivalent problem, namely the (generalized) moment membership problem for matrices. We show that this problem is decidable for orthogonal, unitary and real eigenvalue matrices, and undecidable for matrices over certain commutative and non-commutative polynomial rings. Our results imply that the positivity problem for simple unitary linear recurrence sequences is decidable, and is undecidable for linear recurrence sequences over the ring of commutative polynomials. As a byproduct, we prove a free version of Polya's theorem.
△ Less
Submitted 23 April, 2024;
originally announced April 2024.
-
Beyond Operator Systems
Authors:
Gemma De les Coves,
Mirte van der Eyden,
Tim Netzer
Abstract:
Operator systems connect operator algebra, free semialgebraic geometry and quantum information theory. In this work we generalize operator systems and many of their theorems. While positive semidefinite matrices form the underlying structure of operator systems, our work shows that these can be promoted to far more general structures. For instance, we prove a general extension theorem which unifie…
▽ More
Operator systems connect operator algebra, free semialgebraic geometry and quantum information theory. In this work we generalize operator systems and many of their theorems. While positive semidefinite matrices form the underlying structure of operator systems, our work shows that these can be promoted to far more general structures. For instance, we prove a general extension theorem which unifies the well-known homomorphism theorem, Riesz' extension theorem, Farkas' lemma and Arveson's extension theorem. On the other hand, the same theorem gives rise to new vector-valued extension theorems, even for invariant maps, when applied to other underlying structures. We also prove generalized versions of the Choi-Kraus representation, Choi-Effros theorem, duality of operator systems, factorizations of completely positive maps, and more, leading to new results even for operator systems themselves. In addition, our proofs are shorter and simpler, revealing the interplay between cones and tensor products, captured elegantly in terms of star autonomous categories. This perspective gives rise to new connections between group representations, mapping cones and topological quantum field theory, as they correspond to different instances of our framework and are thus siblings of operator systems.
△ Less
Submitted 21 December, 2023;
originally announced December 2023.
-
A Framework for Universality in Physics, Computer Science, and Beyond
Authors:
Tomáš Gonda,
Tobias Reinhart,
Sebastian Stengele,
Gemma De les Coves
Abstract:
Turing machines and spin models share a notion of universality according to which some simulate all others. Is there a theory of universality that captures this notion? We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and more. By identifying necessary conditio…
▽ More
Turing machines and spin models share a notion of universality according to which some simulate all others. Is there a theory of universality that captures this notion? We set up a categorical framework for universality which includes as instances universal Turing machines, universal spin models, NP completeness, top of a preorder, denseness of a subset, and more. By identifying necessary conditions for universality, we show that universal spin models cannot be finite. We also characterize when universality can be distinguished from a trivial one and use it to show that universal Turing machines are non-trivial in this sense. Our framework allows not only to compare universalities within each instance, but also instances themselves. We leverage a Fixed Point Theorem inspired by a result of Lawvere to establish that universality and negation give rise to unreachability (such as uncomputability). As such, this work sets the basis for a unified approach to universality and invites the study of further examples within the framework.
△ Less
Submitted 3 September, 2024; v1 submitted 30 June, 2023;
originally announced July 2023.
-
Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations
Authors:
Andreas Klingler,
Tim Netzer,
Gemma De les Coves
Abstract:
The matrix rank and its positive versions are robust for small approximations, i.e. they do not decrease under small perturbations. In contrast, the multipartite tensor rank can collapse for arbitrarily small errors, i.e. there may be a gap between rank and border rank, leading to instabilities in the optimization over sets with fixed tensor rank. Can multipartite positive ranks also collapse for…
▽ More
The matrix rank and its positive versions are robust for small approximations, i.e. they do not decrease under small perturbations. In contrast, the multipartite tensor rank can collapse for arbitrarily small errors, i.e. there may be a gap between rank and border rank, leading to instabilities in the optimization over sets with fixed tensor rank. Can multipartite positive ranks also collapse for small perturbations? In this work, we prove that multipartite positive and invariant tensor decompositions exhibit gaps between rank and border rank, including tensor rank purifications and cyclic separable decompositions. We also prove a correspondence between positive decompositions and membership in certain sets of multipartite probability distributions, and leverage the gaps between rank and border rank to prove that these correlation sets are not closed. It follows that testing membership of probability distributions arising from resources like translational invariant Matrix Product States is impossible in finite time. Overall, this work sheds light on the instability of ranks and the unique behavior of bipartite systems.
△ Less
Submitted 26 April, 2023;
originally announced April 2023.
