Search NASA⌕ Search

SEARCH · Search NASA

Results for “quantum optimization”

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 523 records · Page 29
All sourcesNASA NTRSDOE OSTI
NASA NTRS2006

Exploiting Quantum Resonance to Solve Combinatorial Problems

Quantum resonance would be exploited in a proposed quantum-computing approach to the solution of combinatorial optimization problems. In quantum computing in general, one takes advantage of the fact that an algorithm cannot be decoupled from the physical effects available to implement it. Prior approaches to quantum computing have involved exploitation of only a subset of known quantum physical effects, notably including parallelism and entanglement, but not including resonance. In the proposed approach, one would utilize the combinatorial properties of tensor-product decomposability of unitary evolution of many-particle quantum systems for physically simulating solutions to NP-complete problems (a class of problems that are intractable with respect to classical methods of computation). In this approach, reinforcement and selection of a desired solution would be executed by means of quantum resonance. Classes of NP-complete problems that are important in practice and could be solved by the proposed approach include planning, scheduling, search, and optimal design.

Zak, Michail↗
DOE OSTI2016

An Early Quantum Computing Proposal

The D-Wave 2X is the third generation of quantum processing created by D-Wave. NASA (with Google and USRA) and Lockheed Martin (with USC), both own D-Wave systems. Los Alamos National Laboratory (LANL) purchased a D-Wave 2X in November 2015. The D-Wave 2X processor contains (nominally) 1152 quantum bits (or qubits) and is designed to specifically perform quantum annealing, which is a well-known method for finding a global minimum of an optimization problem. This methodology is based on direct execution of a quantum evolution in experimental quantum hardware. While this can be a powerful method for solving particular kinds of problems, it also means that the D-Wave 2X processor is not a general computing processor and cannot be programmed to perform a wide variety of tasks. It is a highly specialized processor, well beyond what NNSA currently thinks of as an “advanced architecture.”A D-Wave is best described as a quantum optimizer. That is, it uses quantum superposition to find the lowest energy state of a system by repeated doses of power and settling stages. The D-Wave produces multiple solutions to any suitably formulated problem, one of which is the lowest energy state solution (global minimum). Mapping problems onto the D-Wave requires defining an objective function to be minimized and then encoding that function in the Hamiltonian of the D-Wave system. The quantum annealing method is then used to find the lowest energy configuration of the Hamiltonian using the current D-Wave Two, two-level, quantum processor. This is not always an easy thing to do, and the D-Wave Two has significant limitations that restrict problem sizes that can be run and algorithmic choices that can be made. Furthermore, as more people are exploring this technology, it has become clear that it is very difficult to come up with general approaches to optimization that can both utilize the D-Wave and that can do better than highly developed algorithms on conventional computers for specific applications. These are all fundamental challenges that must be overcome for the D-Wave, or similar, quantum computing technology to be broadly applicable.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

A Quantum-Inspired Tensor Network Algorithm for Constrained Combinatorial Optimization Problems

Combinatorial optimization is of general interest for both theoretical study and real-world applications. Fast-developing quantum algorithms provide a different perspective on solving combinatorial optimization problems. In this paper, we propose a quantum-inspired tensor-network-based algorithm for general locally constrained combinatorial optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem, then encodes the constraints directly into a tensor network state and solves the optimal solution by evolving the system to the ground state of the Hamiltonian. We demonstrate our algorithm with the open-pit mining problem, which results in a quadratic asymptotic time complexity. Our numerical results show the effectiveness of this construction and potential applications in further studies for general combinatorial optimization problems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2018

Communication: Calculation of interatomic forces and optimization of molecular geometry with auxiliary-field quantum Monte Carlo

We introduce an algorithm for accurate, systematic, and scalable computation of interatomic forces within the auxiliary-field quantum Monte Carlo (AFQMC) method. The algorithm relies on the Hellmann-Feynman theorem and incorporates Pulay corrections in the presence of atomic orbital basis sets. We benchmark the technique for small molecules by comparing the computed forces with the derivatives of the AFQMC potential energy surface and by direct comparison with other quantum chemistry methods. Furthermore, we perform geometry optimizations using the steepest descent algorithm in larger molecules. With realistic basis sets, we obtain equilibrium geometries in agreement, within statistical error bars, with experimental values. The increase in computational cost for computing forces in this approach is only a small prefactor over that of calculating the total energy. This paves the way for a general and efficient method for geometry optimization and molecular dynamics within AFQMC.

