Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs

• URL: http://arxiv.org/abs/2310.01563v1
• Date: Mon, 2 Oct 2023 18:55:26 GMT
• Title: Local algorithms and the failure of log-depth quantum advantage on sparse random CSPs
• Authors: Antares Chen, Neng Huang, Kunal Marwaha
• Abstract summary: 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.
• Score: 0.39901365062418315
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sellke for Maximum Cut [arXiv:2111.06813] through a connection between random CSPs and mean-field Ising spin glasses. For CSPs with even predicates, the algorithm asymptotically solves a stochastic 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:2110.07847], notably including the Quantum Approximate Optimization Algorithm and all quantum circuits on a bounded-degree architecture of up to $\epsilon \cdot \log n$ depth.

Related papers

• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• The role of quantum and classical correlations in shrinking algorithms for optimization [0.0]
  We study the performance of a shrinking algorithm for optimization problems (COPs) We compare the performance of the algorithm equipped with correlations from the quantum approximate optimization algorithm (QAOA) as well as the classical linear programming (LP) and semi-definite programming (SDP) relaxations. Our results indicate that LP outperforms all other approaches for low-density instances, while SDP excels for high-density problems.
  arXiv  Detail & Related papers  (2024-04-26T08:29:04Z)
• Extending relax-and-round combinatorial optimization solvers with quantum correlations [0.0]
  We introduce a relax-and-round approach embedding the quantum approximate optimization algorithm (QAOA) with $pgeq 1$ layers. We show for many problems, including Sherrington-Kirk glasses, that at $p=1$, it is as accurate as its classical counterpart. We pave the way for an overarching quantum relax-and-round framework with performance on par with some of the best classical algorithms.
  arXiv  Detail & Related papers  (2023-07-11T22:02:01Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• An Asymptotically Optimal Algorithm for the Convex Hull Membership Problem [21.312152185262]
  We study the convex hull membership problem in the pure exploration setting. We present the firstally optimal algorithm called Thompson-CHM, whose modular design consists of a stopping rule and a sampling rule.
  arXiv  Detail & Related papers  (2023-02-03T23:41:53Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• An entanglement perspective on the quantum approximate optimization algorithm [0.0]
  We study the entanglement growth and spread resulting from randomized and optimized QAOA circuits. We also investigate the entanglement spectrum in connection with random matrix theory.
  arXiv  Detail & Related papers  (2022-06-14T17:37:44Z)
• Limitations of Local Quantum Algorithms on Random Max-k-XOR and Beyond [1.8374319565577157]
  We show limitations of generic local algorithms including QAOA on random instances of satisfaction problems (CSPs) Specifically, we show that any generic local algorithm whose assignment to a constraint depends only on a local neighborhood with $o(n)$ other vertices (such as the QAOA at depth less than $ilonlog(n)$) cannot arbitrarily-well approximate CSPs.
  arXiv  Detail & Related papers  (2021-08-13T03:55:22Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity with bounds dependence on the confidence level that is either negative-power or logarithmic. We propose novel stepsize rules for two gradient methods with clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• SGD with shuffling: optimal rates without component convexity and large epoch requirements [60.65928290219793]
  We consider the RandomShuffle (shuffle at the beginning of each epoch) and SingleShuffle (shuffle only once) We establish minimax optimal convergence rates of these algorithms up to poly-log factor gaps. We further sharpen the tight convergence results for RandomShuffle by removing the drawbacks common to all prior arts.
  arXiv  Detail & Related papers  (2020-06-12T05:00:44Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)

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.