Search NASA⌕ Search

SEARCH · Search NASA

Results for “exponential advantage”

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 19 records
All sourcesNASA NTRSDOE OSTI
DOE OSTI2022

Quantum algorithmic measurement

There has been recent promising experimental and theoretical evidence that quantum computational tools might enhance the precision and efficiency of physical experiments. However, a systematic treatment and comprehensive framework are missing. Here we initiate the systematic study of experimental quantum physics from the perspective of computational complexity. To this end, we define the framework of quantum algorithmic measurements (QUALMs), a hybrid of black box quantum algorithms and interactive protocols. We use the QUALM framework to study two important experimental problems in quantum many-body physics: determining whether a system’s Hamiltonian is time-independent or time-dependent, and determining the symmetry class of the dynamics of the system. We study abstractions of these problems and show for both cases that if the experimentalist can use her experimental samples coherently (in both space and time), a provable exponential speedup is achieved compared to the standard situation in which each experimental sample is accessed separately. Our work suggests that quantum computers can provide a new type of exponential advantage: exponential savings in resources in quantum experiments.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2023

Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry

Due to intense interest in the potential applications of quantum computing, it is critical to understand the basis for potential exponential quantum advantage in quantum chemistry. Here we gather the evidence for this case in the most common task in quantum chemistry, namely, ground-state energy estimation, for generic chemical problems where heuristic quantum state preparation might be assumed to be efficient. The availability of exponential quantum advantage then centers on whether features of the physical problem that enable efficient heuristic quantum state preparation also enable efficient solution by classical heuristics. Through numerical studies of quantum state preparation and empirical complexity analysis (including the error scaling) of classical heuristics, in both ab initio and model Hamiltonian settings, we conclude that evidence for such an exponential advantage across chemical space has yet to be found. While quantum computers may still prove useful for ground-state quantum chemistry through polynomial speedups, it may be prudent to assume exponential speedups are not generically available for this problem.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2022

Quantum advantage in learning from experiments

Quantum technology promises to revolutionize how we learn about the physical world. An experiment that processes quantum data with a quantum computer could have substantial advantages over conventional experiments in which quantum states are measured and outcomes are processed with a classical computer. We proved that quantum machines could learn from exponentially fewer experiments than the number required by conventional experiments. This exponential advantage is shown for predicting properties of physical systems, performing quantum principal component analysis, and learning about physical dynamics. Furthermore, the quantum resources needed for achieving an exponential advantage are quite modest in some cases. Conducting experiments with 40 superconducting qubits and 1300 quantum gates, we demonstrated that a substantial quantum advantage is possible with today’s quantum processors.

Science & Technology - Other Topics↗
DOE OSTI2023

Basic Research Needs in Quantum Computing and Networking

Employing quantum mechanical resources in computing, information processing, and networking opens the door to potential exponential advantages over classical counterparts. However, quantifying and realizing such advantages poses extensive scientific and engineering challenges. Department of Energy (DOE) investments have driven steady progress in addressing such challenges. Recently developed quantum algorithms offer asymptotic exponential advantages in speed or accuracy for fundamental scientific problems. These problems include simulating physical systems, solving systems of linear equations, differential equations, and optimization problems. Empirical demonstrations on nascent quantum hardware suggest better performance on contrived computational tasks than classical analogs. However, the requirements for a quantum computer or network to demonstrate an end-to-end rigorously quantifiable performance improvement over classical analogs remains a grand challenge, especially for problems of practical value. In particular, what will be required for quantum technology to ultimately exhibit scalable, rigorous, and transformative performance advantages for practical applications? In July 2023, DOE’s Advanced Scientific Computing Research program in the Office of Science convened the Workshop on Basic Research Needs in Quantum Computing and Networking, where major opportunities and grand challenges were identified. The following five priority research directions (PRDs) were identified as a result of the workshop.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Unconventional Quantum Advantages for Computation (U-QuAC)

