Search NASA⌕ Search

SEARCH · Search NASA

Results for “heuristic 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 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
NASA NTRS2000

Automated Design of Quantum Circuits

In order to design a quantum circuit that performs a desired quantum computation, it is necessary to find a decomposition of the unitary matrix that represents that computation in terms of a sequence of quantum gate operations. To date, such designs have either been found by hand or by exhaustive enumeration of all possible circuit topologies. In this paper we propose an automated approach to quantum circuit design using search heuristics based on principles abstracted from evolutionary genetics, i.e. using a genetic programming algorithm adapted specially for this problem. We demonstrate the method on the task of discovering quantum circuit designs for quantum teleportation. We show that to find a given known circuit design (one which was hand-crafted by a human), the method considers roughly an order of magnitude fewer designs than naive enumeration. In addition, the method finds novel circuit designs superior to those previously known.

Williams, Colin P.↗
NASA NTRS2018

XY vs X Mixer in Quantum Alternating Operator Ansatz for Optimization Problems with Constraints

Quantum Approximate Optimization Algorithm, further generalized as Quantum Alternating Operator Ansatz (QAOA), is a family of algorithms for combinatorial optimization problems. It is a leading candidate to run on emerging universal quantum computers to gain insight into quantum heuristics. In constrained optimization, penalties are often introduced so that the ground state of the cost Hamiltonian encodes the solution (a standard practice in quantum annealing). An alternative is to choose a mixing Hamiltonian such that the constraint corresponds to a constant of motion and the quantum evolution stays in the feasible subspace. Better performance of the algorithm is speculated due to a much smaller search space. We consider problems with a constant Hamming weight as the constraint. We also compare different methods of generating the generalized W-state, which serves as a natural initial state for the Hamming-weight constraint. Using graph-coloring as an example, we compare the performance of using XY model as a mixer that preserves the Hamming weight with the performance of adding a penalty term in the cost Hamiltonian.

quantum computing↗
DOE OSTI2022

Controller-Based Energy-Aware Wireless Sensor Network Routing Using Quantum Algorithms

Energy-efficient routing in wireless sensor networks has attracted attention from researchers in both academia and industry, most recently motivated by the opportunity to use software-defined network-inspired approaches. These problems are NP-hard, with algorithms needing computation time that scales faster than polynomials in the problem size. Consequently, heuristic algorithms are used in practice, which are unable to guarantee optimally. In this article, we show proof-of-principle for the use of a quantum annealing processor instead of a classical processor, to find optimal or nearly optimal solutions very quickly. Our preliminary results for small networks show that this approach using quantum computing has great promise and may open the door for other significant improvements in the efficacy of network algorithms.

42 ENGINEERING↗
DOE OSTI2022

Numerical gate synthesis for quantum heuristics on bosonic quantum processors

There is a recent surge of interest and insights regarding the interplay of quantum optimal control and variational quantum algorithms. We study the framework in the context of qudits which are, for instance, definable as controllable electromagnetic modes of a superconducting cavity system coupled to a transmon. By employing recent quantum optimal control approaches described in (Petersson and Garcia, 2021), we showcase control of single-qudit operations up to eight states, and two-qutrit operations, mapped respectively onto a single mode and two modes of the resonator. We discuss the results of numerical pulse engineering on the closed system for parametrized gates useful to implement Quantum Approximate Optimization Algorithm (QAOA) for qudits. The results show that high fidelity ( > 0.99) is achievable with sufficient computational effort for most cases under study, and extensions to multiple modes and open, noisy systems are possible. The tailored pulses can be stored and used as calibrated primitives for a future compiler in circuit quantum electrodynamics (cQED) systems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS2019

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↗
DOE OSTI2022

Quantum annealing algorithms for Boolean tensor networks

Abstract Quantum annealers manufactured by D-Wave Systems, Inc., are computational devices capable of finding high-quality heuristic solutions of NP-hard problems. In this contribution, we explore the potential and effectiveness of such quantum annealers for computing Boolean tensor networks. Tensors offer a natural way to model high-dimensional data commonplace in many scientific fields, and representing a binary tensor as a Boolean tensor network is the task of expressing a tensor containing categorical (i.e., $$\{0, 1\}$$ { 0 , 1 } ) values as a product of low dimensional binary tensors. A Boolean tensor network is computed by Boolean tensor decomposition, and it is usually not exact. The aim of such decomposition is to minimize the given distance measure between the high-dimensional input tensor and the product of lower-dimensional (usually three-dimensional) tensors and matrices representing the tensor network. In this paper, we introduce and analyze three general algorithms for Boolean tensor networks: Tucker, Tensor Train, and Hierarchical Tucker networks. The computation of a Boolean tensor network is reduced to a sequence of Boolean matrix factorizations, which we show can be expressed as a quadratic unconstrained binary optimization problem suitable for solving on a quantum annealer. By using a novel method we introduce called parallel quantum annealing, we demonstrate that Boolean tensor’s with up to millions of elements can be decomposed efficiently using a DWave 2000Q quantum annealer.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Quantum Optimization: Potential, Challenges, and the Path Forward

