Bulletin of the American Physical Society
APS March Meeting 2022
Volume 67, Number 3
Monday–Friday, March 14–18, 2022; Chicago
Session G36: Quantum Algorithms for OptimizationFocus Recordings Available
|
Hide Abstracts |
Sponsoring Units: DQI Chair: Rebekah Herrman, University of Tennessee Room: McCormick Place W-194A |
Tuesday, March 15, 2022 11:30AM - 11:42AM |
G36.00001: Variational Monte Carlo with Conditional-Value-at-Risk Objective Function Daniel Chen, zain H Saleem, Brajesh K Gupt, Martin Suchara Previous work by Barkoutsos et. al has shown that the convergence of quantum optimization algorithms can be greatly improved by replacing the usual expectation of the Hamiltonian operator with the Conditional-Value-at-Risk (CVar). However, empirical results were only demonstrated on small problem sizes due to limited simulation resources. We propose to simulate the behavior of quantum approximate optimization algorithms for large problem sizes with Variational Monte Carlo, which displays similar theoretical properties with quantum optimization algorithms. We verified that using CVar as the objective function, which considers only a subset of samples queried from the quantum state, generally improves the rate of convergence as well as the quality of the result. Yet, the size of the subset included in the calculation must be treated as an additional hyperparameter and be chosen carefully to ensure maximal performance. |
Tuesday, March 15, 2022 11:42AM - 11:54AM |
G36.00002: Reducing the cost of energy estimation in the Variational Quantum Eigensolver through robust amplitude estimation Peter Johnson, Jerome F Gonthier, Maxwell D Radin, Alex A Kunitsa, Corneliu Buda, Eric Doskocil, Clena Abuan, Jhonathan Romero Quantum computers promise to solve previously intractable problems in chemistry and materials. Recent work proposes to use noisy intermediate-scale quantum devices to achieve quantum advantage in the near future. However, a critical subroutine known as expectation value estimation have proven to be a bottleneck in these approaches. Traditional expectation value estimation in the Variational Quantum Eigensolver (VQE) algorithm proceeds by averaging and is thus plagued by an inverse square dependence on the desired absolute precision. This is a considerable obstacle to quantum chemistry applications, which require a fixed absolute precision regardless of the size of the molecular system considered. Previous work has shown that even with measurement reduction techniques such as grouping and Hamiltonian factorization, the runtime to obtain accurate energies with VQE on idealized devices were impractical, thus compromising near-terms prospects of quantum advantage in quantum chemistry. Here, we investigate how robust amplitude estimation can mitigate this issue by extracting more information with each measurement. We estimate minimum hardware parameters needed to achieve quantum advantage and show numerically a reduction in total runtime as device fidelities improve. |
Tuesday, March 15, 2022 11:54AM - 12:06PM |
G36.00003: Unitary Block Optimization for Variational Quantum Algorithms Lucas Slattery Variational quantum algorithms are a promising hybrid framework for solving chemistry and physics problems with broad applicability to optimization as well. They are particularly well suited for noisy intermediate scale quantum (NISQ) computers. In this paper, we describe the unitary block optimization scheme (UBOS) and apply it to two variational quantum algorithms: the variational quantum eigensolver (VQE) and variational time evolution. The goal of VQE is to optimize a classically intractable parameterized quantum wave function to target a physical state of a Hamiltonian or solve an optimization problem. UBOS is an alternative to other VQE optimization schemes with a number of advantages including fast convergence, less sensitivity to barren plateaus, the ability to tunnel through some local minima and no hyperparameters to tune. We additionally describe how UBOS applies to real and imaginary time-evolution (TUBOS). |
Tuesday, March 15, 2022 12:06PM - 12:42PM |
G36.00004: Quantum error correction in quantum metrology Invited Speaker: Sisi Zhou Quantum metrology, which studies parameter estimation in quantum systems, has many important applications in science and technology, ranging from frequency spectroscopy to gravitational wave detection. Quantum mechanics imposes a fundamental limit on the estimation precision, called the Heisenberg limit, which is achievable in noiseless quantum systems, but is in general not achievable in noisy systems. This talk is a summary of some recent works on quantum metrology enhanced by quantum error correction. We present a necessary and sufficient condition for achieving the Heisenberg limit in noisy quantum systems. When the condition is satisfied, the Heisenberg limit is recovered by a quantum error correction protocol which corrects all noises while maintaining the signal; when it is violated, we show the estimation limit still in general has a constant factor improvement over classical strategies, and is achievable using approximate quantum error correction. Both error correction protocols can be optimized using semidefinite programs. Examples in some typical noisy systems will be provided. |
Tuesday, March 15, 2022 12:42PM - 12:54PM |
G36.00005: Kernel Approximation Based Optimization for Variational Quantum Algorithms Ryan Shaffer, Lucas Kocia, Mohan Sarovar Variational quantum algorithms are a class of techniques intended to be used on near-term quantum computers. The goal of these algorithms is to perform large quantum computations by breaking the problem down into a large number of shallow quantum circuits, complemented by classical optimization and feedback between each circuit execution. One path for improving the performance of these algorithms is to enhance the classical optimization technique. Given the relative ease and abundance of classical computing resources, there is ample opportunity to do so. In this work, we develop a technique for variational parameter optimization by reconstructing local patches of a cost function based on batches of noisy quantum circuit results. We compare this technique to commonly-used optimization techniques for noisy data. We also discuss its convergence properties and applicability to NISQ devices. |
Tuesday, March 15, 2022 12:54PM - 1:06PM |
G36.00006: The multi-angle quantum approximate optimization algorithm Rebekah Herrman The quantum approximate optimization algorithm (QAOA) generates an approximate solution to combinatorial optimization problems. In this presentation, we investigate a multi-angle ansatz for QAOA (ma-QAOA) that reduces circuit depth and improves the approximation ratio by increasing the number of classical parameters. 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 QAOA, 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. It also yields a higher approximation ratio than QAOA at the same depth on a collection of larger MaxCut instances. Many of the optimized parameters are zero, so their associated gates can be removed from the circuit implementation, further decreasing the circuit depth. These results indicate that ma-QAOA requires shallower circuits to solve problems than QAOA, making it more viable for near-term intermediate-scale quantum devices. |
Tuesday, March 15, 2022 1:06PM - 1:18PM |
G36.00007: Quantum Local Search with Quantum Alternating Operator Ansatz zain H Saleem, Martin Suchara, Teague Tomesh We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve large problem instances on quantum devices with few qubits. The quantum local search algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We compare the performance of this algorithm on 3-regular graphs with up to 100 nodes against the well known classical Boppana-Halldorsson algorithm for the Maximum Independent Set problem. |
Tuesday, March 15, 2022 1:18PM - 1:30PM |
G36.00008: The QAOA for MaxCut on dense graphs Kunal Marwaha, Beatrice Nash, Boaz Barak Which quantum algorithms are definitively better than classical algorithms? One candidate is the Quantum Approximate Optimization Algorithm (QAOA), but its performance is not well-understood except in sparse instances, where quantum interference is limited. Here we make a first step at studying the lowest-depth QAOA for MaxCut on dense graphs. We find an analytic expression for the optimal cut fraction on large D-regular graphs in terms of the number of triangles per edge. When the graph is nearly a clique, the QAOA is close to optimal. We discuss our parameterization and compare with local classical algorithms. |
Tuesday, March 15, 2022 1:30PM - 1:42PM |
G36.00009: Transferring variational parameters in QAOA for weighted MaxCut Jeffrey Larson, Ruslan Shaydulin, Jim Ostrowski, Travis S Humble, Phillip C Lotshaw The Quantum Approximate Optimization Algorithm (QAOA) is a leading candidate quantum algorithm for solving combinatorial optimization problems. The quality of the solution returned by QAOA depends critically on the quality of the parameters, typically identified by a classical optimizer. Recent results for the unweighted MaxCut and SK model have shown that pre-optimized parameters can be transferred to unseen instances to avoid costly direct optimization. We extend these results to general weighted MaxCut by showing that parameters can be transferred from easier unweighted MaxCut instances to harder weighted ones. We provide theoretical motivation for our parameter transfer scheme. The transferred parameters are competitive with numerically optimized parameters and are robust for a variety of different weight distributions, including negative weights. |
Tuesday, March 15, 2022 1:42PM - 1:54PM |
G36.00010: Accelerating vehicle routing problems on quantum computers Christopher Bentley, Samuel Marsh, Andre Carvalho, Anurag Mishra, Yuval Baum, Michael Hush, Michael Biercuk Vehicle routing problems (VRPs) are ubiquitous in transport and logistics optimization. Quantum approximate optimization algorithms are well-suited to these classically-hard combinatorial optimization problems, offering potential quantum advantage. However these algorithms should not be naively applied; the details of implementation are critical to the algorithm performance and can provide exponential enhancement. We discuss implementation decisions from the high-level initial problem formulation through to the low-level logic gate design. Judicious choices of the problem encoding, the QAOA classical optimization procedure, and the quantum unitary operators can greatly reduce the search space and enhance optimization performance. Further algorithmic enhancement on noise-susceptible quantum hardware can be achieved through lower-level control: we optimize and replace the quantum gates that constitute the quantum circuit. We present the impact of this end-to-end algorithm design on algorithm performance through simulation and hardware results. |
Tuesday, March 15, 2022 1:54PM - 2:06PM |
G36.00011: Applying quantum approximate optimization to the heterogeneous vehicle routing problem Anton Frisk Kockum, David P Fitzek, Mats Granath, Toheed Ghandriz, Leo Laine Quantum computing offers new heuristics for combinatorial problems. With small- and intermediate-scale quantum devices becoming available, it is possible to implement and test these heuristics on small-size problems. A candidate for such combinatorial problems is the \ac{HVRP}: the problem of finding the optimal set of routes, given a heterogeneous fleet of vehicles with varying loading capacities, to deliver goods to a given set of customers. In this work, we investigate the potential use of a quantum computer to find approximate solutions to the \ac{HVRP} using the quantum approximate optimization algorithm (QAOA). For this purpose we formulate a mapping of the \ac{HVRP} to an Ising Hamiltonian and simulate the algorithm on problem instances of up to 21 qubits. We find that the number of qubits needed for this mapping scales quadratically with the number of customers. We compare the performance of different classical optimizers in the QAOA for varying problem size of the \ac{HVRP}, finding a trade-off between optimizer performance and runtime. |
Tuesday, March 15, 2022 2:06PM - 2:18PM |
G36.00012: Penalty methods for a variational quantum eigensolver Yuya Nakagawa, Kohdai Kuroiwa The variational quantum eigensolver (VQE) is a promising algorithm to compute eigenstates and eigenenergies of a given quantum system that can be performed on a near-term quantum computer. Obtaining eigenstates and eigenenergies in a specific symmetry sector of the system is often necessary for practical applications of the VQE in various fields ranging from high-energy physics to quantum chemistry. It is common to add a penalty term in the cost function of the VQE to calculate such a symmetry-resolving energy spectrum; however, systematic analysis of the effect of the penalty term has been lacking, and the use of the penalty term in the VQE has not been justified rigorously. In this paper, we investigate two major types of penalty terms for the VQE that were proposed in previous studies. We show that a penalty term of one of the two types works properly in that eigenstates obtained by the VQE with the penalty term reside in the desired symmetry sector. We further give a convenient formula to determine the magnitude of the penalty term, which may lead to faster convergence of the VQE. Meanwhile, we prove that the other type of penalty term does not work for obtaining the target state with the desired symmetry in a rigorous sense and even gives completely wrong results in some cases. We finally provide numerical simulations to validate our analysis. Our results apply to general quantum systems and lay the theoretical foundation for the use of the VQE with the penalty terms to obtain the symmetry-resolving energy spectrum of the system, which fuels the application of a near-term quantum computer. |
Tuesday, March 15, 2022 2:18PM - 2:30PM |
G36.00013: Diagrammatic Analysis for Parameterized Quantum Circuits Tobias Stollenwerk, Stuart Hadfield Diagrammatic representations of quantum algorithms and circuits offer novel approaches to their design and analysis. |
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