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 451 records · Page 25

Semiclassical Analysis of Constrained Quantum Systems

Exact procedures that follow Dirac's constraint quantization of gauge theories are usually technically involved and often difficult to implement in practice. We overview an 'effective' scheme for obtaining the leading order semiclassical corrections to the dynamics of constrained quantum systems developed elsewhere. Motivated by the geometrical view of quantum mechanics, our method mimics the classical Dirac-Bergmann algorithm and avoids direct reference to a particular representation of the physical Hilbert space. We illustrate the procedure through the example of a relativistic particle in Minkowski spacetime.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Flexibility of the factorized form of the unitary coupled cluster Ansatz

The factorized form of the unitary coupled cluster Ansatz is a popular state preparation Ansatz for electronic structure calculations of molecules on quantum computers. It is often viewed as an approximation (based on the Trotter product formula) for the conventional unitary coupled cluster operator. In this work, we show that the factorized form is quite flexible, allowing one to range from a conventional configuration interaction, to conventional unitary coupled cluster, to efficient approximations that lie in between these two. The variational minimization of the energy often allows simpler factorized unitary coupled cluster approximations to achieve high accuracy, even if they do not accurately approximate the Trotter product formula. This is similar to how quantum approximate optimization algorithms can achieve high accuracy with a small number of levels.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Generation of thermofield double states and critical ground states with a quantum computer

Significance Our experiment prepares two types of nontrivial quantum states on a trapped ion quantum computer: the thermofield double state of the transverse-field Ising model at arbitrary temperature and the quantum critical state of the zero-temperature model. We use techniques motivated by the quantum approximate optimization algorithm, and we implement a hybrid quantum–classical optimization loop to prepare the quantum critical state. Our results pave the way for exploring strongly correlated models at finite temperature and teleportation protocols inspired by black hole physics.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

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↗

Cosmological angular trispectra and non-Gaussian covariance

Angular cosmological correlators are infamously difficult to compute due to the highly oscillatory nature of the projection integrals. Motivated by recent development on analytic approaches to cosmological perturbation theory, in this paper we present an efficient method for computing cosmological four-point correlations in angular space, generalizing previous works on lower-point functions. This builds on the FFTLog algorithm that approximates the matter power spectrum as a sum over power-law functions, which makes certain momentum integrals analytically solvable. The computational complexity is drastically reduced for correlators in a "separable" form—we define a suitable notion of separability for cosmological trispectra, and derive formulas for angular correlators of different separability classes. As an application of our formalism, we compute the angular galaxy trispectrum at tree level, with and without primordial non-Gaussianity. This includes effects of redshift space distortion and bias parameters up to cubic order. We also compute the non-Gaussian covariance of the angular matter power spectrum due to the connected four-point function, beyond the Limber approximation. Finally, we demonstrate that, in contrast to the standard lore, the Limber approximation can fail for the non-Gaussian covariance computation even for large multipoles.

79 ASTRONOMY AND ASTROPHYSICS↗

Success of digital adiabatic simulation with large Trotter step

The simulation of adiabatic evolution has deep connections with adiabatic quantum computation, the quantum approximate optimization algorithm, and adiabatic state preparation. Here we address the error analysis problem in quantum simulation of adiabatic process using Trotter formulas. Here we show that with additional conditions, the circuit depth can be linear in simulation time T. The improvement comes from the observation that the fidelity error here can't be estimated by the norm distance between evolution operators. This phenomenon is termed the robustness of discretization in digital adiabatic simulation. It can be explained in three steps, from analytical and numerical evidence: (1) The fidelity error should be estimated by applying adiabatic theorem on the effective Hamiltonian instead. (2) Because of the specialty of Riemann-Lebesgue lemma, most adiabatic process is naturally robust against discretization. (3) As the Trotter step gets larger, the spectral gap of effective Hamiltonian tends to close, which results in the failure of digital adiabatic simulation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

NLO perturbativity bounds on quartic couplings in renormalizable theories with Φ 4 -like scalar sectors

