Search NASA⌕ Search

SEARCH · Search NASA

Results for “quantum approximate optimization algorithm”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 91 records · Page 5
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA

Understanding the best known parameters, performance, and systematic behavior of the Quantum Approximate Optimization Algorithm (QAOA) remain open research questions, even as the algorithm gains popularity. We introduce QAOAKit, a Python toolkit for the QAOA built for exploratory research. QAOAKit is a unified repository of preoptimized QAOA parameters and circuit generators for common quantum simulation frameworks. We combine, standardize, and cross-validate previously known parameters for the MaxCut problem, and incorporate this into QAOAKit. We also build conversion tools to use these parameters as inputs in several quantum simulation frameworks that can be used to reproduce, compare, and extend known results from various sources in the literature. We describe QAOAKit and provide examples of how it can be used to reproduce research results and tackle open problems in quantum optimization.

Shaydulin, Ruslan↗
DOE OSTI2024

QFw: A Quantum Framework for Large-scale HPC Ecosystems

This work extends Quantum Framework (QFw) by integrating it with Northwest Quantum Simulator (NWQ-Sim) and by introducing a lightweight python library that allows multiple frontends (e.g., Qiskit) to interact with QFw. This extension enables QFw to flexibly decouple frontends from backends (e.g., NWQ-Sim). We demonstrate this capability by executing a Greenberger-Horne-Zeilinger (GHZ) circuit using Qiskit and Pennylane with NWQ-Sim and Tensor-Network Quantum Virtual-Machine (TN-QVM). QFw enables easy scaling to multiple nodes. We showcase this with scaling tests using GHZ with up to 32 qubits for different number of nodes on the Frontier supercomputer. And, to demonstrate the use of QFw for real world problems, we solve a metamaterial optimization problem, using a Quantum Approximate Optimization Algorithm (QAOA). We observe that QFw over NWQ-Sim marginally improves Qiskit-aer’s accuracy in reaching the lowest energy state. These additions to QFw prepare it to run hybrid applications in a hybrid resource environment since it treats actual quantum hardware and simulators alike.

Chundury, Srikar↗
DOE OSTI2024

Provable bounds for noise-free expectation values computed from noisy samples

Quantum computing has emerged as a powerful computational paradigm capable of solving problems beyond the reach of classical computers. However, today’s quantum computers are noisy, posing challenges to obtaining accurate results. Here, we explore the impact of noise on quantum computing, focusing on the challenges in sampling bit strings from noisy quantum computers and the implications for optimization and machine learning. We formally quantify the sampling overhead to extract good samples from noisy quantum computers and relate it to the layer fidelity, a metric to determine the performance of noisy quantum processors. Further, we show how this allows us to use the conditional value at risk of noisy samples to determine provable bounds on noise-free expectation values. We discuss how to leverage these bounds for different algorithms and demonstrate our findings through experiments on real quantum computers involving up to 127 qubits. The results show strong alignment with theoretical predictions.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Simulating large one-dimensional neutral-atom quantum systems

While abstract models of quantum computation assume a closed system of two-level states, practical quantum devices inevitably couple to the environment in some way, creating sources of noise. Understanding the tolerance to noise of specific quantum algorithms run on specific devices is important for determining the feasibility of quantum computing in the current noisy intermediate-scale quantum era. Of particular interest is understanding the noise sensitivity of these devices as more qubits are added to the system. Classical simulations are a useful tool to understand the effects of this noise, but direct classical simulations of open quantum systems are burdened by an exponentially growing cost in the number of qubits and a large local Hilbert space dimension. For onedimensional, shallow circuits, using tensor networks can replace this exponential cost with a linear one and simulate far wider systems than what would normally be available. In this paper, we describe a tensor network simulation of a neutral atom quantum system under the presence of noise, while introducing a purity-preserving truncation technique that compromises between the simplicity of the matrix product state and the positivity of the matrix product density operator. We apply this simulation to a near-optimized iteration of the quantum approximate optimization algorithm on a transverse field Ising model in order to investigate the influence of large system sizes on the performance of the algorithm. We find that while circuits with a large number of qubits fail more often under noise that depletes the qubit population, their outputs on a successful measurement are just as robust under Rydberg atom dissipation or qubit dephasing as smaller systems. However, such circuits might not perform as well under coherent multiqubit errors such as Rydberg atom crosstalk. We also find that the optimized parameters are especially robust to noise, suggesting that a noisier quantum system can be used to find the optimal parameters before switching to a cleaner system for measurements of observables.

Allen, James↗
DOE OSTI2026

Promise of Graph Sparsification and Decomposition for Noise Reduction in QAOA: Analysis for Trapped-Ion Compilations

