Bulletin of the American Physical Society
APS March Meeting 2016
Volume 61, Number 2
Monday–Friday, March 14–18, 2016; Baltimore, Maryland
Session F45: Adiabatic Quantum Computation and Quantum Annealing: Energy Landscapes, Speedup and EmbeddingFocus

Hide Abstracts 
Sponsoring Units: GQI Chair: Daniel Lidar, Univ. of Southern California Room: 348 
Tuesday, March 15, 2016 11:15AM  11:51AM 
F45.00001: Quantum Annealing at Google: Recent Learnings and Next Steps Invited Speaker: Hartmut Neven Recently we studied optimization problems with rugged energy landscapes that featured tall and narrow energy barriers separating energy minima. We found that for a crafted problem of this kind, called the weakstrong cluster glass, the DWave 2X processor achieves a significant advantage in runtime scaling relative to Simulated Annealing (SA). For instances with 945 variables this results in a timeto99\%successprobability $10^9$ times shorter than SA running on a single core. When comparing to the Quantum Monte Carlo (QMC) algorithm we only observe a prefactor advantage but the prefactor is large, about $10^6$ for an implementation on a single core. We should note that we expect QMC to scale like physical quantum annealing only for problems for which the tunneling transitions can be described by a dominant purely imaginary instanton. We expect these findings to carry over to other problems with similar energy landscapes. A class of practical interest are kth order binary optimization problems. We studied 4spin problems using numerical methods and found again that simulated quantum annealing has better scaling than SA. This leaves us with a final step to achieve a wall clock speedup of practical relevance. We need to develop an annealing architecture that supports embedding of kth order binary optimization in a manner that preserves the runtime advantage seen prior to embedding. [Preview Abstract] 
Tuesday, March 15, 2016 11:51AM  12:03PM 
F45.00002: Ground States of Random Spanning Trees on a DWave 2X J.S. Hall, L. Hobl, M.A. Novotny, Kristel Michielsen The performances of two DWave 2 machines (476 and 496 qubits) and of a 1097qubit DWave 2X were investigated. Each chip has a Chimera interaction graph ${\cal G}$. Problem input consists of values for the fields $h_j$ and for the twoqubit interactions $J_{i,j}$ of an Ising spinglass problem formulated on ${\cal G}$. Output is returned in terms of a spin configuration $\{s_j\}$, with $s_j$$=$$\pm 1$. We generated random spanning trees (RSTs) uniformly distributed over all spanning trees of ${\cal G}$. On the 476qubit DWave 2, RSTs were generated on the full chip with $J_{i,j}=1$ and $h_j=0$ and solved one thousand times. The distribution of solution energies and the average magnetization of each qubit were determined. On both the 476 and 1097qubit machines, four identical spanning trees were generated on each quadrant of the chip. The statistical independence of these regions was investigated. In another study, on the DWave 2X, one hundred RSTs with random $J_{i,j}$$\in$$\{1,1\}$ and $h_j=0$ were generated on the full chip. Each RST problem was solved one hundred times and the number of times the ground state energy was found was recorded. This procedure was repeated for square subgraphs, with dimensions ranging from $7$$\times$$7$ to $11$$\times$$11$. [Preview Abstract] 
Tuesday, March 15, 2016 12:03PM  12:15PM 
F45.00003: Instantons and scaling of the transitions rates in Quantum Monte Carlo simulations of thermallyassisted quantum tunneling in spin systems Vadim Smelyanskiy, Zhang Jiang, Sergio Boixo, Sergei Issakov, Guglielmo Mazzola, Matthias Troyer, Hartmut Neven We study analytically and numerically the dynamics of the quantum Monte Carlo (QMC) algorithm to simulate thermallyassisted tunneling in meanfield spin models without conservation of total spin. We use Kramers escape rate theory to calculate the scaling of the QMC time with the problem size to simulate the tunneling transitions. We develop pathintegral instanton approach in coherent state and SuzukiTrotter representations to calculate the escape rate and most probable escape path in QMC dynamics. Analtytical results are in a good agreement with numerical studies. We identify the class of models where the exponent in the scaling of the QMC time is the same as that in physical tunneling but the prefactor depends very significantly on the QMC path representation. We propose the classes of problems where QMC can fail to simulate tunneling efficiently. [Preview Abstract] 
Tuesday, March 15, 2016 12:15PM  12:27PM 
F45.00004: Validating the solutions of the DWave quantum annealers through graph mirroring Dilina Perera, J.S. Hall, M.A. Novotny DWave quantum annealers seek to find the ground states of Ising spin glasses. The problem Hamiltonian is formulated as an undirected graph that can be embedded into the device’s native disordered Chimera graph structure. However, depending on the complexity of the problem and the specifications of the annealing schedule, the device may not necessarily find the global minimum during a given annealing process. We present a method, which we call answer checking, that enhances the expectation that the solution provided by the device is the true ground state of the problem. The underlying principle is to embed a mirrored graph $G'$ of the original graph $G$, and connect the two graphs via ferromagnetic/antiferromagnetic couplers. This allows one to rule out solutions for the composite graph that do not comply with the underlying mirror symmetry inherent to the true ground state, which in turn, reduces the uncertainty associated with the solutions. Using the 1097 qubit DWave 2X, we test this approach by applying it to a range of problems, including random spanning trees and generally allowed graphs $G$. [Preview Abstract] 
Tuesday, March 15, 2016 12:27PM  12:39PM 
F45.00005: Quantum Annealing for Constrained Optimization Itay Hen, Federico Spedalieri Recent advances in quantum technology have led to the development and manufacturing of experimental programmable quantum annealers that could potentially solve certain quadratic unconstrained binary optimization problems faster than their classical analogues. The applicability of such devices for many theoretical and practical optimization problems, which are often constrained, is severely limited by the sparse, rigid layout of the devices' quantum bits. Traditionally, constraints are addressed by the addition of penalty terms to the Hamiltonian of the problem, which in turn requires prohibitively increasing physical resources while also restricting the dynamical range of the interactions. Here we propose a method for encoding constrained optimization problems on quantum annealers that eliminates the need for penalty terms and thereby removes many of the obstacles associated with the implementation of these. We argue the advantages of the proposed technique and illustrate its effectiveness. We then conclude by discussing the experimental feasibility of the suggested method as well as its potential to boost the encodability of other optimization problems. [Preview Abstract] 
Tuesday, March 15, 2016 12:39PM  12:51PM 
F45.00006: Embedding parameters for Quantum Annealing Davide Venturelli Many optimization problems are defined on highly connected graphs and many interesting physical spinglass systems are featuring longrange interactions. One method to solve for the optimum/ground state is quantum annealing (QA). Most architectures for QA devices, manufactured or proposed, are based on optimizing Hamiltonians having spins connected in a noncomplete graph, with nodes with a small maximum degree, compared to the requirements. To overcome this limitation 'embedding' is employed: the native graph is ‘tiled’ with ferromagnetic chains of spins that now are meant to represent the logical binary variables. While it is known how the strength of the ferromagnetic bonds can ensure that the classical Ising ground state of the embedded system can be univocally mapped to the ground state of the original system, there is very little study on the impact of these parameters on QA. Programmers have taken conservative choices for the parameters and the common practices can be improved. Starting from the physics of connected ferromagnetic Ising chains, we will review several parameter choices and discuss previous and new results obtained on the DWave 2X machine, on carefully designed problems that allow to isolate and evaluate the role of connectivity in embedded systems. [Preview Abstract] 
Tuesday, March 15, 2016 12:51PM  1:03PM 
F45.00007: Systematic and Deterministic GraphMinor Embedding of Cartesian Products of Complete Graphs Arman Zaribafiyan, Dominic J.J. Marchand, Seyed Saeed Changiz Rezaei The limited connectivity of current and nextgeneration quantum annealers motivates the need for efficient graphminor embedding methods. The overhead of the widely used heuristic techniques is quickly proving to be a significant bottleneck for realworld applications. To alleviate this obstacle, we propose a systematic deterministic embedding method that exploits the structures of both the input graph of the specific combinatorial optimization problem and the quantum annealer. We focus on the specific case of the Cartesian product of two complete graphs, a regular structure that occurs in many problems. We first divide the problem by embedding one of the factors of the Cartesian product in a repeatable unit. The resulting simplified problem consists of placing copies of this unit and connecting them together appropriately. Aside from the obvious speed and efficiency advantages of a systematic deterministic approach, the embeddings produced can be easily scaled for larger processors and show desirable properties with respect to the number of qubits used and the chain length distribution. [Preview Abstract] 
Tuesday, March 15, 2016 1:03PM  1:15PM 
F45.00008: Simulating highly nonlocal Hamiltonians with less nonlocal Hamiltonians Yigit Subasi, Christopher Jarzynski The need for Hamiltonians with manybody interactions arises in various applications of quantum computing.
However, interactions beyond twobody are difficult to realize experimentally.
Perturbative gadgets were introduced to obtain arbitrary manybody effective interactions using Hamiltonians with twobody interactions only.
Although valid for arbitrary $k$body interactions, their use is limited to small $k$ because the strength of interaction is $k$'th order in perturbation theory.
Here we develop a nonperturbative technique for obtaining effective $k$body interactions using Hamiltonians consisting of at most $l$body interactions with $l 
Tuesday, March 15, 2016 1:15PM  1:27PM 
F45.00009: Crushing runtimes in adiabatic quantum computation with Energy Landscape Manipulation (ELM): Application to Quantum Factoring Nike Dattani, Richard Tanburn, Oliver Lunt We introduce two methods for speeding up adiabatic quantum computations by increasing the energy between the ground and first excited states. Our methods are even more general. They can be used to shift a Hamiltonian's density of states away from the ground state, so that fewer states occupy the lowlying energies near the minimum, hence allowing for faster adiabatic passages to find the ground state with less risk of getting caught in an undesired lowlying excited state during the passage. Even more generally, our methods can be used to transform a discrete optimization problem into a new one whose unique minimum still encodes the desired answer, but with the objective function's values forming a different landscape. Aspects of the landscape such as the objective function's range, or the values of certain coefficients, or how many different inputs lead to a given output value, can be decreased *or* increased. One of the many examples for which these methods are useful is in finding the ground state of a Hamiltonian using NMR. We apply our methods to an AQC algorithm for integer factorization, and the first method reduces the maximum runtime in our example by up to 754\%, and the second method reduces the maximum runtime of another example by up to 250\%. [Preview Abstract] 
Tuesday, March 15, 2016 1:27PM  1:39PM 
F45.00010: On universal adiabatic quantum computation Ari Mizel We give a careful proof that ground state quantum computation can efficiently simulate universal gate model quantum computation. The proof allows for general gate model quantum computations; no restrictions are required on qubit geometry or on the locality of twoqubit gates. Our lowerbound technique may have more general application. [Preview Abstract] 
(Author Not Attending)