The apparent breakdown of unitarity in low order perturbation theory is often is used to place bounds on the parameters of a theory. In this work we give an algorithm for approximately computing the next-to-leading order (NLO) perturbativity bounds on the quartic couplings of a renormalizable theory whose scalar sector is Φ 4 -like. And by this we mean theories where either there are no cubic scalar interactions, or the cubic couplings are related to the quartic couplings through spontaneous symmetry breaking. Furthermore, the quantity that tests where perturbation theory breaks down itself can be written as a perturbative series, and having the NLO terms allows one to test how well the series converges. We also present a simple example to illustrate the effect of considering these bounds at different orders in perturbation theory. For example, there is a noticeable difference in the viable parameter when the square of the NLO piece is included versus when it is not.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Poincare recurrence and spectral cascades in three-dimensional quantum turbulence

The time evolution of the ground state wave function of a zero-temperature Bose-Einstein condensate (BEC) gas is well described by the Hamiltonian Gross-Pitaevskii (GP) equation. Using a set of appropriately interleaved unitary collision-stream operators, a qubit lattice gas algorithm is devised, which on taking moments, recovers the Gross-Pitaevskii (GP) equation under diffusion ordering (time scales as length{sup 2}). Unexpectedly, there is a class of initial states whose Poincare recurrence time is extremely short and which, as the grid resolution is increased, scales with diffusion ordering (and not as length{sup 3}). The spectral results of J. Yepez et al.[Phys. Rev. Lett. 103, 084501 (2009).] for quantum turbulence are revised and it is found that it is the compressible kinetic energy spectrum that exhibits three distinct spectral regions: a small-k classical-like Kolmogorov k{sup -5/3}, a steep semiclassical cascade region, and a large-k quantum vortex spectrum k{sup -3}. For most evolution times the incompressible kinetic energy spectrum exhibits a somewhat robust quantum vortex spectrum of k{sup -3} for an extended range in k with a k{sup -3.4} spectrum for intermediate k. For linear vortices of winding number 1 there is an intermittent loss of the quantum vortex cascade with its signature seen in the time evolution of the kinetic energy E{sub kin}(t), the loss of the quantum vortex k{sup -3} spectrum in the incompressible kinetic energy spectrum as well as the minimalization of the vortex core isosurfaces that would totally inhibit any Kelvin wave vortex cascade. In the time intervals around these intermittencies the incompressible kinetic energy also exhibits a multicascade spectrum.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Isometric Tensor Network States in Two Dimensions

Tensor-network states (TNS) are a promising but numerically challenging tool for simulating two-dimensional (2D) quantum many-body problems. We introduce an isometric restriction of the TNS ansatz that allows for highly efficient contraction of the network. Here we consider two concrete applications using this ansatz. First, we show that a matrix-product state representation of a 2D quantum state can be iteratively transformed into an isometric 2D TNS. Second, we introduce a 2D version of the time-evolving block decimation algorithm for approximating of the ground state of a Hamiltonian as an isometric TNS-which we demonstrate for the 2D transverse field Ising model.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA

Understanding the best known parameters, performance, and systematic behavior of the Quantum Approximate Optimization Algorithm (QAOA) remain open research questions, even as the algorithm gains popularity. We introduce QAOAKit, a Python toolkit for the QAOA built for exploratory research. QAOAKit is a unified repository of preoptimized QAOA parameters and circuit generators for common quantum simulation frameworks. We combine, standardize, and cross-validate previously known parameters for the MaxCut problem, and incorporate this into QAOAKit. We also build conversion tools to use these parameters as inputs in several quantum simulation frameworks that can be used to reproduce, compare, and extend known results from various sources in the literature. We describe QAOAKit and provide examples of how it can be used to reproduce research results and tackle open problems in quantum optimization.

Shaydulin, Ruslan↗

A Multithreaded Algorithm for Network Alignment Via Approximate Matching

Network alignment is an optimization problem to find the best one-to-one map between the vertices of a pair of graphs that overlaps in as many edges as possible. It is a relaxation of the graph isomorphism problem and is closely related to the subgraph isomorphism problem. The best current approaches are entirely heuristic, and are iterative in nature. They generate real-valued heuristic approximations that must be rounded to find integer solutions. This rounding requires solving a bipartite maximum weight matching problem at each step in order to avoid missing high quality solutions. We investigate substituting a parallel, half-approximation for maximum weight matching instead of an exact computation. Our experiments show that the resulting difference in solution quality is negligible. We demonstrate almost a 20-fold speedup using 40 threads on an 8 processor Intel Xeon E7-8870 system (from 10 minutes to 36 seconds).