We develop new approximate compilation schemes that significantly reduce the expense of compiling the Quantum Approximate Optimization Algorithm (QAOA) for solving the Max-Cut problem. Our main focus is on compilation with trapped-ion simulators using Pauli-X operations and all-to-all Ising Hamiltonian HIsing evolution generated by Molmer-Sorensen or optical dipole force interactions, though some of our results also apply to standard gate-based compilations. Our results are based on principles of graph sparsification and decomposition; the former reduces the number of edges in a graph while maintaining its cut structure, while the latter breaks a weighted graph into a small number of unweighted graphs. Though these techniques have been used as heuristics in various hybrid quantum algorithms, there have been no guarantees on their performance, to the best of our knowledge. This work provides the first provable guarantees using sparsification and decomposition to improve quantum noise resilience and reduce quantum circuit complexity. For quantum hardware that uses edge-by-edge QAOA compilations, sparsification leads to a direct reduction in circuit complexity. For trapped-ion quantum simulators implementing all-to-all HIsing pulses, we show that for a (1−ϵ) factor loss in the Max-Cut approximation (ϵ>0), our compilations improve the (worst-case) number of HIsing pulses from O(n2) to O(nlog(n/ϵ)) and the (worst-case) number of Pauli-X bit flips from O(n2) to O(nlog(n/ϵ)ϵ2) for n-node graphs. This is an asymptotic improvement for any constant ϵ>0. We demonstrate that significant improvements to the approximation ratio are obtained using decomposition in simulated trapped-ion experiments with dephasing noise. We further present a generic argument showing that sparsification results in an exponentially improved circuit fidelity lower bound in digital computing schemes based on one- and two-qubit gates, which are relevant to a wide variety of hardwares such as superconducting qubits and certain neutral atom or trapped ion setups, and more sophisticated noise models. We anticipate these approximate compilation techniques will be useful tools in a variety of future quantum computing experiments.

Moondra, Jai [Georgia Institute of Technology]↗
DOE OSTI2024

Scaling whole-chip QAOA for higher-order ising spin glass models on heavy-hex graphs

Abstract We show that the quantum approximate optimization algorithm (QAOA) for higher-order, random coefficient, heavy-hex compatible spin glass Ising models has strong parameter concentration across problem sizes from 16 up to 127 qubits for p = 1 up to p = 5, which allows for computationally efficient parameter transfer of QAOA angles. Matrix product state (MPS) simulation is used to compute noise-free QAOA performance. Hardware-compatible short-depth QAOA circuits are executed on ensembles of 100 higher-order Ising models on noisy IBM quantum superconducting processors with 16, 27, and 127 qubits using QAOA angles learned from a single 16-qubit instance using the JuliQAOA tool. We show that the best quantum processors find lower energy solutions up to p = 2 or p = 3, and find mean energies that are about a factor of two off from the noise-free distribution. We show that p = 1 QAOA energy landscapes remain very similar as the problem size increases using NISQ hardware gridsearches with up to a 414 qubit processor.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2023

Modeling noise in global Mølmer-Sørensen interactions applied to quantum approximate optimization

Many-qubit Mølmer-Sørensen (MS) interactions applied to trapped ions offer unique capabilities for quantum information processing, with applications including quantum simulation and the quantum approximate optimization algorithm (QAOA). Here, we develop a physical model to describe many-qubit MS interactions under four sources of experimental noise: vibrational mode frequency fluctuations, laser power fluctuations, thermal initial vibrational states, and state preparation and measurement errors. The model parametrizes these errors from simple experimental measurements, without free parameters. Herein, we validate the model in comparison with experiments that implement sequences of MS interactions on two 171 Yb + ions. The model shows reasonable agreement after several MS interactions as quantified by the reduced chi-squared statistic $χ^{2}_{red}$≈2. As an application we examine MaxCut QAOA experiments on three and six ions. The experimental performance is quantified by approximation ratios that are 91% and 83% of the optimal theoretical values. Our model predicts $0.93^{+0.03}_{-0.02}$ and $0.95^{+0.04}_{-0.03}$, respectively, with disagreement in the latter value attributable to secondary noise sources beyond those considered in our analysis. With realistic experimental improvements to reduce measurement error and radial trap frequency variations, the model achieves approximation ratios that are 99% of the optimal. Incorporating these improvements into future experiments is expected to reveal new aspects of noise for future modeling and experimental improvements.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2023

Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut

