Bulletin of the American Physical Society
APS March Meeting 2022
Volume 67, Number 3
Monday–Friday, March 14–18, 2022; Chicago
Session F38: Quantum Annealing and Optimization IFocus Recordings Available
|
Hide Abstracts |
Sponsoring Units: DQI Chair: Davide Venturelli, NASA Room: McCormick Place W-195 |
Tuesday, March 15, 2022 8:00AM - 8:12AM |
F38.00001: Non-Convex Optimization by Hamiltonian Alternation Anuj Apte, Arvind Murugan, Kunal Marwaha A major obstacle to non-convex optimization is the problem of getting stuck in local minima. Widely used gradient-based optimization algorithms such as stochastic gradient descent (SGD), simulated annealing, and variational quantum algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) all face this difficulty. We introduce a novel approach to non-convex optimization using an engineered alternative Hamiltonian which shares a single minimum with the original Hamiltonian. For any given algorithm, alternating between the two Hamiltonians allows one to escape local minima. This technique is particularly useful when the energy of the target state is known, but one obtains an improvement even without this knowledge. We illustrate this idea by applying it to the problems of finding the ground state of the Sherrington-Kirkpatrick model of a spin glass, and the QAOA for the transverse-field Ising model. |
Tuesday, March 15, 2022 8:12AM - 8:24AM |
F38.00002: Progress toward favorable landscapes in quantum combinatorial optimization Christian Arenz, Herschel Rabitz, Juneseo Lee, Alicia Magann The performance of variational quantum algorithms relies on the success of using quantum and classical computing resources in tandem. Here, we study how these quantum and classical components interrelate. In particular, we focus on algorithms for solving the combinatorial optimization problem MaxCut, and study how the structure of the classical optimization landscape relates to the quantum circuit used to evaluate the MaxCut objective function. In order to analytically characterize the impact of quantum features on the critical points of the landscape, we consider a family of quantum circuit ansaetze composed of mutually commuting elements. We identify multiqubit operations as a key resource and show that overparameterization allows for obtaining favorable landscapes. Namely, we prove that an ansatz from this family containing exponentially many variational parameters yields a landscape free of local optima for generic graphs. However, we further prove that these ansa¨tze do not offer superpolynomial advantages over purely classical MaxCut algorithms. We then present a series of numerical experiments illustrating that noncommutativity and entanglement are important features for improving algorithm performance. |
Tuesday, March 15, 2022 8:24AM - 8:36AM |
F38.00003: The Quantum Approximate Optimization Algorithm at High Depth for MaxCut on Large-Girth Regular Graphs and the Sherrington-Kirkpatrick Model Joao Basso, Edward Farhi, Kunal Marwaha, Benjamin Villalonga, Leo Zhou The Quantum Approximate Optimization Algorithm (QAOA) finds approximate solutions to combinatorial optimization problems. Its performance monotonically improves with its depth p. We apply the QAOA to MaxCut on large-girth D-regular graphs. We give an iterative formula to evaluate performance for any D at any depth p. Looking at random D-regular graphs, at optimal parameters and as D goes to infinity, we find that the p = 11 QAOA beats all classical algorithms (known to the authors) that are free of unproven conjectures. While the iterative formula for these D-regular graphs is derived by looking at a single tree subgraph, we prove that it also gives the ensembleaveraged performance of the QAOA on the Sherrington-Kirkpatrick (SK) model. Our iteration is a compact procedure, but its computational complexity grows as O(p2 4p). This iteration is more efficient than the previous procedure for analyzing QAOA performance on the SK model, and we are able to numerically go to p = 20. Encouraged by our findings, we make the optimistic conjecture that the QAOA, as p goes to infinity, will achieve the Parisi value. We analyze the performance of the quantum algorithm, but one needs to run it on a quantum computer to produce a string with the guaranteed performance. |
Tuesday, March 15, 2022 8:36AM - 9:12AM |
F38.00004: Optimal Protocols in Quantum Annealing and Quantum Approximate Optimization Algorithm Problems Invited Speaker: Lucas T Brady Quantum computers seek to use the power of quantum mechanics to solve computational tasks in ways fundamentally different from those of classical computers. Quantum advantage has already been demonstrated experimentally, but it remains to be seen what useful applications are possible on small, noisy near-term quantum computers. Analog quantum algorithms provide one possible route to such near-term utility since they have some inherent noise-resistance and are workable on small devices. Quantum Annealing (QA), Quantum Adiabatic Optimization (QAO), and the Quantum Approximate Optimization Algorithm (QAOA) all form a class of analog quantum algorithms where the system is switched between two configurations or Hamiltonians in order to steer the state of the system into a desired target. Which algorithm is more effective has remained unclear. We apply the framework of optimal control theory to derive the form of the optimal annealing procedure. Furthermore, we connect the form of this optimal procedure back to QAO and QAOA, showing that in the limit of short times, the optimal procedure is well approximated by QAOA. In the long time limit, this optimal procedure begins to look locally adiabatic, with a form similar to an optimized annealing schedule. |
Tuesday, March 15, 2022 9:12AM - 9:24AM |
F38.00005: Benchmarking the Operation of Quantum Heuristics and Ising Machines: Scoring Parameter Setting Strategies on Real World Optimization Applications David E Bernal Neira, Davide Venturelli, Filip A Wudarski, Eleanor G Rieffel We discuss guidelines for the performance evaluation of parameterized stochastic solvers of optimization problems, with particular attention to systems that employ quantum or unconventional processors, such as QAOA, Quantum Annealing, or Coherent Ising Machines. We illustrate through an example a benchmarking procedure grounded in the statistical analysis of the expectation of a given performance metric outside a test environment, taking into account all resources related to real-world deployment. |
Tuesday, March 15, 2022 9:24AM - 9:36AM |
F38.00006: Quantum annealing correction with over 1,000 logical qubits Humberto Munoz-Bauza, Evgeny Mozgunov, Daniel A Lidar The scalability of quantum processors depends critically on techniques to suppress and correct errors arising from decoherence and analog control. The large size and connectivity of the latest generation of quantum annealers gives ample opportunity to dedicate qubit resources to robust and practical quantum error suppression schemes even for complex optimization and sampling problems. We propose an embedding of the quantum annealing correction (QAC) method on the topology of the D-Wave Advantage device that yields up to 1,300 error-corrected qubits, with the vast majority having a degree of 5. QAC outperforms unprotected quantum annealing in time-to-solution while also being effective for sampling low temperature states. We evaluate sampling capabilities with a time-to-epsilon metric relative to the ground state and compare the scaling with parallel tempering. |
Tuesday, March 15, 2022 9:36AM - 9:48AM |
F38.00007: Predicting Transferability of Optimal Parameters of Quantum Approximate Optimization Algorithm Eesh A Gupta, Alexey Galda, Xiaoyuan Liu, Danylo Lykov, Yuri Alexeev, Ilya Safro Hybrid quantum-classical algorithms such as the Quantum Approximate Optimization Algorithm (QAOA) have great potential for demonstrating quantum advantage. QAOA relies on the optimization of classical parameters to find the minimum energy solution. Various techniques have been proposed to avoid the direct optimization of parameters for a given instance to speed up calculations. One of the promising techniques is transferring or reusing optimal parameters of similar QAOA instances. However, defining and computing such transferability remains a challenge. In this work, we developed multiple similarity metrics that predict the transferability of optimal parameters between QAOA MaxCut instances. In these metrics, we used the parity of a graph's node degrees as well as the transferability coefficients of its constituent subgraphs. When applied to a diverse dataset of 20-node random graphs, our similarity metrics successfully predict transferability coefficients within a mean squared error of 0.0042. These metrics also explain our earlier demonstrations of successfully transferring optimal parameters of 6 node random graphs to 64 node random graphs. These findings present a pathway to use local properties of instances to speed up QAOA and other hybrid quantum-classical algorithms. |
Tuesday, March 15, 2022 9:48AM - 10:00AM |
F38.00008: Mean-Field QAOA: A quantum inspired classical optimization algorithm Peter K Schuhmacher, Tobias Stollenwerk, Tim Bode, Dmitry Bagrets, Aditi Misra-Spieldenner, Frank K Wilhelm We would like to understand speedup for QAOA and see for what kind of problems QAOA can benefficiently approximated. For this goal, we have developed a mean-field type approach called Mean Field QAOA (MF-QAOA) in which each qubit is represented by its three spin projections. MF-QAOA mimics the classical trajectory of the time-evolution generated by QAOA. We benchmark the performance of MF-QAOA against its quantum counterpart on different standard optimization problems like graph coloring. |
Tuesday, March 15, 2022 10:00AM - 10:12AM |
F38.00009: Identification of driver genes for severe respiratory response to COVID-19 via a Quantum Support Vector Machine Razieh Mohseninia, Daniel A Lidar A Quantum Support Vector Machine (qSVM) is a quantum adaptation of the classical SVM that can be used for classification designed to be run with a quantum annealer (QA) [1]. In this work we implement a qSVM algorithm on the genomic information samples of ~100 young patients with confirmed COVID19, which are classified into three groups: 1) Healthy control, 2) Oxygen: those that need oxygen, and 3) ARDS: Acute Respiratory Distress Syndrome. The computational task is to classify the data as Healthy control vs ARDS patients or Oxygen vs ARDS. Since the QA samples from the quantum distribution, it retains both the lowest energy solution and some of the next lowest-energy solutions. Because of the suboptimal solutions, we expect qSVM to perform worse on the training data than cSVM. However, suboptimal solutions can generate different decision boundaries. As such, a suitable combination of the suboptimal solutions in qSVM might outperform cSVM on the test data. We demonstrate an improved classification performance for qSVM over cSVM on some test data sets, where the optimal solution of qSVM contains both the lowest energy and some of the excited states solutions. We also use the most informative features of different classifiers as input for structural causal modeling to identify potential driver genes for a severe respiratory response. This identified ADAM9 as the key driver gene, which was experimentally validated [2]. |
Tuesday, March 15, 2022 10:12AM - 10:24AM |
F38.00010: Energy Extrapolation in Quantum Optimization Algorithms Chenfeng Cao, Yunlong Yu, Zipeng Wu, Nic Shannon, Bei Zeng, Robert J Joynt Quantum annealing and the variational quantum eigensolver are two promising quantum algorithms to find the ground state of a target Hamiltonian on near-term quantum devices. However, it is necessary to limit the evolution time or the circuit depth as much as possible since otherwise decoherence will degrade the computation. Even when this is done, there always exists a non-negligible estimation error in the ground state energy. Here we propose a scalable extrapolation approach to mitigate this error. With an appropriate regression, we can significantly improve the estimation accuracy for quantum annealing and variational quantum eigensolver for fixed quantum resources. The inference is achieved by extrapolating the annealing time to infinity or extrapolating the variance to zero. The only additional overhead is an increase in the number of measurements by a constant factor. We verified the validity of our method with the transverse-field Ising model. The method is robust to noise, and the techniques are applicable to other physics problems. Analytic derivations for the quadratic convergence feature of the residual energy in quantum annealing and the linear convergence feature of energy variance are given. |
Tuesday, March 15, 2022 10:24AM - 10:36AM |
F38.00011: Steered quantum annealing: improving time efficiency with partial information Ana Palacios, Marta P Estarellas, Artur Garcia-Saez In the computational model of quantum annealing, the size of the minimum gap between the ground state and the first excited state of the system is of particular importance, since it is inversely proportional to the running time of the algorithm. Thus, it is desirable to keep the gap as large as possible during the annealing process, since it allows the computation to remain under the protection of the adiabatic theorem while staying efficient. We propose steered quantum annealing as a new method to enlarge the gap throughout the process, in the case of diagonal final Hamiltonians, based on the exploitation of some assumptions we can make about the particular problem instance. In order to introduce this information, we propose beginning the anneal from a biased Hamiltonian that incorporates reliable assumptions about the final ground state. Our simulations show that this method yields a larger average gap throughout the whole computation, which further highlights the increase in robustness of the latter. |
Tuesday, March 15, 2022 10:36AM - 10:48AM |
F38.00012: Diversity measure for discrete optimization: Sampling rare solutions via algorithmic quantum annealing Marek M Rams, Masoud Mohseni, Sergei V Isakov, Daniel K Eppens, Susanne Pielawa, Johan Strumpfer, Sergio Boixo, Hartmut Neven Sampling a diverse set of high-quality solutions for hard optimization problems is of great practical relevance in many scientific disciplines and applications, such as artificial intelligence and operations research. One of the main open problems is the lack of ergodicity, or mode collapse, for typical stochastic solvers based on Monte Carlo techniques leading to poor generalization or lack of robustness to uncertainties. Currently, there is no universal metric to quantify such performance deficiencies across various solvers. Here, we introduce a new diversity measure for quantifying the number of independent approximate solutions for NP-hard optimization problems. |
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