network alignment, matching, multicore↗

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↗

LEISURE: Load-Balanced Network-Wide Traffic Measurement and Monitor Placement

We report that network-wide traffic measurement is of interest to network operators to uncover global network behavior for the management tasks of traffic accounting, debugging or troubleshooting, security, and traffic engineering. Increasingly, sophisticated network measurement tasks such as anomaly detection and security forensic analysis are requiring in-depth fine-grained flow-level measurements. However, performing in-depth per-flow measurements (e.g., detailed payload analysis) is often an expensive process. Given the fast-changing Internet traffic landscape and large traffic volume, a single monitor is not capable of accomplishing the measurement tasks for all applications of interest due to its resource constraint. Moreover, uncovering global network behavior requires network-wide traffic measurements at multiple monitors across the network since traffic measured at any single monitor only provides a partial view and may not be sufficient or accurate. These factors call for coordinated measurements among multiple distributed monitors. In this paper, we present a centralized optimization framework, LEISURE (Load- EqualIzed meaSUREment), for load-balancing network measurement workloads across distributed monitors. Specifically, we consider various load-balancing problems under different objectives and study their extensions to support both fixed and flexible monitor deployment scenarios. We formulate the latter flexible monitor deployment case as an MILP (Mixed Integer Linear Programming) problem and propose several heuristic algorithms to approximate the optimal solution and reduce the computation complexity. We evaluate LEISURE via detailed simulations on Abilene and GEANT network traces to show that LEISURE can achieve much better load-balanced performance (e.g., 4.75 × smaller peak workload and 70 × smaller variance in workloads) across all coordinated monitors in comparison to a naive solution (uniform assignment) to accomplish network-wide traffic measurement tasks under the fixed monitor deployment scenario. Lastly, we also show that under the flexible monitor deployment setting, our heuristic solutions can achieve almost the same load-balancing performance as the optimal solution while reducing the computation times by a factor up to 22.5 × in Abilene and 800 × in GEANT.

42 ENGINEERING↗

Stochastic DG Placement for Conservation Voltage Reduction Based on Multiple Replications Procedure

Conservation voltage reduction (CVR) and distributed-generation (DG) integration are popular strategies implemented by utilities to improve energy efficiency. This paper investigates the interactions between CVR and DG placement to minimize load consumption in distribution networks, while keeping the lowest voltage level within the predefined range. The optimal placement of DG units is formulated as a stochastic optimization problem considering the uncertainty of DG outputs and load consumptions. A sample average approximation algorithm-based technique is developed to solve the formulated problem effectively. A multiple replications procedure is developed to test the stability of the solution and calculate the confidence interval of the gap between the candidate solution and optimal solution. The proposed method has been applied to the IEEE 37-bus distribution test system with different scenarios. The numerical results indicate that the implementations of CVR and DG, if combined, can achieve significant energy savings.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Electric Power Distribution System Model Simplification Using Segment Substitution

Quasi-static time-series (QSTS) simulation is used to simulate the behavior of distribution systems over long periods of time (typically hours to years). The technique involves repeatedly solving the load-flow problem for a distribution system model and is useful for distributed energy resource (DER) planning. When a QSTS simulation has a small time step and a long duration, the computational burden of the simulation can be a barrier to integration into utility workflows. One way to relieve the computational burden is to simplify the system model. The segment substitution method of simplifying distribution system models introduced in this paper offers model bus reduction of up to 98% with a simplification error as low as 0.2% (0.002 pu voltage). In contrast to existing methods of distribution system model simplification, which rely on topological inspection and linearization, the segment substitution method uses black-box segment data and an assumed simplified topology.

Reiman, Andrew P. (ORCID:0000000302042960)↗

Comparing implementations of penalized weighted least-squares sinogram restoration