Finding high-quality parameters is a central obstacle to using the quantum approximate optimization algorithm (QAOA). Previous work partially addresses this issue for QAOA on unweighted MaxCut problems by leveraging similarities in the objective landscape among different problem instances. However, we show that the more general weighted MaxCut problem has significantly modified objective landscapes, with a proliferation of poor local optima. Our main contribution is a simple rescaling scheme that overcomes these deleterious effects of weights. Here we show that for a given QAOA depth, a single “typical” vector of QAOA parameters can be successfully transferred to weighted MaxCut instances. This transfer leads to a median decrease in the approximation ratio of only 2.0 percentage points relative to a considerably more expensive direct optimization on a dataset of 34,701 instances with up to 20 nodes and multiple weight distributions. This decrease can be reduced to 1.2 percentage points at the cost of only 10 additional QAOA circuit evaluations with parameters sampled from a pretrained metadistribution, or the transferred parameters can be used as a starting point for a single local optimization run to obtain approximation ratios equivalent to those achieved by exhaustive optimization in 96.35% of our cases.

97 MATHEMATICS AND COMPUTING↗
NASA NTRSDate not supplied

Dynamical Decoupling of Crosstalk on Superconducting Qubit Devices

Current NISQ devices are prone to errors. In order to be used for practical applications or achieve fault-tolerant thresholds, strategies to suppress error rates will be needed to maximize the potential of noisy devices. Dynamical decoupling (DD) is one such strategy for suppressing — or at least alleviating — the effects of decoherence, in which sequences of pulses are applied to qubits to decouple their interaction with the environment. Through experimental runs performed on several Rigetti quantum computing units (QPUs), we first demonstrate that DD is capable of improving coherence times for isolated qubits, as well as suppressing errors caused by the ZZ coupling between pairs of qubits. Extending this framework to cycles containing2-qubit gates, we show that DD can be inserted to decouple qubits from crosstalk occurring during neighboring 2-qubit gates, and demonstrate the efficacy of this procedure on quantum approximate optimization algorithm (QAOA) circuits. We also explore the usage of tailored DD sequences for the suppression of characterized error channels. We are grateful for support from the NASA Ames Research Center and from the DARPA ONISQ program under interagency agreement IAA 8839,Annex 114. HYH is supported by the USRA Feynman QuantumAcademy funded by the NAMS R&D Student Program and a UCHellman Fellowship. JS, ZGI and ZW are supported by USRA NASAAcademic Mission Service (NNA16BD14C).

Dynamical decoupling↗
NASA NTRS2019

Quantum Gate-Model Approaches to Exact and Approximate Optimization

Many of the most challenging computational problems arising in practical applications are tackled by heuristic algorithms which have not been rigorously proven to outperform other approaches but rather have been empirically demonstrated to be effective. While quantum heuristics have been proposed since the early days of quantum computing, true empirical evaluation of the real-world performance of these algorithms is only becoming possible now as increasingly powerful quantum gate-model devices continue to come online.In this talk, I will give an overview of the NASA QuAIL team's ongoing investigation into quantum gate-model heuristic algorithms for exact and approximate optimization. In particular, we consider the performance of the Quantum Approximate Optimization Algorithm on NP-hard optimization problems, and describe algorithm parameter setting strategies for real-world quantum hardware. We then show a generalization of QAOA circuits, the Quantum Alternating Operator Ansatz, especially suitable for low-resource implementations of QAOA for problems with hard (feasibility) constraints. The talk will conclude with a discussion of research challenges, particularly for optimization and sampling applications of QAOA, and the potential of more general quantum heuristics to give advantages over classical computers.

Hadfield, Stuart↗
DOE OSTI2026

Self-consistent mean-field quantum approximate optimization

We introduce a self-consistent mean-field quantum optimization algorithm that approximates the ground state of classical Ising Hamiltonians. The algorithm decomposes the problem into independent subproblems and treats the interactions between them in a mean-field manner. These interactions are captured by a common environment, constructed self-consistently through a variational quantum circuit, and which modifies the subproblems to account for mutual influence while maintaining computational independence. Consequently, subproblems can be solved individually, avoiding the computational cost of the full problem. We explore the properties of the generated environment and assess the algorithm's performance through extensive numerical simulations on Sherrington-Kirkpatrick spin glasses. Furthermore, we apply it experimentally to a weighted maximum clique problem applied to molecular docking. This framework enables the solution of problems that would otherwise exceed the qubit and gate counts of current quantum hardware.

