Extending relax-and-round combinatorial optimization solvers with quantum correlations

• URL: http://arxiv.org/abs/2307.05821v2
• Date: Wed, 24 Jan 2024 17:20:57 GMT
• Title: Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Authors: Maxime Dupont, Bhuvanesh Sundar
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a relax-and-round approach embedding the quantum approximate optimization algorithm (QAOA) with $p\geq 1$ layers. We show for many problems, including Sherrington-Kirkpatrick spin glasses, that at $p=1$, it is as accurate as its classical counterpart, and maintains the infinite-depth optimal performance guarantee of the QAOA. Employing a different rounding scheme, we prove the method shares the performance of the Goemans-Williamson algorithm for the maximum cut problem on certain graphs. We pave the way for an overarching quantum relax-and-round framework with performance on par with some of the best classical algorithms.

Related papers

• Quantum Algorithm for Online Exp-concave Optimization [30.962392035110135]
  We present quantum online quasi-Newton methods to tackle the problem. Our method approximates the Hessian by quantum estimated inexact gradient. Such regret improves the optimal classical algorithm by a factor of $T2/3$.
  arXiv  Detail & Related papers  (2024-10-25T16:58:44Z)
• A Multilevel Approach For Solving Large-Scale QUBO Problems With Noisy Hybrid Quantum Approximate Optimization [3.3493770627144004]
  We experimentally test how existing quantum processing units (QPUs) perform as subsolvers within a multilevel strategy. We find approximate solutions to $10$ instances of fully connected $82$-qubit Sherrington-Kirkpatrick graphs. We observe that quantum optimization results are competitive regarding the quality of solutions compared to classicals.
  arXiv  Detail & Related papers  (2024-08-14T20:06:32Z)
• 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)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem [6.783232060611114]
  We propose a framework for designing QAOA circuits to solve larger-scale Max-Cut problem. We derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Our framework only consumes $18$ qubits and $0.9950$ approximation ratio on average.
  arXiv  Detail & Related papers  (2023-07-28T02:06:42Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Warm-starting quantum optimization [6.832341432995627]
  We discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of an optimization problem. This allows the quantum algorithm to inherit the performance guarantees of the classical algorithm. It is straightforward to apply the same ideas to other randomized-rounding schemes and optimization problems.
  arXiv  Detail & Related papers  (2020-09-21T18:00:09Z)
• 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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.