Recent advances in quantum computers are demonstrating the ability to solve problems at a scale beyond brute force classical simulation. As such, a widespread interest in quantum algorithms has developed in many areas, with optimization being one of the most pronounced domains. Across computer science and physics, there are a number of algorithmic approaches, often with little linkage. This is further complicated by the fragmented nature of the field of mathematical optimization, where major classes of optimization problems, such as combinatorial optimization, convex optimization, non-convex optimization, and stochastic extensions, have devoted communities. With these aspects in mind, this work draws on multiple approaches to study quantum optimization. Provably exact versus heuristic settings are first explained using computational complexity theory — highlighting where quantum advantage is possible in each context. Then, the core building blocks for quantum optimization algorithms are outlined to subsequently define prominent problem classes and identify key open questions that, if answered, will advance the field. The effects of scaling relevant problems on noisy quantum devices are also outlined in detail, alongside meaningful benchmarking problems. We underscore the importance of benchmarking by proposing clear metrics to conduct appropriate comparisons with classical optimization techniques. Lastly, we highlight two domains – finance and sustainability – as rich sources of optimization problems that could be used to benchmark, and eventually validate, the potential real-world impact of quantum optimization.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2023

Spoofing Cross-Entropy Measure in Boson Sampling

Cross-entropy (XE) measure is a widely used benchmark to demonstrate quantum computational advantage from sampling problems, such as random circuit sampling using superconducting qubits and boson sampling (BS). We present a heuristic classical algorithm that attains a better XE than the current BS experiments in a verifiable regime and is likely to attain a better XE score than the near-future BS experiments in a reasonable running time. The key idea behind the algorithm is that there exist distributions that correlate with the ideal BS probability distribution and that can be efficiently computed. The correlation and the computability of the distribution enable us to postselect heavy outcomes of the ideal probability distribution without computing the ideal probability, which essentially leads to a large XE. Our method scores a better XE than the recent Gaussian BS experiments when implemented at intermediate, verifiable system sizes. Much like current state-of-the-art experiments, we cannot verify that our spoofer works for quantum-advantage-size systems. However, we demonstrate that our approach works for much larger system sizes in fermion sampling, where we can efficiently compute output probabilities. Finally, we provide analytic evidence that the classical algorithm is likely to spoof noisy BS efficiently.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2023

Suppressing Quantum Circuit Errors Due to System Variability

We present a quantum circuit optimization technique that takes into account the variability in error rates that is inherent across present-day noisy quantum computing platforms. This method can be run after qubit routing or postcompilation and consists of computing isomorphic subgraphs to input circuits and scoring each using heuristic cost functions derived from system calibration data. Using an independent standard algorithmic test suite, we show that it is possible to recover on average nearly 40% of missing fidelity using better qubit selection via efficient to compute cost functions. We demonstrate additional performance gains by considering qubit placement over multiple quantum processors. The overhead from these tools is minimal with respect to other compilation steps, such as qubit routing, as the number of qubits increases. As such, our method can be used to find qubit mappings for problems at the scale of quantum advantage and beyond.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2023

Sampling frequency thresholds for the quantum advantage of the quantum approximate optimization algorithm

We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers Gurobi and MQLib to solve the MaxCut problem on 3-regular graphs. We identify the minimum noiseless sampling frequency and depth p required for a quantum device to outperform classical algorithms. There is potential for quantum advantage on hundreds of qubits and moderate depth with a sampling frequency of 10 kHz. We observe, however, that classical heuristic solvers are capable of producing high-quality approximate solutions in linear time complexity. In order to match this quality for large graph sizes N, a quantum device must support depth p > 11. Additionally, multi-shot QAOA is not efficient on large graphs, indicating that QAOA p ≤ 11 does not scale with N. These results limit achieving quantum advantage for QAOA MaxCut on 3-regular graphs. Other problems, such as different graphs, weighted MaxCut, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
NASA NTRS1972

Design of automata theory of cubical complexes with applications to diagnosis and algorithmic description

