Engineering Papers⌕ Search

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.

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

At least 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

Variational Quantum Algorithms for Semidefinite Programming

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N " M, where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Variational Quantum Algorithms for Semidefinite Programming

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N$\gg$M, where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Efficient state preparation for the Schwinger model with a theta term

We present a comparison of different quantum state preparation algorithms and their overall efficiency for the Schwinger model with a theta term. While adiabatic state preparation is proved to be effective, in practice it leads to large gate counts to prepare the ground state. The quantum approximate optimization algorithm (QAOA) provides excellent results while keeping the counts small by design, at the cost of an expensive classical minimization process. We introduce a “blocked” modification of the Schwinger Hamiltonian to be used in the QAOA that further decreases the length of the algorithms as the size of the problem is increased. The rodeo algorithm (RA) provides a powerful tool to efficiently prepare any eigenstate of the Hamiltonian, as long as its overlap with the initial guess is large enough. We obtain the best results when combining the blocked QAOA ansatz and the RA, as this provides an excellent initial state with a relatively short algorithm without the need to perform any classical steps for large problem sizes. Published by the American Physical Society 2025

Bazavov, Alexei (ORCID:0000000321411901)↗
DOE OSTI2023

Approximate Boltzmann distributions in quantum approximate optimization

Approaches to compute or estimate the output probability distributions from the quantum approximate optimization algorithm (QAOA) are needed to assess the likelihood it will obtain a quantum computational advantage. We analyze output from QAOA circuits solving 7200 random MaxCut instances, with $n$ = 14–23 qubits and depth parameter $p$ ≤ 12 and find that the average basis state probabilities follow approximate Boltzmann distributions: The average probabilities scale exponentially with their energy (cut value), with a peak at the optimal solution. Furthermore, we describe the rate of exponential scaling or effective temperature in terms of a series with a leading-order term $T$ ~ $C$ min /$n$ $\sqrt{p}$, with $C$ min the optimal solution energy. Using this scaling, we generate approximate output distributions with up to 38 qubits and find these give accurate accounts of important performance metrics in cases we can simulate exactly.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2020

Density-Matrix Based Extended Lagrangian Born–Oppenheimer Molecular Dynamics

Extended Lagrangian Born–Oppenheimer molecular dynamics [ Phys. Rev. Lett. 2008, 100, 123004] is presented for Hartree–Fock theory, where the extended electronic degrees of freedom are represented by a density matrix, including fractional occupation numbers at elevated electronic temperatures. In contrast to regular direct Born–Oppenheimer molecular dynamics simulations, no iterative self-consistent field optimization is required prior to the force evaluations. To sample regions of the potential energy landscape where the gap is small or vanishing, which leads to particular convergence problems in regular direct Born–Oppenheimer molecular dynamics simulations, an adaptive integration scheme for the extended electronic degrees of freedom is presented. The integration scheme is based on a tunable, low-rank approximation of a fourth-order kernel, K, that determines the metric tensor, T ≡ K T K, used in the extended harmonic oscillator of the Lagrangian that generates the dynamics of the electronic degrees of freedom. Here, the formulation and algorithms provide a general guide to implement extended Lagrangian Born–Oppenheimer molecular dynamics for quantum chemistry, density functional theory, and semiempirical methods using a density matrix formalism.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
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 OSTI2022

Multi-qubit entanglement and algorithms on a neutral-atom quantum computer

Gate model quantum computers promise to solve currently intractable computational problems if they can be operated at scale with long coherence times and high fidelity logic. Neutral atom hyperfine qubits provide inherent scalability due to their identical characteristics, long coherence times, and ability to be trapped in dense multi-dimensional arrays. Combined with the strong entangling interactions provided by Rydberg states, all the necessary characteristics for quantum computation are available. Here we demonstrate several quantum algorithms on a programmable gate model neutral atom quantum computer in an architecture based on individual addressing of single atoms with tightly focused optical beams scanned across a two-dimensional array of qubits. Preparation of entangled Greenberger-Horne-Zeilinger (GHZ) states with up to 6 qubits, quantum phase estimation for a chemistry problem, and the Quantum Approximate Optimization Algorithm (QAOA) for the MaxCut graph problem are demonstrated. These results highlight the emergent capability of neutral atom qubit arrays for universal, programmable quantum computation, as well as preparation of non-classical states of use for quantum enhanced sensing.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Distributed approximate minimal Steiner trees with millions of seed vertices on billion-edge graphs

