Search NASA⌕ Search

Engineering topics

Herrman, Rebekah

Publications and source records attributed to Herrman, Rebekah.

Approximate Boltzmann distributions in quantum approximate optimization

Approaches to compute or estimate the output probability distributions from the quantum approximate optimization algorithm (QAOA) are needed to assess the likelihood it will obtain a quantum computational advantage. We analyze output from QAOA circuits solving 7200 random MaxCut instances, with $n$ = 14–23 qubits and depth parameter $p$ ≤ 12 and find that the average basis state probabilities follow approximate Boltzmann distributions: The average probabilities scale exponentially with their energy (cut value), with a peak at the optimal solution. Furthermore, we describe the rate of exponential scaling or effective temperature in terms of a series with a leading-order term $T$ ~ $C$ min /$n$ $\sqrt{p}$, with $C$ min the optimal solution energy. Using this scaling, we generate approximate output distributions with up to 38 qubits and find these give accurate accounts of important performance metrics in cases we can simulate exactly.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

Solving MaxCut with quantum imaginary time evolution

We introduce a method to solve the MaxCut problem efficiently based on quantum imaginary time evolution (QITE). We employ a linear Ansatz for unitary updates and an initial state involving no entanglement, as well as an imaginary-time-dependent Hamiltonian interpolating between a given graph and a subgraph with two edges excised. We apply the method to thousands of randomly selected graphs with up to fifty vertices. We show that our algorithm exhibits a 93% and above performance converging to the maximum solution of the MaxCut problem for all considered graphs. Our results compare favorably with the performance of classical algorithms, such as the greedy and Goemans–Williamson algorithms. We also discuss the overlap of the final state of the QITE algorithm with the ground state as a performance metric, which is a quantum feature not shared by other classical algorithms.

97 MATHEMATICS AND COMPUTING↗

Scaling quantum approximate optimization on near-term hardware

The quantum approximate optimization algorithm (QAOA) is an approach for near-term quantum computers to potentially demonstrate computational advantage in solving combinatorial optimization problems. However, the viability of the QAOA depends on how its performance and resource requirements scale with problem size and complexity for realistic hardware implementations. Here, we quantify scaling of the expected resource requirements by synthesizing optimized circuits for hardware architectures with varying levels of connectivity. Assuming noisy gate operations, we estimate the number of measurements needed to sample the output of the idealized QAOA circuit with high probability. We show the number of measurements, and hence total time to solution, grows exponentially in problem size and problem graph degree as well as depth of the QAOA ansatz, gate infidelities, and inverse hardware graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.

97 MATHEMATICS AND COMPUTING↗

Multi-angle quantum approximate optimization algorithm

The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems using a variational ansatz circuit defined by parameterized layers of quantum evolution. In theory, the approximation improves with increasing ansatz depth but gate noise and circuit complexity undermine performance in practice. Here, we investigate a multi-angle ansatz for QAOA that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. Even though the number of parameters increases, our results indicate that good parameters can be found in polynomial time for a test dataset we consider. This new ansatz gives a 33% increase in the approximation ratio for an infinite family of MaxCut instances over QAOA. The optimal performance is lower bounded by the conventional ansatz, and we present empirical results for graphs on eight vertices that one layer of the multi-angle anstaz is comparable to three layers of the traditional ansatz on MaxCut problems. Similarly, multi-angle QAOA yields a higher approximation ratio than QAOA at the same depth on a collection of MaxCut instances on fifty and one-hundred vertex graphs. Many of the optimized parameters are found to be zero, so their associated gates can be removed from the circuit, further decreasing the circuit depth. These results indicate that multi-angle QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices.

97 MATHEMATICS AND COMPUTING↗

Empirical performance bounds for quantum approximate optimization