F45.00011: Quantum Annealing and ManyBody Localization Noah BrayAli The quantum phase transition separating the Ising spin glass from the quantum paramagnet phase in onedimension is manybody localized. We study quantum annealing across this transition using the recently developed, dynamical strongdisorder renormalization group approach. The probability of successful adiabatic quantum computation of the spin glass groundstate obeys a universal scaling function of system size, anneal rate, and strength of disorder, which we obtain. Measurement of this universal scaling behavior in a quantum annealing device, for example, would be the first direct test of the activated dynamics of a manybody localized quantum phase transition. [Preview Abstract] 
Tuesday, March 15, 2016 1:51PM  2:03PM 
F45.00012: Bifurcationbased adiabatic quantum computation with a nonlinear oscillator network Hayato Goto The dynamics of nonlinear systems qualitatively change depending on their parameters, which is called bifurcation. A quantummechanical nonlinear oscillator can yield a quantum superposition of two oscillation states, known as a Schr\"odinger cat state, via its bifurcation with a slowly varying parameter. Here we propose a quantum computer comprising such quantum nonlinear oscillators, instead of quantum bits, to solve hard combinatorial optimization problems. The nonlinear oscillator network finds optimal solutions via quantum adiabatic evolution, where nonlinear terms are increased slowly, in contrast to conventional adiabatic quantum computation or quantum annealing. To distinguish them, we refer to the present approach as bifurcationbased adiabatic quantum computation. Our numerical simulation results suggest that quantum superposition and quantum fluctuation work effectively to find optimal solutions. [Preview Abstract] 
Follow Us 
Engage
Become an APS Member 
My APS
Renew Membership 
Information for 
About APSThe American Physical Society (APS) is a nonprofit membership organization working to advance the knowledge of physics. 
© 2019 American Physical Society
 All rights reserved  Terms of Use
 Contact Us
Headquarters
1 Physics Ellipse, College Park, MD 207403844
(301) 2093200
Editorial Office
1 Research Road, Ridge, NY 119612701
(631) 5914000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 200452001
(202) 6628700