In this report, we present a parallel 2-approximation Steiner minimal tree algorithm and its MPI-based distributed implementation. In place of expensive distance computations between all pairs of seed vertices, the solution we employ exploits a cheaper Voronoi cell computation. Our design leverages asynchronous processing and message prioritization to accelerate convergence of distance computations, and harnesses vertex and edge centric processing to offer fast time-to-solution. We demonstrate scalability and performance using real-world graphs with up to 128 billion edges and 512 compute nodes, and show the ability to find Steiner trees with up to one million seed vertices. Using 12 data instances, we present comparison with the state-of-the-art exact solver, SCIP-Jack, and two sequential 2-approximate algorithms. We empirically show that, on average, the total distance of the Steiner tree identified by our solution is 1.1290 times greater than the Steiner minimal tree – well within the theoretical approximation bound of 2.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Quantum Simulators and Applications on Quantum Framework

Simulating quantum circuits is essential for validating quantum algorithms. However, no single simulator consistently performs best - efficiency depends on circuit structure, entanglement, and depth. In this work, we integrate Qiskit-Aer (state-vector and matrix product state) and QTensor, a tree-tensor-network based simulator, into the Quantum Framework (QFw), a modular platform that supports multiple quantum backends via a unified interface. We also enable distributed quantum approximate optimization algorithm (DQAOA) application compatibility with QFw, allowing sub-problems to be solved in parallel at scale. We then benchmark DQAOA and TFIM (transverse field Ising model) circuits across supported simulators, showing how performance varies significantly with problem type. All simulations are deployed on the Frontier supercomputer using QFw's MPI-based orchestration for distributed, multinode execution. These results underscore the need for simulatoragnostic infrastructure to enable systematic evaluation and highperformance scaling of quantum workloads. QFw provides a practical and extensible path toward reproducible quantum algorithm development across diverse application domains.

Chundury, Srikar [ORNL] (ORCID:0009000183359259)↗
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

Monte Carlo Explicitly Correlated Second-Order Many-Body Green’s Function Calculations of Semiconductor Band Gaps

A systematically converging series of ab initio, post-density-functional, size-consistent, electron-correlated approximations is desired for predictive computing of felectronic band structures of insulating, semiconducting, and metallic solids. A series that meets all of these desiderata (except the applicability to metals) is ab initio many-body Green's function theory based on Gaussian-type-orbital (GTO) basis sets. Here, its leading-order approximation, the second-order Green's function (GF2) method in the diagonal and frequency-independent approximations with the aug-cc-pVDZ basis set, is applied to the fundamental band gaps of three semiconductors (diamond, silicon, and silicon carbide in the zincblende structure) using cluster models. Corrections are made to the basis-set-incompleteness errors by the explicit-correlation (F12) ansatz (GF2-F12) for the valence band edges. The crystals are modeled as surface-passivated clusters of increasing sizes, whose wave functions are expanded by up to 2709 GTO basis functions. Immense computational costs of these calculations are overcome by the highly scalable stochastic algorithm of the Monte Carlo GF2-F12 method, whose operation cost per state increases only as a cubic power of system size, which has a tiny memory footprint and easily achieves near-perfect parallel efficiency on thousands of CPUs or on hundreds of GPUs. The correlated, F12-corrected highest-occupied and lowest-unoccupied molecular-orbital energy (HOMO-LUMO) gap is 5.78 ± 0.07 eV for C 87 H 76 as compared with the experimental value of the fundamental (indirect) band gap of bulk diamond at 5.48 eV. The correlated, F12-corrected HOMO-LUMO gaps for Si 75 H 76 and Si 32 C 43 H 76 are 2.56 ± 0.15 eV and 3.50 ± 0.12 eV, respectively, which are expected to decrease further with increasing cluster sizes. As a result, the experimental fundamental (indirect) band gaps of bulk silicon and silicon carbide are 1.17 eV and 2.42 eV, respectively.

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
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↗
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 OSTI2024

Distributionally Robust Variational Quantum Algorithms With Shifted Noise