While quantum computing offers the promise of exponential advantages, limited quantum speedups are known, especially for practical applications. To open new avenues for quantum advantages, we propose Unconventional Quantum Advantages for Computation (U-QuACs), with respect to unconventional resources such as space (number of bits or quantum bits of memory required to solve a problem), accuracy of solution, communication, or energy consumption. We focus on space-efficient quantum algorithms, where we seek to design algorithms that solve a problem using much less space than the total size of the input. A natural setting in which space is critical is the streaming model of computation, where the input data arrives sequentially in pieces that must each be processed individually. Streaming is motivated by a variety of problems including analysis of internet traffic or social networks. We design the first exponential quantum space advantage for a natural streaming problem, which also constitutes the first quantum advantage for approximating a discrete optimization problem, albeit with respect to space.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Quantum advantages for Pauli channel estimation

We show that entangled measurements provide an exponential advantage in sample complexity for Pauli channel estimation, which is both a fundamental problem and a practically important subroutine for benchmarking near-term quantum devices. The specific task we consider is to simultaneously learn all the eigenvalues of an n-qubit Pauli channel to ±ε precision. We give an estimation protocol with an n-qubit ancilla that succeeds with high probability using only O(n/ε 2 ) copies of the Pauli channel, while proving that any ancilla-free protocol (possibly with adaptive control and channel concatenation) would need at least Ω(2 n/3 ) rounds of measurement. We further study the advantages provided by a small number of ancillas. For the case that a k-qubit ancilla (k≤n) is available, we obtain a sample complexity lower bound of Ω(2 (n-k)/3 ) for any nonconcatenating protocol, and a stronger lower bound of Ω(n 2n-k ) for any nonadaptive, nonconcatenating protocol, which is shown to be tight. We also show how to apply the ancilla-assisted estimation protocol to a practical quantum benchmarking task in a noise-resilient and sample-efficient manner, given reasonable noise assumptions. Our results provide a practically interesting example for quantum advantages in learning and also bring insights for quantum benchmarking.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

Quantum advantage for differential equation analysis

Quantum algorithms for differential equation solving, data processing, and machine learning potentially offer an exponential speedup over all known classical algorithms. However, there also exist obstacles to obtaining this potential speedup in useful problem instances. The essential obstacle for quantum differential equation solving is that outputting useful information may require difficult postprocessing, and the essential obstacle for quantum data processing and machine learning is that inputting the data is a difficult task just by itself. In this study, we demonstrate that, when combined, these difficulties solve one another. We show how the output of quantum differential equation solving can serve as the input for quantum data processing and machine learning, allowing dynamical analysis in terms of principal components, power spectra, and wavelet decompositions. To illustrate this, we consider continuous-time Markov processes on epidemiological and social networks. These quantum algorithms provide an exponential advantage over existing classical Monte Carlo methods.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2023

Report for the ASCR Workshop on Basic Research Needs in Quantum Computing and Networking - 2023

Employing quantum mechanical resources in computing and networking opens the door to new computation and communication models and potential disruptive advantages over classical counterparts. However, quantifying and realizing such advantages face extensive scientific and engineering challenges. Investments by the Department of Energy (DOE) have driven progress toward addressing such challenges. Quantum algorithms have been recently developed, in some cases offering asymptotic exponential advantages in speed or accuracy, for fundamental scientific problems such as simulating physical systems, solving systems of linear equations, or solving differential equations. Empirical demonstrations on nascent quantum hardware suggest better performance than classical analogs on specialized computational tasks favorable to the quantum computing systems. However, demonstration of an end-to-end, substantial and rigorously quantifiable quantum performance advantage over classical analogs remains a grand challenge, especially for problems of practical value. The definition of requirements for quantum technologies to exhibit scalable, rigorous, and transformative performance advantages for practical applications also remains an outstanding open question, namely, what will be required to ultimately demonstrate practical quantum advantage?

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2024

Report for the ASCR Workshop on Basic Research Needs in Quantum Computing and Networking - 2023

