Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “quantum computing 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 397 records · Page 22

Optimization Algorithms as Quantum Performance Benchmarks

Combinatorial optimization is anticipated to be one of the primary use cases for quantum computation in the coming years. The Quantum Approximate Optimization Algorithm (QAOA) and Quantum Annealing (QA) have the potential to demonstrate significant run-time performance benefits over current state-of-the-art solutions. Using existing methods for characterizing classical optimization algorithms, we analyze solution quality obtained by solving Max-Cut problems using a quantum annealing device and gate-model quantum simulators and devices. This is used to guide the development of an advanced benchmarking framework for quantum computers designed to evaluate the trade-off between run-time execution performance and the solution quality for iterative hybrid quantum-classical applications. The framework generates performance profiles through effective visualizations that show performance progression as a function of time for various problem sizes and illustrates algorithm limitations uncovered by the benchmarking approach. The framework is an enhancement to the existing open-source QED-C Application-Oriented Benchmark suite and can connect to the open-source analysis libraries. The suite can be executed on various quantum simulators and quantum hardware systems.

benchmarking↗

Qubit-efficient entanglement spectroscopy using qubit resets

One strategy to fit larger problems on NISQ devices is to exploit a tradeoff between circuit width and circuit depth. Unfortunately, this tradeoff still limits the size of tractable problems since the increased depth is often not realizable before noise dominates. Here, we develop qubit-efficient quantum algorithms for entanglement spectroscopy which avoid this tradeoff. In particular, we develop algorithms for computing the trace of the n -th power of the density operator of a quantum system, T r ( ρ n ) , (related to the Rényi entropy of order n ) that use fewer qubits than any previous efficient algorithm while achieving similar performance in the presence of noise, thus enabling spectroscopy of larger quantum systems on NISQ devices. Our algorithms, which require a number of qubits independent of n , are variants of previous algorithms with width proportional to n , an asymptotic difference. The crucial ingredient in these new algorithms is the ability to measure and reinitialize subsets of qubits in the course of the computation, allowing us to reuse qubits and increase the circuit depth without suffering the usual noisy consequences. We also introduce the notion of effective circuit depth as a generalization of standard circuit depth suitable for circuits with qubit resets. This tool helps explain the noise-resilience of our qubit-efficient algorithms and should aid in designing future algorithms. We perform numerical simulations to compare our algorithms to the original variants and show they perform similarly when subjected to noise. Additionally, we experimentally implement one of our qubit-efficient algorithms on the Honeywell System Model H0, estimating T r ( ρ n ) for larger n than possible with previous algorithms.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Quantum Optimization and Approximation Algorithms

Shor's groundbreaking quantum algorithm for integer factoring provides an exponential speedup over the best-known classical algorithms. In the 20 years since Shor's algorithm was conceived, only a handful of fundamental quantum algorithmic kernels, generally providing modest polynomial speedups over classical algorithms, have been invented. To better understand the potential advantage quantum resources provide over their classical counterparts, one may consider other resources than execution time of algorithms. Quantum Approximation Algorithms direct the power of quantum computing towards optimization problems where quantum resources provide higher-quality solutions instead of faster execution times. We provide a new rigorous analysis of the recent Quantum Approximate Optimization Algorithm, demonstrating that it provably outperforms the best known classical approximation algorithm for special hard cases of the fundamental Maximum Cut graph-partitioning problem. We also develop new types of classical approximation algorithms for finding near-optimal low-energy states of physical systems arising in condensed matter by extending seminal discrete optimization techniques. Our interdisciplinary work seeks to unearth new connections between discrete optimization and quantum information science.

97 MATHEMATICS AND COMPUTING↗

Quantum-Accelerated Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

We present two algorithms in the Quantum CONGEST-CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact spanning arborescence of minimum weight, the analog of a Minimum Spanning Tree in a directed graph, each of which uses O~(n^(1/4)) rounds of communication and O~(n^(9/4)) messages, achieving a lower round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. The CONGEST distributed computational model allows limited-sized messages to be transmitted within a network described by a communication graph of size n in a series of rounds to address a computational problem. The size limitation for such messages isO(log(n)) bits at each edge of the communication graph per round. The communication graph in the CONGEST-CLIQUE model is fully connected. In the Quantum CONGEST-CLIQUE model, at most O(log(n)) classical and quantum bits (qubits) can be communicated across each edge of the communication graph per round. At a high level, we achieve these results by combining classical algorithms with fast quantum subroutines. These speedups further contribute to understanding what problems can be solved more efficiently when we allow quantum communication in this CONGEST-CLIQUE model of distributed computation.

