Approximation algorithms for noncommutative CSPs

• URL: http://arxiv.org/abs/2312.16765v2
• Date: Sat, 28 Sep 2024 20:54:23 GMT
• Title: Approximation algorithms for noncommutative CSPs
• Authors: Eric Culf, Hamoon Mousavi, Taro Spirig,
• Abstract summary: 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.
• Score: 0.0
• License:
• Abstract: 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. A notable example of a noncommutative CSP that is not solvable in polynomial time is NC-Max-$3$-Cut. We present a $0.864$-approximation algorithm for this problem. Our approach extends to a broader class of both classical and noncommutative CSPs. We introduce three key concepts: approximate isometry, relative distribution, and $\ast$-anticommutation, which may be of independent interest.

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)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• KPZ scaling from the Krylov space [83.88591755871734]
  Recently, a superdiffusion exhibiting the Kardar-Parisi-Zhang scaling in late-time correlators and autocorrelators has been reported. Inspired by these results, we explore the KPZ scaling in correlation functions using their realization in the Krylov operator basis.
  arXiv  Detail & Related papers  (2024-06-04T20:57:59Z)
• Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs [0.39901365062418315]
  We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density. For CSPs with even predicates, the algorithmally solves the optimal control problem dual to an extended Parisi variational principle. This gives an optimal fraction of satisfied constraints among algorithms obstructed by the branching overlap gap property of Huang and Sellke.
  arXiv  Detail & Related papers  (2023-10-02T18:55:26Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Bayesian decision-making under misspecified priors with applications to meta-learning [64.38020203019013]
  Thompson sampling and other sequential decision-making algorithms are popular approaches to tackle explore/exploit trade-offs in contextual bandits. We show that performance degrades gracefully with misspecified priors.
  arXiv  Detail & Related papers  (2021-07-03T23:17:26Z)
• Linear semi-infinite programming approach for entanglement quantification [0.0]
  We show the absence of a duality gap between primal and dual problems, even if the entanglement quantifier is not continuous. We implement a central cutting-plane algorithm for LSIP to quantify entanglement between three qubits.
  arXiv  Detail & Related papers  (2020-07-27T19:12:29Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max optimization algorithms encounter problems far greater because of the existence of periodic cycles and similar phenomena. We show that there exist algorithms that do not attract any points of the problem. We illustrate such challenges in simple to almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost
  arXiv  Detail & Related papers  (2020-06-16T10:49:27Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)
• Testing Unsatisfiability of Constraint Satisfaction Problems via Tensor Products [0.8528384027684192]
  We show how to use the tensor decomposition to compute a proof of unsatisfiability efficiently and in parallel. One decomposition yields proofs of unsatisfiability in half the time without sacrificing the quality. Our method is applicable to arbitrary CSPs using the well known dual and hidden variable transformations from an arbitrary CSP to a binary CSP.
  arXiv  Detail & Related papers  (2020-01-31T18:06:52Z)

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.