SEARCH · Engineering Papers

Results for “Quantum algorithm sampling”

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.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 55 records · Page 3

All sources NASA NTRS DOE OSTI

DOE OSTI2026

Predicting Adaptively Chosen Observables in Quantum Systems

Recent advances have demonstrated that 𝒪⁡(log 𝑀) measurements suffice to predict 𝑀 properties of arbitrarily large quantum many-body systems. However, these remarkable findings assume that the properties to be predicted are chosen independently of the data. This assumption can be violated in practice, where scientists adaptively select properties after looking at previous predictions. This work investigates the adaptive setting for three classes of observables: local, Pauli, and bounded-Frobenius-norm observables. We prove that Ω⁡(√𝑀) samples of an arbitrarily large unknown quantum state are necessary to predict expectation values of 𝑀 adaptively chosen local and Pauli observables, where the system size scales exponentially and polynomially in 𝑀, respectively. We also present computationally efficient algorithms that achieve this information-theoretic lower bound. In contrast, for bounded-Frobenius-norm observables, we devise an algorithm requiring only 𝒪⁡(log 𝑀) samples, independent of system size. These results highlight the potential pitfalls of adaptivity in analyzing data from quantum experiments and provide algorithmic tools to safeguard against erroneous predictions in quantum experiments.

Machine learning↗

NASA NTRS2016

Explorations of Quantum-Classical Approaches to Scheduling a Mars Lander Activity Problem

An effective approach to solving problems involving mixed (continuous and discrete) variables and constraints, such as hybrid systems, is to decompose them into subproblems and integrate dedicated solvers geared toward those subproblems. Here, we introduce a new framework based on a tree search algorithm to solve hybrid discrete-continuous problems that incorporates: (1) a quantum annealer that samples from the configuration space for the discrete portion and provides information about the quality of the samples, and (2) a classical computer that makes use of information from the quantum annealer to prune and focus the search as well as check a continuous constraint. We consider four variants of our algorithm, each with progressively more guidance from the results provided by the quantum annealer. We empirically test our algorithm and compare the variants on a simplified Mars Lander task scheduling problem. Variants with more guidance from the quantum annealer have better performance.

scheduling↗

DOE OSTI2023

Non-Boolean quantum amplitude amplification and quantum mean estimation

This paper generalizes the quantum amplitude amplification and amplitude estimation algorithms to work with non-Boolean oracles. The action of a non-Boolean oracle $U_\varphi $ on an eigenstate $\mathinner {|{x}\rangle }$ is to apply a state-dependent phase-shift $\varphi (x)$. Unlike Boolean oracles, the eigenvalues $\exp (i\varphi (x))$ of a non-Boolean oracle are not restricted to be $\pm 1$. Two new oracular algorithms based on such non-Boolean oracles are introduced. The first is the non-Boolean amplitude amplification algorithm, which preferentially amplifies the amplitudes of the eigenstates based on the value of $\varphi (x)$. Starting from a given initial superposition state $\mathinner {|{\psi _0}\rangle }$, the basis states with lower values of $\cos (\varphi )$ are amplified at the expense of the basis states with higher values of $\cos (\varphi )$. The second algorithm is the quantum mean estimation algorithm, which uses quantum phase estimation to estimate the expectation $\mathinner {\langle {\psi _0|U_\varphi |\psi _0}\rangle }$, i.e., the expected value of $\exp (i\varphi (x))$ for a random x sampled by making a measurement on $\mathinner {|{\psi _0}\rangle }$. It is shown that the quantum mean estimation algorithm offers a quadratic speedup over the corresponding classical algorithm. Both algorithms are demonstrated using simulations for a toy example. Potential applications of the algorithms are briefly discussed.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2024

Quantum Tensor-Product Decomposition from Choi-State Tomography