The quantum approximate optimization algorithm (QAOA) has been put forth as a method for near-term quantum computers to solve optimization problems. However, assessments of QAOA performance have mostly focused on small structured problem instances while performance on more general instances is less clear. Here, we numerically simulate QAOA pure state dynamics for every instance of MaxCut on non-isomorphic unweighted graphs with nine or fewer vertices with depth parameters p ≤ 3. We find the approximation ratios and optimized circuit parameters concentrate across graphs of a given size and empirically show increases in concentration as graph size increases. The parameter concentration leads to two median-angle heuristics that overcome difficulties in QAOA parameter optimization and obtain mean approximation ratios within 3% and 0.2% of the optimal. We also analyze the probability to measure an optimal solution and find increasing variations between graphs as depth increases, in stark contrast to the approximation ratios which concentrate as depth increases. Furthermore, the resulting benchmark data set gives empirical bounds for on-going experimental realizations and lays groundwork for theoretical extensions to greater problem sizes and depths where QAOA may prove important for practically relevant problems.

79 ASTRONOMY AND ASTROPHYSICS↗

Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems

We develop a global variable substitution method that reduces n-variable monomials in combinatorial optimization problems to equivalent instances with monomials in fewer variables. We apply this technique to 3-SAT and analyze the optimal quantum unitary circuit depth needed to solve the reduced problem using the quantum approximate optimization algorithm. For benchmark 3-SAT problems, we find that the upper bound of the unitary circuit depth is smaller when the problem is formulated as a product and uses the substitution method to decompose gates than when the problem is written in the linear formulation, which requires no decomposition.

3-SAT↗

Impact of graph structures for QAOA on MaxCut

The quantum approximate optimization algorithm (QAOA) is a promising method of solving combinatorial optimization problems using quantum computing. QAOA on the MaxCut problem has been studied extensively on graphs with specific structure; however, little is known about the general performance of the algorithm on arbitrary graphs. Here, we investigate how different graph characteristics correlate with QAOA performance at depths at most three on the MaxCut problem for all connected non-isomorphic graphs with at most eight vertices. Some good predictors of QAOA success relate to graph symmetries, odd cycles, and density. For example, on eight vertex graphs, the average probability for selecting an optimal solution for graphs that contain no odd cycles after three iterations of QAOA is 60.6% compared to 48.2% for those that do. The data generated from these studies are shared in a publicly accessible database to serve as a benchmark for QAOA calculations and experiments. Knowing the relationship between structure and performance can be used to identify classes of combinatorial problems that are likely to exhibit a quantum advantage.

97 MATHEMATICS AND COMPUTING↗

Lower bounds on circuit depth of the quantum approximate optimization algorithm

The quantum approximate optimization algorithm (QAOA) is a method of approximately solving combinatorial optimization problems. While QAOA is developed to solve a broad class of combinatorial optimization problems, it is not clear which classes of problems are best suited for it. One factor in demonstrating quantum advantage is the relationship between a problem instance and the circuit depth required to implement the QAOA method. As errors in noisy intermediate-scale quantum (NISQ) devices increase exponentially with circuit depth, identifying lower bounds on circuit depth can provide insights into when quantum advantage could be feasible. In this work, we identify how the structure of problem instances can be used to identify lower bounds for circuit depth for each iteration of QAOA and examine the relationship between problem structure and the circuit depth for a variety of combinatorial optimization problems including MaxCut and MaxIndSet. Specifically, we show how to derive a graph, G, that describes a general combinatorial optimization problem and show that the depth of circuit is at least the chromatic index of G. By looking at the scaling of circuit depth, we argue that MaxCut, MaxIndSet, and some instances of vertex covering and Boolean satisfiability problems are suitable for QAOA approaches while knapsack and traveling salesperson problems are not.

97 MATHEMATICS AND COMPUTING↗

Continuous-time quantum walks on dynamic graphs

Continuous-time quantum walks (CTQWs) on static graphs provide efficient methods for search and sampling as well as a model for universal quantum computation. We consider an extension of CTQWs to the case of dynamic graphs, in which an ordered sequence of graphs governs free evolution of the quantum walk. We then consider how perfect state transfer during the quantum walk can be used to design dynamic graphs that implement a universal set of quantum logic gates. We give explicit examples for a complete logical basis, and we validate implementations using numerical simulations for quantum teleportation and addition circuits. Lastly, we discuss the potential for realizing CTQWs on dynamic graphs using actively controlled quantum optical waveguides.

96 KNOWLEDGE MANAGEMENT AND PRESERVATION↗