quantum distributed algorithms↗

Exploring Network-Related Optimization Problems Using Quantum Heuristics

Network-related connectivity optimization problems are underlying a wide range of applications and are also of high computational complexity. We consider studying network optimization problems using two types of quantum heuristics.One is quantum annealing, and the other Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms for gate-model quantum computation, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present problem mappings for problems of finding the spanning-tree or spanning-graph of a graph that optimizes certain costs, and a variant that further requires the spanning-tree be degree-bounded. With quantum annealing, all constraints are cast into penalty terms in the cost Hamiltonian, and the solution is encoded as the ground state of the Hamiltonian. We provide three mappings to the quadratic unconstrained binary optimization (QUBO) form, compare the resource requirements, and analyze the tradeoffs. For QAOA, we give special focus on the design of mixers based on the constraints presented in the problem, such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such hard constraint is that a mixer applied to a spanning-tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.

Wang, Zhihui↗

Study network-related optimization problems using quantum alternating optimization ansatz

Network-related connectivity optimization problems are underlying a wide range of applications and are also of high computational complexity. We consider studying network optimization problems using two types of quantum heuristics. One is quantum annealing, and the other Quantum Alternating Operator Ansatz, an extension of the Quantum Approximate Optimization Algorithms for gate-model quantum computation, in which a cost-function based unitary and a non-commuting mixing unitary are applied alternately. We present problem mappings for problems of finding the spanning-tree or spanning-graph of a graph that optimizes certain costs, and a variant that further requires the spanning-tree be degree-bounded. With quantum annealing, all constraints are cast into penalty terms in the cost Hamiltonian, and the solution is encoded as the ground state of the Hamiltonian. We provide three mappings to the quadratic unconstrained binary optimization (QUBO) form, compare the resource requirements, and analyze the tradeoffs. For QAOA, we give special focus on the design of mixers based on the constraints presented in the problem, such that the system evolution remains in a subspace of the full Hilbert space where all constraints are satisfied. In the spanning-tree problem, one such hard constraint is that a mixer applied to a spanning-tree needs also be a spanning tree. This involves checking the connectivity of a subgraph, which is a global condition common for most network-related problems. We show how this feature can be efficiently represented in the mixer in a quantum coherent way, based on manipulation of a descendant-matrix and an adjacent matrix. We further develop a mixer for the spanning-graphs based on the spanning-tree mixer.

Zhihui Wang↗

Two-Stage Estimation and Variance Modeling for Latency-Constrained Variational Quantum Algorithms

The quantum approximate optimization algorithm (QAOA) has enjoyed increasing attention in noisy, intermediate-scale quantum computing with its application to combinatorial optimization problems. QAOA has the potential to demonstrate a quantum advantage for NP-hard combinatorial optimization problems. As a hybrid quantum-classical algorithm, the classical component of QAOA resembles a simulation optimization problem in which the simulation outcomes are attainable only through a quantum computer. The simulation that derives from QAOA exhibits two unique features that can have a substantial impact on the optimization process: (i) the variance of the stochastic objective values typically decreases in proportion to the optimality gap, and (ii) querying samples from a quantum computer introduces an additional latency overhead. In this paper, we introduce a novel stochastic trust-region method derived from a derivative-free, adaptive sampling trust-region optimization method intended to efficiently solve the classical optimization problem in QAOA by explicitly taking into account the two mentioned characteristics. The key idea behind the proposed algorithm involves constructing two separate local models in each iteration: a model of the objective function and a model of the variance of the objective function. Exploiting the variance model allows us to restrict the number of communications with the quantum computer and also helps navigate the nonconvex objective landscapes typical in QAOA optimization problems. In conclusion, we numerically demonstrate the superiority of our proposed algorithm using the SimOpt library and Qiskit when we consider a metric of computational burden that explicitly accounts for communication costs.

Derivative-free Optimization↗

Novel Relativistic Electronic Structure Theories for Actinide-Containing Compounds

