Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Graph”

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 1,189 records · Page 66

Solving MaxCut with quantum imaginary time evolution

We introduce a method to solve the MaxCut problem efficiently based on quantum imaginary time evolution (QITE). We employ a linear Ansatz for unitary updates and an initial state involving no entanglement, as well as an imaginary-time-dependent Hamiltonian interpolating between a given graph and a subgraph with two edges excised. We apply the method to thousands of randomly selected graphs with up to fifty vertices. We show that our algorithm exhibits a 93% and above performance converging to the maximum solution of the MaxCut problem for all considered graphs. Our results compare favorably with the performance of classical algorithms, such as the greedy and Goemans–Williamson algorithms. We also discuss the overlap of the final state of the QITE algorithm with the ground state as a performance metric, which is a quantum feature not shared by other classical algorithms.

97 MATHEMATICS AND COMPUTING↗

Toward computing bounds for Ramsey numbers using quantum annealing

Quantum annealing is a powerful tool for solving and approximating combinatorial optimization problems, such as graph partitioning, community detection, centrality, routing problems, and more. In this paper we explore the use of quantum annealing as a tool for use in exploring combinatorial mathematics research problems. We consider the monochromatic triangle problem and the Ramsey number problem, both examples of graph coloring. Conversion to quadratic unconstrained binary optimization (QUBO) form is required to run on quantum hardware. While the monochromatic triangle problem is quadratic by nature, the Ramsey number problem requires the use of order reduction methods for a quadratic formulation. The goal is to provide a method for producing special colorings of graphs which if successful would provide lower bounds for certain Ramsey numbers. We discuss implementations, limitations, and results when running on the D-Wave Advantage quantum annealer.

97 MATHEMATICS AND COMPUTING↗

Charged Particle Tracking via Edge-Classifying Interaction Networks

Recent work has demonstrated that geometric deep learning methods such as graph neural networks (GNNs) are well suited to address a variety of reconstruction problems in high-energy particle physics. In particular, particle tracking data are naturally represented as a graph by identifying silicon tracker hits as nodes and particle trajectories as edges, given a set of hypothesized edges, edge-classifying GNNs identify those corresponding to real particle trajectories. In this work, we adapt the physics-motivated interaction network (IN) GNN toward the problem of particle tracking in pileup conditions similar to those expected at the high-luminosity Large Hadron Collider. Assuming idealized hit filtering at various particle momenta thresholds, we demonstrate the IN’s excellent edge-classification accuracy and tracking efficiency through a suite of measurements at each stage of GNN-based tracking: graph construction, edge classification, and track building. The proposed IN architecture is substantially smaller than previously studied GNN tracking architectures; this is particularly promising as a reduction in size is critical for enabling GNN-based tracking in constrained computing environments. Furthermore, the IN may be represented as either a set of explicit matrix operations or a message passing GNN. Efforts are underway to accelerate each representation via heterogeneous computing resources towards both high-level and low-latency triggering applications.

accelerator physics↗

Quantum computing for a profusion of postman problem variants

In this paper we study the viability of solving the Chinese Postman Problem, a graph routing optimization problem, and many of its variants on a quantum annealing device. Routing problem variants considered include graph type, directionally varying weights, number of parties involved in routing, among others. We put emphasis on the explanation of how to convert such problems into quadratic unconstrained binary optimization (QUBO) problems. QUBO is one of two equivalent natural paradigms for quantum annealing devices, the other being the Ising Model. We also expand upon a previously discovered algorithm for solving the Chinese Postman Problem on a closed undirected graph to decrease the number of constraints and variables used in the problem. Optimal annealing parameter settings and constraint weight values are discussed based on results from implementation on the D-Wave 2000Q and Advantage. Results from classical, purely quantum, and hybrid algorithms are compared.

97 MATHEMATICS AND COMPUTING↗

Risk-Averse Bi-Level Stochastic Network Interdiction Model for Cyber-Security Risk Management

Security of cyber networks is crucial; recent severe cyber-attacks have had a devastating effect on many large organizations. The attack graph, which maps the potential attack paths of a cyber network, is a popular tool for analyzing cyber system vulnerability. In this study, we propose a bi-level stochastic network interdiction model on an attack graph to enable a risk-averse, resource constrained cyber network defender to optimally deploy security countermeasures that protect against attackers with an uncertain budget. This risk- averse conditional-value-at-risk (CVaR) model minimizes a weighted sum of the expected maximum loss over all scenarios and the expected maximum loss from the most damaging attack scenarios. We develop a customized constraint and column generation algorithm to solve our model as well as several acceleration techniques to improve the computational efficiency. Numerical experiments demonstrate that the acceleration techniques enable the solution of relatively large problems within a reasonable amount of time: applying all the acceleration techniques also reduces the average computation time of the basic algorithm by 71% for 100-node graphs. Using metrics called mean-risk value of stochastic solution and value of risk-aversion, computational results suggest that our stochastic risk-averse model significantly outperforms deterministic and risk-neutral models when 1) the distribution of attacker budget is heavy-right-tailed and 2) the defender is highly risk-averse.

