Satisfiability problems and algebras of boolean constraint system games

• URL: http://arxiv.org/abs/2310.07901v2
• Date: Wed, 15 Jan 2025 13:38:03 GMT
• Title: Satisfiability problems and algebras of boolean constraint system games
• Authors: Connor Paddock, William Slofstra,
• Abstract summary: We show that certain reductions between constraint systems lead to $*$-homomorphisms between the BCS algebras of the systems.<n>We also show that the question of whether or not there is a non-hyperlinear group is linked to dichotomy theorems for $mathcalRmathcalU$-satisfiability.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Mermin and Peres showed that there are boolean constraint systems (BCSs) which are not satisfiable, but which are satisfiable with quantum observables. This has led to a burgeoning theory of quantum satisfiability for constraint systems, connected to nonlocal games and quantum contextuality. In this theory, different types of quantum satisfying assignments can be understood as representations of the BCS algebra of the system. This theory is closely related to the theory of synchronous games and algebras, and every synchronous algebra is a BCS algebra and vice-versa. The purpose of this paper is to further develop the role of BCS algebras in this theory, and tie up some loose ends: We give a new presentation of BCS algebras in terms of joint spectral projections, and show that it is equivalent to the standard definition. We construct a constraint system which is $C^*$-satisfiable but not tracially satisfiable. We show that certain reductions between constraint systems lead to $*$-homomorphisms between the BCS algebras of the systems, and use this to streamline and strengthen several results of Atserias, Kolaitis, and Severini on analogues of Schaefer's dichotomy theorem. In particular, we show that the question of whether or not there is a non-hyperlinear group is linked to dichotomy theorems for $\mathcal{R}^{\mathcal{U}}$-satisfiability.

Related papers

• A unified approach to quantum resource theories and a new class of free operations [0.0]
  In quantum resource theories (QRTs) certain quantum states and operations are deemed more valuable than others.<n>We argue that QRTs follow from the choice of a preferred algebraic structure $mathcalE$ to be preserved, thus setting the free operations as the automorphisms of $mathcalE$.<n>We show that our new set of operations map free states to free states, as well as determine more general situations where these transformations strictly do not increase the resource of a state.
  arXiv  Detail & Related papers  (2025-07-14T22:50:47Z)
• Partitions in quantum theory [0.0]
  In quantum theory, subsystems are usually framed as sub-C* algebras of the algebra of operators on the global system.<n>We present a definition of partitions into an arbitrary number of parts, each of which is a possibly non-factor sub-C* algebra.<n>We discuss its physical interpretation and study its properties, in particular with regards to the structure of algebras' centres.
  arXiv  Detail & Related papers  (2025-06-27T13:36:48Z)
