CUAOA: A Novel CUDA-Accelerated Simulation Framework for the Quantum Approximate Optimization Algorithm

CUAOA: A Novel CUDA-Accelerated Simulation Framework for the Quantum Approximate Optimization Algorithm

Abstract:

The Quantum Approximate Optimization Algorithm (QAOA) is a prominent quantum algorithm designed to find approximate solutions to combinatorial optimization problems. In the current era, where quantum hardware is constrained by noise and limited qubit availability, simulating QAOA remains essential for research. However, existing state-of-the-art simulation frameworks suffer from long execution times or lack comprehensive functionality, usability, and versatility, often requiring users to implement essential features themselves. Additionally, these frameworks are restricted to Python, limiting their use within safer and faster languages like Rust, which offer, e.g., advanced parallelization capabilities. This thesis presents the development of a new GPU-accelerated QAOA simulation framework utilizing the NVIDIA CUDA toolkit.

This framework offers a complete interface for QAOA simulations, enabling the calculation of (exact) expectation values, direct access to the state-vector, fast sampling, and high-performance optimization methods using an advanced state-of-the-art gradient calculation technique. The framework is designed for use in Python and Rust, providing flexibility for integration into a wide range of applications, including those requiring fast algorithm implementations leveraging the QAOA at its core. Such an algorithm, specifically the QAOA^2 , a divide-and-conquer algorithm, is implemented using the new QAOA simulation framework to showcase its usage in a possibly parallized application. The new QAOA simulation framework’s performance is rigorously benchmarked using various random graphs for the MaxCut problem and compared against current state-of-the-art general-purpose quantum circuit simulation frameworks and a specialized QAOA simulation tool. The evaluation shows that the developed simulator can outperform the current state-of-the-art simulators in terms of runtime, with a speedup of up to multiple orders of magnitude. Furthermore, the framework’s capabilities are evaluated within the divide-and-conquer algorithm utilizing the QAOA at its core. This implementation significantly outperforms the reference implementation using the current state-of-the-art simulators for a large problem instance.

Author:

Jonas Felix Blenninger

Advisors:

Claudia Linnhoff-Popien, Jonas Stein, Maximilian Zorn

Student Thesis | Published September 2024 | Copyright © QAR-Lab
Direct Inquiries to this work to the Advisors