The fixed angle conjecture for QAOA on regular MaxCut graphs

• URL: http://arxiv.org/abs/2107.00677v2
• Date: Mon, 19 Jul 2021 17:20:20 GMT
• Title: The fixed angle conjecture for QAOA on regular MaxCut graphs
• Abstract summary: We provide numerical evidence for a fixed angle conjecture for $p12$. These fixed angles serve for an optimization-free version of QAOA, and have universally good performance on any 3 regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are close" to global optimum.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for $p>2$. A recent work \cite{Wurtz_guarantee} computing MaxCut performance guarantees for 3-regular graphs conjectures that any $d$-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for $p<12$. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA, and have universally good performance on any 3 regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are ``close" to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for $p\geq 11$.

Related papers

• A Unified Complexity-Algorithm Account of Constant-Round QAOA Expectation Computation [5.137643077079792]
  We show that for general graphs and any fixed round $pge2$, exactly evaluating the expectation of fixed-round QAOA at prescribed angles is $mathrmNP$-hard.<n>We extend the framework to general Binary Unconstrained Combinatorial Optimization (BUCO)
  arXiv  Detail & Related papers  (2025-11-25T11:35:37Z)
• Graph Random Features for Scalable Gaussian Processes [52.89901965157282]
  We study the application of graph random features (GRFs) to scalable Gaussian processes on discrete input spaces.<n>We prove that (under mild assumptions) Bayesian inference with GRFs enjoys $O(N3/2)$ time complexity with respect to the number of nodes $N$, compared to $O(N3)$ for exact kernels.
  arXiv  Detail & Related papers  (2025-09-03T20:13:23Z)
• Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA [0.0]
  We present a new QAOA ansatz that introduces only one additional parameter to the standard ansatz. We derive a general formula for our new ansatz at $p=1$ and analytically show an improvement in the approximation ratio for cycle graphs.
  arXiv  Detail & Related papers  (2024-11-07T22:20:01Z)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• On Convergence of Incremental Gradient for Non-Convex Smooth Functions [63.51187646914962]
  In machine learning and network optimization, algorithms like shuffle SGD are popular due to minimizing the number of misses and good cache. This paper delves into the convergence properties SGD algorithms with arbitrary data ordering.
  arXiv  Detail & Related papers  (2023-05-30T17:47:27Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems. We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$. We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
  arXiv  Detail & Related papers  (2022-12-03T02:45:23Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  We study high-probability regret bounds for adversarial $K$-armed bandits with time-varying feedback graphs over $T$ rounds. We develop an algorithm that achieves the optimal regret $widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$ with high probability. We also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs.
  arXiv  Detail & Related papers  (2022-10-04T04:36:15Z)
• The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model [0.0]
  The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to optimization problems. We give an iterative formula to evaluate performance for any $D$ at any depth $p$. We make an optimistic conjecture that the QAOA, as $p$ goes to infinity, will achieve the Parisi value.
  arXiv  Detail & Related papers  (2021-10-27T06:35:59Z)
• Learning Sparse Graph with Minimax Concave Penalty under Gaussian Markov Random Fields [51.07460861448716]
  This paper presents a convex-analytic framework to learn from data. We show that a triangular convexity decomposition is guaranteed by a transform of the corresponding to its upper part.
  arXiv  Detail & Related papers  (2021-09-17T17:46:12Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Local classical MAX-CUT algorithm outperforms $p=2$ QAOA on high-girth regular graphs [0.0]
  We show that for all degrees $D ge 2$ of girth $> 5$, QAOA$ has a larger expected cut fraction than QAOA$$ on $G$. We conjecture that for every constant $p$, there exists a local classical MAX-CUT algorithm that performs as well as QAOA$_p$ on all graphs.
  arXiv  Detail & Related papers  (2021-01-14T09:17:20Z)
• MAXCUT QAOA performance guarantees for p >1 [0.0]
  We obtain worst case performance guarantees for $p=2$ and $3$ QAOA for MAXCUT on uniform 3-regular graphs. We conjecture a hierarchy for all $p$, where worst case graphs have with no cycles $leq 2p+1$.
  arXiv  Detail & Related papers  (2020-10-21T18:00:12Z)
• The Quantum Approximate Optimization Algorithm Needs to See the Whole Graph: Worst Case Examples [6.810856082577402]
  The Quantum Approximate Optimization Algorithm can be applied to search problems on graphs with a cost function that is a sum of terms corresponding to the edges. We show that the QAOA with $(d-1)2p nA$ for any $A1$, can only achieve an approximation ratio of 1/2 for Max-Cut on bipartite random d-regular graphs for d large.
  arXiv  Detail & Related papers  (2020-05-18T14:23:09Z)

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.