Bhuiyan, Tanveer H.↗

Parallel algorithms for finding connected components using linear algebra

Finding connected components is one of the most widely used operations on a graph. Optimal serial algorithms for the problem have been known for half a century, and many competing parallel algorithms have been proposed over the last several decades under various different models of parallel computation. This paper presents a class of parallel connected-component algorithms designed using linear-algebraic primitives. These algorithms are based on a PRAM algorithm by Shiloach and Vishkin and can be designed using standard GraphBLAS operations. Here, we demonstrate two algorithms of this class, one named LACC for Linear Algebraic Connected Components, and the other named FastSV which can be regarded as LACC’s simplification. With the support of the highly-scalable Combinatorial BLAS library, LACC and FastSV outperform the previous state-of-the-art algorithm by a factor of up to 12x for small to medium scale graphs. For large graphs with more than 50B edges, LACC and FastSV scale to 4K nodes (262K cores) of a Cray XC40 supercomputer and outperform previous algorithms by a significant margin. This remarkable performance is accomplished by (1) exploiting sparsity that was not present in the original PRAM algorithm formulation, (2) using high-performance primitives of Combinatorial BLAS, and (3) identifying hot spots and optimizing them away by exploiting algorithmic insights.

97 MATHEMATICS AND COMPUTING↗

Importance of Engineered and Learned Molecular Representations in Predicting Organic Reactivity, Selectivity, and Chemical Properties

Machine-readable chemical structure representations are foundational in all attempts to harness machine learning for the prediction of reactivities, selectivities, and chemical properties directly from molecular structure. The featurization of discrete chemical structures into a continuous vector space is a critical phase undertaken before model selection, and the development of new ways to quantitatively encode molecules is an active area of research. Here, we highlight the application and suitability of different representations, from expert-guided “engineered” descriptors to automatically “learned” features, in different prediction tasks relevant to organic and organometallic chemistry, where differing amounts of training data are available. These tasks include statistical models of stereo- and enantioselectivity, thermochemistry, and kinetics developed using experimental and quantum chemical data. The use of expert-guided molecular descriptors provides an opportunity to incorporate chemical knowledge, domain expertise, and physical constraints into statistical modeling. In applications to stereoselective organic and organometallic catalysis, where data sets may be relatively small and 3D-geometries and conformations play an important role, mechanistically informed features can be used successfully to obtain predictive statistical models that are also chemically interpretable. We provide an overview of several recent applications of this approach to obtain quantitative models for reactivity and selectivity, where topological descriptors, quantum mechanical calculations of electronic and steric properties, along with conformational ensembles, all feature as essential ingredients of the molecular representations used. Alternatively, more flexible, general-purpose molecular representations such as attributed molecular graphs can be used with machine learning approaches to learn the complex relationship between a structure and prediction target. This approach has the potential to out-perform more traditional representation methods such as “hand-crafted” molecular descriptors, particularly as data set sizes grow. One area where this is particularly relevant is in the use of large sets of quantum mechanical data to train quantitative structure–property relationships. A general approach toward curating useful data sets and training highly accurate graph neural network models is discussed in the context of organic bond dissociation enthalpies, where this strategy outperforms regression using precomputed descriptors. Finally, we describe how graph neural network predictions can be incorporated into mechanistically informed statistical models of chemical reactivity and selectivity. Once trained, this approach avoids the expensive computational overhead associated with quantum mechanical calculations, while maintaining chemical interpretability. We illustrate examples for which fast predictions of bond dissociation enthalpy and of the identities of radicals formed through cleavage of a molecule’s weakest bond are used in simple physical models of site-selectivity and reactivity.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Beyond nothingness in the formation and functional relevance of voids in polymer films

