Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
- URL: http://arxiv.org/abs/2406.17383v1
- Date: Tue, 25 Jun 2024 09:02:31 GMT
- Title: Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA
- Authors: Aniello Esposito, Tamuz Danzig,
- Abstract summary: In this work, an implementation of the QAOA2 method for the scalable solution of the MaxCut problem is presented.
The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated.
Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation.
- Score: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Quantum approximate optimization algorithm (QAOA) is a leading hybrid classical-quantum algorithm for solving complex combinatorial optimization problems. QAOA-in-QAOA (QAOA^2) uses a divide-and-conquer heuristic to solve large-scale Maximum Cut (MaxCut) problems, where many subgraph problems can be solved in parallel. In this work, an implementation of the QAOA2 method for the scalable solution of the MaxCut problem is presented, based on the Classiq platform. The framework is executed on an HPE-Cray EX supercomputer by means of the Message Passing Interface (MPI) and the SLURM workload manager. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated to understand if QAOA^2 could benefit from solving certain sub-graphs classically. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation, as well as the adequacy of the workflow in the preparation of real quantum devices. For the considered graphs, the best choice for the sub-graphs does not significantly improve results and is still outperformed by GW.
Related papers
- MG-Net: Learn to Customize QAOA with Circuit Depth Awareness [51.78425545377329]
Quantum Approximate Optimization Algorithm (QAOA) and its variants exhibit immense potential in tackling optimization challenges.
The requisite circuit depth for satisfactory performance is problem-specific and often exceeds the maximum capability of current quantum devices.
We introduce the Mixer Generator Network (MG-Net), a unified deep learning framework adept at dynamically formulating optimal mixer Hamiltonians.
arXiv Detail & Related papers (2024-09-27T12:28:18Z) - Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem [8.738180371389097]
The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers.
Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem.
We observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers.
arXiv Detail & Related papers (2023-08-04T14:17:21Z) - An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum-classical algorithm used to approximately solve optimisation problems.
While QAOA can be implemented on NISQ devices, physical limitations can limit circuit depth and decrease performance.
This work introduces the eXpressive QAOA (XQAOA) that assigns more classical parameters to the ansatz to improve its performance at low depths.
arXiv Detail & Related papers (2023-02-09T07:47:06Z) - 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) - Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity.
We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree.
These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
arXiv Detail & Related papers (2022-01-06T21:02:30Z) - Quantum Approximate Optimization Algorithm Based Maximum Likelihood
Detection [80.28858481461418]
Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
arXiv Detail & Related papers (2021-07-11T10:56:24Z) - Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
Quantifying performance bounds provides insight into when QAOA may be viable for solving real-world applications.
We find QAOA exceeds the Goemans-Williamson approximation ratio bound for most graphs.
The resulting data set is presented as a benchmark for establishing empirical bounds on QAOA performance.
arXiv Detail & Related papers (2021-02-12T23:12:09Z) - Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph.
We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
arXiv Detail & Related papers (2020-11-26T18:22:21Z) - Evaluation of QAOA based on the approximation ratio of individual
samples [0.0]
We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives.
Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage.
arXiv Detail & Related papers (2020-06-08T18:00:18Z) - 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.