The Schmidt decomposition is the go-to tool for measuring bipartite entanglement of pure quantum states. Similarly, it is possible to study the entangling features of a quantum operation using its operator-Schmidt or tensor-product decomposition. While quantum technological implementations of the former are thoroughly studied, entangling properties on the operator level are harder to extract in the quantum computational framework because of the exponential nature of sample complexity. Here, we present an algorithm for unbalanced partitions into a small subsystem and a large one (the environment) to compute the tensor-product decomposition of a unitary the effect of which on the small subsystem is captured in classical memory, while the effect on the environment is accessible as a quantum resource. This quantum algorithm may be used to make predictions about operator nonlocality and effective open quantum dynamics on a subsystem, as well as for finding low-rank approximations and low-depth compilations of quantum circuit unitaries. We demonstrate the method and its applications on a time-evolution unitary of an isotropic Heisenberg model in two dimensions. Published by the American Physical Society 2024

Mansuroglu, Refik (ORCID:000000017352513X)↗

NASA NTRS2017

Exponentially-Biased Ground-State Sampling of Quantum Annealing Machines with Transverse-Field Driving Hamiltonians

We study the performance of the D-Wave 2X quantum annealing machine on systems with well-controlled ground-state degeneracy. While obtaining the ground state of a spin-glass benchmark instance represents a difficult task, the gold standard for any optimization algorithm or machine is to sample all solutions that minimize the Hamiltonian with more or less equal probability. Our results show that while naive transverse-field quantum annealing on the D-Wave 2X device can find the ground-state energy of the problems, it is not well suited in identifying all degenerate ground-state configurations associated to a particular instance. Even worse, some states are exponentially suppressed, in agreement with previous studies on toy model problems [New J. Phys. 11, 073021 (2009)]. These results suggest that more complex driving Hamiltonians are needed in future quantum annealing machines to ensure a fair sampling of the ground-state manifold.

Quantum Annealing↗

DOE OSTI2021

Weak Simulation v.0.1

The SPARSIFY algorithm implemented by the code allows for classical simulation of universal quantum computer sample outcomes. The code sparsifies the stabilizer decomposition of a qubit t-tensored T gate magic state to some additive error. This is accomplished by either independent L1 sampling or with correlated L1 sampling to supplement an independent subset, which offers a more efficient decomposition: for a given t, a sparser decomposition is sufficient with correlated L1 sampling to satisfy a given additive error. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525. SAND2021-8296 O

SciDAC↗

DOE OSTI2022

Autoregressive Neural Network for Simulating Open Quantum Systems via a Probabilistic Formulation

The theory of open quantum systems lays the foundation for a substantial part of modern research in quantum science and engineering. Rooted in the dimensionality of their extended Hilbert spaces, the high computational complexity of simulating open quantum systems calls for the development of strategies to approximate their dynamics. In this Letter, we present an approach for tackling open quantum system dynamics. Using an exact probabilistic formulation of quantum physics based on positive operator-valued measure, we compactly represent quantum states with autoregressive neural networks; such networks bring significant algorithmic flexibility due to efficient exact sampling and tractable density. We further introduce the concept of string states to partially restore the symmetry of the autoregressive neural network and improve the description of local correlations. Efficient algorithms have been developed to simulate the dynamics of the Liouvillian superoperator using a forward-backward trapezoid method and find the steady state via a variational formulation. Our approach is benchmarked on prototypical one-dimensional and two-dimensional systems, finding results which closely track the exact solution and achieve higher accuracy than alternative approaches based on using Markov chain Monte Carlo method to sample restricted Boltzmann machines. Our Letter provides general methods for understanding quantum dynamics in various contexts, as well as techniques for solving high-dimensional probabilistic differential equations in classical setups.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

DOE OSTI2022

Automated quantum error mitigation based on probabilistic error reduction

Current quantum computers suffer from a level of noise that prohibits extracting useful results directly from longer computations. The figure of merit in many near-term quantum algorithms is an expectation value measured at the end of the computation, which experiences a bias in the presence of hardware noise. A systematic way to remove such bias is probabilistic error cancellation (PEC). PEC requires a full characterization of the noise and introduces a sampling overhead that increases exponentially with circuit depth, prohibiting high-depth circuits at realistic noise levels. Probabilistic error reduction (PER) is a related quantum error mitigation method that systematically reduces the sampling overhead at the cost of reintroducing bias. In combination with zero-noise extrapolation, PER can yield expectation values with an accuracy comparable to PEC.Noise reduction through PER is broadly applicable to near-term algorithms, and the automated implementation of PER is thus desirable for facilitating its widespread use. To this end, we present an automated quantum error mitigation software framework that includes noise tomography and application of PER to user-specified circuits. We provide a multi-platform Python package that implements a recently developed Pauli noise tomography (PNT) technique for learning a sparse Pauli noise model and exploits a Pauli noise scaling method to carry out PER.We also provide software tools that leverage a previously developed toolchain, employing PyGSTi for gate set tomography and providing a functionality to use the software Mitiq for PER and zero-noise extrapolation to obtain error-mitigated expectation values on a user-defined circuit.