Actinides of importance to basic energy sciences contain electrons moving at speed comparable to the speed of light. Reliable computational simulation of these electrons and hence actinide chemistry requires accurate description of relativistic effects. The present project advances computational actinide chemistry with development of new methodologies, algorithms, and computer programs in relativistic quantum chemistry, as well as applications to actinide chemistry and spectroscopy. A new “electrons-only” exact two-component approach has been developed to provide efficient treatments of relativistic effects, while maintaining chemical accuracy. New computational algorithms developed here extend the applicability of relativistic electron-correlation methods to larger molecules. The method-development work in this project also features the first implementation of analytic gradient technique for relativistic electron-correlation methods, which provides significantly enhanced ability to compute properties for molecules containing actinides. The applicability and usefulness of these new methods and computer programs have been demonstrated in calculations of actinide-containing molecules to facilitate understanding of actinide chemistry and spectroscopy.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Resolving Wave-Particle Duality Could Accelerate the Mass Production of Quantum Computers

Quantum computers, hypothesized in 1980s, use concepts of superposition and entanglement phenomena. Although theoretical propositions and associated search algorithms for accurate measurements are being generated, the development of practical quantum computers themselves are advancing very slowly requiring enormous time and investments. The underlying concepts of a quantum computer are not new to the optical domain. However, the crucial enabling concepts of Entanglement and Superposition Principle are remaining clouded under the unresolved postulates, Wave-Particle Duality (WPD), and Wave Packet Reduction (WPR), implicating incompleteness in the interpretations of the mathematical formalism behind Quantum Mechanics. The WPD debate started during late1600 between Newton and Huygens. Young’s resolution of WPD through his double-slit experiment in 1802 was effectively overturned by Einstein’s interpretation of photoelectric effect as due to “indivisible light quanta”. However, Einstein disowned his “light quanta” postulate shortly before his death in1955, even though it had earned him the Nobel Prize. We resolve WPD by synthesizing Newton’s and Maxwell’s concepts and assume atoms do emit quanta but propagate as time-finite exponential pulses. This assumption also resolves WPR for light-matter interaction with the assumption that Schrodinger’s ψ represents atom’s internal dipolar amplitude stimulations. This over-turns Born’s interpretation that ψ only represents the abstract mathematical probability amplitude, rather than the physical “internal amplitude stimulation” of the quantum entity. However, our concept of atomic pulse emission forces us to re-derive the expression for the N-slit grating-spectrometer response since the classical derivation uses CW light, which does not exist. This pulsespectrometric response function strengthens our postulate since the grating response to the exponential pulse appears to be the convolution of a Lorentzian spectrum with the classical CW response function of the grating. The Fourier Transform of an exponential function is Lorentzian and QM predicts spontaneous emission line width to be Lorentzian. Then, conceptually one can extend the grating-expression (with N=2) to get the double-slit pattern. This approach preserves the classical causality that each of the two slits, like the N-signals out of a grating, are physically real and jointly stimulate the quantum detector array at the far field to generate the “Local” cosine fringes. The detector array executes the square modulus operation on its imposed dipolar amplitude stimulation and absorbs the necessary energy to fill up their quantum cups. Hence the double-slit pattern must also be “Local”, just as the N-slit grating spectrum is generated locally at the exit spectral-plane of the spectrometer. This removes the need to believe that “single photons” mysteriously generate the double slit pattern. Quantum computers, hypothesized in 1980s, use concepts of superposition and entanglement phenomena. Although theoretical propositions and associated search algorithms for accurate measurements are being generated, the development of practical quantum computers themselves are advancing very slowly requiring enormous time and investments. The underlying concepts of a quantum computer are not new to the optical domain. However, the crucial enabling concepts of Entanglement and Superposition Principle are remaining clouded under the unresolved postulates, Wave-Particle Duality (WPD), and Wave Packet Reduction (WPR), implicating incompleteness in the interpretations of the mathematical formalism behind Quantum Mechanics. The WPD debate started during late1600 between Newton and Huygens. Young’s resolution of WPD through his double-slit experiment in 1802 was effectively overturned by Einstein’s interpretation of photoelectric effect as due to “indivisible light quanta”. However, Einstein disowned his “light quanta” postulate shortly before his death in1955, even though it had earned him the Nobel Prize. We resolve WPD by synthesizing Newton’s and Maxwell’s concepts and assume atoms do emit quanta but propagate as time-finite exponential pulses. This assumption also resolves WPR for light-matter interaction with the assumption that Schrodinger’s ψ represents atom’s internal dipolar amplitude stimulations. This over-turns Born’s interpretation that ψ only represents the abstract mathematical probability amplitude, rather than the physical “internal amplitude stimulation” of the quantum entity. However, our concept of atomic pulse emission forces us to re-derive the expression for the N-slit grating-spectrometer response since the classical derivation uses CW light, which does not exist. This pulsespectrometric response function strengthens our postulate since the grating response to the exponential pulse appears to be the convolution of a Lorentzian spectrum with the classical CW response function of the grating. The Fourier Transform of an exponential function is Lorentzian and QM predicts spontaneous emission line width to be Lorentzian. Then, conceptually one can extend the grating-expression (with N=2) to get the double-slit pattern. This approach preserves the classical causality that each of the two slits, like the N-signals out of a grating, are physically real and jointly stimulate the quantum detector array at the far field to generate the “Local” cosine fringes. The detector array executes the square modulus operation on its imposed dipolar amplitude stimulation and absorbs the necessary energy to fill up their quantum cups. Hence the double-slit pattern must also be “Local”, just as the N-slit grating spectrum is generated locally at the exit spectral-plane of the spectrometer. This removes the need to believe that “single photons” mysteriously generate the double slit pattern.

