Bulletin of the American Physical Society
APS March Meeting 2019
Volume 64, Number 2
Monday–Friday, March 4–8, 2019; Boston, Massachusetts
Session L42: Quantum Annealing: Algorithms and ApplicationsFocus
|
Hide Abstracts |
Sponsoring Units: DQI Chair: Lin Tian, University of California, Merced Room: BCEC 210A |
Wednesday, March 6, 2019 11:15AM - 11:27AM |
L42.00001: Benchmarking coherent Ising machines and quantum annealers with MAX-CUT and SK problems Ryan Hamerly, Takahiro Inagaki, Peter McMahon, Davide Venturelli, Alireza Marandi, Tatsuhiro Onodera, Edwin Ng, Eleanor Rieffel, Martin Fejer, Hideo Mabuchi, Shoko Utsunomiya, Hiroki Takesue, Yoshihisa Yamamoto We benchmark the performance of two types of physical annealing machines -- coherent Ising machines (CIMs) built from coupled optical parametric oscillators, and a commercial quantum annealer (QA) by D-Wave Systems -- on a range of NP-hard Ising problems including MAX-CUT and ground-state computation of Sherrington-Kirkpatrick (SK) spin glasses. Connectivity and embeddability play a central role in the performance differences between the machines, as the QA's connections are defined on a Chimera graph while the CIM is all-to-all. The QA outperforms the CIM for MAX-CUT problems on sparse graphs, while for dense-graph MAX-CUT and SK problems, the QA exhibits an exponential performance penalty relative to the CIM. This performance difference persists in an optimal anneal-time analysis. The strong correlation between hardness and graph edge density when solving problems on the QA, which is absent in the CIM, motivates future work to increase the connectivity in quantum annealers. [arXiv:1805.05217] |
Wednesday, March 6, 2019 11:27AM - 11:39AM |
L42.00002: Benchmarking Portfolio Selection with Adiabatic Quantum Optimization Erica Grant, Travis Humble, Nada Wael Samir Elsokkary, Faisal Shah Khan, Greg Quiroz Portfolio selection is a constrained optimization problem to choose a set of financial assets that maximizes returns while staying under budget and minimizing risk. Markowitz portfolio theory strategically uses correlated behaviors between assets to mitigate financial risk, which we formulate as a quadratic unconstrained binary optimization problem with frustrated stoquastic form. We benchmark the probability of success with the D-Wave 2000Q quantum annealer using problems derived from cryptocurrency market data. We retrieve the lowest energy result from the quantum annealer and compare to the ground truth of a brute force solver. We observe a weakly sub-exponential decay in the probability of success for up to 20 assets, which we extrapolate to estimate the samples required for larger problems. We also find that the relative contributions of the positive diagonal and negative off-diagonal elements have minor influence on the performance as described by the risk. We further investigate performance improvements due to changes in annealing duration, spin-reversal transformations, and reverse annealing post-processing techniques. |
Wednesday, March 6, 2019 11:39AM - 11:51AM |
L42.00003: Circuit fault diagnosis using quantum annealing and other spin glass solvers Brendan Reid, Elizabeth Crosson, Itay Hen In this work we present a novel approach to solving circuit fault diagnosis (CFD) problems using quantum annealers and other spin glass solvers, such as simulated annealing and parallel tempering. |
Wednesday, March 6, 2019 11:51AM - 12:03PM |
L42.00004: Forward-reverse error mitigation algorithm for quantum annealers Nic Ezzell, Mark Novotny We propose a novel way to try to improve ground-state sampling statistics on quantum annealers with no cost in ancilla qubits—“forward-reverse error mitigation” (FREM) sampling. FREM starts by partitioning a Hamiltonian such that H = HF + HR and proceeds by forward annealing HF while backward annealing HR. While there are no strict requirements on how H should be partitioned, one should have a good approximation of the ground-state of H projected onto the qubits in HR for the reverse anneal. We study the efficacy of FREM using numerical simulations. In particular, our simulation is modelled after the annealing processes on a D-Wave 2000Q, and we use it to compare the ground-state sampling success of forward, reverse, and FREM annealing by comparing their Kullback-Leibler divergence with respect to direct diagonalization. Overall, this work provides an interesting new method to attempt to mitigate errors on near-term quantum annealers with limited qubit numbers. |
Wednesday, March 6, 2019 12:03PM - 12:15PM |
L42.00005: Minor embedding: an application in quantum annealing Yan-Long Fang, Simone Severini, Paul A. Warburton Minor embedding is the embedding of a logical graph as a minor of another graph representing a real quantum annealing device. In the embedded graph each logical qubit is represented by a tree of ferromagnetically-coupled physical qubits. |
Wednesday, March 6, 2019 12:15PM - 12:27PM |
L42.00006: Performance Improvement of a Quantum Annealer Using Optimized Quantum Control Gregory Quiroz Adiabatic quantum computation (AQC) relies on controlled adiabatic evolution to implement a quantum algorithm. Properly designed time-optimal control has been shown to be particularly advantageous for AQC. Grover's search algorithm is one such example where analytically-derived time-optimal control leads to improved scaling of the minimum energy gap between the ground state and first excited state and thus, the well-known quadratic quantum speedup. Recently, the D-Wave Systems quantum processing unit (QPU) -- a system designed to implement quantum annealing (a non-universal, finite-temperature version of AQC) -- has been upgraded with the ability to manipulate the annealing schedule; thus, enabling an evaluation of the effect of optimized control on computational accuracy. Here, we evaluate the new control features of the device for a range of optimization techniques, assessing the potential benefits of control for enhancing QPU performance for hard problem instances. Specifically, we employ closed-loop control optimization protocols based on stochastic gradient ascent and Bayesian optimization to optimize QPU performance. We focus on engineered hard problem instances for the QPU that exhibit small energy gaps and strong susceptibility to noise. |
Wednesday, March 6, 2019 12:27PM - 1:03PM |
L42.00007: Quantum magnetism on a chip Invited Speaker: Richard Harris D-Wave Systems builds superconducting quantum annealing processors that are primarily intended to be used for solving classical computation problems such as optimization and sampling. However, recent publications in Science (Vol. 361, Issue 6398, pp. 162-165) and Nature (Vol. 560, Issue 7719, August 22, 2018) have shown how this computing platform can be used as a programmable quantum magnet that can be used to simulate physical systems relevant to the field of condensed matter physics. This lecture will provide a brief review of the aforementioned results and an update on related experiments. |
Wednesday, March 6, 2019 1:03PM - 1:15PM |
L42.00008: Reverse Quantum Annealing on D-Wave 2000Q Davide Venturelli We review results to date obtained by the usage of the quantum reverse annealing feature introduced in the latest model of the D-Wave machine - especially comparatively with forward annealing protocols. Results suggest that there is sizable advantage in hybridizing runs with classical initialization algorithms. Particular attention will be devoted in combinatorial optimization problems connected to applications, with examples taken from several different industrial domains, where a large ferromagnetic structure is present in the spin systems due to minor embedding. |
Wednesday, March 6, 2019 1:15PM - 1:27PM |
L42.00009: Quantum Annealing XORSAT on Dilute Square Lattices Pranay Patil, Claudio Chamon, Stefanos Kourtis, Andrei E Ruckenstein, Eduardo R Mucciolo Here we show how we can embed the 3-regular 3-XORSAT on a square lattice made out of gates |
Wednesday, March 6, 2019 1:27PM - 1:39PM |
L42.00010: Solution planting scheme for fully-connected spin glasses Christopher Pattison, Firas Hamze, Jack Raymond, Helmut Katzgraber The advent of new specialized hardware designed to tackle spin-glass-like problems on dense graphs has resulted in a renewed interest in planted solutions for spin-glass Hamiltonians. Here we present a method for planting solutions in fully-connected spin-glass systems with tunable hardness. In particular, the hardness of the problems undergoes a complexity transition. Using both analytical and numerical techniques, we characterize the behavior of these new planted systems. |
Wednesday, March 6, 2019 1:39PM - 1:51PM |
L42.00011: Testing the D-Wave 2000Q as a quantum Monte Carlo simulator Zoe Gonzalez Izquierdo, Itay Hen, Tameem Albash
|
Wednesday, March 6, 2019 1:51PM - 2:03PM |
L42.00012: Theoretical survey of unconventional quantum annealing methods applied to a difficult trial problem Zhijie Tang, Eliot Kapit Adiabatic quantum annealing is a promising method to solve optimization problems. In our work, we define an artificial trial problem inspired by "transverse field chaos" in larger systems where classical and quantum methods are steered toward a local false minimum and the minimum gap to the true ground state is exponentially small. (all N spins must be flipped from the local minimum to the global minimum, which makes the problem exponentially difficult to solve.) We numerically study this problem by using a variety of new methods from the literature: ramping the transverse field down one by one; adding transverse couplers between qubits; adding local oscillating transverse field. We show that the standard adiabatic quantum annealing method can be improved with these methods, and comparison of these methods could help identify the most promising routes to a quantum speedup in future quantum hardware. |
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