74 ATOMIC AND MOLECULAR PHYSICS↗
DOE OSTI2026

Translation-Invariant Quantum Algorithms for Ordered Search are Optimal

Ordered search is the task of finding an item in an ordered list using comparison queries. The best exact classical algorithm for this fundamental problem uses [log 2 n] queries for a list of length n. Quantum computers can achieve a constant-factor speedup, but the best possible coefficient of log 2 n for exact quantum algorithms is only known to lie between (ln2)/π ≈ 0.221 and 4/log 2 605 ≈ 0.4333. We consider a special class of translation-invariant algorithms with no workspace, introduced by Farhi, Goldstone, Gutmann, and Sipser, that has been used to find the best known upper bounds. First, we show that any bounded-error, k-query quantum algorithm for ordered search can be implemented by a k-query algorithm in this special class. Second, we use linear programming to show that the best exact 5-query quantum algorithm can search a list of length 7265, giving an ordered search algorithm that asymptotically uses 5 log 7265 n ≈ 0.390 log 2 n quantum queries.

Translation-invariant quantum algorithms↗
DOE OSTI2024

Optimal Realization of Yang–Baxter Gate on Quantum Computers

Quantum computers provide a promising method to study the dynamics of many-body systems beyond classical simulation. On the other hand, the analytical methods developed and results obtained from the integrable systems provide deep insights on the many-body system. Quantum simulation of the integrable system not only provides a valid benchmark for quantum computers but is also the first step in studying integrable-breaking systems. The building block for the simulation of an integrable system is the Yang–Baxter gate. It is vital to know how to optimally realize the Yang–Baxter gates on quantum computers. Based on the geometric picture of the Yang–Baxter gates, the optimal realizations of two types of Yang–Baxter gates with a minimal number of controlled NOT (CNOT) or gates are presented. It is also shown how to systematically realize the Yang–Baxter gates via the pulse control. The different realizations on IBM quantum computers are tested and compared. It is found that the pulse realizations of the Yang–Baxter gates always have a higher gate fidelity compared to the optimal CNOT or realizations. On the basis of the above optimal realizations, the simulation of the Yang–Baxter equation on quantum computers is demonstrated. Finally, these results provide a guideline and standard for further experimental studies based on the Yang–Baxter gate.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2022

Prediction and compression of lattice QCD data using machine learning algorithms on quantum annealer

We present regression and compression algorithms for lattice QCD data utilizing the efficient binary optimization ability of quantum annealers. In the regression algorithm, we encode the correlation between the input and output variables into a sparse coding machine learning algorithm. The trained correlation pattern is used to predict lattice QCD observables of unseen lattice configurations from other observables measured on the lattice. In the compression algorithm, we define a mapping from lattice QCD data of floating-point numbers to the binary coefficients that closely reconstruct the input data from a set of basis vectors. Since the reconstruction is not exact, the mapping defines a lossy compression, but, a reasonably small number of binary coefficients are able to reconstruct the input vector of lattice QCD data with the reconstruction error much smaller than the statistical fluctuation. In both applications, we use D-Wave quantum annealers to solve the NP-hard binary optimization problems of the machine learning algorithms.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2020

Error-mitigated data-driven circuit learning on noisy quantum hardware

Application-level benchmarks measure how well a quantum device performs meaningful calculations. In the case of parameterized circuit training, the computational task is the preparation of a target quantum state via optimization over a loss landscape. This is complicated by various sources of noise, fixed hardware connectivity, and generative modeling, the choice of target distribution. Gradient-based training has become a useful benchmarking task for noisy intermediate-scale quantum computers because of the additional requirement that the optimization step uses the quantum device to estimate the loss function gradient. In this work, we use gradient-based data-driven circuit learning to qualitatively evaluate the performance of several superconducting platform devices and present results that show how error mitigation can improve the training of quantum circuit Born machines with 28 tunable parameters.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2020