Quantum Computer↗

Quantum-Inspired Maximizer

A report discusses an algorithm for a new kind of dynamics based on a quantum- classical hybrid-quantum-inspired maximizer. The model is represented by a modified Madelung equation in which the quantum potential is replaced by different, specially chosen 'computational' potential. As a result, the dynamics attains both quantum and classical properties: it preserves superposition and entanglement of random solutions, while allowing one to measure its state variables, using classical methods. Such optimal combination of characteristics is a perfect match for quantum-inspired computing. As an application, an algorithm for global maximum of an arbitrary integrable function is proposed. The idea of the proposed algorithm is very simple: based upon the Quantum-inspired Maximizer (QIM), introduce a positive function to be maximized as the probability density to which the solution is attracted. Then the larger value of this function will have the higher probability to appear. Special attention is paid to simulation of integer programming and NP-complete problems. It is demonstrated that the problem of global maximum of an integrable function can be found in polynomial time by using the proposed quantum- classical hybrid. The result is extended to a constrained maximum with applications to integer programming and TSP (Traveling Salesman Problem).

Zak, Michail↗

NISQ Benchmarking

Test suite of quantum algorithms for Noisy Intermediate Scale Quantum (NISQ) computers. The test suite includes benchmark-style code for quantum volume circuits (QV), fairness sampling circuits, quantum telecloning circuits, and other NISQ benchmark style algorithms on small problems (i.e., up to 100 qubits), such as Variational Quantum Eigensolver (VQE), Hamiltonian Simulation, and Grover unstructured search example circuits. These benchmark-style applications are implemented in quantum software packages, mostly IBM's QISKIT, but may include vendor-specific frameworks, such as PyQuil (for Rigetti) or Q\# for Microsoft, or CirQ (for Google) as the test suite grows with the vendor sample. The test suite also includes numerical simulation code for Quantum Alternating Operator Ansatz (QAOA) algorithms, VQE, Hamiltonian Simulation and search examples. Numerical simulation code simulates quantum computers on classical computers, which is only possible for small problem instances; the implementation framework of choice is typically within Python, using the numpy/scipy libraries as well as extensions to the Julia language.

Pelofske, Elijah↗

Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees

We present two algorithms in the Quantum CONGEST- CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which uses O ̃(n1/4) rounds of communication and O ̃(n9/4) messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithms with fast quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms, as well as related classical algorithms, revealing that advances are needed to render both practical.

quantum computing↗

Quantum Simulation of Field Theories Without State Preparation

We propose an algorithm for computing real-time observables using a quantum processor while avoiding the need to prepare the full quantum state. This reduction in quantum resources is achieved by classically sampling configurations in imaginary-time using standard lattice field theory. These configurations can then be passed to quantum processor for time-evolution. This method encounters a signal-to-noise problem which we characterize, and we demonstrate the application of standard lattice QCD methods to mitigate it.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗

Quantum Distributed Algorithms for Approximate Steiner Trees and Directed Minimum Spanning Trees​

We present two algorithms in the Quantum CONGEST- CLIQUE model of distributed computation that succeed with high probability; one for producing an approximately optimal Steiner Tree, and one for producing an exact directed minimum spanning tree, each of which uses O ̃(n 1/4 ) rounds of communication and O ̃(n 9/4 ) messages, achieving a lower asymptotic round and message complexity than any known algorithms in the classical CONGEST-CLIQUE model. At a high level, we achieve these results by combining classical algorithms with fast quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms, as well as related classical algorithms, revealing that advances are needed to render both practical.