Employing quantum mechanical resources in computing and networking opens the door to new computation and communication models and potential disruptive advantages over classical counterparts. However, quantifying and realizing such advantages face extensive scientific and engineering challenges. Investments by the Department of Energy (DOE) have driven progress toward addressing such challenges. Quantum algorithms have been recently developed, in some cases offering asymptotic exponential advantages in speed or accuracy, for fundamental scientific problems such as simulating physical systems, solving systems of linear equations, or solving differential equations. Empirical demonstrations on nascent quantum hardware suggest better performance than classical analogs on specialized computational tasks favorable to the quantum computing systems. However, demonstration of an end-to-end, substantial and rigorously quantifiable quantum performance advantage over classical analogs remains a grand challenge, especially for problems of practical value. The definition of requirements for quantum technologies to exhibit scalable, rigorous, and transformative performance advantages for practical applications also remains an outstanding open question, namely, what will be required to ultimately demonstrate practical quantum advantage?

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Many-fermion simulation from the contracted quantum eigensolver without fermionic encoding of the wave function

Quantum computers potentially have an exponential advantage over classical computers for the quantum simulation of many-fermion quantum systems. Nonetheless, fermions are more expensive to simulate than bosons due to the fermionic encoding—a mapping by which the qubits are encoded with fermion statistics. Here we generalize the contracted quantum eigensolver (CQE) to avoid fermionic encoding of the wave function. In contrast to the variational quantum eigensolver, the CQE solves for a many-fermion stationary state by minimizing the contraction (projection) of the Schrödinger equation onto two fermions. We avoid fermionic encoding of the wave function by contracting the Schrödinger equation onto an unencoded pair of particles. Solution of the resulting contracted equation by a series of unencoded two-body exponential transformations generates an unencoded wave function from which the energy and two-fermion reduced density matrix (2-RDM) can be computed. We apply the unencoded and the encoded CQE algorithms to the hydrogen fluoride molecule, the dissociation of oxygen O 2 , and a series of hydrogen chains. Both algorithms show comparable convergence towards the exact ground-state energies and 2-RDMs, but the unencoded algorithm has computational advantages in terms of state preparation and tomography.

74 ATOMIC AND MOLECULAR PHYSICS↗
DOE OSTI2025

Scalable quantum simulations of scattering in scalar field theory on 120 qubits

Simulations of collisions of fundamental particles on a quantum computer are expected to have an exponential advantage over classical methods and promise to enhance searches for new physics. Furthermore, scattering in scalar field theory has been shown to be bounded-error quantum polynomial time (BQP) complete, making it a representative problem for which quantum computation is efficient. As a step toward large-scale quantum simulations of collision processes, scattering of wave packets in one-dimensional scalar field theory is simulated using 120 qubits of IBM’s Heron superconducting quantum computer ibm_fez. Variational circuits compressing vacuum preparation, wave packet initialization, and time evolution are determined using classical resources. By leveraging physical properties of states in the theory, such as symmetries and locality, the variational quantum algorithm constructs scalable circuits that can be used to simulate arbitrarily large system sizes. A new strategy is introduced to mitigate errors in quantum simulations, which enables the extraction of meaningful results from circuits with up to 4924 two-qubit gates and two-qubit gate depths of 103. The effect of interactions is clearly seen, and is found to be in agreement with classical matrix product state simulations. Finally, the developments that will be necessary to simulate high-energy inelastic collisions on a quantum computer are discussed.

quantum circuits↗
DOE OSTI2021

Information-Theoretic Bounds on Quantum Advantage in Machine Learning

We study the performance of classical and quantum machine learning (ML) models in predicting outcomes of physical experiments. The experiments depend on an input parameter x and involve execution of a (possibly unknown) quantum process E. Our figure of merit is the number of runs of E required to achieve a desired prediction performance. We consider classical ML models that perform a measurement and record the classical outcome after each run of E, and quantum ML models that can access E coherently to acquire quantum data; the classical or quantum data are then used to predict the outcomes of future experiments. We prove that for any input distribution D(x), a classical ML model can provide accurate predictions on average by accessing E a number of times comparable to the optimal quantum ML model. In contrast, for achieving an accurate prediction on all inputs, we prove that the exponential quantum advantage is possible. For example, to predict the expectations of all Pauli observables in an n-qubit system ρ, classical ML models require 2 Ω(n) copies of ρ, but we present a quantum ML model using only O(n) copies. Our results clarify where the quantum advantage is possible and highlight the potential for classical ML models to address challenging quantum problems in physics and chemistry.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2025