McDonough, Benjamin↗

DOE OSTI2024

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↗

DOE OSTI2023

Quantum Search Approaches to Sampling-Based Motion Planning

In this paper, we present a novel formulation of traditional sampling-based motion planners as database-oracle structures that can be solved via quantum search algorithms. We consider two complementary scenarios: for simpler sparse environments, we formulate the Quantum Full Path Search Algorithm (q-FPS), which creates a superposition of full random path solutions, manipulates probability amplitudes with Quantum Amplitude Amplification (QAA), and quantum measures a single obstacle free full path solution. For dense unstructured environments, we formulate the Quantum Rapidly Exploring Random Tree algorithm, q-RRT, that creates quantum superpositions of possible parent-child connections, manipulates probability amplitudes with QAA, and quantum measures a single reachable state, which is added to a tree. As performance depends on the number of oracle calls and the probability of measuring good quantum states, we quantify how these errors factor into the probabilistic completeness properties of the algorithm. We then numerically estimate the expected number of database solutions to provide an approximation of the optimal number of oracle calls in the algorithm. We compare the q-RRT algorithm with a classical implementation and verify quadratic run-time speedup in the largest connected component of a 2D dense random lattice. We conclude by evaluating a proposed approach to limit the expected number of database solutions and thus limit the optimal number of oracle calls to a given number.

97 MATHEMATICS AND COMPUTING↗

DOE OSTI2021

Sampling on NISQ Devices: "Who’s the Fairest One of All?"

Modern NISQ devices are subject to a variety of biases and sources of noise that degrade the solution quality of computations carried out on these devices. A natural question that arises in the NISQ era, is how fairly do these devices sample ground state solutions. To this end, we run five fair sampling problems (each with at least three ground state solutions) that are based both on quantum annealing and, on the Grover Mixer, -QAOA algorithm for gate-based NISQ hardware. In particular, we use seven IBM Q devices, the Aspen-9 Rigetti device, the IonQ device, and three D-Wave quantum annealers. For each of the fair sampling problems, we measure the ground state probability, the relative fairness of the frequency of each ground state solution with respect to the other ground state solutions, and the aggregate error as given by each hardware provider. Overall, our results show that NISQ devices do not achieve fair sampling yet. Furthermore, we also observe differences in the software stack with a particular focus on compilation techniques that illustrate what work will still need to be done to achieve a seamless integration of frontend (i.e., quantum circuit description) and backend compilation.

Computer Science↗

DOE OSTI2021

Quantum Machine-Learning for Eigenstate Filtration in Two-Dimensional Materials

Quantum machine-learning algorithms have emerged to be a promising alternative to their classical counterparts as they leverage the power of quantum computers. Such algorithms have been developed to solve problems like electronic structure calculations of molecular systems and spin models in magnetic systems. However, the discussion in all these recipes focuses specifically on targeting the ground state. Herein we demonstrate a quantum algorithm that can filter any energy eigenstate of the system based on either symmetry properties or a predefined choice of the user. The workhorse of our technique is a shallow neural network encoding the desired state of the system with the amplitude computed by sampling the Gibbs–Boltzmann distribution using a quantum circuit and the phase information obtained classically from the nonlinear activation of a separate set of neurons. We show that the resource requirements of our algorithm are strictly quadratic. To demonstrate its efficacy, we use state filtration in monolayer transition metal dichalcogenides which are hitherto unexplored in any flavor of quantum simulations. We implement our algorithm not only on quantum simulators but also on actual IBM-Q quantum devices and show good agreement with the results procured from conventional electronic structure calculations. We thus expect our protocol to provide a new alternative in exploring the band structures of exquisite materials to usual electronic structure methods or machine-learning techniques that are implementable solely on a classical computer.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2024

