Search NASA⌕ Search

SEARCH · Search NASA

Results for “heuristic quantum algorithms”

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 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRSDate not supplied

A NASA Perspective on Quantum Computing: Algorithmic Opportunities and Challenges

In the last couple of decades, the world has seen several stunning instances of quantum algorithms that provably outperform the best classical algorithms. For most problems, however, it is currently unknown whether quantum algorithms can provide an advantage, and if so how to design quantum algorithms that realize such advantages. Today, classical heuristics are used to solve many of the most challenging computational problems arising in the practical world, algorithms that have been shown to be effective empirically but have not been mathematically proven to outperform other approaches. With the advent of quantum advantage, the ability of current quantum hardware to do certain computations beyond the ability of even that largest supercomputers, we have an unprecedented opportunity to explore heuristic quantum algorithms. The next few years will be exciting as empirical testing of quantum heuristic algorithms becomes more and more feasible. The talk will begin overview of the NASA QuAIL team’s ongoing quantum computing investigations, and then focus on both near-term and longer term algorithms for optimization, including distributed algorithms.

quantum computing↗
DOE OSTI2020

K-Spin Hamiltonian for Quantum-Resolvable Markov Decision Processes

The Markov decision process is the mathematical formalization underlying the modern field of reinforcement learning when transition and reward functions are unknown. We derive a pseudo-Boolean cost function that is equivalent to a K-spin Hamiltonian representation of the discrete, finite, discounted Markov decision process with infinite horizon. This K-spin Hamiltonian furnishes a starting point from which to solve for an optimal policy using heuristic quantum algorithms such as adiabatic quantum annealing and the quantum approximate optimization algorithm on near-term quantum hardware. In arguing that the variational minimization of our Hamiltonian is approximately equivalent to the Bellman optimality condition for a prevalent class of environments we establish an interesting analogy with classical field theory. Along with proof-of-concept calculations to corroborate our formulation by simulated and quantum annealing against classical Q-Learning, we analyze the scaling of physical resources required to solve our Hamiltonian on quantum hardware.

Hamiltonian↗
DOE OSTI2023

Diabatic quantum annealing for the frustrated ring model

Abstract Quantum annealing (QA) is a continuous-time heuristic quantum algorithm for solving or approximately solving classical optimization problems. The algorithm uses a schedule to interpolate between a driver Hamiltonian with an easy-to-prepare ground state and a problem Hamiltonian whose ground state encodes solutions to an optimization problem. The standard implementation relies on the evolution being adiabatic: keeping the system in the instantaneous ground state with high probability and requiring a time scale inversely related to the minimum energy gap between the instantaneous ground and excited states. However, adiabatic evolution can lead to evolution times that scale exponentially with the system size, even for computationally simple problems. Here, we study whether non-adiabatic evolutions with optimized annealing schedules can bypass this exponential slowdown for one such class of problems called the frustrated ring model. For sufficiently optimized annealing schedules and system sizes of up to 39 qubits, we provide numerical evidence that we can avoid the exponential slowdown. Our work highlights the potential of highly-controllable QA to circumvent bottlenecks associated with the standard implementation of QA.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
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↗
NASA NTRS2019

On Benchmarking Quantum Heuristics

Present an outline of important aspects for benchmarking quantum algorithms, in particular quantum heuristics. Using quantum approximate optimization algorithm as an example, we demonstrate how the choice of cost Hamiltonian, of mixer, and of initial states can affect the performance. We also discuss how realistic aspects of near-term quantum hardware will influence the algorithm performance.

Wang, Zhihui↗
DOE OSTI2025

Iterative quantum optimization of spin glass problems with rapidly oscillating transverse fields

In this work, we introduce a new iterative quantum algorithm, called Iterative Symphonic Tunneling for Satisfiability problems (IST-SAT), which solves quantum spin glass optimization problems using high-frequency oscillating transverse fields. IST-SAT operates as a sequence of iterations, in which bitstrings returned from one iteration are used to set spin-dependent phases in oscillating transverse fields in the next iteration. Over several iterations, the novel mechanism of the algorithm steers the system toward the problem ground state. We benchmark IST-SAT on sets of hard MAX-3-XORSAT problem instances with exact state vector simulation, and report polynomial speedups over Trotterized adiabatic quantum computation and the best known semi-greedy classical algorithm. When IST-SAT is seeded with a sufficiently good initial approximation, the algorithm converges to exact solution(s) in a polynomial number of iterations. Our numerical results identify a critical Hamming radius, or quality of initial approximation, where the time-to-solution crosses from exponential to polynomial scaling in problem size. This work proposes IST-SAT a new quantum algorithm, which improves upon solutions obtained from initial classical or quantum optimization algorithms. The steering mechanism we introduce through IST-SAT presents a new path toward achieving quantum advantage in optimization.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
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

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 OSTI2025

End-to-end protocol for high-quality quantum approximate optimization algorithm parameters with few shots

The quantum approximate optimization algorithm (QAOA) is a quantum heuristic for combinatorial optimization that has been demonstrated to scale better than state-of-the-art classical solvers for some problems. For a given problem instance, QAOA performance depends crucially on the choice of the parameters. While average-case optimal parameters are available in many cases, meaningful performance gains can be obtained by fine-tuning these parameters for a given instance. This task is especially challenging, however, when the number of circuit executions (shots) is limited. In this work, we develop an end-to-end protocol that combines multiple parameter settings and fine-tuning techniques. We use large-scale numerical experiments to optimize the protocol for the shot-limited setting and observe that optimizers with the simplest internal model (linear) perform best. We implement the optimized pipeline on a trapped-ion processor using up to 32 qubits and 5 QAOA layers, and we demonstrate that the pipeline is robust to small amounts of hardware noise. To the best of our knowledge, these are the largest demonstrations of QAOA parameter fine-tuning on a trapped-ion processor in terms of two-qubit gate count.

quantum algorithms & computation↗
DOE OSTI2021

TEQUILA: a platform for rapid development of quantum algorithms

Variational quantum algorithms are currently the most promising class of algorithms for deployment on near-term quantum computers. In contrast to classical algorithms, there are almost no standardized methods in quantum algorithmic development yet, and the field continues to evolve rapidly. As in classical computing, heuristics play a crucial role in the development of new quantum algorithms, resulting in a high demand for flexible and reliable ways to implement, test, and share new ideas. In this paper, inspired by this demand, we introduce TEQUILA, a development package for quantum algorithms in PYTHON, designed for fast and flexible implementation, prototyping and deployment of novel quantum algorithms in electronic structure and other fields. TEQUILA operates with abstract expectation values which can be combined, transformed, differentiated, and optimized. On evaluation, the abstract data structures are compiled to run on state of the art quantum simulators or interfaces.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2025

A New Hybrid Quantum-Classical Algorithm for Solving the Unit Commitment Problem

Solving problems related to planning and operations of large-scale power systems is challenging on classical computers due to their inherent nature as mixed-integer and nonlinear problems. Quantum computing provides new avenues to approach these problems. We develop a hybrid quantum-classical algorithm for the Unit Commitment (UC) problem in power systems which aims at minimizing the total cost while optimally allocating generating units to meet the hourly demand of the power loads. The hybrid algorithm combines a variational quantum algorithm (VQA) with a classical Benders-type heuristic. The resulting algorithm computes approximate solutions to UC in three stages: i) a collection of UC vectors capable meeting the power demand with lowest possible operating costs is generated based on VQA; ii) a classical sequential least squares programming (SLSQP) routine is leveraged to find the optimal power level corresponding to a predetermined number of candidate vectors; iii) in the last stage, the approximate solution of UC along with generating units power level combination is given. To demonstrate the effectiveness of the presented method, three different systems with 3 generating units, 10 generating units, and 26 generating units were tested for different time periods. In addition, convergence of the hybrid quantum-classical algorithm for select time periods is proven out on IonQ's Forte system.

Aboumrad, Willie [IonQ, Inc]↗
DOE OSTI2021

Adaptive pruning-based optimization of parameterized quantum circuits

Abstract Variational hybrid quantum–classical algorithms are powerful tools to maximize the use of noisy intermediate-scale quantum devices. While past studies have developed powerful and expressive ansatze, their near-term applications have been limited by the difficulty of optimizing in the vast parameter space. In this work, we propose a heuristic optimization strategy for such ansatze used in variational quantum algorithms, which we call ‘parameter-efficient circuit training (PECT)’. Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms, in which each iteration of the algorithm activates and optimizes a subset of the total parameter set. To update the parameter subset between iterations, we adapt the Dynamic Sparse Reparameterization scheme which was originally proposed for training deep convolutional neural networks. We demonstrate PECT for the Variational Quantum Eigensolver, in which we benchmark unitary coupled-cluster ansatze including UCCSD and k -UpCCGSD, as well as the Low-Depth Circuit Ansatz (LDCA), to estimate ground state energies of molecular systems. We additionally use a layerwise variant of PECT to optimize a hardware-efficient circuit for the Sycamore processor to estimate the ground state energy densities of the one-dimensional Fermi-Hubbard model. From our numerical data, we find that PECT can enable optimizations of certain ansatze that were previously difficult to converge and more generally can improve the performance of variational algorithms by reducing the optimization runtime and/or the depth of circuits that encode the solution candidate(s).

Physics↗
DOE OSTI2023

Short-Depth QAOA circuits and Quantum Annealing on Higher-Order Ising Models (Rev.2)

The Quantum Alternating Operator Ansatz (QAOA) and Quantum Annealing (QA) are quantum algorithms that are both based on the adiabatic theorem and both have the goal of sampling the optimal solution(s) of combinatorial optimization problems. Quantum annealing has been physically instantiated on D-Wave devices using superconducting flux qubits, and QAOA can be programmed on digital gate-model quantum computers such as the programmable superconducting transmon qubits devices of the IBMQ series, for instance ibm washington. QAOA and QA address the same types of problems, but it is unclear how they will scale to large problem sizes and to larger and higher-fidelity quantum computers. In this article, we present a direct comparison between QAOA, one and two rounds, run on all 127 qubits of ibm washington and QA run on D-Wave Advantage system4.1 and Advantage system6.1. The problems which allow for this comparison are random Ising model problems whose connectivity matches the heavy hexagonal lattice topology of ibm washington and the Pegasus graph connectivity of the two D-Wave devices. We create two classes of problem instances for this comparison: one with higher order terms (ZZZ variable interactions), linear terms, and quadratic terms, and a separate problem type with only linear and quadratic terms. Our QAOA circuits are novel and extremely short depth, with a CNOT depth of 6 per round, which allows whole chip usage of ibm washington’s heavy hexagonal lattice and can be applied to future heavy-hex chips. We also test the effectiveness of the error suppression technique digital dynamical decoupling on the QAOA circuits. The QAOA circuits compiled to ibm washington are composed of several thousand circuit instructions, approximately 3, 000 depending on the details of the circuit, making these some the largest quantum circuits ever executed on a digital quantum processor. QAOA and QA are compared against the classical heuristic algorithm of simulated annealing and all problem instances are exactly solved using CPLEX in order to evaluate which samplers, if any, correctly found the ground state solution(s) of the problem instances. We find that (i) QA outperforms QAOA on all problem instances, (ii) QAOA samples the problems better than random sampling, and (iii) QAOA angle computation exhibits clear parameter concentration across the ensemble of Ising models.

127 Qubits↗
DOE OSTI2024

Adiabatic quantum imaginary time evolution

We introduce an adiabatic state preparation protocol which implements quantum imaginary time evolution under the Hamiltonian of the system. Unlike the original quantum imaginary time evolution algorithm, adiabatic quantum imaginary time evolution does not require quantum state tomography during its runtime and, unlike standard adiabatic state preparation, the final Hamiltonian is not the system Hamiltonian. Instead, the algorithm obtains the adiabatic Hamiltonian by integrating a classical differential equation that ensures that one follows the imaginary time evolution state trajectory. We introduce some heuristics that allow this protocol to be implemented on quantum architectures with limited resources. We explore the performance of this algorithm via classical simulations in a one-dimensional spin model and highlight essential features that determine its cost, performance, and implementability for longer times, and compare to the original quantum imaginary time evolution for ground-state preparation. More generally, our algorithm expands the range of states accessible to adiabatic state preparation methods beyond those that are expressed as ground states of simple explicit Hamiltonians. Published by the American Physical Society 2024

Hejazi, Kasra (ORCID:000000032349478X)↗
DOE OSTI2020

Efficient Step-Merged Quantum Imaginary Time Evolution Algorithm for Quantum Chemistry

In this work, we develop a resource-efficient step-merged quantum imaginary time evolution approach (smQITE) to solve for the ground state of a Hamiltonian on quantum computers. This heuristic method features a fixed shallow quantum circuit depth along the state evolution path. We use this algorithm to determine the binding energy curves of a set of molecules, including H 2 , H 4 , H 6 , LiH, HF, H 2 O, and BeH 2 , and find highly accurate results. The required quantum resources of smQITE calculations can be further reduced by adopting the circuit form of the variational quantum eigensolver (VQE) technique, such as the unitary coupled cluster ansatz. We demonstrate that smQITE achieves a similar computational accuracy as VQE at the same fixed-circuit ansatz, without requiring a generally complicated high-dimensional nonconvex optimization. Finally, smQITE calculations are carried out on Rigetti quantum processing units, demonstrating that the approach is readily applicable on current noisy intermediate-scale quantum devices.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
NASA NTRS2000

Automated Design of Quantum Circuits

In order to design a quantum circuit that performs a desired quantum computation, it is necessary to find a decomposition of the unitary matrix that represents that computation in terms of a sequence of quantum gate operations. To date, such designs have either been found by hand or by exhaustive enumeration of all possible circuit topologies. In this paper we propose an automated approach to quantum circuit design using search heuristics based on principles abstracted from evolutionary genetics, i.e. using a genetic programming algorithm adapted specially for this problem. We demonstrate the method on the task of discovering quantum circuit designs for quantum teleportation. We show that to find a given known circuit design (one which was hand-crafted by a human), the method considers roughly an order of magnitude fewer designs than naive enumeration. In addition, the method finds novel circuit designs superior to those previously known.

Williams, Colin P.↗
NASA NTRS2018

XY vs X Mixer in Quantum Alternating Operator Ansatz for Optimization Problems with Constraints

Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.

quantum computing↗