The following problems are considered: (1) methods for development of logic design together with algorithms, so that it is possible to compute a test for any failure in the logic design, if such a test exists, and developing algorithms and heuristics for the purpose of minimizing the computation for tests; and (2) a method of design of logic for ultra LSI (large scale integration). It was discovered that the so-called quantum calculus can be extended to render it possible: (1) to describe the functional behavior of a mechanism component by component, and (2) to compute tests for failures, in the mechanism, using the diagnosis algorithm. The development of an algorithm for the multioutput two-level minimization problem is presented and the program MIN 360 was written for this algorithm. The program has options of mode (exact minimum or various approximations), cost function, cost bound, etc., providing flexibility.

Roth, J. P.↗
DOE OSTI2022

Quantum annealing for jet clustering with thrust

Quantum computing holds the promise of substantially speeding up computationally expensive tasks, such as solving optimization problems over a large number of elements. In high-energy collider physics, quantum-assisted algorithms might accelerate the clustering of particles into jets. In this study, we benchmark quantum annealing strategies for jet clustering based on optimizing a quantity called “thrust” in electron-positron collision events. Here, we find that quantum annealing yields similar performance to exact classical approaches and classical heuristics, after tuning the annealing parameters. Without tuning, comparable performance can be obtained through a hybrid quantum/classical approach.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2023

Description of reaction and vibrational energetics of CO 2 –NH 3 interaction using quantum computing algorithms

CO 2 capture is critical to solving global warming. Amine-based solvents are extensively used to chemically absorb CO 2 . Thus, it is crucial to study the chemical absorption of CO 2 by amine-based solvents to better understand and optimize CO 2 capture processes. Here, we use quantum computing algorithms to quantify molecular vibrational energies and reaction pathways between CO 2 and a simplified amine-based solvent model—NH 3 . Molecular vibrational properties are important to understanding kinetics of reactions. However, the molecule size correlates with the strength of anharmonicity effect on vibrational properties, which can be challenging to address using classical computing. Quantum computing can help enhance molecular vibrational calculations by including anharmonicity. We implement a variational quantum eigensolver (VQE) algorithm in a quantum simulator to calculate ground state vibrational energies of reactants and products of the CO 2 and NH 3 reaction. The VQE calculations yield ground vibrational energies of CO 2 and NH 3 with similar accuracy to classical computing. In the presence of hardware noise, Compact Heuristic for Chemistry (CHC) ansatz with shallower circuit depth performs better than Unitary Vibrational Coupled Cluster. The “Zero Noise Extrapolation” error-mitigation approach in combination with CHC ansatz improves the vibrational calculation accuracy. Excited vibrational states are accessed with quantum equation of motion method for CO 2 and NH 3 . Using quantum Hartree–Fock (HF) embedding algorithm to calculate electronic energies, the corresponding reaction profile compares favorably with Coupled Cluster Singles and Doubles while being more accurate than HF. Our research showcases quantum computing applications in the study of CO 2 capture reactions.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2026

Classical combinatorial optimization scaling for random Ising models on 2D heavy-hex graphs

Motivated by near term quantum computing hardware limitations, combinatorial optimization problems that can be addressed by current quantum algorithms and noisy hardware with little or no overhead are used to probe capabilities of quantum algorithms such as the quantum approximate optimization algorithm. In this study, a specific class of near term quantum computing hardware defined combinatorial optimization problems, Ising models on heavy-hex graphs both with and without geometrically local cubic terms, are examined for their classical computational hardness via empirical computation time scaling quantification. Specifically the time-to-solution (TTS) metric using the classical heuristic simulated annealing is measured for finding optimal variable assignments (ground states), as well as the time required for the optimization software Gurobi to find an optimal variable assignment. Because of the sparsity of these Ising models, the classical algorithms are able to find optimal solutions efficiently even for large instances (i.e. 100 000 spin variables). The Ising models both with and without geometrically local cubic terms exhibit average-case linear-time or weakly quadratic scaling when solved exactly using Gurobi, and the Ising models with no cubic terms show evidence of exponential-time TTS scaling when sampled using simulated annealing. These findings point to the necessity of developing and testing more complex, namely more densely connected, optimization problems in order for quantum computing to ever have a practical advantage over classical computing. Our results are another illustration that different classical algorithms can indeed have exponentially different running times, thus making the identification of the best practical classical technique important in any quantum computing vs. classical computing comparison.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Cost function dependent barren plateaus in shallow parametrized quantum circuits

