Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “QAOA”

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 55 records · Page 3
All sourcesNASA NTRSDOE OSTI
DOE OSTI2023

Parameter Transfer for Quantum Approximate Optimization of Weighted MaxCut

Finding high-quality parameters is a central obstacle to using the quantum approximate optimization algorithm (QAOA). Previous work partially addresses this issue for QAOA on unweighted MaxCut problems by leveraging similarities in the objective landscape among different problem instances. However, we show that the more general weighted MaxCut problem has significantly modified objective landscapes, with a proliferation of poor local optima. Our main contribution is a simple rescaling scheme that overcomes these deleterious effects of weights. Here we show that for a given QAOA depth, a single “typical” vector of QAOA parameters can be successfully transferred to weighted MaxCut instances. This transfer leads to a median decrease in the approximation ratio of only 2.0 percentage points relative to a considerably more expensive direct optimization on a dataset of 34,701 instances with up to 20 nodes and multiple weight distributions. This decrease can be reduced to 1.2 percentage points at the cost of only 10 additional QAOA circuit evaluations with parameters sampled from a pretrained metadistribution, or the transferred parameters can be used as a starting point for a single local optimization run to obtain approximation ratios equivalent to those achieved by exhaustive optimization in 96.35% of our cases.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

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

Classical symmetries and the Quantum Approximate Optimization Algorithm

Here, we study the relationship between the Quantum Approximate Optimization Algorithm (QAOA) and the underlying symmetries of the objective function to be optimized. Our approach formalizes the connection between quantum symmetry properties of the QAOA dynamics and the group of classical symmetries of the objective function. The connection is general and includes but is not limited to problems defined on graphs. We show a series of results exploring the connection and highlight examples of hard problem classes where a nontrivial symmetry subgroup can be obtained efficiently. In particular, we show how classical objective function symmetries lead to invariant measurement outcome probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. To illustrate the power of the developed connection, we apply machine learning techniques toward predicting QAOA performance based on symmetry considerations. We provide numerical evidence that a small set of graph symmetry properties suffices to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important setting where QAOA parameter schedules are constrained to be linear and hence easier to optimize.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

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

Data-driven quantum approximate optimization algorithm for power systems

Abstract Quantum technology provides a ground-breaking methodology to tackle challenging computational issues in power systems. It is especially promising for Distributed Energy Resources (DERs) dominant systems that have been widely developed to promote energy sustainability. In those systems, knowing the maximum sections of power and data delivery is essential for monitoring, operation, and control. However, high computational effort is required. By leveraging quantum resources, Quantum Approximate Optimization Algorithm (QAOA) provides a means to search for these sections efficiently. However, QAOA performance relies heavily on critical parameters, especially for weighted graphs. Here we present a data-driven QAOA, which transfers quasi-optimal parameters between weighted graphs based on the normalized graph density. We verify the strategy with 39,774 expectation value calculations. Without parameter optimization, our data-driven QAOA is comparable with the Goemans-Williamson algorithm. This work advances QAOA and pilots its practical application to power systems in noisy intermediate-scale quantum devices.

Jing, Hang (ORCID:0000000256343489)↗
DOE OSTI2025

Analyzing the Quantum Approximate Optimization Algorithm: Ansätze, Symmetries, and Lie Algebras

The quantum approximate optimization algorithm (QAOA) has been proposed as a method to obtain approximate solutions for combinatorial optimization tasks. In this work, we study the underlying algebraic properties of three QAOA ansätze for the maximum-cut problem on connected graphs, while focusing on the generated Lie algebras as well as their invariant subspaces. Specifically, we analyze the standard QAOA ansatz as well as the orbit and multiangle ansätze. We are able to fully characterize the Lie algebras of the multiangle ansatz across arbitrary connected graphs, finding that they only fall into one of just six families. Aside from the cycle and path graphs, the Lie dimensions for every graph are exponentially large in the system size, meaning that multiangle ansätze are extremely prone to exhibiting barren plateaus. Then, a similar quasi-graph-independent Lie-algebraic characterization beyond the multiangle ansatz is impeded as the circuit exhibits additional “hidden” symmetries besides those naturally arising from a certain parity-superselection operator and all automorphisms of the considered graph. Disregarding the “hidden” symmetries, we can upper bound the dimensions of the orbit and the standard Lie algebras, and the dimensions of the associated invariant subspaces are determined via explicit character formulas. To finish, we conjecture that (for most graphs) the standard Lie algebras have only components that are either exponential or that grow, at most, polynomially with the system size. This would imply that the QAOA is either prone to barren plateaus or classically simulable. More generally, our work provides a symmetry framework and tools to analyze any desired variational quantum algorithm.

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

Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator

Quantum computers and simulators may offer significant advantages over their classical counterparts, providing insights into quantum many-body systems and possibly improving performance for solving exponentially hard problems, such as optimization and satisfiability. Here, we report the implementation of a low-depth Quantum Approximate Optimization Algorithm (QAOA) using an analog quantum simulator. We estimate the ground-state energy of the Transverse Field Ising Model with long-range interactions with tunable range, and we optimize the corresponding combinatorial classical problem by sampling the QAOA output with high-fidelity, single-shot, individual qubit measurements. We execute the algorithm with both an exhaustive search and closed-loop optimization of the variational parameters, approximating the ground-state energy with up to 40 trapped-ion qubits. We benchmark the experiment with bootstrapping heuristic methods scaling polynomially with the system size. We observe, in agreement with numerics, that the QAOA performance does not degrade significantly as we scale up the system size and that the runtime is approximately independent from the number of qubits. We finally give a comprehensive analysis of the errors occurring in our system, a crucial step in the path forward toward the application of the QAOA to more general problem instances.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2025

End-to-end protocol for high-quality quantum approximate optimization algorithm parameters with few shots

The quantum approximate optimization algorithm (QAOA) is a quantum heuristic for combinatorial optimization that has been demonstrated to scale better than state-of-the-art classical solvers for some problems. For a given problem instance, QAOA performance depends crucially on the choice of the parameters. While average-case optimal parameters are available in many cases, meaningful performance gains can be obtained by fine-tuning these parameters for a given instance. This task is especially challenging, however, when the number of circuit executions (shots) is limited. In this work, we develop an end-to-end protocol that combines multiple parameter settings and fine-tuning techniques. We use large-scale numerical experiments to optimize the protocol for the shot-limited setting and observe that optimizers with the simplest internal model (linear) perform best. We implement the optimized pipeline on a trapped-ion processor using up to 32 qubits and 5 QAOA layers, and we demonstrate that the pipeline is robust to small amounts of hardware noise. To the best of our knowledge, these are the largest demonstrations of QAOA parameter fine-tuning on a trapped-ion processor in terms of two-qubit gate count.

quantum algorithms & computation↗
DOE OSTI2025

Classical optimization with imaginary-time block encoding on quantum computers: The MaxCut problem

Optimization problems in finance, physics, and computer science are typically very hard to tackle in classical computing; quantum computing could help speed up computations and provide efficient methods for tackling large problems. Typically, to treat a problem with a quantum computer, the optimal solution is cast as the ground state of a diagonal Hamiltonian. Here, we develop a method, called imaginary-time evolution block encoding (ITE-BE), based on a recent imaginary-time algorithm, which requires no variational parameter optimization, as all parameters can be derived analytically from the target Hamiltonian. We also demonstrate that our method can be successfully combined with other quantum algorithms such as the quantum approximate optimization algorithm (QAOA). For illustration, here we study the MaxCut problem. We find that the QAOA ansatz increases the postselection success of ITE-BE, and shallow QAOA circuits, when boosted with ITE-BE, achieve better performance than deeper QAOA circuits. For the special case of the transverse initial state, we adapt our block-encoding scheme to allow for a deterministic application of the first layer of the circuit.

