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 55 records · Page 3

All sources NASA NTRS DOE OSTI

DOE OSTI2025

Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms

The quantum approximate optimization algorithm (QAOA) has the potential to approximately solve complex combinatorial optimization problems in polynomial time. However, current noisy quantum devices cannot solve large problems due to hardware constraints. In this work, we develop an algorithm that decomposes the QAOA input problem graph into a smaller problem and solves MaxCut using QAOA on the reduced graph. The algorithm requires a subroutine that can be classical or quantum—in this work, we implement the algorithm twice on each graph. One implementation uses the classical solver Gurobi in the subroutine and the other uses QAOA. We solve these reduced problems with QAOA. On average, the reduced problems require only approximately 1/10 of the number of vertices than the original MaxCut instances. Furthermore, the average approximation ratio of the original MaxCut problems is 0.75, while the approximation ratios of the decomposed graphs are on average of 0.96 for both Gurobi and QAOA. With this decomposition, we are able to measure optimal solutions for ten 100-vertex graphs by running single-layer QAOA circuits on the Quantinuum trapped-ion quantum computer H1-1, sampling each circuit only 500 times. This approach is best suited for sparse, particularly k-regular graphs, as k-regular graphs on n vertices can be decomposed into a graph with at most $\frac{nk}{k+1}$ vertices in polynomial time. Further reductions can be obtained with a potential trade-off in computational time. In conclusion, while this paper applies the decomposition method to the MaxCut problem, it can be applied to more general classes of combinatorial optimization problems.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2025

DONKEY: A Flexible and Accurate Algorithm for Clustering

We propose an accurate clustering algorithm suitable for the varied and multidimensional data sets that correspond to temporal snapshots from on-the-fly nonadiabatic trajectory-based simulations of photoexcited dynamics. The algorithm approximates the underlying probability density function using variable kernel density estimation, with local maxima corresponding to cluster centers. Each data point is then assigned to one of the maxima by employing a maximization procedure. Finally, clusters artificially separated by minor fluctuations in the probability density are merged. The algorithm does not require parameter tuning, which ensures flexibility and reduces the risk of bias. It is tested on several synthetic data sets, where it consistently outperforms conventional clustering algorithms. As a final example, the algorithm is applied to the excited dynamics of the norbornadiene ⇌ quadricyclane (C 7 H 8 ) molecular photoswitch, demonstrating how distinct reaction pathways can be identified.

algorithms↗

DOE OSTI2021

Scaling Out a Combinatorial Algorithm for Discovering Carcinogenic Gene Combinations to Thousands of GPUs

Cancer is a leading cause of death in the US, second only to heart disease. It is primarily a result of a combination of an estimated two-nine genetic mutations (multi-hit combinations). Although a body of research has identified hundreds of cancer-causing genetic mutations, we don’t know the specific combination of mutations responsible for specific instances of cancer for most cancer types. An approximate algorithm for solving the weighted set cover problem was previously adapted to identify combinations of genes with mutations that may be responsible for individual instances of cancer. However, the algorithm’s computational requirement scales exponentially with the number of genes, making it impractical for identifying more than three-hit combinations, even after the algorithm was parallelized and scaled up to a V100 GPU. Since most cancers have been estimated to require more than three hits, we scaled out the algorithm to identify combinations of four or more hits using 1000 nodes (6000 V100 GPUs with ≈48×106 processing cores) on the Summit supercomputer at Oak Ridge National Laboratory. Efficiently scaling out the algorithm required a series of algorithmic innovations and optimizations for balancing an exponentially divergent workload across processors and for minimizing memory latency and inter-node communication. We achieved an average strong scaling efficiency of 90.14% (80.96%–97.96% for 200 to 1000 nodes), compared to a 100 node run, with 84.18% scaling efficiency for 1000 nodes. With experimental validation, the multi-hit combinations identified here could provide further insight into the etiology of different cancer subtypes and provide a rational basis for targeted combination therapy.

Dash, Sajal↗

DOE OSTI2026

A Structure-Preserving Decorated Particle Method for the Vlasov-Poisson System

We revisit the Scovel-Weinstein framework (Scovel & Weinstein, CPAM 1994) for reducing the Vlasov-Poisson system while preserving its Hamiltonian structure. Standard particle-in-cell (PIC) algorithms approximate the distribution function by macro-particles with position and velocity. In contrast, Scovel-Weinstein decorated particles involve additional shape degrees of freedom, while maintaining a finite-dimensional reduction with Hamiltonian structure inherited from the continuum model. Although the original work established this structure three decades ago, its computational potential has remained largely unexplored. We present a practical implementation of the Scovel-Weinstein model and compare it with a standard PIC algorithm. Numerical experiments demonstrate that macro-particles in standard PIC can be replaced by far fewer decorated particles while retaining comparable accuracy. This decorated particle approach offers a new structure-preserving paradigm for kinetic plasma simulation.

