Approximation algorithms for noncommutative constraint satisfaction problems

• URL: http://arxiv.org/abs/2312.16765v1
• Date: Thu, 28 Dec 2023 01:22:27 GMT
• Title: Approximation algorithms for noncommutative constraint satisfaction problems
• Authors: Eric Culf, Hamoon Mousavi, and Taro Spirig
• Abstract summary: We study operator - or noncommutative - variants of constraint satisfaction problems (CSPs) We introduce a framework for designing approximation algorithms for noncommutative CSPs. This work is the first to establish approximation ratios for a broader class of noncommutative CSPs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: We study operator - or noncommutative - variants of constraint satisfaction problems (CSPs). These higher-dimensional variants are a core topic of investigation in quantum information, where they arise as nonlocal games and entangled multiprover interactive proof systems (MIP*). The idea of higher-dimensional relaxations of CSPs is also important in the classical literature. For example since the celebrated work of Goemans and Williamson on Max-Cut, higher dimensional vector relaxations have been central in the design of approximation algorithms for classical CSPs. We introduce a framework for designing approximation algorithms for noncommutative CSPs. Prior to this work Max-$2$-Lin$(k)$ was the only family of noncommutative CSPs known to be efficiently solvable. This work is the first to establish approximation ratios for a broader class of noncommutative CSPs. In the study of classical CSPs, $k$-ary decision variables are often represented by $k$-th roots of unity, which generalise to the noncommutative setting as order-$k$ unitary operators. In our framework, using representation theory, we develop a way of constructing unitary solutions from SDP relaxations, extending the pioneering work of Tsirelson on XOR games. Then, we introduce a novel rounding scheme to transform these solutions to order-$k$ unitaries. Our main technical innovation here is a theorem guaranteeing that, for any set of unitary operators, there exists a set of order-$k$ unitaries that closely mimics it. As an integral part of the rounding scheme, we prove a random matrix theory result that characterises the distribution of the relative angles between eigenvalues of random unitaries using tools from free probability.

Related papers

• A competitive NISQ and qubit-efficient solver for the LABS problem [0.0]
  Pauli Correlation.<n>(PCE) has recently been introduced as a qubit-efficient approach to optimization problems within variational quantum algorithms.<n>We extend the PCE-based framework to solve the Low Autocorrelation Binary Sequences (LABS) problem.
  arXiv  Detail & Related papers  (2025-06-20T18:00:02Z)
• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [64.99236464953032]
  We propose a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.<n>By applying our hinge-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution, we achieve a new state-of-the-art complexity of $O(/epsilon)$ for finding an (nearly) $'level KKT solution.
  arXiv  Detail & Related papers  (2025-06-03T06:31:59Z)
• A Practically Scalable Approach to the Closest Vector Problem for Sieving via QAOA with Fixed Angles [0.0]
  NP-hardness of the closest vector problem (CVP) is an important basis for quantum-secure cryptography. Recent work with quantum algorithms indicates the possibility to find close approximations to (constrained) CVP instances. This work explores the potential for a quantum advantage for approximate CVP, without regard for the subsequent factoring claims.
  arXiv  Detail & Related papers  (2025-03-11T13:06:38Z)
• Applying the quantum approximate optimization algorithm to general constraint satisfaction problems [0.0]
  We develop theoretical techniques for analysing the performance of the quantum approximate optimization (QAOA) when applied to random constraint satisfaction problems (CSPs) Our techniques allow us to compute the success probability of QAOA with one layer and given parameters, when applied to randomly generated instances of CSPs. We find that random $k$-SAT seems to be the most promising of these CSPs for demonstrating a quantum-classical separation using QAOA.
  arXiv  Detail & Related papers  (2024-11-26T14:00:34Z)
• 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.