Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA

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.

Equal Contribution

References in corpus (24)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Noisy intermediate-scale quantum (NISQ) algorithms
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Quantum Computation by Adiabatic Evolution
• QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
• Trading classical and quantum computational resources
• Obstacles to State Preparation and Variational Optimization from Symmetry Protection
• Simulating Large Quantum Circuits on a Small Quantum Computer
• Noise Resilience of Variational Quantum Compiling
• Benchmarking the Quantum Approximate Optimization Algorithm
• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Circuit knitting with classical communication
• Constructing a virtual two-qubit gate by sampling single-qubit operations
• Fast quantum circuit cutting with randomized measurements
• Overhead for simulating a non-local channel with local channels by quasiprobability sampling
• To quantum or not to quantum: towards algorithm selection in near-term quantum optimization
• Investigating the effect of circuit cutting in QAOA for the MaxCut problem on NISQ devices
• Cache Blocking Technique to Large Scale Quantum Computing Simulation on Supercomputers
• Evaluating the Q-score of Quantum Annealers
• Overhead-constrained circuit knitting for variational quantum dynamics
• Iterative-Free Quantum Approximate Optimization Algorithm Using Neural Networks
• Entanglement Forging with generative neural network models
• Quantum Task Offloading with the OpenMP API