Abstract Voids—the nothingness—broadly exist within nanomaterials and impact properties ranging from catalysis to mechanical response. However, understanding nanovoids is challenging due to lack of imaging methods with the needed penetration depth and spatial resolution. Here, we integrate electron tomography, morphometry, graph theory and coarse-grained molecular dynamics simulation to study the formation of interconnected nanovoids in polymer films and their impacts on permeance and nanomechanical behaviour. Using polyamide membranes for molecular separation as a representative system, three-dimensional electron tomography at nanometre resolution reveals nanovoid formation from coalescence of oligomers, supported by coarse-grained molecular dynamics simulations. Void analysis provides otherwise inaccessible inputs for accurate fittings of methanol permeance for polyamide membranes. Three-dimensional structural graphs accounting for the tortuous nanovoids within, measure higher apparent moduli with polyamide membranes of higher graph rigidity. Our study elucidates the significance of nanovoids beyond the nothingness, impacting the synthesis‒morphology‒function relationships of complex nanomaterials.

36 MATERIALS SCIENCE↗

Short-depth QAOA circuits and quantum annealing on higher-order ising models

Abstract We present a direct comparison between QAOA (Quantum Alternating Operator Ansatz), and QA (Quantum Annealing) on 127 qubit problem instances. QAOA with p = 1, 2 rounds is executed on the 127 qubit heavy-hex graph gate-model quantum computer ibm_washington, using on-device grid-searches for angle finding, and QA is executed on two Pegasus-chip D-Wave quantum annealers. The problems are random Ising models whose connectivity matches heavy-hex graphs and the Pegasus graph connectivity, and optionally include hardware-compatible cubic terms ( Z Z Z terms). The QAOA circuits are heavily optimized and of extremely short depth, with a CNOT depth of 6 per round, which allows whole chip usage of the heavy-hex lattice. QAOA and QA are both compared against simulated annealing and the optimal solutions are computed exactly using CPLEX. The noiseless mean QAOA expectation values for p = 1, 2 are computed using classical light-cone based simulations. We find QA outperforms QAOA on the evaluated devices.

127 qubits↗

Data-driven quantum approximate optimization algorithm for power systems

Abstract Quantum technology provides a ground-breaking methodology to tackle challenging computational issues in power systems. It is especially promising for Distributed Energy Resources (DERs) dominant systems that have been widely developed to promote energy sustainability. In those systems, knowing the maximum sections of power and data delivery is essential for monitoring, operation, and control. However, high computational effort is required. By leveraging quantum resources, Quantum Approximate Optimization Algorithm (QAOA) provides a means to search for these sections efficiently. However, QAOA performance relies heavily on critical parameters, especially for weighted graphs. Here we present a data-driven QAOA, which transfers quasi-optimal parameters between weighted graphs based on the normalized graph density. We verify the strategy with 39,774 expectation value calculations. Without parameter optimization, our data-driven QAOA is comparable with the Goemans-Williamson algorithm. This work advances QAOA and pilots its practical application to power systems in noisy intermediate-scale quantum devices.

Jing, Hang (ORCID:0000000256343489)↗

Deep learning for characterizing the self-assembly of three-dimensional colloidal systems

Creating a systematic framework to characterize the structural states of colloidal self-assembly systems is crucial for unraveling the fundamental understanding of these systems’ stochastic and non-linear behavior. The most accurate characterization methods create high-dimensional neighborhood graphs that may not provide useful information about structures unless these are well-defined reference crystalline structures. Dimensionality reduction methods are thus required to translate the neighborhood graphs into a low-dimensional space that can be easily interpreted and used to characterize non-reference structures. We investigate a framework for colloidal system state characterization that employs deep learning methods to reduce the dimensionality of neighborhood graphs. The framework next uses agglomerative hierarchical clustering techniques to partition the low-dimensional space and assign physically meaningful classifications to the resulting partitions. In this work, we first demonstrate the proposed colloidal self-assembly state characterization framework on a three-dimensional in silico system of 500 multi-flavored colloids that self-assemble under isothermal conditions. We next investigate the generalizability of the characterization framework by applying the framework to several independent self-assembly trajectories, including a three-dimensional in silico system of 2052 colloidal particles that undergo evaporation-induced self-assembly.

36 MATERIALS SCIENCE↗

Graphical Gaussian Process Regression Model for Aqueous Solvation Free Energy Prediction of Organic Molecules in Redox Flow Battery

