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 weak-strong cluster glass, the D-Wave 2X processor achieves a significant advantage in runtime scaling relative to Simulated Annealing (SA). For instances with 945 variables this results in a time-to-99\%-success-probability $10^9$ times shorter than SA running on a single core. When comparing to the Quantum Monte Carlo (QMC) algorithm we only observe a pre-factor advantage but the pre-factor 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 k-th order binary optimization problems. We studied 4-spin 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 k-th 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 D-Wave 2X J.S. Hall, L. Hobl, M.A. Novotny, Kristel Michielsen The performances of two D-Wave 2 machines (476 and 496 qubits) and of a 1097-qubit D-Wave 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 two-qubit interactions $J_{i,j}$ of an Ising spin-glass 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 476-qubit D-Wave 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 1097-qubit 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 D-Wave 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 thermally-assisted 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 thermally-assisted tunneling in mean-field 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 path-integral instanton approach in coherent state and Suzuki-Trotter 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 pre-factor 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 D-Wave quantum annealers through graph mirroring Dilina Perera, J.S. Hall, M.A. Novotny D-Wave 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 D-Wave 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 spin-glass systems are featuring long-range 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 non-complete 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 D-Wave 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 Graph-Minor Embedding of Cartesian Products of Complete Graphs Arman Zaribafiyan, Dominic J.J. Marchand, Seyed Saeed Changiz Rezaei The limited connectivity of current and next-generation quantum annealers motivates the need for efficient graph-minor embedding methods. The overhead of the widely used heuristic techniques is quickly proving to be a significant bottleneck for real-world 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 many-body interactions arises in various applications of quantum computing.
However, interactions beyond two-body are difficult to realize experimentally.
Perturbative gadgets were introduced to obtain arbitrary many-body effective interactions using Hamiltonians with two-body 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 low-lying energies near the minimum, hence allowing for faster adiabatic passages to find the ground state with less risk of getting caught in an undesired low-lying 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 two-qubit gates. Our lower-bound technique may have more general application. [Preview Abstract] |
(Author Not Attending)
|
F45.00011: Quantum Annealing and Many-Body Localization Noah Bray-Ali The quantum phase transition separating the Ising spin glass from the quantum paramagnet phase in one-dimension is many-body localized. We study quantum annealing across this transition using the recently developed, dynamical strong-disorder renormalization group approach. The probability of successful adiabatic quantum computation of the spin glass ground-state 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 many-body localized quantum phase transition. [Preview Abstract] |
Tuesday, March 15, 2016 1:51PM - 2:03PM |
F45.00012: Bifurcation-based 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 quantum-mechanical 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 bifurcation-based 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 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