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
- 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) - 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) - Bayesian Optimization for QAOA [0.0]
We present a Bayesian optimization procedure to optimise a quantum circuit.
We show that our approach allows for a significant reduction in the number of calls to the quantum circuit.
Our results suggest that the method proposed here is a promising framework to leverage the hybrid nature of QAOA on the noisy intermediate-scale quantum devices.
arXiv Detail & Related papers (2022-09-08T13:59:47Z) - 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) - 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) - 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.