Fast Simulation of High-Depth QAOA Circuits

Abstract

Until high-fidelity quantum computers with a large number of qubits become widely available, classical simulation remains a vital tool for algorithm design, tuning, and validation. We present a simulator for the Quantum Approximate Optimization Algorithm (QAOA). Our simulator is designed with the goal of reducing the computational cost of QAOA parameter optimization and supports both CPU and GPU execution. Our central observation is that the computational cost of both simulating the QAOA state and computing the QAOA objective to be optimized can be reduced by precomputing the diagonal Hamiltonian encoding the problem. We reduce the time for a typical QAOA parameter optimization by eleven times for $n=26$ qubits compared to a state-of-the-art GPU quantum circuit simulator based on cuQuantum. Our simulator is available on GitHub: https://github.com/jpmorganchase/QOKit

arXiv commentAdditional references added in v2

References in corpus (13)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Counting
• Hyper-optimized tensor network contraction
• Quantum annealing initialization of the quantum approximate optimization algorithm
• Full-State Quantum Circuit Simulation by Using Data Compression
• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• Classical symmetries and the Quantum Approximate Optimization Algorithm
• Exploiting Symmetry Reduces the Cost of Training QAOA
• QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• An adaptive algorithm for quantum circuit simulation
• Quantum simulation with just-in-time compilation
• Tools for Quantum Algorithms

Cited by in corpus (10)

• Evidence of Scaling Advantage for the Quantum Approximate Optimization Algorithm on a Classically Intractable Problem
• Integrating Quantum Computing Resources into Scientific HPC Ecosystems
• Trainability Barriers in Low-Depth QAOA Landscapes
• JuliQAOA: Fast, Flexible QAOA Simulation
• A quantum algorithm for solving 0-1 Knapsack problems
• Accelerating Simulation of Quantum Circuits under Noise via Computational Reuse
• Generalized Probabilistic Approximate Optimization Algorithm
• Classical optimization with imaginary time block encoding on quantum computers: The MaxCut problem
• A quantum search method for quadratic and multidimensional knapsack problems
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems