SEARCH · Engineering Papers

Results for “approximation 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.

SourceResearch connectionFrom yearThrough year

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

At least 37 records · Page 2

All sources NASA NTRS DOE OSTI

DOE OSTI2025

Quantifying the impact of precision errors on quantum approximate optimization algorithms

The quantum approximate optimization algorithm (QAOA) is a hybrid quantum-classical algorithm that seeks to achieve approximate solutions to optimization problems by iteratively alternating between intervals of controlled quantum evolution. Here, we examine the effect of analog precision errors on QAOA performance from the perspective of both algorithmic training and performance guarantees. Leveraging cumulant expansions, we recast the faulty QAOA as a control problem in which precision errors are expressed as multiplicative control noise and derive bounds on the performance of QAOA. We show using both analytical techniques and numerical simulations that fixed precision implementations of QAOA circuits are subject to an exponential degradation in performance dependent upon the number of optimal QAOA layers and magnitude of the precision error. Despite this significant reduction, we show that it is possible to mitigate precision errors in QAOA via digitization of the variational parameters at the cost of increasing circuit depth.

quantum algorithms↗

NASA NTRS1986

Parametric effects of CFL number and artificial smoothing on numerical solutions using implicit approximate factorization algorithm

An implicit approximate factorization algorithm is employed to quantify the parametric effects of Courant number and artificial smoothing on numerical solutions of the unsteady 3-D Euler equations for a windmilling propeller (low speed) flow field. The results show that propeller global or performance chracteristics vary strongly with Courant number and artificial dissipation parameters, though the variation is such less severe at high Courant numbers. Candidate sets of Courant number and dissipation parameters could result in parameter-dependent solutions. Parameter-independent numerical solutions can be obtained if low values of the dissipation parameter-time step ratio are used in the computations. Furthermore, it is realized that too much artificial damping can degrade numerical stability. Finally, it is demonstrated that highly resolved meshes may, in some cases, delay convergence, thereby suggesting some optimum cell size for a given flow solution. It is suspected that improper boundary treatment may account for the cell size constraint.

Daso, E. O.↗

DOE OSTI2022

Hybrid quantum-classical algorithms for approximate graph coloring

We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX- k -CUT, the problem of finding an approximate k -vertex coloring of a graph. We compare this proposal to the best known classical and hybrid classical-quantum algorithms. First, we show that the standard (non-recursive) QAOA fails to solve this optimization problem for most regular bipartite graphs at any constant level p : the approximation ratio achieved by QAOA is hardly better than assigning colors to vertices at random. Second, we construct an efficient classical simulation algorithm which simulates level- 1 QAOA and level- 1 RQAOA for arbitrary graphs. In particular, these hybrid algorithms give rise to efficient classical algorithms, and no benefit arising from the use of quantum mechanics is to be expected. Nevertheless, they provide a suitable testbed for assessing the potential benefit of hybrid algorithm: We use the simulation algorithm to perform large-scale simulation of level- 1 QAOA and RQAOA with up to 300 qutrits applied to ensembles of randomly generated 3 -colorable constant-degree graphs. We find that level- 1 RQAOA is surprisingly competitive: for the ensembles considered, its approximation ratios are often higher than those achieved by the best known generic classical algorithm based on rounding an SDP relaxation. This suggests the intriguing possibility that higher-level RQAOA may be a potentially useful algorithm for NISQ devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

NASA NTRS2017

The Quantum Approximation Optimization Algorithm for MaxCut: A Fermionic View

Farhi et al. recently proposed a class of quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA), for approximately solving combinatorial optimization problems. A level-p QAOA circuit consists of steps in which a classical Hamiltonian, derived from the cost function, is applied followed by a mixing Hamiltonian. The 2p times for which these two Hamiltonians are applied are the parameters of the algorithm. As p increases, however, the parameter search space grows quickly. The success of the QAOA approach will depend, in part, on finding effective parameter-setting strategies. Here, we analytically and numerically study parameter setting for QAOA applied to MAXCUT. For level-1 QAOA, we derive an analytical expression for a general graph. In principle, expressions for higher p could be derived, but the number of terms quickly becomes prohibitive. For a special case of MAXCUT, the Ring of Disagrees, or the 1D antiferromagnetic ring, we provide an analysis for arbitrarily high level. Using a Fermionic representation, the evolution of the system under QAOA translates into quantum optimal control of an ensemble of independent spins. This treatment enables us to obtain analytical expressions for the performance of QAOA for any p. It also greatly simplifies numerical search for the optimal values of the parameters. By exploring symmetries, we identify a lower-dimensional sub-manifold of interest; the search effort can be accordingly reduced. This analysis also explains an observed symmetry in the optimal parameter values. Further, we numerically investigate the parameter landscape and show that it is a simple one in the sense of having no local optima.

quantum algorithm↗

DOE OSTI2021

Adapting Quantum Approximation Optimization Algorithm (QAOA) for Unit Commitment