65M75, 70H05, 70G65↗

DOE OSTI2023

AMG Preconditioners based on parallel hybrid coarsening and multi-objective graph matching

We describe preliminary results from a multi-objective graph matching algorithm, in the coarsening step of an aggregation-based Algebraic MultiGrid (AMG) preconditioner, for solving large and sparse linear systems of equations on high-end parallel computers. We have two objectives. First, we wish to improve the convergence behavior of the AMG method when applied to highly anisotropic problems. Second, we wish to extend the parallel package \texttt{PSCToolkit} to exploit multi-threaded parallelism at the node level on multi-core processors. Our matching proposal balances the need to simultaneously compute high weights and large cardinalities by a new formulation of the weighted matching problem combining both these objectives using a parameter $\lambda$. We compute the matching by a parallel $2/3-\varepsilon$-approximation algorithm for maximum weight matchings. Results with the new matching algorithm show that for a suitable choice of the parameter $\lambda$ we compute effective preconditioners in the presence of anisotropy, i.e., smaller solve times, setup times, iterations counts, and operator complexity.

D'Ambra, Pasqua↗

DOE OSTI2026

An efficient explicit implementation of a near-optimal quantum algorithm for simulating linear dissipative differential equations

We propose an efficient block-encoding technique for the implementation of the Linear Combination of Hamiltonian Simulations (LCHS) for simulating dissipative initial-value problems. This algorithm approximates a target nonunitary operator as a weighted sum of Hamiltonian evolutions, thereby emulating a dissipative problem by mixing various time scales. We introduce an efficient encoding of the LCHS into a quantum circuit based on a simple coordinate transformation that turns the dependence on the summation index into a trigonometric function. Classically, this method is equivalent to the use of a highly accurate Fejér-Clenshaw-Curtis quadrature formula. Quantumly, this significantly simplifies block-encoding of a dissipative problem and allows one to perform an exponential number of Hamiltonian simulations by a single Quantum Signal Processing (QSP) circuit. The resulting LCHS circuit has high success probability and the selector scales logarithmically with the number of terms in the LCHS sum and linearly with time. Careful analysis of error convergence proves that this method is more efficient than other LCHS circuits that have recently appeared in the literature. We verify the quantum circuit and its scaling by simulating it on a digital emulator of fault-tolerant quantum computers and, as a test problem, solve the advection-diffusion equation. The proposed algorithm can be used for simulating a wide class of nonunitary initial-value problems including the Liouville equation with added dissipation and linear embeddings of nonlinear systems, such as the Koopman-von Neumann and Carleman embeddings.

