Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “approximation 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 145 records · Page 8
All sourcesNASA NTRSDOE OSTI
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)↗
NASA NTRS1988

A methodology for the synthesis of robust feedback systems

A new methodology is developed for the synthesis of linear, time-variant (LTI) controllers for multivariable LTI systems. The resulting closed-loop system is nominally stable and exhibits a known level of performance. In addition, robustness of the feedback system is guaranteed, i.e., stability and performance are retained in the presence of multiple unstructured uncertainty blocks located at various points in the feedback loop. The design technique is referred to as the Causality Recovery Methodology (CRM). The CRM relies on the Youla parameterization of all stabilizing compensators to ensure nominal stability of the feedback system. A frequency-domain inequality in terms of the structured singular value mu defines the robustness specification. The optimal compensator, with respect to the mu condition, is shown to be noncausal in general. The aim of the CRM is to find a stable, causal transfer function matrix that approximates the robustness characteristics of the optimal solution. The CRM, via a series of infinite-dimensional convex programs, produces a closed-loop system whose performance robustness is at least as good as that of any initial design. The algorithm is approximated by a finite dimensional process for the purposes of implementation. Two numerical examples confirm the potential viability of the CRM concept; however, the robustness improvement comes at the expense of increased computational burden and compensator complexity.

Milich, David Albert↗
NASA NTRS1993

Producing approximate answers to database queries

We have designed and implemented a query processor, called APPROXIMATE, that makes approximate answers available if part of the database is unavailable or if there is not enough time to produce an exact answer. The accuracy of the approximate answers produced improves monotonically with the amount of data retrieved to produce the result. The exact answer is produced if all of the needed data are available and query processing is allowed to continue until completion. The monotone query processing algorithm of APPROXIMATE works within the standard relational algebra framework and can be implemented on a relational database system with little change to the relational architecture. We describe here the approximation semantics of APPROXIMATE that serves as the basis for meaningful approximations of both set-valued and single-valued queries. We show how APPROXIMATE is implemented to make effective use of semantic information, provided by an object-oriented view of the database, and describe the additional overhead required by APPROXIMATE.

Vrbsky, Susan V.↗
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]↗
NASA NTRS1988

Parallel algorithm for determining motion vectors in ice floe images by matching edge features

A parallel algorithm is described to determine motion vectors of ice floes using time sequences of images of the Arctic ocean obtained from the Synthetic Aperture Radar (SAR) instrument flown on-board the SEASAT spacecraft. Researchers describe a parallel algorithm which is implemented on the MPP for locating corresponding objects based on their translationally and rotationally invariant features. The algorithm first approximates the edges in the images by polygons or sets of connected straight-line segments. Each such edge structure is then reduced to a seed point. Associated with each seed point are the descriptions (lengths, orientations and sequence numbers) of the lines constituting the corresponding edge structure. A parallel matching algorithm is used to match packed arrays of such descriptions to identify corresponding seed points in the two images. The matching algorithm is designed such that fragmentation and merging of ice floes are taken into account by accepting partial matches. The technique has been demonstrated to work on synthetic test patterns and real image pairs from SEASAT in times ranging from .5 to 0.7 seconds for 128 x 128 images.

Manohar, M.↗
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)↗
NASA NTRS1986

Multiple grid problems on concurrent-processing computers

Three computer codes were studied which make use of concurrent processing computer architectures in computational fluid dynamics (CFD). The three parallel codes were tested on a two processor multiple-instruction/multiple-data (MIMD) facility at NASA Ames Research Center, and are suggested for efficient parallel computations. The first code is a well-known program which makes use of the Beam and Warming, implicit, approximate factored algorithm. This study demonstrates the parallelism found in a well-known scheme and it achieved speedups exceeding 1.9 on the two processor MIMD test facility. The second code studied made use of an embedded grid scheme which is used to solve problems having complex geometries. The particular application for this study considered an airfoil/flap geometry in an incompressible flow. The scheme eliminates some of the inherent difficulties found in adapting approximate factorization techniques onto MIMD machines and allows the use of chaotic relaxation and asynchronous iteration techniques. The third code studied is an application of overset grids to a supersonic blunt body problem. The code addresses the difficulties encountered when using embedded grids on a compressible, and therefore nonlinear, problem. The complex numerical boundary system associated with overset grids is discussed and several boundary schemes are suggested. A boundary scheme based on the method of characteristics achieved the best results.

