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 199 records · Page 11

Variational quantum simulation of the critical Ising model with symmetry averaging

Here we investigate the use of deep multiscale entanglement renormalization ansatz (DMERA) circuits as a variational ansatz. We use the exactly solvable one-dimensional critical transverse-field Ising model as a test bed. Numerically exact simulation of the quantum circuit ansatz can in this case be carried out to hundreds of qubits by exploiting efficient classical algorithms for simulating matchgate circuits. We find that, for this system, the DMERA strongly outperforms a standard quantum approximate optimization algorithm (QAOA)–style ansatz, and that a major source of systematic error in correlation functions approximated using the DMERA is the breaking of the translational and Kramers-Wannier symmetries of the transverse-field Ising model. We are able to reduce this error by up to four orders of magnitude by symmetry averaging, without incurring additional cost in qubits or circuit depth. Here, we propose that this technique for mitigating systematic error could be applied to noisy intermediate-scale quantum (NISQ) simulations of physical systems with other symmetries.

1-dimensional spin chains↗

Mathematical model of the metal mould surface temperature optimization

The article is focused on the problem of generating a uniform temperature field on the inner surface of shell metal moulds. Such moulds are used e.g. in the automotive industry for artificial leather production. To produce artificial leather with uniform surface structure and colour shade the temperature on the inner surface of the mould has to be as homogeneous as possible. The heating of the mould is realized by infrared heaters located above the outer mould surface. The conceived mathematical model allows us to optimize the locations of infrared heaters over the mould, so that approximately uniform heat radiation intensity is generated. A version of differential evolution algorithm programmed in Matlab development environment was created by the authors for the optimization process. For temperate calculations software system ANSYS was used. A practical example of optimization of heaters locations and calculation of the temperature of the mould is included at the end of the article.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

MPI-FAUN: An MPI-Based Framework for Alternating-Updating Nonnegative Matrix Factorization

Non-negative matrix factorization (NMF) is the problem of determining two non-negative low rank factors W and H, for the given input matrix A, such that A≈WH. NMF is a useful tool for many applications in different domains such as topic modeling in text mining, background separation in video analysis, and community detection in social networks. Despite its popularity in the data mining community, there is a lack of efficient parallel algorithms to solve the problem for big data sets. The main contribution of this work is a new, high-performance parallel computational framework for a broad class of NMF algorithms that iteratively solves alternating non-negative least squares (NLS) subproblems for W and H. It maintains the data and factor matrices in memory (distributed across processors), uses MPI for interprocessor communication, and, in the dense case, provably minimizes communication costs (under mild assumptions). The framework is flexible and able to leverage a variety of NMF and NLS algorithms, including Multiplicative Update, Hierarchical Alternating Least Squares, and Block Principal Pivoting. Our implementation allows us to benchmark and compare different algorithms on massive dense and sparse data matrices of size that spans from few hundreds of millions to billions. We demonstrate the scalability of our algorithm and compare it with baseline implementations, showing significant performance improvements. The code and the datasets used for conducting the experiments are available online.

2D↗

Quantum-classical tradeoffs and multi-controlled quantum gate decompositions in variational algorithms

The computational capabilities of near-term quantum computers are limited by the noisy execution of gate operations and a limited number of physical qubits. Hybrid variational algorithms are well-suited to near-term quantum devices because they allow for a wide range of tradeoffs between the amount of quantum and classical resources used to solve a problem. This paper investigates tradeoffs available at both the algorithmic and hardware levels by studying a specific case – applying the Quantum Approximate Optimization Algorithm (QAOA) to instances of the Maximum Independent Set (MIS) problem. We consider three variants of the QAOA which offer different tradeoffs at the algorithmic level in terms of their required number of classical parameters, quantum gates, and iterations of classical optimization needed. Since MIS is a constrained combinatorial optimization problem, the QAOA must respect the problem constraints. This can be accomplished by using many multi-controlled gate operations which must be decomposed into gates executable by the target hardware. We study the tradeoffs available at this hardware level, combining the gate fidelities and decomposition efficiencies of different native gate sets into a single metric called the gate decomposition cost .

Tomesh, Teague↗

A nonlinearly preconditioned conjugate gradient algorithm for rank‐ R canonical tensor approximation

Summary Alternating least squares (ALS) is often considered the workhorse algorithm for computing the rank‐ R canonical tensor approximation, but for certain problems, its convergence can be very slow. The nonlinear conjugate gradient (NCG) method was recently proposed as an alternative to ALS, but the results indicated that NCG is usually not faster than ALS. To improve the convergence speed of NCG, we consider a nonlinearly preconditioned NCG (PNCG) algorithm for computing the rank‐ R canonical tensor decomposition. Our approach uses ALS as a nonlinear preconditioner in the NCG algorithm. Alternatively, NCG can be viewed as an acceleration process for ALS. We demonstrate numerically that the convergence acceleration mechanism in PNCG often leads to important pay‐offs for difficult tensor decomposition problems, with convergence that is significantly faster and more robust than for the stand‐alone NCG or ALS algorithms. We consider several approaches for incorporating the nonlinear preconditioner into the NCG algorithm that have been described in the literature previously and have met with success in certain application areas. However, it appears that the nonlinearly PNCG approach has received relatively little attention in the broader community and remains underexplored both theoretically and experimentally. Thus, this paper serves several additional functions, by providing in one place a concise overview of several PNCG variants and their properties that have only been described in a few places scattered throughout the literature, by systematically comparing the performance of these PNCG variants for the tensor decomposition problem, and by drawing further attention to the usefulness of nonlinearly PNCG as a general tool. In addition, we briefly discuss the convergence of the PNCG algorithm. In particular, we obtain a new convergence result for one of the PNCG variants under suitable conditions, building on known convergence results for non‐preconditioned NCG. Copyright © 2014 John Wiley & Sons, Ltd.