In the present Noisy Intermediate-Scale Quantum (NISQ), hybrid algorithms that leverage classical resources to reduce quantum costs are particularly appealing. We formulate and apply such a hybrid quantum-classical algorithm to a power system optimization problem called Unit Commitment, which aims to satisfy a target power load at minimal cost. Our algorithm extends the Quantum Approximation Optimization Algorithm (QAOA) with a classical minimizer in order to support mixed binary optimization. Using Qiskit, we simulate results for sample systems to validate the effectiveness of our approach. Here, we also compare to purely classical methods. Our results indicate that classical solvers are effective for our simulated Unit Commitment instances with fewer than 400 power generation units. However, for larger problem instances, the classical solvers either scale exponentially in runtime or must resort to coarse approximations. This opens the door to potential quantum advantage for systems with several hundred units, though quantum error correction may be necessary at this scale.

42 ENGINEERING↗

DOE OSTI2025

Biased degenerate ground-state sampling of small Ising models with converged quantum approximate optimization algorithm

The quantum alternating operator ansatz, a generalization of the quantum approximate optimization algorithm (QAOA), is a quantum algorithm used for approximately solving combinatorial optimization problems. QAOA typically uses the transverse field mixer as the driving Hamiltonian. One of the interesting properties of the transverse field driving Hamiltonian is that it results in nonuniform sampling of degenerate ground states of optimization problems. In this study, we numerically examine the fair sampling properties of the transverse field mixer QAOA, and Grover mixer QAOA (GM-QAOA), which provides theoretical guarantees of fair sampling of degenerate optimal solutions, up to a large enough p such that the mean expectation value converges to an optimal approximation ratio of 1. This comparison is performed with high-quality heuristically computed, but not necessarily optimal, QAOA angles, which give strictly monotonically improving solution quality as p increases. These angles are computed using the Julia based numerical simulation software JuliQAOA. Fair sampling of degenerate ground states is quantified using the Shannon entropy of the ground-state amplitudes distribution. The fair sampling properties are reported on several quantum signature Hamiltonians from previous quantum annealing fair sampling studies. Small random fully connected spin glasses are shown, which exhibit exponential suppression of some degenerate ground states with transverse field mixer QAOA. The transverse field mixer QAOA simulations show that some problem instances clearly saturate the Shannon entropy of 0 with a maximally biased distribution that occurs when the learning converges to an approximation ratio of 1 while other problem instances never deviate from a maximum Shannon entropy (uniform distribution) at any p step. Published by the American Physical Society 2025

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2023

Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm

We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depth p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizes N, a quantum device must support depth p > 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOA p ≤ 11 does not scale with N. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2021

Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs

The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for p > 2. A recent work computing MaxCut performance guarantees for 3-regular graphs conjectures that any d-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for p < 12. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA and have universally good performance on any 3-regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are "close" to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for p >= 11.

Wurtz, Jonathan↗

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 OSTI2025

Analyzing the Quantum Approximate Optimization Algorithm: Ansätze, Symmetries, and Lie Algebras

The quantum approximate optimization algorithm (QAOA) has been proposed as a method to obtain approximate solutions for combinatorial optimization tasks. In this work, we study the underlying algebraic properties of three QAOA ansätze for the maximum-cut problem on connected graphs, while focusing on the generated Lie algebras as well as their invariant subspaces. Specifically, we analyze the standard QAOA ansatz as well as the orbit and multiangle ansätze. We are able to fully characterize the Lie algebras of the multiangle ansatz across arbitrary connected graphs, finding that they only fall into one of just six families. Aside from the cycle and path graphs, the Lie dimensions for every graph are exponentially large in the system size, meaning that multiangle ansätze are extremely prone to exhibiting barren plateaus. Then, a similar quasi-graph-independent Lie-algebraic characterization beyond the multiangle ansatz is impeded as the circuit exhibits additional “hidden” symmetries besides those naturally arising from a certain parity-superselection operator and all automorphisms of the considered graph. Disregarding the “hidden” symmetries, we can upper bound the dimensions of the orbit and the standard Lie algebras, and the dimensions of the associated invariant subspaces are determined via explicit character formulas. To finish, we conjecture that (for most graphs) the standard Lie algebras have only components that are either exponential or that grow, at most, polynomially with the system size. This would imply that the QAOA is either prone to barren plateaus or classically simulable. More generally, our work provides a symmetry framework and tools to analyze any desired variational quantum algorithm.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2021

Freedom of the mixer rotation axis improves performance in the quantum approximate optimization algorithm

Variational quantum algorithms such as the quantum approximate optimization algorithm (QAOA) are particularly attractive candidates for implementation on near-term quantum processors. As hardware realities such as error and qubit connectivity will constrain achievable circuit depth in the near future, new ways to achieve high performance at low depth are of great interest. In this work, we present a modification to QAOA that adds additional variational parameters in the form of freedom of the rotation axis in the XY plane of the mixer Hamiltonian. Here, via numerical simulation, we show that this leads to a drastic performance improvement over standard QAOA at finding solutions to the MaxCut problem on graphs of up to seven qubits. Furthermore, we explore the Z-phase error mitigation properties of our modified Ansatz, its performance under a realistic error model for a neutral atom quantum processor, and the class of problems it can solve in a single round.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2021