Variational quantum algorithms (VQAs) optimize the parameters θ of a parametrized quantum circuit V(θ) to minimize a cost function C. While VQAs may enable practical applications of noisy quantum computers, they are nevertheless heuristic methods with unproven scaling. Here, we rigorously prove two results, assuming V(θ) is an alternating layered ansatz composed of blocks forming local 2-designs. Our first result states that defining C in terms of global observables leads to exponentially vanishing gradients (i.e., barren plateaus) even when V(θ) is shallow. Hence, several VQAs in the literature must revise their proposed costs. On the other hand, our second result states that defining C with local observables leads to at worst a polynomially vanishing gradient, so long as the depth of V(θ) is Ο(logn). Our results establish a connection between locality and trainability. We illustrate these ideas with large-scale simulations, up to 100 qubits, of a quantum autoencoder implementation.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

3-regular three-XORSAT planted solutions benchmark of classical and quantum heuristic optimizers

With current semiconductor technology reaching its physical limits, special-purpose hardware has emerged as an option to tackle specific computing-intensive challenges. Optimization in the form of solving quadratic unconstrained binary optimization problems, or equivalently Ising spin glasses, has been the focus of several new dedicated hardware platforms. These platforms come in many different flavors, from highly-efficient hardware implementations on digital-logic of established algorithms to proposals of analog hardware implementing new algorithms. In this work, we use a mapping of a specific class of linear equations whose solutions can be found efficiently, to a hard constraint satisfaction problem (three-regular three-XORSAT, or an Ising spin glass) with a 'golf-course' shaped energy landscape, to benchmark several of these different approaches. We perform a scaling and prefactor analysis of the performance of Fujitsu's digital annealer unit (DAU), the D-Wave advantage quantum annealer, a virtual MemComputing machine, Toshiba's simulated bifurcation machine (SBM), the SATonGPU algorithm from Bernaschi et al, and our implementation of parallel tempering. We identify the SATonGPU and DAU as currently having the smallest scaling exponent for this benchmark, with SATonGPU having a small scaling advantage and in addition having by far the smallest prefactor thanks to its use of massive parallelism. Furthermore, our work provides an objective assessment and a snapshot of the promise and limitations of dedicated optimization hardware relative to a particular class of optimization problems.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2025

Clifford Circuit-Based Heuristic Optimization of Fermion-To-Qubit Mappings

Simulation of interacting Fermionic Hamiltonians is one of the most promising applications of quantum computers. However, the feasibility of analyzing Fermionic systems with a quantum computer hinges on the efficiency of Fermion-to-qubit mappings that encode nonlocal Fermionic degrees of freedom in local qubit degrees of freedom. While recent studies have highlighted the importance of designing Fermion-to-qubit mappings that are tailored to specific problem Hamiltonians, the methods proposed so far either are restricted to a narrow class of mappings or they use computationally expensive and unscalable brute-force search algorithms. Here, in this work, we address this challenge by designing a heuristic numerical optimization framework for Fermion-to-qubit mappings. To this end, we first translate the Fermion-to-qubit mapping problem to a Clifford circuit optimization problem and then use simulated annealing to optimize the average Pauli weight of the problem Hamiltonian. For all Fermionic Hamiltonians we have considered, the numerically optimized mappings outperform their conventional counterparts, including ternary-tree-based mappings that are known to be optimal for single creation and annihilation operators. We find that our optimized mappings yield between 15% and 40% improvements on the average Pauli weight when the simulation Hamiltonian has an intermediate level of complexity. Most remarkably, the optimized mappings improve the average Pauli weight for 6 × 6 nearest-neighbor hopping and Hubbard models by more than 40% and 20%, respectively. Surprisingly, we also find specific interaction Hamiltonians for which the optimized mapping outperforms any ternary-tree-based mapping. Our results establish heuristic numerical optimization as an effective method for obtaining mappings tailored for specific Fermionic Hamiltonian.

Hamiltonians↗
DOE OSTI2022

Variational quantum state eigensolver

Extracting eigenvalues and eigenvectors of exponentially large matrices will be an important application of near-term quantum computers. The variational quantum eigensolver (VQE) treats the case when the matrix is a Hamiltonian. Here, we address the case when the matrix is a density matrix ρ. We introduce the variational quantum state eigensolver (VQSE), which is analogous to VQE in that it variationally learns the largest eigenvalues of ρ as well as a gate sequence V that prepares the corresponding eigenvectors. VQSE exploits the connection between diagonalization and majorization to define a cost function C=Tr(ρ~H) where H is a non-degenerate Hamiltonian. Due to Schur-concavity, C is minimized when ρ~=VρV† is diagonal in the eigenbasis of H. VQSE only requires a single copy of ρ (only n qubits) per iteration of the VQSE algorithm, making it amenable for near-term implementation. We heuristically demonstrate two applications of VQSE: (1) Principal component analysis, and (2) Error mitigation.

97 MATHEMATICS AND COMPUTING↗