K-Spin Hamiltonian for Quantum-Resolvable Markov Decision Processes

The Markov decision process is the mathematical formalization underlying the modern field of reinforcement learning when transition and reward functions are unknown. We derive a pseudo-Boolean cost function that is equivalent to a K-spin Hamiltonian representation of the discrete, finite, discounted Markov decision process with infinite horizon. This K-spin Hamiltonian furnishes a starting point from which to solve for an optimal policy using heuristic quantum algorithms such as adiabatic quantum annealing and the quantum approximate optimization algorithm on near-term quantum hardware. In arguing that the variational minimization of our Hamiltonian is approximately equivalent to the Bellman optimality condition for a prevalent class of environments we establish an interesting analogy with classical field theory. Along with proof-of-concept calculations to corroborate our formulation by simulated and quantum annealing against classical Q-Learning, we analyze the scaling of physical resources required to solve our Hamiltonian on quantum hardware.

Hamiltonian↗
DOE OSTI2014

Investigation and optimization of low-frequency noise performance in readout electronics of dc superconducting quantum interference device

We investigated and optimized the low-frequency noise characteristics of a preamplifier used for readout of direct current superconducting quantum interference devices (SQUIDs). When the SQUID output was detected directly using a room-temperature low-voltage-noise preamplifier, the low-frequency noise of a SQUID system was found to be dominated by the input current noise of the preamplifiers in case of a large dynamic resistance of the SQUID. To reduce the current noise of the preamplifier in the low-frequency range, we investigated the dependence of total preamplifier noise on the collector current and source resistance. When the collector current was decreased from 8.4 mA to 3 mA in the preamplifier made of 3 parallel SSM2220 transistor pairs, the low-frequency total voltage noise of the preamplifier (at 0.1 Hz) decreased by about 3 times for a source resistance of 30 Ω whereas the white noise level remained nearly unchanged. Since the relative contribution of preamplifier's input voltage and current noise is different depending on the dynamic resistance or flux-to-voltage transfer of the SQUID, the results showed that the total noise of a SQUID system at low-frequency range can be improved significantly by optimizing the preamplifier circuit parameters, mainly the collector current in case of low-noise bipolar transistor pairs.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2023

Toward Consistent High-Fidelity Quantum Learning on Unstable Devices via Efficient In-Situ Calibration

In the near-term noisy intermediate-scale quantum (NISQ) era, high noise will significantly reduce the fidelity of quantum computing. What's worse, recent works reveal that the noise on quantum devices is not stable, that is, the noise is dynamically changing over time. This leads to an imminent challenging problem: At run-time, is there a way to efficiently achieve a consistent high-fidelity quantum system on unstable devices? To study this problem, we take quantum learning (a.k.a., variational quantum algorithm) as a vehicle, which has a wide range of applications, such as combinatorial optimization and machine learning. A straightforward approach is to optimize a variational quantum circuit (VQC) with a parameter-shift approach on the target quantum device before using it; however, the optimization has an extremely high time cost, which is not practical at run-time. To address the pressing issue, in this paper, we proposed a novel quantum pulse-based noise adaptation framework, namely QuPAD. In the proposed framework, first, we identify that the CNOT gate is the fidelity bottleneck of the conventional VQC, and we employ a more robust parameterized multi-qubit gate (i.e., Rzx gate) to replace CNOT gate. Second, by benchmarking Rzx gate with different parameters, we build a fitting function for each coupling qubit pair, such that the deviation between the theoretic output of Rzx gate and its on-device output under a given pulse amplitude and duration can be efficiently predicted. On top of this, an evolutionary algorithm is devised to identify the pulse amplitude and duration of each Rzx gate (i.e., calibration) and find the quantum circuits with high fidelity. Experiments show that the runtime on quantum devices of QuPAD with 8–10 qubits is less than 15 minutes, which is up to 270 x faster than the parameter-shift approach. In addition, compared to the vanilla VQC as a baseline, QuPAD can achieve 59.33% accuracy gain on a classification task, and average 66.34% closer to ground state energy for molecular simulation.