Eberhardt, D. S.↗
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↗
NASA NTRS1993

Fast structural design and analysis via hybrid domain decomposition on massively parallel processors

A hybrid domain decomposition framework for static, transient and eigen finite element analyses of structural mechanics problems is presented. Its basic ingredients include physical substructuring and /or automatic mesh partitioning, mapping algorithms, 'gluing' approximations for fast design modifications and evaluations, and fast direct and preconditioned iterative solvers for local and interface subproblems. The overall methodology is illustrated with the structural design of a solar viewing payload that is scheduled to fly in March 1993. This payload has been entirely designed and validated by a group of undergraduate students at the University of Colorado using the proposed hybrid domain decomposition approach on a massively parallel processor. Performance results are reported on the CRAY Y-MP/8 and the iPSC-860/64 Touchstone systems, which represent both extreme parallel architectures. The hybrid domain decomposition methodology is shown to outperform leading solution algorithms and to exhibit an excellent parallel scalability.

Farhat, Charbel↗
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 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 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 OSTI2024

Hamiltonian switching control of noisy bipartite qubit systems

Abstract We develop a Hamiltonian switching ansatz for bipartite control that is inspired by the quantum approximate optimization algorithm, to mitigate environmental noise on qubits. We demonstrate the control for a central spin coupled to bath spins via isotropic Heisenberg interactions, and then make physical applications to the protection of quantum gates performed on superconducting transmon qubits coupling to environmental two-level-systems (TLSs) through dipole-dipole interactions, as well as on such qubits coupled to both TLSs and a Lindblad bath. The control field is classical and acts only on the system qubits. We use reinforcement learning with policy gradient to optimize the Hamiltonian switching control protocols, using a fidelity objective for specific target quantum gates. We use this approach to demonstrate effective suppression of both coherent and dissipative noise, with numerical studies achieving target gate implementations with fidelities over 0.9999 (four nines) in the majority of our test cases and showing improvement beyond this to values of 0.999 999 999 (nine nines) upon a subsequent optimization by GRadient Ascent Pulse Engineering (GRAPE). We analyze how the control depth, total evolution time, number of environmental TLS, and choice of optimization method affect the fidelity achieved by the optimal protocols and reveal some critical behaviors of bipartite control of quantum gates.

Physics↗
DOE OSTI2025

Closed-Form Approximation of the Total Variation Proximal Operator

Total variation (TV) is a widely used function for regularizing imaging inverse problems that is particularly appropriate for images whose underlying structure is piecewise constant. TV regularized optimization problems are typically solved using proximal methods, but the way in which they are applied is constrained by the absence of a closed-form expression for the proximal operator of the TV function. A closed-form approximation of the TV proximal operator has previously been proposed, but its accuracy was not theoretically explored in detail. Here, we address this gap by making several new theoretical contributions, proving that the approximation leads to a proximal operator of some convex function, it is equivalent to a gradient descent step on a smoothed version of TV, and that its error can be fully characterized and controlled with its scaling parameter. We experimentally validate our theoretical results on image denoising and sparse-view computed tomography (CT) image reconstruction.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Synthesis of Single Qutrit Circuits from Clifford + R Gates

The Clifford + R gate-set is a promising basis for fault-tolerant synthesis of qutrit unitaries. We present an algorithm for approximating an arbitrary single-qutrit unitary with a circuit over the Clifford + R gates. Moreover, we analyze its complexity and obtain the non-Clifford gates cost.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
NASA NTRS1977

Implicit approximate-factorization schemes for the efficient solution of steady transonic flow problems

Implicit approximate-factorization algorithms (AF) are developed for the solution of steady-state transonic flow problems. The performance of the AF solution method is evaluated relative to that of the standard solution method for transonic flow problems, successive line over-relaxation (SLOR). Both methods are applied to the solution of the nonlinear, two-dimensional transonic small-disturbance equation. Results indicate that the AF method requires substantially less computer time than SLOR to solve the nonlinear finite-difference matrix equation for a transonic flow field. This increase in computational efficiency is achieved with no appreciable increase in computer storage or coding complexity.

Ballhaus, W. F.↗