Satisfiability of commutative vs. non-commutative CSPs

• URL: http://arxiv.org/abs/2404.11709v3
• Date: Mon, 04 Nov 2024 20:10:14 GMT
• Title: Satisfiability of commutative vs. non-commutative CSPs
• Authors: Andrei A. Bulatov, Stanislav Živný,
• Abstract summary: We show that NP-hard CSPs admit a separation between classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces. We also show that tractable CSPs of unbounded width have no satisfiability gaps of any kind.
• Score: 2.07180164747172
• License:
• Abstract: The Mermin-Peres magic square is a celebrated example of a system of Boolean linear equations that is not (classically) satisfiable but is satisfiable via linear operators on a Hilbert space of dimension four. A natural question is then, for what kind of problems such a phenomenon occurs? Atserias, Kolaitis, and Severini answered this question for all Boolean Constraint Satisfaction Problems (CSPs): For 0-Valid-SAT, 1-Valid-SAT, 2-SAT, Horn-SAT, and Dual Horn-SAT, classical satisfiability and operator satisfiability is the same and thus there is no gap; for all other Boolean CSPs, these notions differ as there are gaps, i.e., there are unsatisfiable instances that are satisfiable via operators on Hilbert spaces. We generalize their result to CSPs on arbitrary finite domains and give an almost complete classification: First, we show that NP-hard CSPs admit a separation between classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces. Second, we show that tractable CSPs of bounded width have no satisfiability gaps of any kind. Finally, we show that tractable CSPs of unbounded width can simulate, in a satisfiability-gap-preserving fashion, linear equations over an Abelian group of prime order $p$; for such CSPs, we obtain a separation of classical satisfiability and satisfiability via operators on infinite-dimensional Hilbert spaces. Furthermore, if $p=2$, such CSPs also have gaps separating classical satisfiability and satisfiability via operators on finite- and infinite-dimensional Hilbert spaces.

Related papers

• RE-completeness of entangled constraint satisfaction problems [0.0]
  Schaefer's theorem shows that CSP languages are either efficiently decidable, or NP-complete. It is possible to extend CSP languages to quantum assignments using the formalism of nonlocal games.
  arXiv  Detail & Related papers  (2024-10-28T17:05:58Z)
• Convergence guarantee for linearly-constrained combinatorial optimization with a quantum alternating operator ansatz [0.0]
  We present a quantum alternating operator ansatz (QAOA$+$) that solves a class of linearly constrained optimization problems. For problems in this class, we devise circuits that provably converge to the optimal solution as the number of circuit layers increases. This analysis extends QAOA$+$ performance guarantees to a more general set of linearly-constrained problems and provides tools for future generalizations.
  arXiv  Detail & Related papers  (2024-09-27T15:23:47Z)
• Approximation algorithms for noncommutative CSPs [0.0]
  Noncommutative constraint satisfaction problems (NC-CSPs) are higher-dimensional operator extensions of classical CSPs. Despite their significance in quantum information, their approximability remains largely unexplored. We introduce three key concepts: approximate isometry, relative distribution, and $ast$-anticommutation.
  arXiv  Detail & Related papers  (2023-12-28T01:22:27Z)
• The Mutual Information In The Vicinity of Capacity-Achieving Input Distributions [6.675805308519987]
  The exact characterization of the slowest decrease of the mutual information with the distance to $Pi_mathcalA$ is determined on small neighborhoods of $Pi_mathcalA$. Results for classical-quantum channels are established under separable output Hilbert space assumption for the quadratic bound and under finite-dimensional output Hilbert space assumption for the exact characterization.
  arXiv  Detail & Related papers  (2023-04-27T14:27:08Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  We show that pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. We also show that focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints.
  arXiv  Detail & Related papers  (2023-01-16T10:30:04Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Continuous percolation in a Hilbert space for a large system of qubits [58.720142291102135]
  The percolation transition is defined through the appearance of the infinite cluster. We show that the exponentially increasing dimensionality of the Hilbert space makes its covering by finite-size hyperspheres inefficient. Our approach to the percolation transition in compact metric spaces may prove useful for its rigorous treatment in other contexts.
  arXiv  Detail & Related papers  (2022-10-15T13:53:21Z)
• The Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) Equation for Two-Dimensional Systems [62.997667081978825]
  Open quantum systems can obey the Franke-Gorini-Kossakowski-Lindblad-Sudarshan (FGKLS) equation. We exhaustively study the case of a Hilbert space dimension of $2$.
  arXiv  Detail & Related papers  (2022-04-16T07:03:54Z)
• Annihilating Entanglement Between Cones [77.34726150561087]
  We show that Lorentz cones are the only cones with a symmetric base for which a certain stronger version of the resilience property is satisfied. Our proof exploits the symmetries of the Lorentz cones and applies two constructions resembling protocols for entanglement distillation.
  arXiv  Detail & Related papers  (2021-10-22T15:02:39Z)
• Bistochastic operators and quantum random variables [0.0]
  We considerintegrable functions $Xrightarrow mathcal B(mathcal H)$ that are positive quantum random variables. We define a seminorm on the span of such functions which in the quotient leads to a Banach space. As in classical majorization theory, we relate majorization in this context to an inequality involving all possible convex functions of a certain type.
  arXiv  Detail & Related papers  (2020-04-30T12:45:54Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

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.