Composite Qdrift-product formulas for quantum and classical simulations in real and imaginary time

Recent study has shown that it can be advantageous to implement a composite channel that partitions the Hamiltonian H for a given simulation problem into subsets A and B such that H = A + B , where the terms in A are simulated with a Trotter-Suzuki channel and the B terms are randomly sampled via the Qdrift algorithm. Here we extend Qdrift and composite product formulas to imaginary time, formulating candidate classical algorithms for quantum Monte Carlo calculations. We upper bound the induced Schatten- 1 → 1 norm on both imaginary-time Qdrift and composite channels. Another recent result demonstrated that simulations of lattice Hamiltonians containing geometrically local interactions can be improved using a Lieb-Robinson argument to decompose H into subsets that contain only terms supported on that subset of the lattice. Here, we provide a quantum algorithm by unifying this result with the composite approach into “local composite channels” and we upper bound the diamond distance. We provide exact numerical simulations of algorithmic cost by counting the number of gates of the form e − i H j t and e − H j β to meet a certain error tolerance ε . In doing so, we optimize the partitioning into sets A and B using gradient boosted tree models from machine learning. These numerical studies are important given that product formulas have been historically known to outperform analytic upper bounds. We show constant factor advantages for a variety of interesting Hamiltonians, the maximum of which is a ≈ 20 -fold speedup that occurs in the simulation of Jellium. Published by the American Physical Society 2024

Pocrnic, Matthew (ORCID:0000000203089376)↗

DOE OSTI2021

Adapting Quantum Approximation Optimization Algorithm (QAOA) for Unit Commitment

In the present Noisy Intermediate-Scale Quantum (NISQ), hybrid algorithms that leverage classical resources to reduce quantum costs are particularly appealing. We formulate and apply such a hybrid quantum-classical algorithm to a power system optimization problem called Unit Commitment, which aims to satisfy a target power load at minimal cost. Our algorithm extends the Quantum Approximation Optimization Algorithm (QAOA) with a classical minimizer in order to support mixed binary optimization. Using Qiskit, we simulate results for sample systems to validate the effectiveness of our approach. Here, we also compare to purely classical methods. Our results indicate that classical solvers are effective for our simulated Unit Commitment instances with fewer than 400 power generation units. However, for larger problem instances, the classical solvers either scale exponentially in runtime or must resort to coarse approximations. This opens the door to potential quantum advantage for systems with several hundred units, though quantum error correction may be necessary at this scale.

42 ENGINEERING↗

DOE OSTI2024

Benchmarking Optimizers for Qumode State Preparation with Variational Quantum Algorithms

Quantum state preparation involves preparing a target state from an initial system, a process integral to applications such as quantum machine learning and solving systems of linear equations. Recently, there has been a growing interest in qumodes due to advancements in the field and their potential applications. However there is a notable gap in the literature specifically addressing this area. This paper aims to bridge this gap by providing performance benchmarks of various optimizers used in state preparation with Variational Quantum Algorithms. We conducted extensive testing across multiple scenarios, including different target states, both ideal and sampling simulations, and varying numbers of basis gate layers. Our evaluations offer insights into the complexity of learning each type of target state and demonstrate that some optimizers perform better than others in this context. Notably, the Powell optimizer was found to be exceptionally robust against sampling errors, making it a preferred choice in scenarios prone to such inaccuracies. Additionally, the Simultaneous Perturbation Stochastic Approximation optimizer was distinguished for its efficiency and ability to handle increased parameter dimensionality effectively.

Kan, Shuwen [Fordham University]↗

DOE OSTI2022

Variational approach to quantum state tomography based on maximal entropy formalism