Dupont, Maxime [Rigetti Computing] (ORCID:00000001↗
DOE OSTI2026

Self-consistent mean-field quantum approximate optimization

We introduce a self-consistent mean-field quantum optimization algorithm that approximates the ground state of classical Ising Hamiltonians. The algorithm decomposes the problem into independent subproblems and treats the interactions between them in a mean-field manner. These interactions are captured by a common environment, constructed self-consistently through a variational quantum circuit, and which modifies the subproblems to account for mutual influence while maintaining computational independence. Consequently, subproblems can be solved individually, avoiding the computational cost of the full problem. We explore the properties of the generated environment and assess the algorithm's performance through extensive numerical simulations on Sherrington-Kirkpatrick spin glasses. Furthermore, we apply it experimentally to a weighted maximum clique problem applied to molecular docking. This framework enables the solution of problems that would otherwise exceed the qubit and gate counts of current quantum hardware.

Dupont, Maxime [Rigetti Computing] (ORCID:00000001↗
DOE OSTI2026

Self-consistent mean-field quantum approximate optimization

We introduce a self-consistent mean-field quantum optimization algorithm that approximates the ground state of classical Ising Hamiltonians. The algorithm decomposes the problem into independent subproblems and treats the interactions between them in a mean-field manner. These interactions are captured by a common environment, constructed self-consistently through a variational quantum circuit, and which modifies the subproblems to account for mutual influence while maintaining computational independence. Consequently, subproblems can be solved individually, avoiding the computational cost of the full problem. We explore the properties of the generated environment and assess the algorithm's performance through extensive numerical simulations on Sherrington-Kirkpatrick spin glasses. Furthermore, we apply it experimentally to a weighted maximum clique problem applied to molecular docking. This framework enables the solution of problems that would otherwise exceed the qubit and gate counts of current quantum hardware.

Dupont, Maxime [Rigetti Computing] (ORCID:00000001↗
DOE OSTI2022

Quantum Local Search with the Quantum Alternating Operator Ansatz

We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve large problem instances on quantum devices with few qubits. This hybrid algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We study the performance of this algorithm on 3-regular, Community, and Erdős-Rényi graphs with up to 100 nodes.

Tomesh, Teague↗
DOE OSTI2020

Classical Optimizers for Noisy Intermediate-Scale Quantum Devices

We present a collection of optimizers tuned for usage on Noisy Inter-mediate-Scale Quantum (NISQ) devices. Optimizers have a range of applications in quantum computing, including the Variational Quantum Eigensolver (VQE) and Quantum Approximate Optimization (QAOA) algorithms. They have further uses in calibration, hyperparameter tuning, machine learning, etc. We employ the VQE algorithm as a case study. VQE is a hybrid algorithm, with a classical minimizer step driving the next evaluation on the quantum processor. While most results to date concentrated on tuning the quantum VQE circuit, our study indicates that in the presence of quantum noise the classical minimizer step is a weak link and a careful choice combined with tuning is required for correct results. We explore state-of-the-art gradient-free optimizers capable of handling noisy, black-box, cost functions and stress-test them using a quantum circuit simulation environment with noise injection capabilities on individual gates. Our results indicate that specifically tuned optimizers are crucial to obtaining valid science results on NISQ hardware, as well as projecting forward on fault tolerant circuits.

Lavrijsen, Wim↗
DOE OSTI2023

On the Approximability of Random-Hypergraph MAX-3-XORSAT Problems with Quantum Algorithms

Constraint satisfaction problems are an important area of computer science. Many of these problems are in the complexity class NP which is exponentially hard for all known methods, both for worst cases and often typical. Fundamentally, the lack of any guided local minimum escape method ensures the hardness of both exact and approximate optimization classically, but the intuitive mechanism for approximation hardness in quantum algorithms based on Hamiltonian time evolution is poorly understood. We explore this question using the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We qualitatively identify why traditional methods such as quantum adiabatic optimization are not good approximation algorithms. We propose a new spectral folding optimization method that does not suffer from these issues and study it analytically and numerically. We consider random rank-3 hypergraphs including extremal planted solution instances, where the ground state satisfies an anomalously high fraction of constraints compared to truly random problems. We show that, if we define the energy to be $E = N_{unsat}-N_{sat}$, then spectrally folded quantum optimization will return states with energy $E \leq A E_{GS}$ (where $E_{GS}$ is the ground state energy) in polynomial time, where conservatively, $A \simeq 0.6$. We thoroughly benchmark variations of spectrally folded quantum optimization for random classically approximation-hard (planted solution) instances in simulation, and find performance consistent with this prediction. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.

Kapit, Eliot↗
NASA NTRS2017

Quantum Approximate Optimization with Hard and Soft Constraints

Challenging computational problems arising in the practical world are frequently tackled by heuristic algorithms. Small universal quantum computers will emerge in the next year or two, enabling a substantial broadening of the types of quantum heuristics that can be investigated beyond quantum annealing. The immediate question is What experiments should we prioritize that will give us insight into quantum heuristics? One leading candidate is the quantum approximate optimization algorithm (QAOA) metaheuristic. Here, we provide a framework for designing QAOA circuits for a variety of combinatorial optimization problems with both hard constraints that must be met and soft constraints whose violation we wish to minimize. We work through a number of examples, and discuss design principles and implementation considerations.

Hadfield, Stuart↗