We introduce JuliQAOA, a simulation package specifically built for the Quantum Alternating Operator Ansatz (QAOA). JuliQAOA does not require a circuit-level description of QAOA problems, or another package to simulate such circuits, instead relying on a more direct linear algebra implementation. This allows for increased QAOA-specific performance improvements, as well as improved flexibility and generality. JuliQAOA is the first QAOA package designed to aid in the study of both constrained and unconstrained combinatorial optimization problems, and can easily include novel cost functions, mixer Hamiltonians, and other variations. JuliQAOA also includes robust and extensible methods for learning optimal angles. Written in the Julia language, JuliQAOA outperforms existing QAOA software packages and scales well to HPC-level resources.
We introduce JuliQAOA, a simulation package specifically built for the Quantum Alternating Operator Ansatz (QAOA). JuliQAOA does not require a circuit-level description of QAOA problems, or another package to simulate such circuits, instead relying on a more direct linear algebra implementation. This allows for increased QAOA-specific performance improvements, as well as improved flexibility and generality. JuliQAOA is the first QAOA package designed to aid in the study of both constrained and unconstrained combinatorial optimization problems, and can easily include novel cost functions, mixer Hamiltonians, and other variations. JuliQAOA also includes robust and extensible methods for learning optimal angles. Written in the Julia language, JuliQAOA outperforms existing QAOA software packages and scales well to HPC-level resources.
Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA-QAOA+. Unlike QAOA+, AMA-QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA-QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA-QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by 5.30% on ER random graphs and 5.41% on 3-regular graphs. Moreover, AMA-QAOA+ significantly reduces the CNOT gate consumption, requiring only 15.30% and 25.18% of the CNOT gates used by QAOA+ on ER and 3-regular random graphs, respectively. These results demonstrate that AMA-QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource-efficient quantum circuits.
We present MPS-JuliQAOA, an open-source, Julianative framework for simulating the Quantum Approximate Optimization Algorithm (QAOA) using Matrix Product States (MPS). The tool supports general cost Hamiltonians that are diagonal in the computational basis and integrates tensornetwork simulation with automatic differentiation for parameter optimization within a unified workflow. Built on the ITensor ecosystem, MPS-JuliQAOA replaces exact statevector simulation with an MPS backend, enabling QAOA simulations beyond the practical limits of full statevector methods when entanglement growth remains controlled. We demonstrate simulations of up to 512 qubits and 20 QAOA layers on 3-regular Max-Cut instances, and analyze runtime scaling and approximation accuracy as functions of bond dimension and circuit depth. The framework abstracts tensor-network and differentiation details from the user, allowing high-level Hamiltonian specification without requiring expertise in MPS methods. Source code is publicly available at https://github.com/lanl/JuliQAOA.jl/tree/mps.
We present a quantum alternating operator ansatz (QAOA + ) that solves a class of linearly constrained optimization problems by evolving a quantum state within a Hilbert subspace of feasible problem solutions. Our main focus is on a class of problems with a linear constraint containing sequential integer coefficients. For problems in this class, we devise QAOA + circuits that provably converge to the optimal solution as the number of circuit layers increases, generalizing previous guarantees for solving unconstrained problems or problems with symmetric constraints. Our approach includes asymmetric “mixing” Hamiltonians that drive transitions between feasible states, as well as a method to incorporate an arbitrary known feasible solution as the initial state, each of which can be applied beyond the specific linear constraints considered here. This analysis extends QAOA + performance guarantees to a more general set of linearly-constrained problems and provides tools for future generalizations.
ABSTRACT Recently, Hadfield et al. proposed the quantum alternating operator ansatz algorithm (QAOA+), an extension of the quantum approximate optimization algorithm (QAOA), to solve constrained combinatorial optimization problems (CCOPs). Compared with QAOA, QAOA+ enables the search for optimal solutions within a feasible solution space by encoding problem constraints into the mixer Hamiltonian, thereby reducing the search space and eliminating the possibility of yielding infeasible solutions. However, QAOA+ may incur high overall gate costs when the mixer is applied to all qubits in each layer, and each mixer is costly to implement. To address this challenge, an adaptive mixer allocation strategy is tailored for QAOA+. The resulting algorithm, which integrates this strategy into the original QAOA+ framework, is referred to as AMA‐QAOA+. Unlike QAOA+, AMA‐QAOA+ adaptively applies the mixer to a subset of qubits in each layer of the mixer unitary operator based on an evaluation function. The performance of AMA‐QAOA+ is evaluated on the maximum independent set problem. Numerical simulation results show that, under the same number of optimization runs, AMA‐QAOA+ achieves better solution quality than QAOA+, with the optimal approximation ratio improved by on Erdős–Rényi random graphs and on 3‐regular graphs. Moreover, AMA‐QAOA+ significantly reduces the CNOT gate consumption, requiring only and of the CNOT gates used by QAOA+ on Erdős–Rényi and 3‐regular random graphs, respectively. These results demonstrate that AMA‐QAOA+ enhances solution quality and computational efficiency, enabling the design of more compact and resource‐efficient quantum circuits.
The quantum alternating operator ansatz (QAOA) is a promising gate-model metaheuristic for combinatorial optimization. Applying the algorithm to problems with constraints presents an implementation challenge for near-term quantum resources. This paper explores strategies for enforcing hard constraints by using XY Hamiltonians as mixing operators (mixers). Despite the complexity of simulating the XY model, we demonstrate that, for an integer variable admitting $\ensuremath{\kappa}$ discrete values represented through one-hot encoding, certain classes of the mixer Hamiltonian can be implemented without Trotter error in depth $O(\ensuremath{\kappa})$. We also specify general strategies for implementing QAOA circuits on all-to-all connected hardware graphs and linearly connected hardware graphs inspired by fermionic simulation techniques. Performance is validated on graph-coloring problems that are known to be challenging for a given classical algorithm. The general strategy of using XY mixers is borne out numerically, demonstrating a significant improvement over the general X mixer, and moreover the generalized W state yields better performance than easier-to-generate classical initial states when XY mixers are used.
The Quantum Approximate Optimization Algorithm (QAOA) is a prominent quantum algorithm designed to find approximate solutions to combinatorial optimization problems, which are challenging for classical computers. In the current era, where quantum hardware is constrained by noise and limited qubit availability, simulating the QAOA remains essential for research. However, existing state-of-the-art simulation frame-works suffer from long execution times or lack comprehensive functionality, usability, and versatility, often requiring users to implement essential features themselves. Additionally, these frameworks are primarily restricted to Python, limiting their use in safer and faster languages like Rust, which offer, e.g., advanced parallelization capabilities. In this paper, we develop a 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 statevector, 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 QAOA at its core. The new framework's performance is rigorously benchmarked on the MaxCut problem and compared against the current state-of-the-art general-purpose quantum circuit simulation frameworks Qiskit and Pennylane as well as the specialized QAOA simulation tool QOKit. Our evaluation shows that our approach outperforms the existing state-of-the-art solutions in terms of runtime up to multiple orders of magnitude. Our implementation is publicly available at https://github.com/JFLXB/cuaoa and Zenodo [1].