Gate-Based Quantum Simulation of Gaussian Bosonic Circuits on Exponentially Many Modes

We introduce a framework for simulating, on an ( n + 1 )-qubit quantum computer, the action of a Gaussian bosonic (GB) circuit on a state over 2 n modes. Specifically, we encode the initial bosonic state’s expectation values over quadrature operators (and their covariance matrix) as an input qubit state. This is then evolved by a quantum circuit that effectively implements the symplectic propagators induced by the GB gates. We find families of GB circuits and initial states leading to efficient quantum simulations. For this purpose, we introduce a dictionary that maps between GB and qubit gates such that particle- (non-particle-) preserving GB gates lead to real- (imaginary-) time evolutions at the qubit level. For the special case of particle-preserving circuits, we present a bounded-error-quantum-polynomial time (BQP)-complete GB decision problem, indicating that GB evolutions of Gaussian states on exponentially many modes are as powerful as universal quantum computers. We also perform numerical simulations of an interferometer on ∼ 8 × 10 9 modes, illustrating the power of our framework. Published by the American Physical Society 2025

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2024

Dynamic Cooling on Contemporary Quantum Computers

We study the problem of dynamic cooling whereby a target qubit is cooled at the expense of heating up N − 1 further identical qubits by means of a global unitary operation. A standard back-of-the-envelope high-temperature estimate establishes that the target qubit temperature can be dynamically cooled by at most a factor of 1 / N . Here we provide the exact expression for the minimum temperature to which the target qubit can be cooled and reveal that there is a crossover from the high initial temperature regime, where the scaling is 1 / N , to a low initial temperature regime, where a much faster scaling of 1 / N occurs. This slow, 1 / N scaling, which was relevant for early high-temperature NMR quantum computers, is the reason dynamic cooling was dismissed as ineffectual around 20 years ago; the fact that current low-temperature quantum computers fall in the fast, 1 / N scaling regime, reinstates the appeal of dynamic cooling today. We further show that the associated work cost of cooling is exponentially more advantageous in the low-temperature regime. We discuss the implementation of dynamic cooling in terms of quantum circuits and examine the effects of hardware noise. We successfully demonstrate dynamic cooling in a three-qubit system on a real quantum processor. Since the circuit size grows quickly with N , scaling dynamic cooling to larger systems on noisy devices poses a challenge. We therefore propose a suboptimal cooling algorithm, whereby relinquishing a small amount of cooling capability results in a drastically reduced circuit complexity, greatly facilitating the implementation of dynamic cooling on near-future quantum computers. Published by the American Physical Society2024

Physics↗
DOE OSTI2024

Flag Gadgets Based on Classical Codes

Fault-tolerant syndrome extraction is a key ingredient in implementing fault-tolerant quantum computation. While conventional methods use a number of extra qubits that are linear in the weight of the syndrome, several improvements have been introduced using flag gadgets. In this work, we develop a framework to design flag gadgets using classical codes. Using this framework, we show how to perform fault-tolerant syndrome extraction for any stabilizer code with arbitrary distance using exponentially fewer qubits than conventional methods when qubit measurement and reset are relatively slow compared to a round of error correction. In particular, our method requires only ( 2 t + 1 ) t ⌈ log 2 ( w ) ⌉ flag qubits to fault-tolerantly measure a weight- w stabilizer. We further take advantage of the saving provided by our construction to fault-tolerantly measure multiple stabilizers using a single gadget and show that it maintains the same exponential advantage when it is used to fault-tolerantly extract the syndromes of quantum low-density parity-check codes. Using the developed framework, we perform computer-assisted search to find several small examples where our constructions reduce the number of qubits required. These small examples may be relevant to near-term experiments on small-scale quantum computers. Published by the American Physical Society 2024