Zhong, Dawei [University of Southern California, L↗
DOE OSTI2022

Dual-map framework for noise characterization of quantum computers

In order to understand the capabilities and limitations of quantum computers, it is necessary to develop methods that efficiently characterize and benchmark error channels present on these devices. In this paper, we present a method that faithfully reconstructs a marginal (local) approximation of the effective noise (MATEN) channel, that acts as a single layer at the end of the circuit. We first introduce a dual-map framework that allows us to analytically derive expectation values of observables with respect to noisy circuits. These findings are supported by numerical simulations of the quantum approximate optimization algorithm (QAOA) that also justify the MATEN, even in the presence of nonlocal errors that occur during a circuit. Finally, we demonstrate the performance of the method on Rigetti's Aspen-11 quantum computer for QAOA circuits up to six qubits, successfully predicting the observed measurements on a majority of the qubits.

Sud, James↗
DOE OSTI2024

Efficient quantum circuits based on the quantum natural gradient

Efficient preparation of arbitrary entangled quantum states is crucial for quantum computation. This is particularly important for noisy intermediate-scale quantum simulators relying on variational hybrid quantum-classical algorithms. To that end, we propose symmetry-conserving modified quantum approximate optimization algorithm (SCom-QAOA) circuits. The depths of these circuits depend not only on the desired fidelity to the target state but also on the amount of entanglement the state contains. The parameters of the SCom-QAOA circuits are optimized using the quantum natural gradient method based on the Fubini-Study metric. The SCom-QAOA circuit transforms an unentangled state into a ground state of a gapped one-dimensional Hamiltonian with a circuit depth that depends not on the system size but rather on the finite correlation length. In contrast, the circuit depth grows proportionally to the system size for preparing low-lying states of critical one-dimensional systems. Even in the latter case, SCom-QAOA circuits with depth less than the system size were sufficient to generate states with fidelity in excess of 99%, which is relevant for near-term applications. The proposed scheme enlarges the set of the initial states accessible for variational quantum algorithms and widens the scope of investigation of nonequilibrium phenomena in quantum simulators. Published by the American Physical Society 2024

75 CONDENSED MATTER PHYSICS, SUPERCONDUCTIVITY AND↗
DOE OSTI2022

Hybrid quantum-classical algorithms for approximate graph coloring

We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX- k -CUT, the problem of finding an approximate k -vertex coloring of a graph. We compare this proposal to the best known classical and hybrid classical-quantum algorithms. First, we show that the standard (non-recursive) QAOA fails to solve this optimization problem for most regular bipartite graphs at any constant level p : the approximation ratio achieved by QAOA is hardly better than assigning colors to vertices at random. Second, we construct an efficient classical simulation algorithm which simulates level- 1 QAOA and level- 1 RQAOA for arbitrary graphs. In particular, these hybrid algorithms give rise to efficient classical algorithms, and no benefit arising from the use of quantum mechanics is to be expected. Nevertheless, they provide a suitable testbed for assessing the potential benefit of hybrid algorithm: We use the simulation algorithm to perform large-scale simulation of level- 1 QAOA and RQAOA with up to 300 qutrits applied to ensembles of randomly generated 3 -colorable constant-degree graphs. We find that level- 1 RQAOA is surprisingly competitive: for the ensembles considered, its approximation ratios are often higher than those achieved by the best known generic classical algorithm based on rounding an SDP relaxation. This suggests the intriguing possibility that higher-level RQAOA may be a potentially useful algorithm for NISQ devices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2021

Coreset Clustering on Small Quantum Computers

Many quantum algorithms for machine learning require access to classical data in superposition. However, for many natural data sets and algorithms, the overhead required to load the data set in superposition can erase any potential quantum speedup over classical algorithms. Recent work by Harrow introduces a new paradigm in hybrid quantum-classical computing to address this issue, relying on coresets to minimize the data loading overhead of quantum algorithms. We investigated using this paradigm to perform k-means clustering on near-term quantum computers, by casting it as a QAOA optimization instance over a small coreset. We used numerical simulations to compare the performance of this approach to classical k-means clustering. We were able to find data sets with which coresets work well relative to random sampling and where QAOA could potentially outperform standard k-means on a coreset. However, finding data sets where both coresets and QAOA work well—which is necessary for a quantum advantage over k-means on the entire data set—appears to be challenging.

42 ENGINEERING↗
DOE OSTI2026

Distributed quantum approximate optimization algorithm on a quantum-centric supercomputing architecture

Quantum approximate optimization algorithm (QAOA) has shown promise in solving combinatorial optimization problems by providing quantum speedup on near-term gate-based quantum computing systems. However, QAOA faces challenges for high-dimensional problems due to the large number of qubits required and the complexity of deep circuits, limiting its scalability for real-world applications. In this study, we present a distributed QAOA (DQAOA), which leverages distributed computing strategies to decompose a large computational workload into smaller tasks that require fewer qubits and shallower circuits than are necessary to solve the original problem. These sub-problems are processed using a combination of high-performance and quantum computing resources. The global solution is iteratively updated by aggregating sub-solutions, allowing convergence toward the optimal solution. We demonstrate that DQAOA can handle considerably large-scale optimization problems (e.g., 1000-bit problem), achieving a high solution quality and short time-to-solution, outperforming existing strategies. Furthermore, we realize DQAOA on a quantum-centric supercomputing architecture, paving the way for practical applications of gate-based quantum computers in real-world optimization tasks. To extend DQAOA’s applicability to materials science, we further develop an active learning algorithm integrated with our DQAOA (AL-DQAOA), which involves machine learning, DQAOA, and active data production in an iterative loop. We successfully optimize photonic structures using AL-DQAOA, indicating that solving real-world optimization problems using gate-based quantum computing is feasible. We expect the proposed DQAOA to be applicable to a wide range of optimization problems and AL-DQAOA to find broader applications in material design.

Kim, Seongmin [ORNL] (ORCID:0000000159063004)↗
DOE OSTI2022

Constrained quantum optimization for extractive summarization on a trapped-ion quantum computer

Abstract Realizing the potential of near-term quantum computers to solve industry-relevant constrained-optimization problems is a promising path to quantum advantage. In this work, we consider the extractive summarization constrained-optimization problem and demonstrate the largest-to-date execution of a quantum optimization algorithm that natively preserves constraints on quantum hardware. We report results with the Quantum Alternating Operator Ansatz algorithm with a Hamming-weight-preserving XY mixer (XY-QAOA) on trapped-ion quantum computer. We successfully execute XY-QAOA circuits that restrict the quantum evolution to the in-constraint subspace, using up to 20 qubits and a two-qubit gate depth of up to 159. We demonstrate the necessity of directly encoding the constraints into the quantum circuit by showing the trade-off between the in-constraint probability and the quality of the solution that is implicit if unconstrained quantum optimization methods are used. We show that this trade-off makes choosing good parameters difficult in general. We compare XY-QAOA to the Layer Variational Quantum Eigensolver algorithm, which has a highly expressive constant-depth circuit, and the Quantum Approximate Optimization Algorithm. We discuss the respective trade-offs of the algorithms and implications for their execution on near-term quantum hardware.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2022

Simulations of frustrated Ising Hamiltonians using quantum approximate optimization

Novel magnetic materials are important for future technological advances. Theoretical and numerical calculations of ground-state properties are essential in understanding these materials, however, computational complexity limits conventional methods for studying these states. Here we investigate an alternative approach to preparing materials ground states using the quantum approximate optimization algorithm (QAOA) on near-term quantum computers. We study classical Ising spin models on unit cells of square, Shastry-Sutherland and triangular lattices, with varying field amplitudes and couplings in the material Hamiltonian. We find relationships between the theoretical QAOA success probability and the structure of the ground state, indicating that only a modest number of measurements (≲100) are needed to find the ground state of our nine-spin Hamiltonians, even for parameters leading to frustrated magnetism. We further demonstrate the approach in calculations on a trapped-ion quantum computer and succeed in recovering each ground state of the Shastry-Sutherland unit cell with probabilities close to ideal theoretical values. The results demonstrate the viability of QAOA for materials ground state preparation in the frustrated Ising limit, giving important first steps towards larger sizes and more complex Hamiltonians where quantum computational advantage may prove essential in developing a systematic understanding of novel materials.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Fixed-angle conjectures for the quantum approximate optimization algorithm on regular MaxCut graphs

The quantum approximate optimization algorithm (QAOA) is a near-term combinatorial optimization algorithm suitable for noisy quantum devices. However, little is known about performance guarantees for p > 2. A recent work computing MaxCut performance guarantees for 3-regular graphs conjectures that any d-regular graph evaluated at particular fixed angles has an approximation ratio greater than some worst-case guarantee. In this work, we provide numerical evidence for this fixed angle conjecture for p < 12. We compute and provide these angles via numerical optimization and tensor networks. These fixed angles serve for an optimization-free version of QAOA and have universally good performance on any 3-regular graph. Heuristic evidence is presented for the fixed angle conjecture on graph ensembles, which suggests that these fixed angles are "close" to global optimum. Under the fixed angle conjecture, QAOA has a larger performance guarantee than the Goemans Williamson algorithm on 3-regular graphs for p >= 11.

Wurtz, Jonathan↗