Hu, Zhirui↗
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 OSTI2021

Large gradients via correlation in random parameterized quantum circuits

Scaling of variational quantum algorithms to large problem sizes requires efficient optimization of random parameterized quantum circuits. For such circuits with uncorrelated parameters, the presence of exponentially vanishing gradients in cost function landscapes is an obstacle to optimization by gradient descent methods. In this work, we prove that reducing the dimensionality of the parameter space by utilizing circuit modules containing spatially or temporally correlated gate layers can allow one to circumvent the vanishing gradient phenomenon. Here, examples are drawn from random separable circuits and asymptotically optimal variational versions of Grover's algorithm based on the quantum alternating operator ansatz. In the latter scenario, our bounds on cost function variation imply a transition between vanishing gradients and efficient trainability as the number of layers is increased toward $\mathcal{O}\left({2}^{n/2}\right)$, the optimal oracle complexity of quantum unstructured search.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS2019

Quantum Gate-Model Approaches to Exact and Approximate Optimization

Many of the most challenging computational problems arising in practical applications are tackled by heuristic algorithms which have not been rigorously proven to outperform other approaches but rather have been empirically demonstrated to be effective. While quantum heuristics have been proposed since the early days of quantum computing, true empirical evaluation of the real-world performance of these algorithms is only becoming possible now as increasingly powerful quantum gate-model devices continue to come online.In this talk, I will give an overview of the NASA QuAIL team's ongoing investigation into quantum gate-model heuristic algorithms for exact and approximate optimization. In particular, we consider the performance of the Quantum Approximate Optimization Algorithm on NP-hard optimization problems, and describe algorithm parameter setting strategies for real-world quantum hardware. We then show a generalization of QAOA circuits, the Quantum Alternating Operator Ansatz, especially suitable for low-resource implementations of QAOA for problems with hard (feasibility) constraints. The talk will conclude with a discussion of research challenges, particularly for optimization and sampling applications of QAOA, and the potential of more general quantum heuristics to give advantages over classical computers.

Hadfield, Stuart↗
DOE OSTI2023

On the Approximability of Random-Hypergraph MAX-3-XORSAT Problems with Quantum Algorithms

Constraint satisfaction problems are an important area of computer science. Many of these problems are in the complexity class NP which is exponentially hard for all known methods, both for worst cases and often typical. Fundamentally, the lack of any guided local minimum escape method ensures the hardness of both exact and approximate optimization classically, but the intuitive mechanism for approximation hardness in quantum algorithms based on Hamiltonian time evolution is poorly understood. We explore this question using the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We qualitatively identify why traditional methods such as quantum adiabatic optimization are not good approximation algorithms. We propose a new spectral folding optimization method that does not suffer from these issues and study it analytically and numerically. We consider random rank-3 hypergraphs including extremal planted solution instances, where the ground state satisfies an anomalously high fraction of constraints compared to truly random problems. We show that, if we define the energy to be $E = N_{unsat}-N_{sat}$, then spectrally folded quantum optimization will return states with energy $E \leq A E_{GS}$ (where $E_{GS}$ is the ground state energy) in polynomial time, where conservatively, $A \simeq 0.6$. We thoroughly benchmark variations of spectrally folded quantum optimization for random classically approximation-hard (planted solution) instances in simulation, and find performance consistent with this prediction. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed.

Kapit, Eliot↗
DOE OSTI2024

SQMS Quantum R&D in Machine Learning, Optimization and Sensing beyond Fundamental Physics Applications