Novikau, I [Lawrence Livermore National Laboratory↗

DOE OSTI2023

High-Level Synthesis of Irregular Applications: A Case Study on Influence Maximization

The Influence Maximization problem is the problem of identifying a small cohort of actors from a broader population that, when initially activated in a diffusion process, are expected to result in a large number of activations in the population. While the problem is known to be NP-hard, several approximation algorithms have been devised by leveraging its submodular structure. While these algorithms are theoretically efficient, they are computationally very expensive in practice. This work advances the current state-of-the-art parallelization scheme for the IMM algorithm by devising the adoption of custom hardware accelerators implemented on FPGAs by leveraging High Level Synthesis from OpenCL. We study the performance of our proposed approach by exploring optimizations tailored at improving the parallel efficiency of the accelerators and highlight their effects and limitations in accelerating complex graph analytic applications. Our experimental evaluation shows that FPGA acceleration can improve the performance of the LT diffusion model up to 1.72x for the entire application and up to 2.90x for its most important kernel with respect to a CPU only parallel execution. The FPGA acceleration of the LT model shows also a 1.54x reduction in energy consumption when compared to a parallel CPU only run.

Neff, Reece W.↗

DOE OSTI2026

Evaluating the Limits of QAOA Parameter Transfer at High-Rounds on Sparse Ising Models With Geometrically Local Cubic Terms

The emergent practical applicability of the Quantum Approximate Optimization Algorithm (QAOA) for approximate combinatorial optimization is a subject of considerable interest. One of the primary limitations of QAOA is the task of finding a set of good parameters, which is usually done using a variational optimization loop. Parameter transfer, or parameter concentration, is a phenomenon where QAOA angles trained on problem instances that are self-similar tend to perform well for other problem instances from that similar class. This suggests a potentially highly efficient and scalable non-variational learning method for QAOA angle finding. In this work, we systematically study QAOA parameter transferability from small problem sizes (16 and 27 decision variables) onto large problem instances (up to 156 qubits) for heavy-hex graph Ising models with geometrically local higher order terms using the Julia based QAOA simulation tool \texttt{JuliQAOA} to perform classical angle finding for up to $49$ QAOA layers ($p$). Parameter transfer of the fixed angles is validated using a combination of full statevector, Projected Entangled Pair States (PEPS), Matrix Product State (MPS), and LOWESA numerical simulations. We find that the QAOA parameter transfer from single instances applied to other (unseen) problem instances does not in general provide monotonically improving performance as a function of $p$ - there are many cases where the performance temporarily decreases as a function of $p$ - but despite this the transferred angles have a general trend of improved expectation value as the QAOA depth increases, in many cases converging close to the true ground-state energy of the $100+$ qubit instances. We also sample the hardware-compatible Ising models using the ensemble of transfer-learned QAOA parameters on several superconducting qubit IBM Quantum processors with 127, 133, and 156 qubits. We find continuous solution quality improvement of the hardware-compatible QAOA circuits run on the IBM NISQ processors up to $p=5$ on \texttt{ibm\_fez}, up to $p=9$ on \texttt{ibm\_torino}, and up to $p=10$ on \texttt{ibm\_pittsburgh}.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2022

Optimal Power Dispatch of DGs in Radial and Mesh AC Grids: A Hybrid Solution Methodology between the Salps Swarm Algorithm and Successive Approximation Power Flow Method

In this paper, we address the problem of the optimal power dispatch of Distributed Generators (DGs) in Alternating Current (AC) networks, better known as the Optimal Power Flow (OPF) problem. We used, as the objective function, the minimization of power losses (P loss ) associated with energy transport, which are subject to the set of constraints that compose AC networks in an environment of distributed generation. To validate the effectiveness of the proposed methodology in solving the OPF problem in any network topology, we employed one 10-node mesh test system and three radial text systems: 10, 33, and 69 nodes. In each test system, DGs were allowed to inject 20%, 40%, and 60% of the power supplied by the slack generator in the base case. To solve the OPF problem, we used a master–slave methodology that integrates the optimization method Salps Swarm Algorithm (SSA) and the load flow technique based on the Successive Approximation (SA) method. Moreover, for comparison purposes, we employed some of the algorithms reported in the specialized literature to solve the OPF problem (the continuous genetic algorithm, the particle swarm optimization algorithm, the black hole algorithm, the antlion optimization algorithm, and the Multi-Verse Optimizer algorithm), which were selected because of their excellent results in solving such problems. The results obtained by the proposed solution methodology demonstrate its superiority and convergence capacity in terms of minimization of P loss in both radial and mesh systems. It provided the best reduction in minimum P loss in short processing times and showed excellent repeatability in each test system and scenario under analysis.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

DOE OSTI2022

Quantum computational phase transition in combinatorial problems

Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. As there are no algorithmic guarantee possible for QAOA to outperform classical computers, without a proof that bounded-error quantum polynomial time (BQP) ≠ nondeterministic polynomial time (NP), it is necessary to investigate the empirical advantages of QAOA. We identify a computational phase transition of QAOA when solving hard problems such as SAT—random instances are most difficult to train at a critical problem density. We connect the transition to the controllability and the complexity of QAOA circuits. Moreover, we find that the critical problem density in general deviates from the SAT-UNSAT phase transition, where the hardest instances for classical algorithms lies. Then, we show that the high problem density region, which limits QAOA’s performance in hard optimization problems (reachability deficits), is actually a good place to utilize QAOA: its approximation ratio has a much slower decay with the problem density, compared to classical approximate algorithms. Indeed, it is exactly in this region that quantum advantages of QAOA over classical approximate algorithms can be identified.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2021

Combinatorial Algorithms in Scientific Computing

We provide the final report for this grant, detailing the publications, software produced, students trained who have joined the DOE workforce, and the impact our work has had on computational mathematics and related disciplines.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2022

Low rank approximation in simulations of quantum algorithms

Simulating quantum algorithms on classical computers is challenging when the system size, i.e., the number of qubits used in the quantum algorithm, is moderately large. However, some quantum algorithms and the corresponding quantum circuits can be simulated efficiently on a classical computer if the input quantum state is a low rank tensor and all intermediate states of the quantum algorithm can be represented or approximated by low rank tensors. Here, in this paper, we examine the possibility of simulating a few quantum algorithms by using low-rank canonical polyadic (CP) decomposition to represent the input and all intermediate states of these algorithms. Two rank reduction algorithms are used to enable efficient simulation. We show that some of the algorithms preserve the low rank structure of the input state and can thus be efficiently simulated on a classical computer. However, the rank of the intermediate states in other quantum algorithms can increase rapidly, making efficient simulation more difficult. To some extent, such difficulty reflects the advantage or superiority of a quantum computer over a classical computer. As a result, understanding the low rank structure of a quantum algorithm allows us to identify algorithms that can benefit significantly from quantum computers.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2026

Classical combinatorial optimization scaling for random Ising models on 2D heavy-hex graphs

Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the quantum approximate optimization algorithm. In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the time-to-solution (TTS) metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. 100 000 spin variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time TTS scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2025

Classical optimization with imaginary-time block encoding on quantum computers: The MaxCut problem

Optimization problems in finance, physics, and computer science are typically very hard to tackle in classical computing; quantum computing could help speed up computations and provide efficient methods for tackling large problems. Typically, to treat a problem with a quantum computer, the optimal solution is cast as the ground state of a diagonal Hamiltonian. Here, we develop a method, called imaginary-time evolution block encoding (ITE-BE), based on a recent imaginary-time algorithm, which requires no variational parameter optimization, as all parameters can be derived analytically from the target Hamiltonian. We also demonstrate that our method can be successfully combined with other quantum algorithms such as the quantum approximate optimization algorithm (QAOA). For illustration, here we study the MaxCut problem. We find that the QAOA ansatz increases the postselection success of ITE-BE, and shallow QAOA circuits, when boosted with ITE-BE, achieve better performance than deeper QAOA circuits. For the special case of the transverse initial state, we adapt our block-encoding scheme to allow for a deterministic application of the first layer of the circuit.

Zhong, Dawei [University of Southern California, L↗

DOE OSTI2024

Benchmarking highly entangled states on a 60-atom analogue quantum simulator

Abstract Quantum systems have entered a competitive regime in which classical computers must make approximations to represent highly entangled quantum states 1,2 . However, in this beyond-classically-exact regime, fidelity comparisons between quantum and classical systems have so far been limited to digital quantum devices 2–5 , and it remains unsolved how to estimate the actual entanglement content of experiments 6 . Here, we perform fidelity benchmarking and mixed-state entanglement estimation with a 60-atom analogue Rydberg quantum simulator, reaching a high-entanglement entropy regime in which exact classical simulation becomes impractical. Our benchmarking protocol involves extrapolation from comparisons against an approximate classical algorithm, introduced here, with varying entanglement limits. We then develop and demonstrate an estimator of the experimental mixed-state entanglement 6 , finding our experiment is competitive with state-of-the-art digital quantum devices performing random circuit evolution 2–5 . Finally, we compare the experimental fidelity against that achieved by various approximate classical algorithms, and find that only the algorithm we introduce is able to keep pace with the experiment on the classical hardware we use. Our results enable a new model for evaluating the ability of both analogue and digital quantum devices to generate entanglement in the beyond-classically-exact regime, and highlight the evolving divide between quantum and classical systems.

Science & Technology - Other Topics↗

DOE OSTI2026

Quantum Computing in Next-Generation Transportation Optimization

We explore how quantum computing (QC) can advance transportation optimization, with a focus on two high-impact areas: traffic signal control and vehicle electrification with grid integration. As transportation systems grow in complexity, classical optimization methods increasingly struggle to deliver scalable and efficient solutions, particularly for real-time, data-rich environments. This work identifies key challenges within these two domains where QC may offer advantages, particularly in handling combinatorial decision spaces and dynamic constraints. We begin by outlining the limitations of classical approaches for traffic signal control optimization and electric vehicle charging coordination, highlighting where computational limitations arise. Previous quantum formulations are presented and new formulations are proposed to demonstrate how emerging quantum algorithms, including quantum annealing and the Quantum Approximation Optimization Algorithm, could be leveraged to reformulate and address these problems. We also evaluate the suitability of current quantum hardware and discuss recent trends that indicate when QC may become a viable tool for transportation applications. While acknowledging the present limitations of QC technologies, this poster emphasizes the importance of preparing quantum-compatible models today. By reviewing and establishing formulations that align with the strengths of quantum algorithms, researchers and practitioners can better position themselves to take advantage of QC advancements as they occur. This work aims to provide a practical, forward-looking perspective on the near-term potential of quantum computing in transportation optimization.

33 ADVANCED PROPULSION SYSTEMS↗

DOE OSTI2026

Self-consistent mean-field quantum approximate optimization

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

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

DOE OSTI2026

Self-consistent mean-field quantum approximate optimization

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