• Stark-Coleman Invariants and Quantum Lower Bounds: An Integrated Framework for Real Quadratic Fields [0.0]
  Stark-Coleman invariants $kappa_p(K) = log_p left( fracvarepsilon_mathrmSt,psigma(varepsilon_mathrmSt,p) mod pmathrmord_p(Delta_K)$ through a synthesis of $p$-adic Hodge theory and extended Coleman integration.<n>We show that Stark units constrain the geometric organization of class groups, providing theoretical insight into computational complexity barriers.
  arXiv  Detail & Related papers  (2025-06-09T11:06:17Z)
• Packaged Quantum States and Symmetry: A Group-Theoretic Approach to Gauge-Invariant Packaged Entanglements [0.0]
  A packaged quantum state refers to a quantum state that includes an inseparable block of internal quantum numbers. We show that in multiparticle quantum systems, any nontrivial representation of a finite or compact group induces packaged entanglement. The results may be useful for applications in exotic hadron spectroscopy, extended symmetries in quantum field theory, and quantum technologies.
  arXiv  Detail & Related papers  (2025-03-26T07:35:58Z)
• Connecting classical finite exchangeability to quantum theory [69.62715388742298]
  Exchangeability is a fundamental concept in probability theory and statistics. We show how a de Finetti-like representation theorem for finitely exchangeable sequences requires a mathematical representation which is formally equivalent to quantum theory.
  arXiv  Detail & Related papers  (2023-06-06T17:15:19Z)
• Correspondence between open bosonic systems and stochastic differential equations [77.34726150561087]
  We show that there can also be an exact correspondence at finite $n$ when the bosonic system is generalized to include interactions with the environment. A particular system with the form of a discrete nonlinear Schr"odinger equation is analyzed in more detail.
  arXiv  Detail & Related papers  (2023-02-03T19:17:37Z)
• Quantum computing with anyons: an $F$-matrix and braid calculator [0.0]
  We introduce a pentagon equation solver, available as part of SageMath, and use it to construct braid group representations associated to certain anyon systems. We present anyons abstractly as sets of labels together with a collection of data satisfying a number of axioms. In the language of RFCs, our solver can produce $F$-matrices for anyon systems corresponding to multiplicity-free fusion rings.
  arXiv  Detail & Related papers  (2022-12-01T19:31:17Z)
• Quantum Mechanics as a Theory of Incompatible Symmetries [77.34726150561087]
  We show how classical probability theory can be extended to include any system with incompatible variables. We show that any probabilistic system (classical or quantal) that possesses incompatible variables will show not only uncertainty, but also interference in its probability patterns.
  arXiv  Detail & Related papers  (2022-05-31T16:04:59Z)
• Quantum scrambling of observable algebras [0.0]
  quantum scrambling is defined by how the associated physical degrees of freedom get mixed up with others by the dynamics. This is accomplished by introducing a measure, the geometric algebra anti-correlator (GAAC) of the self-orthogonalization of the commutant of $cal A$ induced by the dynamics. For generic energy spectrum we find explicit expressions for the infinite-time average of the GAAC which encode the relation between $cal A$ and the full system of Hamiltonian eigenstates.
  arXiv  Detail & Related papers  (2021-07-02T14:30:58Z)
• Quantum double aspects of surface code models [77.34726150561087]
  We revisit the Kitaev model for fault tolerant quantum computing on a square lattice with underlying quantum double $D(G)$ symmetry. We show how our constructions generalise to $D(H)$ models based on a finite-dimensional Hopf algebra $H$.
  arXiv  Detail & Related papers  (2021-06-25T17:03:38Z)
• Quantum Relativity of Subsystems [58.720142291102135]
  We show that different reference frame perspectives induce different sets of subsystem observable algebras, which leads to a gauge-invariant, frame-dependent notion of subsystems and entanglement. Such a QRF perspective does not inherit the distinction between subsystems in terms of the corresponding tensor factorizability of the kinematical Hilbert space and observable algebra. Since the condition for this to occur is contingent on the choice of QRF, the notion of subsystem locality is frame-dependent.
  arXiv  Detail & Related papers  (2021-03-01T19:00:01Z)
• Sub-bosonic (deformed) ladder operators [62.997667081978825]
  We present a class of deformed creation and annihilation operators that originates from a rigorous notion of fuzziness. This leads to deformed, sub-bosonic commutation relations inducing a simple algebraic structure with modified eigenenergies and Fock states. In addition, we investigate possible consequences of the introduced formalism in quantum field theories, as for instance, deviations from linearity in the dispersion relation for free quasibosons.
  arXiv  Detail & Related papers  (2020-09-10T20:53:58Z)
• Quantum information theory and Fourier multipliers on quantum groups [0.0]
  We compute the exact values of the minimum output entropy and the completely bounded minimal entropy of quantum channels acting on matrix algebras. Our results use a new and precise description of bounded Fourier multipliers from $mathrmL1(mathbbG)$ into $mathrmLp(mathbbG)$ for $1 p leq infty$ where $mathbbG$ is a co-amenable locally compact quantum group.
  arXiv  Detail & Related papers  (2020-08-27T09:47:10Z)
• PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations [77.34726150561087]
  We introduce the PBS-calculus to represent and reason on quantum computations involving coherent control of quantum operations. We equip the language with an equational theory, which is proved to be sound and complete. We consider applications like the implementation of controlled permutations and the unrolling of loops.
  arXiv  Detail & Related papers  (2020-02-21T16:15:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.