Purpose: A CT scanner measures the energy that is deposited in each channel of a detector array by x rays that have been partially absorbed on their way through the object. The measurement process is complex and quantitative measurements are always and inevitably associated with errors, so CT data must be preprocessed prior to reconstruction. In recent years, the authors have formulated CT sinogram preprocessing as a statistical restoration problem in which the goal is to obtain the best estimate of the line integrals needed for reconstruction from the set of noisy, degraded measurements. The authors have explored both penalized Poisson likelihood (PL) and penalized weighted least-squares (PWLS) objective functions. At low doses, the authors found that the PL approach outperforms PWLS in terms of resolution-noise tradeoffs, but at standard doses they perform similarly. The PWLS objective function, being quadratic, is more amenable to computational acceleration than the PL objective. In this work, the authors develop and compare two different methods for implementing PWLS sinogram restoration with the hope of improving computational performance relative to PL in the standard-dose regime. Sinogram restoration is still significant in the standard-dose regime since it can still outperform standard approaches and it allows for correction of effects that are not usually modeled in standard CT preprocessing. Methods: The authors have explored and compared two implementation strategies for PWLS sinogram restoration: (1) A direct matrix-inversion strategy based on the closed-form solution to the PWLS optimization problem and (2) an iterative approach based on the conjugate-gradient algorithm. Obtaining optimal performance from each strategy required modifying the naive off-the-shelf implementations of the algorithms to exploit the particular symmetry and sparseness of the sinogram-restoration problem. For the closed-form approach, the authors subdivided the large matrix inversion into smaller coupled problems and exploited sparseness to minimize matrix operations. For the conjugate-gradient approach, the authors exploited sparseness and preconditioned the problem to speed up convergence. Results: All methods produced qualitatively and quantitatively similar images as measured by resolution-variance tradeoffs and difference images. Despite the acceleration strategies, the direct matrix-inversion approach was found to be uncompetitive with iterative approaches, with a computational burden higher by an order of magnitude or more. The iterative conjugate-gradient approach, however, does appear promising, with computation times half that of the authors' previous penalized-likelihood implementation. Conclusions: Iterative conjugate-gradient based PWLS sinogram restoration with careful matrix optimizations has computational advantages over direct matrix PWLS inversion and over penalized-likelihood sinogram restoration and can be considered a good alternative in standard-dose regimes.

60 APPLIED LIFE SCIENCES↗

First-order convex feasibility algorithms for x-ray CT

Purpose: Iterative image reconstruction (IIR) algorithms in computed tomography (CT) are based on algorithms for solving a particular optimization problem. Design of the IIR algorithm, therefore, is aided by knowledge of the solution to the optimization problem on which it is based. Often times, however, it is impractical to achieve accurate solution to the optimization of interest, which complicates design of IIR algorithms. This issue is particularly acute for CT with a limited angular-range scan, which leads to poorly conditioned system matrices and difficult to solve optimization problems. In this paper, we develop IIR algorithms which solve a certain type of optimization called convex feasibility. The convex feasibility approach can provide alternatives to unconstrained optimization approaches and at the same time allow for rapidly convergent algorithms for their solution-thereby facilitating the IIR algorithm design process. Methods: An accelerated version of the Chambolle-Pock (CP) algorithm is adapted to various convex feasibility problems of potential interest to IIR in CT. One of the proposed problems is seen to be equivalent to least-squares minimization, and two other problems provide alternatives to penalized, least-squares minimization. Results: The accelerated CP algorithms are demonstrated on a simulation of circular fan-beam CT with a limited scanning arc of 144 Degree-Sign . The CP algorithms are seen in the empirical results to converge to the solution of their respective convex feasibility problems. Conclusions: Formulation of convex feasibility problems can provide a useful alternative to unconstrained optimization when designing IIR algorithms for CT. The approach is amenable to recent methods for accelerating first-order algorithms which may be particularly useful for CT with limited angular-range scanning. The present paper demonstrates the methodology, and future work will illustrate its utility in actual CT application.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗

U.S. stock market interaction network as learned by the Boltzmann machine

Here, we study historical dynamics of joint equilibrium distribution of stock returns in the U.S. stock market using the Boltzmann distribution model being parametrized by external fields and pairwise couplings. Within Boltzmann learning framework for statistical inference, we analyze historical behavior of the parameters inferred using exact and approximate learning algorithms. Since the model and inference methods require use of binary variables, effect of this mapping of continuous returns to the discrete domain is studied. The presented results show that binarization preserves the correlation structure of the market. Properties of distributions of external fields and couplings as well as the market interaction network and industry sector clustering structure are studied for different historical dates and moving window sizes. We demonstrate that the observed positive heavy tail in distribution of couplings is related to the sparse clustering structure of the market. We also show that discrepancies between the model’s parameters might be used as a precursor of financial instabilities.

97 MATHEMATICS AND COMPUTING↗