The solvation free energy of organic molecules is a critical parameter in determining emergent properties such as solubility, liquid-phase equilibrium constants, and pKa and redox potentials in an organic redox flow battery. In this work, we present a machine learning (ML) model that can learn and predict the aqueous solvation free energy of an organic molecule using Gaussian process regression method based on a new molecular graph kernel. To investigate the performance of the ML model on electrostatic interaction, the nonpolar interaction contribution of solvent and the conformational entropy of solute in solvation free energy, three data sets with implicit or explicit water solvent models, and contribution of conformational entropy of solute are tested. We demonstrate that our ML model can predict the solvation free energy of molecules at chemical accuracy with a mean absolute error of less than 1 kcal/mol for subsets of the QM9 dataset and the Freesolv database. To solve the general data scarcity problem for a graph-based ML model, we propose a dimension reduction algorithm based on the distance between molecular graphs, which can be used to examine the diversity of the molecular data set. It provides a promising way to build a minimum training set to improve prediction for certain test sets where the space of molecular structures is predetermined.

25 ENERGY STORAGE↗

Advancing energy storage through solubility prediction: leveraging the potential of deep learning

Solubility prediction plays a crucial role in energy storage applications, such as redox flow batteries, because it directly affects the efficiency and reliability. Researchers have developed various methods that utilize quantum calculations and descriptors to predict the aqueous solubilities of organic molecules. Notably, machine learning models based on descriptors have shown promise for solubility prediction. As deep learning tools, graph neural networks (GNNs) have emerged to capture complex structure–property relationships for material property prediction. Specifically, MolGAT, a type of GNN model, was designed to incorporate n-dimensional edge attributes, enabling the modeling of intricacies in molecular graphs and enhancing the prediction capabilities. In a previous study, MolGAT successfully screened 23 467 promising redox-active molecules from a database of over 500 000 compounds, based on redox potential predictions. This study focused on applying the MolGAT model to predict the aqueous solubility (log S) of a broad range of organic compounds, including those previously screened for redox activity. The model was trained on a diverse sample of 8494 organic molecules from AqSolDB and benchmarked against literature data, demonstrating superior accuracy compared with other state of the art graph-based and descriptor-based models. Subsequently, the trained MolGAT model was employed to screen redox-active organic compounds identified in the first phase of high-throughput virtual screening, targeting favorable solubility in energy storage applications. The second round of screening, which considered solubility, yielded 12 332 promising redox-active and soluble organic molecules suitable for use in aqueous redox flow batteries. Thus, the two-phase high-throughput virtual screening approach utilizing MolGAT, specifically trained for redox potential and solubility, is an effective strategy for selecting suitable intrinsically soluble redox-active molecules from extensive databases, potentially advancing energy storage through reliable material development. This indicates that the model is reliable for predicting the solubility of various molecules and provides valuable insights for energy storage, pharmaceutical, environmental, and chemical applications.

25 ENERGY STORAGE↗

High performance FPGA embedded system for machine learning based tracking and trigger in sPhenix and EIC

We present a comprehensive end-to-end pipeline to classify triggers versus background events in this paper. This pipeline makes online decisions to select signal data and enables the intelligent trigger system for efficient data collection in the Data Acquisition System (DAQ) of the upcoming sPHENIX and future EIC (Electron-Ion Collider) experiments. Starting from the coordinates of pixel hits that are lightened by passing particles in the detector, the pipeline applies three-stage of event processing (hits clustering, track reconstruction, and trigger detection) and labels all processed events with the binary tag of trigger versus background events. The pipeline consists of deterministic algorithms such as clustering pixels to reduce event size, tracking reconstruction to predict candidate edges, and advanced graph neural network-based models for recognizing the entire jet pattern. In particular, we apply the message-passing graph neural network to predict links between hits and reconstruct tracks and a hierarchical pooling algorithm (DiffPool) to make the graph-level trigger detection. We obtain an impressive performance (≥70% accuracy) for trigger detection with only 3200 neuron weights in the end-to-end pipeline. We deploy the end-to-end pipeline into a field-programmable gate array (FPGA) and accelerate the three stages with speedup factors of 1152, 280, and 21, respectively.

Instruments & Instrumentation↗

Many-body expansion based machine learning models for octahedral transition metal complexes