Anker, Benjamin↗
DOE OSTI2023

Real-time spin systems from lattice field theory

We construct a lattice field theory method for computing the real-time dynamics of spin systems in a thermal bath. This is done by building on previous work of Takano with Schwinger-Keldysh and functional differentiation techniques. We derive a Schwinger-Keldysh path integral for generic spin Hamiltonians, then demonstrate the method on a simple system. Our path integral has a sign problem, which generally requires exponential run time in the system size, but requires only linear storage. The latter may place this method at an advantage over exact diagonalization, which is exponential in both. Our path integral is amenable to contour deformations, a technique for reducing sign problems.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2021

Quantum-classical hybrid algorithm for the simulation of all-electron correlation

While chemical systems containing hundreds to thousands of electrons remain beyond the reach of quantum devices, hybrid quantum-classical algorithms present a promising pathway toward a quantum advantage. Hybrid algorithms treat the exponentially scaling part of the calculation-the static correlation-on the quantum computer and the non-exponentially scaling part-the dynamic correlation-on the classical computer. While a variety of algorithms have been proposed, the dependence of many methods on the total wave function limits the development of easy-to-use classical post-processing implementations. Here, we present a novel combination of quantum and classical algorithms, which computes the all-electron energy of a strongly correlated molecular system on the classical computer from the 2-electron reduced density matrix (2-RDM) evaluated on the quantum device. Significantly, we circumvent the wave function in the all-electron calculations by using density matrix methods that only require input of the statically correlated 2-RDM. Although the algorithm is completely general, we test it with two classical density matrix methods, the anti-Hermitian contracted Schrödinger equation (ACSE) and multiconfiguration pair-density functional theories, using the recently developed quantum ACSE method for simulating the statically correlated 2-RDM. Furthermore, we obtain experimental accuracy for the relative energies of all three benzyne isomers and thereby demonstrate the ability of the developed algorithm to achieve chemically relevant and accurate results on noisy intermediate-scale quantum devices.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2026

Fault-tolerant resource comparison of qudit and qubit encodings for diagonal quadratic operators

Finite local Hilbert-space truncations arise naturally in quantum simulations of lattice field theories and motivate qudit encodings, but their fault-tolerant advantage over qubit encodings remains unclear. We compare the non-Clifford cost of implementing quadratic diagonal evolutions, exemplified by 𝑈 = 𝑒$^{−𝑖⁢𝑡⁢𝜙^2_𝑥}$ in a uniform field-amplitude discretization of a real scalar field, using either one logical 𝑑-level qudit or 𝑛 𝑏 = ⌈log 2⁡ 𝑑⌉ logical qubits. We analyze two standard settings: product-formula simulation and linear combination of unitaries (LCU) per block encoding, taking the resource metric to be the number of non-Clifford gates after synthesis into a discrete logical gate set. Because tight synthesis bounds for general single-qudit rotations are not known, we express the qudit constructions in terms of embedded two-level SU⁡(2) rotations and derive explicit finite-𝑑 break-even conditions for their synthesis cost; these serve as compiler targets for when qudit encodings can outperform the qubit baseline. Within the constructive models studied here, product-formula implementations would require an exponentially stronger per-primitive synthesis advantage for qudits to win asymptotically, while in the LCU setting the qubit encoding is asymptotically cheaper in 𝑑. Nevertheless, the finite-𝑑 threshold analysis identifies low-dimensional regions in which qudits can yield meaningful constant-factor savings, particularly for LCU-based implementations. As a secondary analysis of the LCU construction, we use an idealized negligible-overhead qubit-qudit code-switching model to give an absolute 𝑇-count comparison and reinterpret the savings as an allowable per-switch overhead budget.

Godwood, Samuel [Univ. of Liverpool (United Kingdo↗