Quantum state tomography is an integral part of quantum computation and offers the starting point for the validation of various quantum devices. One of the central tasks in the field of state tomography is to reconstruct, with high fidelity, the quantum states of a quantum system. From an experiment on a real quantum device, one can obtain the mean measurement values of different operators. With such data as input, in this report we employ the maximal entropy formalism to construct the least biased mixed quantum state that is consistent with the given set of expectation values. Even though, in principle, the reported formalism is quite general and should work for an arbitrary set of observables, in practice we shall demonstrate the efficacy of the algorithm on an informationally complete (IC) set of Hermitian operators. Such a set possesses the advantage of uniquely specifying a single quantum state from which the experimental measurements have been sampled and hence renders the rare opportunity not only to construct a least-biased quantum state but even replicate the exact state prepared experimentally within a preset tolerance. Here, the primary workhorse of the algorithm is reconstructing an energy function which we designate as the effective Hamiltonian of the system, and parameterizing it with Lagrange multipliers, according to the formalism of maximal entropy. These parameters are thereafter optimized variationally so that the reconstructed quantum state of the system converges to the true quantum state within an error threshold. To this end, we employ a parameterized quantum circuit and a hybrid quantum-classical variational algorithm to obtain such a target state, making our recipe easily implementable on a near-term quantum device.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

DOE OSTI2026

Testing Classical Properties from Quantum Data

Many properties of Boolean functions can be tested far more efficiently than the function itself can be learned. However, this dramatic advantage often disappears when testers are limited to random samples of ƒ instead of adaptively chosen queries to f. In this work we investigate the quantum version of this restriction: quantum algorithms that test properties of a Boolean function f solely from copies of either the function state |ƒ⟩ ∝ ∑ x |x, ƒ(x)⟩ or the phase state |(-1) ƒ ⟩ ∝ ∑ x (-1) ƒ(x) |x⟩. For monotonicity, symmetry, and triangle-freeness, we show passive quantum testers are unboundedly or super-polynomially better than their classical passive testing counterparts. They are competitive with classic query -based testers in each case. Our new testers use techniques beyond quantum Fourier sampling, and it turns out this is necessary: we show a certain class of bent functions can be tested from 𝒪(1) function states but has a sample complexity lower bound of 2 Ω(n) for any tester relying exclusively on Fourier and classical samples. Our passive quantum testers are competitive with classical query -based testers, but this isn't universal: we exhibit a testing problem that can be solved from 𝒪(1) classical queries but requires Ω(2 n/2 ) function state copies. The Forrelation problem provides a separation of the same magnitude in the opposite direction, so we conclude that quantum data and classical queries are "maximally incomparable" resources for testing. We also begin the study of lower bounds for testing from quantum data. For quantum monotonicity testing, we prove that the ensembles of [Goldreich et al., 2000; Black, 2024], which give exponential lower bounds for classical sample-based testing, do not yield any nontrivial lower bounds for testing from quantum data. New insights specific to quantum data will be required for proving copy complexity lower bounds for testing in this model.

Boolean Functions↗

DOE OSTI2020

Modern Approaches to Exact Diagonalization and Selected Configuration Interaction with the Adaptive Sampling CI Method

Recent advances in selected configuration interaction methods have made them competitive with the most accurate techniques available and, hence, creating an increasingly powerful tool for solving quantum Hamiltonians. In this work, we build on recent advances from the adaptive sampling configuration interaction (ASCI) algorithm. We show that a useful paradigm for generating efficient selected CI/exact diagonalization algorithms is driven by fast sorting algorithms, much in the same way iterative diagonalization is based on the paradigm of matrix vector multiplication. We present several new algorithms for all parts of performing a selected CI, which includes new ASCI search, dynamic bit masking, fast orbital rotations, fast diagonal matrix elements, and residue arrays. The ASCI search algorithm can be used in several different modes, which includes an integral driven search and a coefficient driven search. The algorithms presented here are fast and scalable, and we find that because they are built on fast sorting algorithms they are more efficient than all other approaches we considered. After introducing these techniques, we present ASCI results applied to a large range of systems and basis sets to demonstrate the types of simulations that can be practically treated at the full-CI level with modern methods and hardware, presenting double- and triple-ζ benchmark data for the G1 data set. The largest of these calculations is Si$_2$H$_6$ which is a simulation of 34 electrons in 152 orbitals. We also present some preliminary results for fast deterministic perturbation theory simulations that use hash functions to maintain high efficiency for treating large basis sets.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