Abstract Graph-based machine learning (ML) models for material properties show great potential to accelerate virtual high-throughput screening of large chemical spaces. However, in their simplest forms, graph-based models do not include any 3D information and are unable to distinguish stereoisomers such as those arising from different orderings of ligands around a metal center in coordination complexes. In this work we present a modification to revised autocorrelation descriptors, a molecular graph featurization method, for predicting spin state dependent properties of octahedral transition metal complexes (TMCs). Inspired by analytical semi-empirical models for TMCs, the new modeling strategy is based on the many-body expansion (MBE) and allows one to tune the captured stereoisomer information by changing the truncation order of the MBE. We present the necessary modifications to include this approach in two commonly used ML methods, kernel ridge regression and feed-forward neural networks. On a test set composed of all possible isomers of binary TMCs, the best MBE models achieve mean absolute errors (MAEs) of 2.75 kcal mol −1 on spin-splitting energies and 0.26 eV on frontier orbital energy gaps, a 30%–40% reduction in error compared to models based on our previous approach. We also observe improved generalization to previously unseen ligands where the best-performing models exhibit MAEs of 4.00 kcal mol −1 (i.e. a 0.73 kcal mol −1 reduction) on the spin-splitting energies and 0.53 eV (i.e. a 0.10 eV reduction) on the frontier orbital energy gaps. Because the new approach incorporates insights from electronic structure theory, such as ligand additivity relationships, these models exhibit systematic generalization from homoleptic to heteroleptic complexes, allowing for efficient screening of TMC search spaces.

Meyer, Ralf (ORCID:0000000322360261)↗

Quantum Routing and Entanglement Dynamics Through Bottlenecks

To implement arbitrary quantum circuits in architectures with restricted interactions, one may effectively simulate all-to-all connectivity by routing quantum information. We consider the entanglement dynamics and routing between two regions only connected through an intermediate “bottleneck” region with few qubits. In such systems, where the entanglement rate is restricted by a vertex boundary rather than an edge boundary of the underlying interaction graph, existing results such as the small incremental entangling theorem give only a trivial constant lower bound on the routing time (the minimum time to perform an arbitrary permutation). We significantly improve the lower bound on the routing time in systems with a vertex bottleneck. Specifically, for any system with two regions 𝐿,𝑅 with 𝑁 𝐿 ,𝑁 𝑅 qubits, respectively, coupled only through an intermediate region 𝐶 with 𝑁 𝐶 qubits, for any 𝛿 > 0 we show a lower bound of Ω⁢(𝑁$^{1−𝛿}_{𝑅}$/√𝑁 𝐿⁢ 𝑁 𝐶 ) on the Hamiltonian quantum routing time when using piecewise time-independent Hamiltonians, or time-dependent Hamiltonians subject to a smoothness condition. We also prove an upper bound on the average amount of bipartite entanglement between 𝐿 and 𝐶,𝑅 that can be generated in time 𝑡 by such architecture-respecting Hamiltonians in systems constrained by vertex bottlenecks, improving the scaling in the system size from 𝑂⁡(𝑁 𝐿⁢ 𝑡) to 𝑂⁡(√𝑁 𝐿⁢ 𝑡). As a special case, when applied to the star graph (i.e., one vertex connected to 𝑁 leaves), we obtain an Ω⁡(√𝑁 1−𝛿 ) lower bound on the routing time and on the time to prepare 𝑁/2 Bell pairs between the vertices. We also show that, in systems of free particles, we can route optimally on the star graph in time Θ⁡(√𝑁) using Hamiltonian quantum routing, obtaining a speedup over gate-based routing, which takes time Θ⁡(𝑁).

97 MATHEMATICS AND COMPUTING↗

Dimer piling problems and interacting field theory

The dimer tiling problem asks in how many ways can the edges of a graph be covered by dimers so that each site is covered once. In the special case of a planar graph, this problem has a solution in terms of a free fermionic field theory. We rediscover and explore an expression for the number of coverings of an arbitrary graph by arbitrary objects in terms of an interacting fermionic field theory first proposed by Samuel. Generalizations of the dimer tiling problem, which we call “dimer piling problems,” demand that each site be covered N times by indistinguishable dimers. Our field theory provides a solution of these problems in the large- N limit. We give a similar path integral representation for certain lattice coloring problems. Published by the American Physical Society 2024

Astronomy & Astrophysics↗

Quantum routing with teleportation

We study the problem of implementing arbitrary permutations of qubits under interaction constraints in quantum systems that allow for arbitrarily fast local operations and classical communication (LOCC). In particular, we show examples of speedups over swap-based and more general unitary routing methods by distributing entanglement and using LOCC to perform quantum teleportation. We further describe an example of an interaction graph for which teleportation gives a logarithmic speedup in the worst-case routing time over swap-based routing. We also study limits on the speedup afforded by quantum teleportation—showing an O ( N log N ) upper bound on the separation in routing time for any interaction graph—and give tighter bounds for some common classes of graphs. Published by the American Physical Society 2024

Devulapalli, Dhruv (ORCID:000000022612308X)↗