Given their potential to demonstrate near-term quantum advantage, variational quantum algorithms (VQAs) have been extensively studied. Although numerous techniques have been developed for VQA parameter optimization, it remains a significant challenge. A practical issue is the high sensitivity of quantum noise to environmental changes, and its propensity to shift in real time. This presents a critical problem as an optimized VQA ansatz may not perform effectively under a different noise environment. For the first time, we explore how to optimize VQA parameters to be robust against unknown shifted noise. We model the noise level as a random variable with an unknown probability density function (PDF), and we assume that the PDF may shift within an uncertainty set. This assumption guides us to formulate a distributionally robust optimization problem, with the goal of finding parameters that maintain effectiveness under shifted noise. We utilize a distributionally robust Bayesian optimization solver for our proposed formulation. This provides numerical evidence in both the Quantum Approximate Optimization Algorithm (QAOA) and the Variational Quantum Eigensolver (VQE) with hardware-efficient ansatz, indicating that we can identify parameters that perform more robustly under shifted noise. We regard this work as the first step towards improving the reliability of VQAs influenced by real-time noise.

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 OSTI2022

Simulations of frustrated Ising Hamiltonians using quantum approximate optimization

Novel magnetic materials are important for future technological advances. Theoretical and numerical calculations of ground-state properties are essential in understanding these materials, however, computational complexity limits conventional methods for studying these states. Here we investigate an alternative approach to preparing materials ground states using the quantum approximate optimization algorithm (QAOA) on near-term quantum computers. We study classical Ising spin models on unit cells of square, Shastry-Sutherland and triangular lattices, with varying field amplitudes and couplings in the material Hamiltonian. We find relationships between the theoretical QAOA success probability and the structure of the ground state, indicating that only a modest number of measurements (≲100) are needed to find the ground state of our nine-spin Hamiltonians, even for parameters leading to frustrated magnetism. We further demonstrate the approach in calculations on a trapped-ion quantum computer and succeed in recovering each ground state of the Shastry-Sutherland unit cell with probabilities close to ideal theoretical values. The results demonstrate the viability of QAOA for materials ground state preparation in the frustrated Ising limit, giving important first steps towards larger sizes and more complex Hamiltonians where quantum computational advantage may prove essential in developing a systematic understanding of novel materials.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Semiglobal Safety-Filtered Extremum Seeking With Unknown CBFs

We introduce a safe extremum-seeking (Safe ES) algorithm which achieves the minimization of an unknown objective function while ensuring that an unknown, yet measured, control barrier function (CBF) remains above an arbitrarily small negative value for all time. In other words, “practical safety” is maintained during the entire period of convergence to the constrained extremum. Our design is based on quadratic program (QP) CBF style filters for safety, which is applied in an average and estimated sense. Using nonsmooth analysis tools, we guarantee semiglobal practical asymptotic (SPA) stability of the global constrained optimum, practical convergence to the safe set if starting in a condition violating the CBF, and practical safety for all time—semiglobally—if starting in safe set. The safety result of the paper is analogous with modern notions of SPA stability, guaranteeing that, for any small violation of safety, there exist design coefficients which guarantee that such a small violation is not exceeded. The paper outlines a set of sufficient conditions on the barrier and objective functions, and by way of a Lyapunov argument, we demonstrate that nonconvex constrained optimization problems can be solved. We present these results in the setting of a static map and a dynamical system. A simulation example illustrates the results.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Impact of graph structures for QAOA on MaxCut

The quantum approximate optimization algorithm (QAOA) is a promising method of solving combinatorial optimization problems using quantum computing. QAOA on the MaxCut problem has been studied extensively on graphs with specific structure; however, little is known about the general performance of the algorithm on arbitrary graphs. Here, we investigate how different graph characteristics correlate with QAOA performance at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices. Some good predictors of QAOA success relate to graph symmetries, odd cycles, and density. For example, on eight vertex graphs, the average probability for selecting an optimal solution for graphs that contain no odd cycles after three iterations of QAOA is 60.6% compared to 48.2% for those that do. The data generated from these studies are shared in a publicly accessible database to serve as a benchmark for QAOA calculations and experiments. Knowing the relationship between structure and performance can be used to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.

97 MATHEMATICS AND COMPUTING↗