Sterck, Hans De↗

Exploiting Kronecker structure in exponential integrators: Fast approximation of the action of φ $-$functions of matrices via quadrature

Here, in this article, we propose an algorithm for approximating the action of φ $-$ functions of matrices against vectors, which is a key operation in exponential time integrators. In particular, we consider matrices with Kronecker sum structure, which arise from problems admitting a tensor product representation. The method is based on quadrature approximations of the integral form of the φ $-$ functions combined with a scaling and modified squaring method. Owing to the Kronecker sum representation, only actions of 1D matrix exponentials are needed at each quadrature node and assembly of the full matrix can be avoided. Additionally, we derive a priori bounds for the quadrature error, which show that, as expected by classical theory, the rate of convergence of our method is supergeometric. Guided by our analysis, we construct a fast and robust method for estimating the optimal scaling factor and number of quadrature nodes that minimizes the total cost for a prescribed error tolerance. We investigate the performance of our algorithm by solving several linear and semilinear time-dependent problems in 2D and 3D. The results show that our method is accurate and orders of magnitude faster than the current state-of-the-art.

97 MATHEMATICS AND COMPUTING↗

Empirical performance bounds for quantum approximate optimization

The quantum approximate optimization algorithm (QAOA) has been put forth as a method for near-term quantum computers to solve optimization problems. However, assessments of QAOA performance have mostly focused on small structured problem instances while performance on more general instances is less clear. Here, we numerically simulate QAOA pure state dynamics for every instance of MaxCut on non-isomorphic unweighted graphs with nine or fewer vertices with depth parameters p ≤ 3. We find the approximation ratios and optimized circuit parameters concentrate across graphs of a given size and empirically show increases in concentration as graph size increases. The parameter concentration leads to two median-angle heuristics that overcome difficulties in QAOA parameter optimization and obtain mean approximation ratios within 3% and 0.2% of the optimal. We also analyze the probability to measure an optimal solution and find increasing variations between graphs as depth increases, in stark contrast to the approximation ratios which concentrate as depth increases. Furthermore, the resulting benchmark data set gives empirical bounds for on-going experimental realizations and lays groundwork for theoretical extensions to greater problem sizes and depths where QAOA may prove important for practically relevant problems.

79 ASTRONOMY AND ASTROPHYSICS↗

Stable schemes for dissipative particle dynamics with conserved energy

This article presents a new numerical scheme for the discretization of dissipative particle dynamics with conserved energy. The key idea is to reduce elementary pairwise stochastic dynamics (either fluctuation/dissipation or thermal conduction) to effective single-variable dynamics, and to approximate the solution of these dynamics with one step of a Metropolis–Hastings algorithm. This ensures by construction that no negative internal energies are encountered during the simulation, and hence allows to increase the admissible timesteps to integrate the dynamics, even for systems with small heat capacities. Stability is only limited by the Hamiltonian part of the dynamics, which suggests resorting to multiple timestep strategies where the stochastic part is integrated less frequently than the Hamiltonian one.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer

Abstract Realizing the potential of near-term quantum computers to solve industry-relevant constrained-optimization problems is a promising path to quantum advantage. In this work, we consider the extractive summarization constrained-optimization problem and demonstrate the largest-to-date execution of a quantum optimization algorithm that natively preserves constraints on quantum hardware. We report results with the Quantum Alternating Operator Ansatz algorithm with a Hamming-weight-preserving XY mixer (XY-QAOA) on trapped-ion quantum computer. We successfully execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159. We demonstrate the necessity of directly encoding the constraints into the quantum circuit by showing the trade-off between the in-constraint probability and the quality of the solution that is implicit if unconstrained quantum optimization methods are used. We show that this trade-off makes choosing good parameters difficult in general. We compare XY-QAOA to the Layer Variational Quantum Eigensolver algorithm, which has a highly expressive constant-depth circuit, and the Quantum Approximate Optimization Algorithm. We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.

97 MATHEMATICS AND COMPUTING↗

Numerical gate synthesis for quantum heuristics on bosonic quantum processors