This newly formed team at SQMS under the Ecosystem Thrust is looking to develop capabilities impacting societal advances outside the core domain of HEP and condensed matter physics. We explicitly leverage the experimental and algorithmic innovations developed across all groups as well as connect to broad-scope external projects of the diverse team of PIs. As the inaugural set of projects, we are studying numerically quantum machine learning models inspired by efficiently trainable echo-state and orthogonal neural networks and developing designs for related experiments to be performed on quantum processors based on SQMS SRF cQED technology and Rigetti s transmon arrays. Investigated models exploit ideas and lessons learned from multiple prior work by SQMS team members in a variety of internal and external activities [R1]. Target initial applications include noisy signal processing, potentially captured by quantum sensors or noisy QPUs, as well as simulation and classification of healthcare data. For instance, image reconstruction of the brain s electrical properties by solving the inverse Maxwell equation problem with uncertainty [R2] through a hybrid quantum-classical physics-informed architecture for time-dependent processes [R3]. The group is also investigating the application and development of novel quantum sensors based on magnetic levitation of a superconducting sphere coupled to a superconducting qubit. This coupling enables high-precision measurements of the position of the sphere, which can be used for sensitive detection of forces, enabling practical applications such as gravimetry for geophysics analysis, or accelerometry for GPS-denied navigation [R4] [R1] Rieffel, Eleanor G., Ata Akbari Asanjan, M. Sohaib Alam, Namit Anand, David E. Bernal Neira, Sophie Block, Lucas T. Brady et al. "Assessing and advancing the potential of quantum computing: A NASA case study." Future Generation Computer Systems (2024). [R2] Yu, X., Serrall s, J.E., Giannakopoulos, I.I., Liu, Z., Daniel, L., Lattanzi, R. and Zhang, Z., 2023. Pifon-ept: Mr-based electrical property tomography using physics-informed fourier networks. IEEE Journal on Multiscale and Multiphysics Computational Techniques. [R3] Wudarski, Filip, Daniel OConnor, Shaun Geaney, Ata Akbari Asanjan, Max Wilson, Elena Strbac, P. Aaron Lott, and Davide Venturelli. "Hybrid quantum-classical reservoir computing for simulating chaotic systems." arXiv preprint arXiv:2311.14105 (2023). [R4] Higgins, Gerard, Saarik Kalia, and Zhen Liu. "Maglev for dark matter: Dark-photon and axion dark matter sensing with levitated superconductors." Physical Review D 109.5 (2024): 055024.

Venturelli, Davide↗
DOE OSTI2025

Simulating large one-dimensional neutral-atom quantum systems

While abstract models of quantum computation assume a closed system of two-level states, practical quantum devices inevitably couple to the environment in some way, creating sources of noise. Understanding the tolerance to noise of specific quantum algorithms run on specific devices is important for determining the feasibility of quantum computing in the current noisy intermediate-scale quantum era. Of particular interest is understanding the noise sensitivity of these devices as more qubits are added to the system. Classical simulations are a useful tool to understand the effects of this noise, but direct classical simulations of open quantum systems are burdened by an exponentially growing cost in the number of qubits and a large local Hilbert space dimension. For onedimensional, shallow circuits, using tensor networks can replace this exponential cost with a linear one and simulate far wider systems than what would normally be available. In this paper, we describe a tensor network simulation of a neutral atom quantum system under the presence of noise, while introducing a purity-preserving truncation technique that compromises between the simplicity of the matrix product state and the positivity of the matrix product density operator. We apply this simulation to a near-optimized iteration of the quantum approximate optimization algorithm on a transverse field Ising model in order to investigate the influence of large system sizes on the performance of the algorithm. We find that while circuits with a large number of qubits fail more often under noise that depletes the qubit population, their outputs on a successful measurement are just as robust under Rydberg atom dissipation or qubit dephasing as smaller systems. However, such circuits might not perform as well under coherent multiqubit errors such as Rydberg atom crosstalk. We also find that the optimized parameters are especially robust to noise, suggesting that a noisier quantum system can be used to find the optimal parameters before switching to a cleaner system for measurements of observables.

Allen, James↗
DOE OSTI2021

Perspective: Reproducible Coherence Characterization of Superconducting Quantum Devices

As the field of superconducting quantum computing approaches maturity, optimization of single-device performance is proving to be a promising avenue towards large-scale quantum computers. However, this optimization is possible only if performance metrics can be accurately compared among measurements, devices, and laboratories. Currently such comparisons are inaccurate or impossible due to understudied errors from a plethora of sources. In this Perspective, we outline the current state of error analysis for qubits and resonators in superconducting quantum circuits, and discuss what future investigations are required before superconducting quantum device optimization can be realized.

McRae, Corey H.↗