Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “quantum 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 73 records · Page 4
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

Variational Quantum Algorithms for Semidefinite Programming

A semidefinite program (SDP) is a particular kind of convex optimization problem with applications in operations research, combinatorial optimization, quantum information science, and beyond. In this work, we propose variational quantum algorithms for approximately solving SDPs. For one class of SDPs, we provide a rigorous analysis of their convergence to approximate locally optimal solutions, under the assumption that they are weakly constrained (i.e., N " M, where N is the dimension of the input matrices and M is the number of constraints). We also provide algorithms for a more general class of SDPs that requires fewer assumptions. Finally, we numerically simulate our quantum algorithms for applications such as MaxCut, and the results of these simulations provide evidence that convergence still occurs in noisy settings.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Quantum Algorithm for Approximating Maximum Independent Sets

We present a quantum algorithm for approximating maximum independent sets of a graph based on quantum non-Abelian adiabatic mixing in the sub-Hilbert space of degenerate ground states, which generates quantum annealing in a secondary Hamiltonian. For both sparse and dense random graphs G , numerical simulation suggests that our algorithm on average finds an independent set of size close to the maximum size α ( G ) in low polynomial time. The best classical algorithms, by contrast, produce independent sets of size about half of α ( G ) in polynomial time.

Physics↗
DOE OSTI2023

Navigating the Dynamic Noise Landscape of Variational Quantum Algorithms with QISMET

In the Noisy Intermediate Scale Quantum (NISQ) era, the dynamic nature of quantum systems causes noise sources to constantly vary over time. Transient errors from the dynamic NISQ noise landscape are challenging to comprehend and are especially detrimental to classes of applications that are iterative and/or long-running, and therefore their timely mitigation is important for quantum advantage in real-world applications. The most popular examples of iterative long-running quantum applications are variational quantum algorithms (VQAs). Iteratively, VQA’s classical optimizer evaluates circuit candidates on an objective function and picks the best circuits towards achieving the application’s target. Noise fluctuation can cause a significant transient impact on the objective function estimation of the VQA iterations’ tuning candidates. This can severely affect VQA tuning and, by extension, its accuracy and convergence. Furthermore, this paper proposes QISMET: Quantum Iteration Skipping to Mitigate Error Transients, to navigate the dynamic noise landscape of VQAs. QISMET actively avoids instances of high fluctuating noise which are predicted to have a significant transient error impact on specific VQA iterations. To achieve this, QISMET estimates transient error in VQA iterations and designs a controller to keep the VQA tuning faithful to the transient-free scenario. By doing so, QISMET efficiently mitigates a large portion of the transient noise impact on VQAs and is able to improve the fidelity by 1.3x-3x over a traditional VQA baseline, with 1.6-2.4x improvement over alternative approaches, across different applications and machines.

Ravi, Gokul Subramanian↗
DOE OSTI2023

Quantum algorithms for geologic fracture networks

Abstract Solving large systems of equations is a challenge for modeling natural phenomena, such as simulating subsurface flow. To avoid systems that are intractable on current computers, it is often necessary to neglect information at small scales, an approach known as coarse-graining. For many practical applications, such as flow in porous, homogenous materials, coarse-graining offers a sufficiently-accurate approximation of the solution. Unfortunately, fractured systems cannot be accurately coarse-grained, as critical network topology exists at the smallest scales, including topology that can push the network across a percolation threshold. Therefore, new techniques are necessary to accurately model important fracture systems. Quantum algorithms for solving linear systems offer a theoretically-exponential improvement over their classical counterparts, and in this work we introduce two quantum algorithms for fractured flow. The first algorithm, designed for future quantum computers which operate without error, has enormous potential, but we demonstrate that current hardware is too noisy for adequate performance. The second algorithm, designed to be noise resilient, already performs well for problems of small to medium size (order 10–1000 nodes), which we demonstrate experimentally and explain theoretically. We expect further improvements by leveraging quantum error mitigation and preconditioning.

58 GEOSCIENCES↗
DOE OSTI2022

Quantum algorithm for electronic band structures with local tight-binding orbitals

While the main thrust of quantum computing research in materials science is to accurately measure the classically intractable electron correlation effects due to Coulomb repulsion, designing optimal quantum algorithms for simpler problems with well-understood solutions is a useful tactic to advance our quantum “toolbox”. With this in mind, we consider the quantum calculation of a periodic system’s single-electron band structure over a path through reciprocal space. Previous efforts have used the Variational Quantum Eigensolver algorithm to solve the energy of each band, which involves numerically optimizing the parameters of a variational quantum circuit to minimize a cost function, constructed as the expectation value of a Hamiltonian operator. Traditionally, a unique Hamiltonian operator is constructed for each k-point, so that many cost functions, each with their own parameter space, must be optimized to generate a single band. Similarly, calculating higher bands than the first has traditionally involved modifying the cost function with additional overlap terms to ensure higher-energy eigenstates are orthogonal to those of lower bands. In this paper, we adopt a direct space approach, using a novel hybrid first/second-quantized qubit mapping which allows us to construct a single Hamiltonian, and a single cost-function, suitable for solving the entire electronic band structure. In contrast to previous approaches, the k-point and the band index are selected by additional parameters in our quantum circuit, rather than through modifications to the cost function. The result is a technically and conceptually simpler approach to band structure calculations on a quantum computer. Moreover, we expect that the tools developed herein will motivate new strategies for tackling highly-correlated materials beyond the grasp of classical computing.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Reducing measurement costs by recycling the Hessian in adaptive variational quantum algorithms

Abstract Adaptive protocols enable the construction of more efficient state preparation circuits in variational quantum algorithms (VQAs) by utilizing data obtained from the quantum processor during the execution of the algorithm. This idea originated with Adaptive Derivative-Assembled Problem-Tailored variational quantum eigensolver (ADAPT-VQE), an algorithm that iteratively grows the state preparation circuit operator by operator, with each new operator accompanied by a new variational parameter, and where all parameters acquired thus far are optimized in each iteration. In ADAPT-VQE and other adaptive VQAs that followed it, it has been shown that initializing parameters to their optimal values from the previous iteration speeds up convergence and avoids shallow local traps in the parameter landscape. However, no other data from the optimization performed at one iteration is carried over to the next. In this work, we propose an improved quasi-Newton optimization protocol specifically tailored to adaptive VQAs. The distinctive feature in our proposal is that approximate second derivatives of the cost function are recycled across iterations in addition to optimal parameter values. We implement a quasi-Newton optimizer where an approximation to the inverse Hessian matrix is continuously built and grown across the iterations of an adaptive VQA. The resulting algorithm has the flavor of a continuous optimization where the dimension of the search space is augmented when the gradient norm falls below a given threshold. We show that this inter-optimization exchange of second-order information leads the approximate Hessian in the state of the optimizer to be consistently closer to the exact Hessian. As a result, our method achieves a superlinear convergence rate even in situations where the typical implementation of a quasi-Newton optimizer converges only linearly. Our protocol decreases the measurement costs in implementing adaptive VQAs on quantum hardware as well as the runtime of their classical simulation.

Ramôa, Mafalda (ORCID:0000000302187801)↗
DOE OSTI2025

Quantum algorithm to simulate Lindblad master equations

We present a quantum algorithm for simulating a family of Markovian master equations that can be realized through a probabilistic application of unitary channels and state preparation. Our approach employs a second-order product formula for the Lindblad master equation, achieved by decomposing the dynamics into dissipative and Hamiltonian components and replacing the dissipative segments with randomly compiled, easily implementable elements. The sampling approach eliminates the need for ancillary qubits to simulate the dissipation process and reduces the gate complexity in terms of the number of jump operators. We provide a rigorous performance analysis of the algorithm. We also extend the algorithm to time-dependent Lindblad equations, generalize the family of Markovian master equations it can be applied to, and explore applications beyond the Markovian noise model. A new error bound, in terms of the diamond norm, for second-order product formulas for time-dependent Liouvillians is provided that might be of independent interest. Published by the American Physical Society 2025

Borras, Evan (ORCID:000900017709037X)↗
DOE OSTI2025

Resilience–runtime tradeoff relations for quantum algorithms

Abstract A leading approach to algorithm design aims to minimize the number of operations in an algorithm’s compilation. One intuitively expects that reducing the number of operations may decrease the chance of errors. This paradigm is particularly prevalent in quantum computing, where gates are hard to implement and noise rapidly decreases a quantum computer’s potential to outperform classical computers. Here, we find that minimizing the number of operations in a quantum algorithm can be counterproductive, leading to a noise sensitivity that induces errors when running the algorithm in non-ideal conditions. To show this, we develop a framework to characterize the resilience of an algorithm to perturbative noises (including coherent errors, dephasing, and depolarizing noise). Some compilations of an algorithm can be resilient against certain noise sources while being unstable against other noises. We condense these results into a tradeoff relation between an algorithm’s number of operations and its noise resilience. We also show how this framework can be leveraged to identify compilations of an algorithm that are better suited to withstand certain noises.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1999

Fast Quantum Algorithm for Predicting Descriptive Statistics of Stochastic Processes

Stochastic processes are used as a modeling tool in several sub-fields of physics, biology, and finance. Analytic understanding of the long term behavior of such processes is only tractable for very simple types of stochastic processes such as Markovian processes. However, in real world applications more complex stochastic processes often arise. In physics, the complicating factor might be nonlinearities; in biology it might be memory effects; and in finance is might be the non-random intentional behavior of participants in a market. In the absence of analytic insight, one is forced to understand these more complex stochastic processes via numerical simulation techniques. In this paper we present a quantum algorithm for performing such simulations. In particular, we show how a quantum algorithm can predict arbitrary descriptive statistics (moments) of N-step stochastic processes in just O(square root of N) time. That is, the quantum complexity is the square root of the classical complexity for performing such simulations. This is a significant speedup in comparison to the current state of the art.

Williams Colin P.↗
DOE OSTI2023

Demonstration of Algorithmic Quantum Speedup

Despite the development of increasingly capable quantum computers, an experimental demonstration of a provable algorithmic quantum speedup employing today’s non-fault-tolerant devices has remained elusive. Here, in this study, we unequivocally demonstrate such a speedup within the oracular model, quantified in terms of the scaling with the problem size of the time-to-solution metric. We implement the single-shot Bernstein-Vazirani algorithm, which solves the problem of identifying a hidden bitstring that changes after every oracle query, using two different 27-qubit IBM Quantum superconducting processors. The speedup is observed on only one of the two processors when the quantum computation is protected by dynamical decoupling but not without it. The quantum speedup reported here does not rely on any additional assumptions or complexity-theoretic conjectures and solves a bona fide computational problem in the setting of a game with an oracle and a verifier.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Noisy intermediate-scale quantum algorithms

A universal fault-tolerant quantum computer that can efficiently solve problems such as integer factorization and unstructured database search requires millions of qubits with low error rates and long coherence times. While the experimental advancement toward realizing such devices will potentially take decades of research, noisy intermediate-scale quantum (NISQ) computers already exist. These computers are composed of hundreds of noisy qubits, i.e., qubits that are not error corrected, and therefore perform imperfect operations within a limited coherence time. In the search for achieving quantum advantage with these devices, algorithms have been proposed for applications in various disciplines spanning physics, machine learning, quantum chemistry, and combinatorial optimization. The overarching goal of such algorithms is to leverage the limited available resources to perform classically challenging tasks. In this review, a thorough summary of NISQ computational paradigms and algorithms is provided. The key structure of these algorithms and their limitations and advantages are discussed. Finally, a comprehensive overview of various benchmarking and software tools useful for programming and testing NISQ devices is additionally provided.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems

We investigate the limitations of quantum computers for solving nonlinear dynamical systems. In particular, we tighten the worst-case bounds of the quantum Carleman linearisation (QCL) algorithm answering one of their open questions. We provide a further significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector. Given a natural choice of coordinates for a dynamical system with one or more positive Lyapunov exponents and solutions that grow sub-exponentially, we prove that any such algorithm has complexity scaling at least exponentially in the integration time. As such, an efficient quantum algorithm for simulating chaotic systems or regimes is likely not possible.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Stochastic noise can be helpful for variational quantum algorithms

Saddle points constitute a crucial challenge for first-order gradient descent algorithms. In notions of classical machine learning, they are avoided, for example, by means of stochastic gradient descent methods. In this work, we provide evidence that the saddle-points problem can be naturally avoided in variational quantum algorithms by exploiting the presence of stochasticity. We prove convergence guarantees and present practical examples in numerical simulations and on quantum hardware. We argue that the natural stochasticity of variational algorithms can be beneficial for avoiding strict saddle points, i.e., those saddle points with at least one negative Hessian eigenvalue. This insight that some levels of shot noise could help is expected to add a new perspective to notions of near-term variational quantum algorithms. Published by the American Physical Society 2025

Liu, Junyu↗
DOE OSTI2023

General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory

With a focus on universal quantum computing for quantum simulation, and through the example of lattice gauge theories, we introduce rather general quantum algorithms that can efficiently simulate certain classes of interactions consisting of correlated changes in multiple (bosonic and fermionic) quantum numbers with non-trivial functional coefficients. In particular, we analyze diagonalization of Hamiltonian terms using a singular-value decomposition technique, and discuss how the achieved diagonal unitaries in the digitized time-evolution operator can be implemented. The lattice gauge theory studied is the SU(2) gauge theory in 1+1 dimensions coupled to one flavor of staggered fermions, for which a complete quantum-resource analysis within different computational models is presented. The algorithms are shown to be applicable to higher-dimensional theories as well as to other Abelian and non-Abelian gauge theories. The example chosen further demonstrates the importance of adopting efficient theoretical formulations: it is shown that an explicitly gauge-invariant formulation using loop, string, and hadron degrees of freedom simplifies the algorithms and lowers the cost compared with the standard formulations based on angular-momentum as well as the Schwinger-boson degrees of freedom. The loop-string-hadron formulation further retains the non-Abelian gauge symmetry despite the inexactness of the digitized simulation, without the need for costly controlled operations. Such theoretical and algorithmic considerations are likely to be essential in quantumly simulating other complex theories of relevance to nature.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Quantum Algorithm for High Energy Physics Simulations

Simulating quantum field theories is a flagship application of quantum computing. However, calculating experimentally relevant high energy scattering amplitudes entirely on a quantum computer is prohibitively difficult. It is well known that such high energy scattering processes can be factored into pieces that can be computed using well established perturbative techniques, and pieces which currently have to be simulated using classical Markov chain algorithms. These classical Markov chain simulation approaches work well to capture many of the salient features, but cannot capture all quantum effects. To exploit quantum resources in the most efficient way, we introduce a new paradigm for quantum algorithms in field theories. This approach uses quantum computers only for those parts of the problem which are not computable using existing techniques. In particular, we develop a polynomial time quantum final state shower that accurately models the effects of intermediate spin states similar to those present in high energy electroweak showers with a global evolution variable. The algorithm is explicitly demonstrated for a simplified quantum field theory on a quantum computer.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2025

Quantum algorithm for polaritonic chemistry based on an exact ansatz

Abstract Cavity-modified chemistry uses strong light-matter interactions to modify the electronic properties of molecules in order to enable new physical phenomena such as novel reaction pathways. As cavity chemistry often involves critical regions where configurations become nearly degenerate, the ability to treat multireference problems is crucial to understanding polaritonic systems. In this Letter, we show through the use of a unitary ansatz derived from the anti-Hermitian contracted Schrödinger equation that cavity-modified systems with strong correlation, such as the deformation of rectangular H 4 coupled to a cavity mode, can be solved efficiently and accurately on a quantum device. In contrast, while our quantum algorithm can be made formally exact, classical-computing methods as well as other quantum-computing algorithms often yield answers that are both quantitatively and qualitatively incorrect. Additionally, we demonstrate the current feasibility of the algorithm on near intermediate-scale quantum hardware by computing the dissociation curve of H 2 strongly coupled to a bosonic bath.

Warren, Samuel (ORCID:0000000157134454)↗
DOE OSTI2026

Reducing Randomized Quantum Algorithm Cost [Slides]

We derive the optimal sampling strategy for minimizing total resource cost in randomized quantum algorithms. Our framework is completely general, allowing for resources as diverse as gate counts circuit depth, runtime, or even dissipated energy.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Quantum Algorithm for Simulating Hamiltonian Dynamics with an Off-diagonal Series Expansion

We propose an efficient quantum algorithm for simulating the dynamics of general Hamiltonian systems. Our technique is based on a power series expansion of the time-evolution operator in its off-diagonal terms. The expansion decouples the dynamics due to the diagonal component of the Hamiltonian from the dynamics generated by its off-diagonal part, which we encode using the linear combination of unitaries technique. Our method has an optimal dependence on the desired precision and, as we illustrate, generally requires considerably fewer resources than the current state-of-the-art. We provide an analysis of resource costs for several sample models.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