There is a recent surge of interest and insights regarding the interplay of quantum optimal control and variational quantum algorithms. We study the framework in the context of qudits which are, for instance, definable as controllable electromagnetic modes of a superconducting cavity system coupled to a transmon. By employing recent quantum optimal control approaches described in (Petersson and Garcia, 2021), we showcase control of single-qudit operations up to eight states, and two-qutrit operations, mapped respectively onto a single mode and two modes of the resonator. We discuss the results of numerical pulse engineering on the closed system for parametrized gates useful to implement Quantum Approximate Optimization Algorithm (QAOA) for qudits. The results show that high fidelity ( > 0.99) is achievable with sufficient computational effort for most cases under study, and extensions to multiple modes and open, noisy systems are possible. The tailored pulses can be stored and used as calibrated primitives for a future compiler in circuit quantum electrodynamics (cQED) systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems

We develop a global variable substitution method that reduces n-variable monomials in combinatorial optimization problems to equivalent instances with monomials in fewer variables. We apply this technique to 3-SAT and analyze the optimal quantum unitary circuit depth needed to solve the reduced problem using the quantum approximate optimization algorithm. For benchmark 3-SAT problems, we find that the upper bound of the unitary circuit depth is smaller when the problem is formulated as a product and uses the substitution method to decompose gates than when the problem is written in the linear formulation, which requires no decomposition.

3-SAT↗

A Model-Free No-arbitrage Price Bound for Variance Options

We suggest a numerical approximation for an optimization problem, motivated by its applications in finance to find the model-free no-arbitrage bound of variance options given the marginal distributions of the underlying asset. A first approximation restricts the computation to a bounded domain. Then we propose a gradient projection algorithm together with the finite difference scheme to solve the optimization problem. We prove the general convergence, and derive some convergence rate estimates. Finally, we give some numerical examples to test the efficiency of the algorithm.

97 MATHEMATICS AND COMPUTING↗

Multistart algorithm for identifying all optima of nonconvex stochastic functions

Here, we propose a multistart algorithm to identify all local minima of a constrained, nonconvex stochastic optimization problem. The algorithm uniformly samples points in the domain and then starts a local stochastic optimization run from any point that is the "probabilistically best" point in its neighborhood. Under certain conditions, our algorithm is shown to asymptotically identify all local optima with high probability; this holds even though our algorithm is shown to almost surely start only finitely many local stochastic optimization runs. We demonstrate the performance of an implementation of our algorithm on nonconvex stochastic optimization problems, including identifying optimal variational parameters for the quantum approximate optimization algorithm.

97 MATHEMATICS AND COMPUTING↗

Stable Difference Schemes for the Neutron Transport Equation

The initial boundary value problem for the neutron transport equation is considered. The first and second orders of accuracy difference schemes for the approximate solution of this problem are presented. In applications, the stability estimates for solutions of difference schemes for the approximate solution of the neutron transport equation are obtained. Numerical techniques are developed and algorithms are tested on an example in MATLAB.

73 NUCLEAR PHYSICS AND RADIATION PHYSICS↗

First order nonadiabatic coupling matrix elements between excited states: Implementation and application at the TD-DFT and pp-TDA levels

The recently proposed rigorous yet abstract theory of first order nonadiabatic coupling matrix elements (fo-NACME) between electronically excited states [Z. Li and W. Liu, J. Chem. Phys. 141, 014110 (2014)] is specified in detail for two widely used models: The time-dependent density functional theory and the particle-particle Tamm-Dancoff approximation. The actual implementation employs a Lagrangian formalism with atomic-orbital based direct algorithms, which makes the computation of fo-NACME very similar to that of excited-state gradients. Although the methods have great potential in investigating internal conversions and nonadiabatic dynamics between excited states of large molecules, only prototypical systems as a first pilot application are considered here to illustrate some conceptual aspects.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Grover-QAOA for 3-SAT: quadratic speedup, fair-sampling, and parameter clustering

Abstract The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT (All-SAT) and Max-SAT problems. G-QAOA is less resource-intensive and more adaptable for these problems than Grover’s algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles.

Zhang, Zewen (ORCID:000000032258613X)↗

An Adaptive Derivative-based Method for Function Approximation

To alleviate the high computational cost of large-scale multi-physics simulations to study the relationships between the model parameters and the outputs of interest, response surfaces are often used in place of the exact functional relationships. This report explores a method for response surface construction using adaptive sampling guided by derivative information at each selected sample point. This method is especially suitable for applications that can readily provide added information such as gradients and Hessian with respect to the input parameters under study. When higher order terms (third and above) in the Taylor series are negligible, the approximation error for this method can be controlled. We present details of the adaptive algorithm and numerical results on a few test problems.

99 GENERAL AND MISCELLANEOUS↗

A Monte Carlo algorithm for degenerate plasmas

A procedure for performing Monte Carlo calculations of plasmas with an arbitrary level of degeneracy is outlined. It has possible applications in inertial confinement fusion and astrophysics. Degenerate particles are initialised according to the Fermi–Dirac distribution function, and scattering is via a Pauli blocked binary collision approximation. The algorithm is tested against degenerate electron–ion equilibration, and the degenerate resistivity transport coefficient from unmagnetised first order transport theory. The code is applied to the cold fuel shell and alpha particle equilibration problem of inertial confinement fusion.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