Bulletin of the American Physical Society
APS March Meeting 2021
Volume 66, Number 1
Monday–Friday, March 15–19, 2021; Virtual; Time Zone: Central Daylight Time, USA
Session L34: Quantum Annealing and Optimization IIILive
|
Hide Abstracts |
Sponsoring Units: DQI Chair: Ryan LaRose, Michigan State University |
Wednesday, March 17, 2021 8:00AM - 8:12AM Live |
L34.00001: Analytical framework for Quantum Alternating Operator Ansätze Stuart Hadfield, Tad Hogg, Eleanor G Rieffel We develop a framework for analyzing quantum alternating operator ansätze circuits, in particular the quantum approximate optimization algorithm (QAOA). Our framework relates quantum cost gradient operators, derived from the cost and mixing Hamiltonians, to classical cost difference functions that reflect cost function neighborhood structure. For QAOA we show exact series expansions in the algorithm parameters and cost gradient operators, which enable novel insight and analysis in different parameter regimes. For single-layer QAOA-1 we show that leading-order changes in the solution probabilities and cost expectation value are determined by cost differences; for sufficiently small positive parameters probability provably flows from lower to higher cost states on average. We further show a classical random algorithm emulating QAOA-1 in the small-parameter regime, i.e., that samples with the same probabilities up to small error. Our results are general and apply under minimal cost function assumptions. For deeper QAOA-p circuits we derive analogous results in several settings. We outline applications of our framework to performance analysis, parameter setting, and design of more effective QAOA mixing operators. |
Wednesday, March 17, 2021 8:12AM - 8:24AM Live |
L34.00002: Classical symmetries and QAOA Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, Ilya Safro We study the relationship between the quantum approximate optimization algorithm (QAOA) and the classical symmetries of the problem cost function to be optimized. Our approach formalizes the connection between (i) symmetry properties of the QAOA dynamics and (ii) the group of symmetries of the cost 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. We show how classical cost function symmetries lead to invariant measurement probabilities across states connected by such symmetries, independent of the choice of algorithm parameters or number of layers. We provide an illustrative application of the developed connection by using symmetry properties of graphs as features in a machine learning model used to predict the minimum QAOA depth required to achieve a target approximation ratio on the MaxCut problem, in a practically important and well-studied setting where QAOA schedules are constrained to be linear and hence easier to optimize. |
Wednesday, March 17, 2021 8:24AM - 8:36AM Live |
L34.00003: Empirical performance bounds for quantum approximate optimization Phillip Charles Lotshaw, Travis S Humble, Rebekah Herrman, James Ostrowski The quantum approximate optimization algorithm (QAOA) is a promising application for near-term intermediate-scale quantum (NISQ) computers to solve combinatorial optimization problems. However, it is unclear how QAOA performance varies for different problem instances corresponding to different graphs. We numerically simulated pure-state QAOA on the MaxCut problem for instances on every connected non-isomorphic graph with nine or fewer vertices with up to three layers of QAOA unitary operations. We find the expectation values for the approximation ratios are not very sensitive to graph structure, with distributions over the sets of graphs that narrow as the number of QAOA layers increases. In contrast, the probability of obtaining the optimal result from QAOA is much more sensitive to graph structure, with distributions over different graphs that widen with additional QAOA layers. The results provide performance bounds for NISQ computers and suggest future directions for using relationships between graph structure and performance to identify specific types of problems that are best suited for QAOA. |
Wednesday, March 17, 2021 8:36AM - 8:48AM Live |
L34.00004: Quantifying the efficiency of state preparation via quantum variational eigensolvers Gabriel Matos, Sonika Johri, Zlatko Papic Recently, there has been much interest in the efficient preparation of complex quantum states using low-depth quantum circuits, such as Quantum Approximate Optimization Algorithm (QAOA). While it has been numerically shown that such algorithms prepare certain correlated states of quantum spins with surprising accuracy, a systematic way of quantifying the efficiency of QAOA in general classes of models has been lacking. Here, we propose that the success of QAOA in preparing ordered states is related to the interaction distance of the target state, which measures how close that state is to the manifold of all Gaussian states in an arbitrary basis of single-particle modes. We numerically verify this for the ground state of the quantum Ising model with arbitrary transverse and longitudinal field strengths, a canonical example of a non-integrable model. Our results suggest that the structure of the entanglement spectrum, as witnessed by the interaction distance, correlates with the success of QAOA state preparation. We conclude that QAOA typically finds a solution that perturbs around the closest free-fermion state. |
Wednesday, March 17, 2021 8:48AM - 9:00AM Live |
L34.00005: Lyapunov control-inspired protocol for quantum approximate optimization Alicia Magann, Kenneth Rudinger, Matthew Grace, Mohan Sarovar It is widely hoped that quantum devices will be able to solve practical problems in the near future. One potential path for realizing this is via the quantum approximate optimization algorithm, which seeks an approximate solution to an optimization problem by encoding it in the ground state of an Ising problem Hamiltonian. A classical processor is then used to optimize a set of coefficients parameterizing a relatively-shallow quantum circuit in order to drive the qubits to the problem Hamiltonian’s ground state. However, the success of this approach hinges on the performance of the classical optimizer, which depends on numerous factors. In this talk, we introduce an alternate strategy based on Lyapunov control that offers a deterministic, constructive protocol for assigning values to the quantum circuit parameters, such that the problem Hamiltonian's expectation value decreases layer-by-layer. The parameter values are assigned sequentially as a function per layer of measurement information, eliminating the need for any classical optimization. Numerical analyses are presented that investigate the utility of this Lyapunov control-inspired protocol towards the MaxCut problem. |
Wednesday, March 17, 2021 9:00AM - 9:12AM Live |
L34.00006: Warm-starting quantum optimization Daniel Egger, Jakub Marecek, Stefan Woerner There is an increasing interest in quantum algorithms for problems of combinatorial optimization. Classical solvers for such problems employ relaxations, which replace binary variables with continuous ones, for instance in the form of higher-dimensional matrix-valued problems (semidefinite programming). Under the Unique Games Conjecture, these relaxations often provide the best approximation ratios available classically in polynomial time. Here, we discuss how to warm-start quantum optimization with an initial state corresponding to the solution of a relaxation of a combinatorial optimization problem and how to analyze properties of the associated quantum algorithms. Considering that the Unique Games Conjecture is not valid when there are entangled provers, warm-starting quantum algorithms may allow for an improvement over classical algorithms. We illustrate this in the context of portfolio optimization, where our results indicate that warm-starting the QAOA is particularly beneficial at low depth. Likewise, Recursive QAOA for MAXCUT problems shows a systematic increase in the size of the obtained cut for fully connected graphs with random weights, when Goemans-Williamson randomized rounding is utilized in a warm start. |
Wednesday, March 17, 2021 9:12AM - 9:24AM Live |
L34.00007: Constrained Quantum Annealing for Circuit Fault Diagnosis Hannes Leipold, Federico Maximiliano Spedalieri We present a very general construction for quantum annealing protocols for solving Circuit Fault Diagnosis (CFD) problems that restrict the evolution to the feasible space of solutions using all local driver terms. We demonstrate the usefulness of our approach through simulations to show how our construction could be advantageous for near term quantum systems designed to tackle smaller scale CFD problems. Our approach also can be translated to the Quantum Approximate Optimization Algorithm (QAOA) framework, where the driver terms act as the mixing operators that explore only the space of feasible configurations, rather than the whole space. |
Wednesday, March 17, 2021 9:24AM - 9:36AM Live |
L34.00008: Towards Quantum Gate-Model Heuristics for Real-World Planning Problems Tobias Stollenwerk, Stuart Hadfield, Zhihui Wang Many challenging scheduling, planning, and resource allocation problems come with real-world input data and hard problem constraints, and reduce to optimizing a cost function over a combinatorially-defined feasible set, such as colorings of a graph. Towards tackling such problems with quantum computers using quantum approximate optimization algorithms, |
Wednesday, March 17, 2021 9:36AM - 9:48AM Live |
L34.00009: Impact of Graph Structure for QAOA Performance on MaxCut Rebekah Herrman, Lorna Treffert, James Ostrowski, Phillip Charles Lotshaw, Travis S Humble, George Siopsis 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 specific families of regular graphs but little is known about the algorithm on arbitrary ones. The lack of comprehensive study may hide insight on QAOA performance. We evaluate the performance of QAOA at depths one, two, and three on the MaxCut problem for all graphs with at most eight vertices and analyze how graph structure affects QAOA. To do this, we examine correlations between graph properties and metrics associated with QAOA performance. We find that the number of edges and clique number have a strong positive correlation to the expected value of the cost operator C while diameter and number of cut vertices have strong negative correlations. Interestingly, while group size and the number of orbits are closely related, the number of orbits tends to correlate better with the expected value and a quantity we call the gap. Knowing how graph structure positively or negatively impacts performance can allow us to identify classes of combinatorial problems that are likely to exhibit a quantum advantage. |
Wednesday, March 17, 2021 9:48AM - 10:00AM Live |
L34.00010: Improving the Performance of Quantum Approximate Optimization Algorithm Through an Adaptive, Problem-Tailored Ansatz Linghua Zhu, Ho Lun Tang, George S Barron, Fernando. A. Calderon-Vargas, Nicholas J. Mayhall, Edwin Barnes, Sophia Economou The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves combinatorial optimization problems. While there is evidence suggesting that the fixed form of the original QAOA ansatz is not optimal, there is no systematic approach for finding better ansatze. We address this problem by introducing a new method for creating wavefunction ansätze iteratively in a way that is tailored to the problem being solved and, if desired, to the quantum hardware it is being solved on. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the original QAOA, while simultaneously reducing the required number of CNOT gates and optimization parameters. |
Wednesday, March 17, 2021 10:00AM - 10:12AM Live |
L34.00011: Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem: part 1 Pontus Vikstål, Mattias Grönkvist, Marika Svensson, Martin Andersson, Göran Johansson, Giulia Ferrini Noisy intermediate-scale quantum (NISQ) devices, composed of a few tenths of qubits are now starting to become available. They have been shown to be able to perform some tasks that are hard to replicate on a supercomputer. However, these tasks have not been linked yet with the solution of useful problems. A relevant question is therefore whether NISQs devices can also solve real-world problems. In this work, we study numerically the solution of an airline optimization problem, namely the Tail-Assignment problem (TAS), on near-term quantum processors composed of up to 25 qubits, by using the quantum approximate optimization algorithm (QAOA). |
Wednesday, March 17, 2021 10:12AM - 10:24AM Live |
L34.00012: Applying the Quantum Approximate Optimization Algorithm to the Tail Assignment Problem: part 2 Marika Svensson, Martin Andersson, Mattias Grönkvist, Pontus Vikstål, Devdatt Dubhashi, Giulia Ferrini, Göran Johansson We investigate the Quantum Approximate Optimization Algorithm (QAOA) applied to the Exact Cover and Set Partitioning problem with multiple feasible solutions. The problem instances have been extracted from real world aircraft assignment problems. For the Exact Cover problem our numerical results indicate that for a given success probability of finding a feasible solution the required algorithm depth decreases with the number of feasible solutions. For the Set Partitioning problem on the other hand, we find that for a given success probability of finding the optimal solution the required algorithm depth can increase with the number of feasible solutions, which in the worst case is exponential in the problem size. We also address the importance of properly weighting the objective and constraint parts of the Hamiltonian when solving the Set Partitioning problem since these weights have a significant impact on the QAOA performance. |
Wednesday, March 17, 2021 10:24AM - 10:36AM On Demand |
L34.00013: Low depth mechanisms for quantum optimization Jarrod McClean, Matthew Harrigan, Masoud Mohseni, Nicholas Rubin, Zhang Jiang, Sergio Boixo, Vadim Smelyanskiy, Ryan Babbush, Hartmut Neven One of the major application areas of interest for both near-term and fault-tolerant quantum computers is the optimization of classical objective functions. In this work, we develop intuitive constructions for a large class of these algorithms based on connections to simple dynamics of quantum systems, quantum walks, and classical continuous relaxations. We focus on developing a language and tools connected with kinetic energy on a graph for understanding the physical mechanisms of success and failure to guide algorithmic improvement. Connections to classical methods of continuous extensions, homotopy methods, and iterated rounding suggest new directions for research in quantum optimization. Throughout, we unveil many pitfalls and mechanisms in quantum optimization using a physical perspective, which aim to spur the development of novel quantum optimization algorithms and refinements. |
Wednesday, March 17, 2021 10:36AM - 10:48AM Not Participating |
L34.00014: Efficient analytic construction of quantum circuits for MaxCut problems Taichi Kosugi, Hirofumi Nishi, Yu-ichiro Matsushita For performing various algorithms on current and near-future quantum computers, it is crucial to find systematically efficent ways to construct quantum circuits. It is mathematically known that an arbitrary unitary for a multiple-qubit system can be represented as a combination of at most two-qubit unitaries. For the quantum imaginary-time evolution method[1, 2] for MaxCut problems, we derive the conditions imposed on the gate parameters, from which they can be calculated analytically. We demonstrate that the expected energy exhibits numerically stable behavior both in noiseless and noiseful simulations. |
Follow Us |
Engage
Become an APS Member |
My APS
Renew Membership |
Information for |
About APSThe American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics. |
© 2024 American Physical Society
| All rights reserved | Terms of Use
| Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 20740-3844
(301) 209-3200
Editorial Office
100 Motor Pkwy, Suite 110, Hauppauge, NY 11788
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700