Classical symmetries and the Quantum Approximate Optimization Algorithm

Here, we study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular, we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques toward predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm

The trading of fidelity for scale enables approximate classical simulators such as matrix product states (MPSs) to run quantum circuits beyond exact methods. A control parameter, the so-called bond dimension $\mathcal{χ}$ for MPSs, governs the allocated computational resources and the output fidelity. Here, we characterize the fidelity for the quantum approximate optimization algorithm by the expectation value of the cost function that it seeks to minimize and find that it follows a scaling law $\mathscr{F}$(ln $\mathcal{χ}$/N), where N is the number of qubits. With ln $\mathcal{χ}$ amounting to the entanglement that a MPS can encode, we show that the relevant variable for investigating the fidelity is the entanglement per qubit. Importantly, our results calibrate the classical computational power required to achieve the desired fidelity and benchmark the performance of quantum hardware in a realistic setup. For instance, we quantify the hardness of performing better classically than a noisy superconducting quantum processor by readily matching its output to the scaling function. Moreover, we relate the global fidelity to that of individual operations and establish its relationship with $\mathcal{χ}$ and N. We sharpen the requirements for noisy quantum computers to outperform classical techniques at running a quantum optimization algorithm in speed, size, and fidelity.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2024

Evidence of scaling advantage for the quantum approximate optimization algorithm on a classically intractable problem

The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

Distributed quantum approximate optimization algorithm on a quantum-centric supercomputing architecture

Quantum approximate optimization algorithm (QAOA) has shown promise in solving combinatorial optimization problems by providing quantum speedup on near-term gate-based quantum computing systems. However, QAOA faces challenges for high-dimensional problems due to the large number of qubits required and the complexity of deep circuits, limiting its scalability for real-world applications. In this study, we present a distributed QAOA (DQAOA), which leverages distributed computing strategies to decompose a large computational workload into smaller tasks that require fewer qubits and shallower circuits than are necessary to solve the original problem. These sub-problems are processed using a combination of high-performance and quantum computing resources. The global solution is iteratively updated by aggregating sub-solutions, allowing convergence toward the optimal solution. We demonstrate that DQAOA can handle considerably large-scale optimization problems (e.g., 1000-bit problem), achieving a high solution quality and short time-to-solution, outperforming existing strategies. Furthermore, we realize DQAOA on a quantum-centric supercomputing architecture, paving the way for practical applications of gate-based quantum computers in real-world optimization tasks. To extend DQAOA’s applicability to materials science, we further develop an active learning algorithm integrated with our DQAOA (AL-DQAOA), which involves machine learning, DQAOA, and active data production in an iterative loop. We successfully optimize photonic structures using AL-DQAOA, indicating that solving real-world optimization problems using gate-based quantum computing is feasible. We expect the proposed DQAOA to be applicable to a wide range of optimization problems and AL-DQAOA to find broader applications in material design.

Kim, Seongmin [ORNL] (ORCID:0000000159063004)↗

DOE OSTI2025

Simulations of Quantum Approximate Optimization Algorithm on HPC-QC Integrated Systems

The Quantum Approximate Optimization Algorithm (QAOA) has emerged as a promising tool for accelerating optimization processes in the Noisy Intermediate-Scale Quantum (NISQ) era. Compared to classical methods, QAOA efficiently solves optimization problems, often formulated as Quadratic Unconstrained Binary Optimization (QUBO) problems. Classical quantum simulators are crucial for evaluating quantum algorithms due to limited quantum resources. However, QAOA's performance can vary with different simulation methods. This study analyzes QAOA's performance using various quantum simulators (e.g., density _matrix, statevector, and matrix_product_state) and demonstrates the benefits of HPC-QC integrated systems in solving QUBO problems on an active learning workflow. By simulating QAOA on dense, large-matrix QUBO problems, we evaluate accuracy and problem-solving time. We also assess QAOA's performance on local computers and HPC-QC inte-grated systems, using Oak Ridge Leadership Computing Facility (OLCF)'s Frontier supercomputer with local Qiskit Aer and remote IBM Quantum simulators.

Kim, Seongmin [ORNL] (ORCID:0000000159063004)↗

NASA NTRS1981

A diagonal form of an implicit approximate-factorization algorithm

A modification of an implicit approximate-factorization finite-difference algorithm applied to partial differential equations is presented. This algorithm is applied to the two- and three-dimensional Euler equations in general curvilinear coordinates. The modification transforms the coupled system of equations into an uncoupled diagonal form that requires less computational work. For steady-state applications, the resulting diagonal algorithm retains the stability and accuracy characteristics of the original algorithm. The diagonal algorithm reduces the storage requirement of the implicit solution process and therefore has an important effect on the application of implicit finite-difference schemes to vector processors. Results are presented for realistic two-dimensional transonic flow fields about airfoils. Computation costs are reduced to 24-34%.

Pulliam, T. H.↗

NASA NTRS1981

A Diagonal Form of an Implicit Approximate-Factorization Algorithm

Pulliam, T. H.↗