quantum computing↗

Measurement-induced entanglement phase transitions in variational quantum circuits

Variational quantum algorithms (VQAs), which classically optimize a parametrized quantum circuit to solve a computational task, promise to advance our understanding of quantum many-body systems and improve machine learning algorithms using near-term quantum computers. Prominent challenges associated with this family of quantum-classical hybrid algorithms are the control of quantum entanglement and quantum gradients linked to their classical optimization. Known as the barren plateau phenomenon, these quantum gradients may rapidly vanish in the presence of volume-law entanglement growth, which poses a serious obstacle to the practical utility of VQAs. Inspired by recent studies of measurement-induced entanglement transition in random circuits, we investigate the entanglement transition in variational quantum circuits endowed with intermediate projective measurements. Considering the Hamiltonian Variational Ansatz (HVA) for the XXZ model and the Hardware Efficient Ansatz (HEA), we observe a measurement-induced entanglement transition from volume-law to area-law with increasing measurement rate. Moreover, we provide evidence that the transition belongs to the same universality class of random unitary circuits. Importantly, the transition coincides with a “landscape transition” from severe to mild/no barren plateaus in the classical optimization. Our work may provide an avenue for improving the trainability of quantum circuits by incorporating intermediate measurement protocols in currently available quantum hardware.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Quantum Davidson algorithm for excited states

Abstract Excited state properties play a pivotal role in various chemical and physical phenomena, such as charge separation and light emission. However, the primary focus of most existing quantum algorithms has been the ground state, as seen in quantum phase estimation and the variational quantum eigensolver (VQE). Although VQE-type methods have been extended to explore excited states, these methods grapple with optimization challenges. In contrast, the quantum Krylov subspace (QKS) method has been introduced to address both ground and excited states, positioning itself as a cost-effective alternative to quantum phase estimation. However, conventional QKS methodologies depend on a pre-generated subspace through real or imaginary-time evolutions. This subspace is inherently expansive and can be plagued with issues like slow convergence or numerical instabilities, often leading to relatively deep circuits. Our research presents an economic QKS algorithm, which we term the quantum Davidson (QDavidson) algorithm. This innovation hinges on the iterative expansion of the Krylov subspace and the incorporation of a pre-conditioner within the Davidson framework. By using the residues of eigenstates to expand the Krylov subspace, we manage to formulate a compact subspace that aligns closely with the exact solutions. This iterative subspace expansion paves the way for a more rapid convergence in comparison to other QKS techniques, such as the quantum Lanczos. Using quantum simulators, we employ the novel QDavidson algorithm to delve into the excited state properties of various systems, spanning from the Heisenberg spin model to real molecules. Compared to the existing QKS methods, the QDavidson algorithm not only converges swiftly but also demands a significantly shallower circuit. This efficiency establishes the QDavidson method as a pragmatic tool for elucidating both ground and excited state properties on quantum computing platforms.

97 MATHEMATICS AND COMPUTING↗

Noise analysis for the Sorkin and Peres tests performed on a quantum computer

We use quantum computers to test the foundations of quantum mechanics through quantum algorithms that implement some of the experimental tests as the basis of the theory's postulates. These algorithms can be used as a test of the physical theory under the premise of a perfect hardware or as a test of the hardware under the premise that quantum theory is correct. In this paper, we show how the algorithms can be used to test the efficacy of a quantum computer in obeying the postulates of quantum mechanics. We study the effect of different types of errors on the results of experimental tests of the postulates. A salient feature of this error analysis is that it is deeply rooted in the fundamentals of quantum mechanics as it highlights how systematic errors affect the quantumness of the quantum computer.

Sadana, Simanraj↗

Exact-Factorization-Based Surface Hopping without Velocity Adjustment

While surface hopping has emerged as a powerful method for simulating non-adiabatic dynamics in large molecules, the ad hoc nature of the necessary velocity adjustments and decoherence corrections in the algorithm somewhat reduces its reliability. Here we propose a new scheme that eliminates these aspects by combining the nuclear equation from the quantum-trajectory surface-hopping approach with the electronic equation derived from the exact-factorization approach. Furthermore, the resulting method, denoted QTSH-XF, yields a surface-hopping method on firmer ground than previous and is shown to successfully capture dynamics in Tully models and in a linear vibronic coupling model of the photoexcited uracil cation.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