Bulletin of the American Physical Society
APS March Meeting 2017
Volume 62, Number 4
Monday–Friday, March 13–17, 2017; New Orleans, Louisiana
Session A51: Quantum Annealing: Algorithms & Theory |
Hide Abstracts |
Sponsoring Units: GQI Chair: Alejandro Perdomo-Ortiz, NASA Ames Research Center Room: 398 |
Monday, March 13, 2017 8:00AM - 8:12AM |
A51.00001: Inducing mean-field criticality in spin glasses on quasi-planar topologies: Improved quantum annealer designs Helmut G. Katzgraber, Mark A. Novotny Using large-scale Monte Carlo simulations, we demonstrate how mean-field behavior can be induced in spin glasses on (quasi) planar topologies. By adding spin-spin interactions whose length is distributed according to a small-world distribution, we show that the zero-temperature two-dimensional spin-glass universality class becomes a mean-field-like universality class. In particular, this means the system orders at a finite transition temperature. This has important consequences for the design of quantum annealing chips: Combined with the fact that the addition of small-world bonds also changes the percolation universality class to mean field [Phys.~Rev.~E 93, 042128 (2016)], this means that the embedding of complex problems and the generation of harder benchmark instances should be easier in these topologies. Although the implementation of unrestricted small-world couplers (spin-spin interactions) would be prohibitively difficult in quantum annealers, we show that the mean-field behavior only requires four additional fabrication layers with a fixed general direction and small number of small-world couplers -- something that can, in principle, be implemented. [Preview Abstract] |
Monday, March 13, 2017 8:12AM - 8:24AM |
A51.00002: Patch planting of hard spin-glass problems: Getting ready for the next generation of optimization approaches Wenlong Wang, Salvatore Mandr{\`a}, Helmut Katzgraber We propose a patch planting heuristic that allows us to create arbitrarily-large Ising spin-glass instances on any topology and with any type of disorder, and where the exact ground-state energy of the problem is known by construction. By breaking up the problem into patches that can be treated either with exact or heuristic solvers, we can reconstruct the optimum of the original, considerably larger, problem. The scaling of the computational complexity of these instances with various patch numbers and sizes is investigated and compared with random instances using population annealing Monte Carlo and quantum annealing on the D-Wave 2X quantum annealer. The method can be useful for benchmarking of novel computing technologies and algorithms. [Preview Abstract] |
Monday, March 13, 2017 8:24AM - 8:36AM |
A51.00003: Thermalization, freeze-out and J-chaos: deciphering experimental quantum annealers Itay Hen, Jeffrey Marshall, Eleanor Rieffel By contrasting the performances of two prototypical quantum annealing optimizers held at different temperatures, we address and resolve several recent pressing questions pertaining to the role of temperature in these devices. In particular, we study the ability of experimental quantum annealers to function as `Boltzmann samplers'. While to date the discrepancies between the observed output and theoretical predictions have been prone to conjecture, we demonstrate how the simultaneous benchmarking on two devices sheds light on the inner workings of these otherwise inaccessible processors. Our results show that the output distributions of the annealers do not in general correspond to classical Boltzmann distributions but rather correspond to distributions generated by Hamiltonians with a non-negligible quantum part. Moreover, we find that the observed effective temperatures of these devices are significantly higher than their physical temperatures and argue that this is in accord with the `freeze-out' picture. We also find that J-chaos plays an increasingly dominant role in determining these instance-dependent effective temperatures. We discuss the implications of our results to potential applications of current and near future practical quantum annealing. [Preview Abstract] |
Monday, March 13, 2017 8:36AM - 8:48AM |
A51.00004: Model-based diagnosis in combinational digital circuits: An application with potential for quantum speedup Alejandro Perdomo-Ortiz, Alexander Feldman, Zheng Zhu, Asier Ozaeta, Sergei Isakov, Vasil Denchev, Helmut Katzgraber, Hartmut Neven, Alexander Diedrich, Brad Lackey, Johan De Kleer, Rupak Biswas Only recently, it was demonstrated that optimization on the D-Wave 2X quantum annealer can outperform other sequential algorithms on CMOS-based hardware. However, the benchmark problems were tailored to yield an advantage over classical local search algorithms. Furthermore, including state-of-the-art optimization techniques that are not sequential in nature closed the gap between quantum and classical optimization techniques. Therefore, the question arises if there are real-world application problems small enough in the number of variables such that they can be optimized on current quantum hardware, and where quantum annealing might excel over classical optimization techniques. Here we demonstrate that model-based diagnosis in combinational circuits is an ideal problem for quantum enhanced optimization and the first application problem with potential for quantum speedup. Benchmark instances generated from this real-world application tend to be considerably harder than any specially-tuned random spin-glass instances (excluding post selection). We address the relevancy of many-body interactions beyond quadratic in current quantum annealers, as well as connectivity requirements to solve real-world problems. [Preview Abstract] |
Monday, March 13, 2017 8:48AM - 9:00AM |
A51.00005: Quantum-assisted learning of graphical models with arbitrary pairwise connectivity John Realpe-Gómez, Marcello Benedetti, Rupak Biswas, Alejandro Perdomo-Ortiz Mainstream machine learning techniques rely heavily on sampling from generally intractable probability distributions. There is increasing interest in the potential advantages of using quantum computing technologies as sampling engines to speedup these tasks. However, some pressing challenges in state-of-the-art quantum annealers have to be overcome before we can assess their actual performance. The sparse connectivity, resulting from the local interaction between quantum bits in physical hardware implementations, is considered the most severe limitation to the quality of constructing powerful machine learning models. Here we show how to surpass this `curse of limited connectivity' bottleneck and illustrate our findings by training probabilistic generative models with arbitrary pairwise connectivity on a real dataset of handwritten digits and two synthetic datasets in experiments with up to $940$ quantum bits. Our model can be trained in quantum hardware without full knowledge of the effective parameters specifying the corresponding Boltzmann-like distribution. Therefore, the need to infer the effective temperature at each iteration is avoided, speeding up learning, and the effect of noise in the control parameters is mitigated, improving accuracy. [Preview Abstract] |
Monday, March 13, 2017 9:00AM - 9:12AM |
A51.00006: Quantum walks on the chimera graph and its variants Barry Sanders, Xiangxiang Sun, Shu Xu, Jizhou Wu, Wei-Wei Zhang, Nigum Arshed We study quantum walks on the chimera graph, which is an important graph for performing quantum annealing, and we explore the nature of quantum walks on variants of the chimera graph. Features of these quantum walks provide profound insights into the nature of the chimera graph, including effects of greater and lesser connectivity, strong differences between quantum and classical random walks, isotropic spreading and localization only in the quantum case, and random graphs. We analyze finite-size effects due to limited width and length of the graph, and we explore the effect of different boundary conditions such as periodic and reflecting. Effects are explained via spectral analysis and the properties of stationary states, and spectral analysis enables us to characterize asymptotic behavior of the quantum walker in the long-time limit. [Preview Abstract] |
Monday, March 13, 2017 9:12AM - 9:24AM |
A51.00007: Towards a measureable pathway for learning quantum annealing Elizabeth Behrman, James Steck In previous work, we have proposed and developed an algorithm for quantum annealing machines, to expand their repertoire using systematic quantum control via machine learning. Current technologies limit measurement of the states of these machines to determination of the average spin at each site. We therefore construct a ``broken pathway'' between the initial and the desired states, at each step of which the average spins are nonzero, and show successful learning of that pathway. Using this technique we show we can direct annealing to multiqubit GHZ states and W states. The procedure is robust to noise and decoherence. [Preview Abstract] |
Monday, March 13, 2017 9:24AM - 9:36AM |
A51.00008: Artificial neural networks as quantum associative memory Kathleen Hamilton, Jonathan Schrock, Neena Imam, Travis Humble We present results related to the recall accuracy and capacity of Hopfield networks implemented on commercially available quantum annealers. The use of Hopfield networks and artificial neural networks as content-addressable memories offer robust storage and retrieval of classical information, however, implementation of these models using currently available quantum annealers faces several challenges: the limits of precision when setting synaptic weights, the effects of spurious spin-glass states and minor embedding of densely connected graphs into fixed-connectivity hardware. We consider neural networks which are less than fully-connected, and also consider neural networks which contain multiple sparsely connected clusters. We discuss the effect of weak edge dilution on the accuracy of memory recall, and discuss how the multiple clique structure affects the storage capacity. Our work focuses on storage of patterns which can be embedded into physical hardware containing $n < 1000$ qubits. [Preview Abstract] |
Monday, March 13, 2017 9:36AM - 9:48AM |
A51.00009: Anti-Kibble-Zurek Behavior in the Quantum Dynamics of Thermally Isolated Systems Driven by a Noisy Control Field Armin Rahmani, Anirban Dutta, Adolfo del Campo We show that a thermally isolated system driven across a quantum phase transition by a noisy control field exhibits anti-Kibble-Zurek behavior, whereby slower driving results in higher excitations. We characterize the density of excitations as a function of the ramping rate and the noise strength. The optimal driving time to minimize excitations is shown to scale as a universal power law of the noise strength. Our findings reveal the limitations of adiabatic protocols such as quantum annealing and demonstrate the universality of the optimal ramping rate. [Preview Abstract] |
Monday, March 13, 2017 9:48AM - 10:00AM |
A51.00010: Efficient Online Optimized Quantum Control for Adiabatic Quantum Computation Gregory Quiroz Adiabatic quantum computation (AQC) relies on controlled adiabatic evolution to implement a quantum algorithm. While control evolution can take many forms, 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. Analytical extensions beyond Grover's search algorithm present a daunting task that requires potentially intractable calculations of energy gaps and a significant degree of model certainty. Here, an in situ quantum control protocol is developed for AQC. The approach is shown to yield controls that approach the analytically-derived time-optimal controls for Grover's search algorithm. In addition, the protocol's convergence rate as a function of iteration number is shown to be essentially independent of system size. Thus, the approach is potentially scalable to many-qubit systems. [Preview Abstract] |
Monday, March 13, 2017 10:00AM - 10:12AM |
A51.00011: Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle Zhi-Cheng Yang, Armin Rahmani, Alireza Shabani, Hartmut Neven, Claudio Chamon We use the Pontryagin's minimum principle to optimize variational quantum algorithms. We show that for a fixed computation time, the optimal evolution has a bang-bang (square pulse) form, both for closed and open quantum systems with Markovian decoherence. Our findings support the choice of evolution ansatz in the recently proposed Quantum Approximate Optimization Algorithm. Focusing on the Sherrington-Kirkpatrick spin glass as an example, we find a system-size independent distribution of the duration of pulses, with characteristic time scale set by the inverse of the coupling constants in the Hamiltonian. We numerically demonstrate that our optimal nonadiabatic bang-bang protocols can significantly outperform quantum annealing, favoring gate-model quantum computation for quantum enhanced optimization. Moreover, the fidelity of the final states following the bang-bang protocol remains high in the presence of weak additive white noise. The optimality of the bang-bang protocols and the characteristic time scale of the pulses inform the search for effective hybrid (classical and quantum) schemes for tackling combinatorial optimization problems. [Preview Abstract] |
Monday, March 13, 2017 10:12AM - 10:24AM |
A51.00012: General compiler for reducing multi-qubit terms and controlling coupling strengths in AQC Hamiltonians Nike Dattani, Richard Tanburn, Richard Ngo, Toby Cathcart-Burn After encoding the solution to your problem into the ground state of a Hamiltonian, it is necessary to "compile" the Hamiltonian into one which can be realized in existing hardware or in hardware that is likely to emerge in the near future. We have recently developed methods to reduce multi-qubit terms to 2-qubit terms without adding auxiliary qubits (https://arxiv.org/abs/1508.04816, https://arxiv.org/abs/1508.07190) and for controlling properties of the Hamiltonian such as the spectral gap, spectral width, number of local minima in a particular state, and strength of couplings between/among qubits (https://arxiv.org/abs/1510.07420). We combine these methods with established methods for reducing multi-qubit terms in worse cases where auxiliary qubits are needed, into a general purpose "compiler" that reads in a general Hamiltonian, and attempts to output a 2-local Hamiltonian with **as few extra qubits as possible** and **as large a spectral gap as possible** and **as small a spectral width as possible** and **coupling strengths that are as small as possible**. We show results on several types of AQC Hamiltonians: neural network Hamiltonians, computer vision problems, Ramsey number determination, integer factorization, and quantum chemistry. [Preview Abstract] |
Monday, March 13, 2017 10:24AM - 10:36AM |
A51.00013: Efficient Embedding of Integer Programming Problems on Quantum Annealers Davide Venturelli, Immanuel Trummer Quantum Annealers are being considered as a possible platform to solve challenging Integer Optimization Problems (IOP). Hard-coding an IOP as an Ising model onto an annealer is however no easy task due to the severe restrictions imposed mostly by the connectivity of the graph implemented by the hardware architecture, as it has widely discussed for the D-Wave machines. The current approaches employ graph minor embedding algorithms that require a significant overhead of resources (number of qubits, computing power) with respect to the number of logical variables in the IOP. This overhead is arguably the primary problems for practitioners of quantum annealing. We present a new method to deterministically embed an arbitrary IOP in a generic class of annealing chip layouts such that the asymptotic scaling beats all the current methods. It is shown on the latest D-Wave chips to allow programming of problems, relevant for database and space sciences, with approximately 5-10x more variables with respect to the published approaches. The method is efficient in the sense that a valid embedding can be computed at run-time in polynomial time. The discussed methods can inform the design of next-generation of quantum annealers. [Preview Abstract] |
Monday, March 13, 2017 10:36AM - 10:48AM |
A51.00014: Quantum annealing of disordered spin systems Lukas Sieberer, Philipp Hauke, Ehud Altman, Wolfgang Lechner Quantum annealing is a general purpose optimization algorithm, whose goal is to find the ground state of a given "problem" Hamiltonian. This is accomplished by starting from the ground state of a simple Hamiltonian and slowly deforming the Hamiltonian to the one of interest. If this is carried out adiabatically, the system will end up in the desired ground state. For a broad class of hard optimization problems it is known that the minimal gap between the ground state and the first excited state is exponentially small in the system size, and passing this gap adiabatically is unfeasible for large systems. However, even if the quantum state at the end of an annealing protocol is not the desired ground state but a superposition of not-too-highly excited states, it might still give a useful approximation to the solution of the original optimization problem. In our work, we investigate how good of an approximation one can expect to get. We build on recent advances in the understanding of the structure of excited states and the spectral properties of disordered spin systems (i.e., random optimization problems). In particular, we show that the two generic paradigms of ergodic and many-body localized phases entail surprisingly different behavior under quantum annealing. [Preview Abstract] |
Monday, March 13, 2017 10:48AM - 11:00AM |
A51.00015: Goldiocks probes for noisy interferometry via quantum annealing to criticality Gabriel Durkin Quantum annealing is explored as a resource for quantum information beyond solution of classical combinatorial problems. Envisaged as a generator of robust interferometric probes, we examine a Hamiltonian of $N≫1$ uniformly coupled spins subject to a transverse magnetic field. The discrete many-body problem is mapped onto dynamics of a single one-dimensional particle in a continuous potential. This reveals all the qualitative features of the ground state beyond typical mean-field or large classical spin models. It illustrates explicitly a graceful warping from an entangled unimodal to bimodal ground state in the phase transition region. The transitional “Goldilocks” probe has a component distribution of width $\propto N^{2/3}$ and exhibits characteristics for enhanced phase estimation in a decoherent environment. In the presence of realistic local noise and collective dephasing, we find this probe state asymptotically saturates ultimate precision bounds calculated previously. By reducing the transverse field adiabatically, the Goldilocks probe is prepared in advance of the minimum gap bottleneck, allowing the annealing schedule to be terminated “early.” Adiabatic time complexity of probe preparation is shown to be linear in $N$. [Preview Abstract] |
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