Bulletin of the American Physical Society
APS March Meeting 2016
Volume 61, Number 2
Monday–Friday, March 14–18, 2016; Baltimore, Maryland
Session C45: Adiabatic Quantum Computation and Quantum Annealing: Tunneling, Speedup and Noise EffectsFocus

Hide Abstracts 
Sponsoring Units: GQI Chair: Davide Venturelli, NASA Ames Research Center Room: 348 
Monday, March 14, 2016 2:30PM  3:06PM 
C45.00001: Tunneling and Speedup in PermutationInvariant Quantum Optimization Problem Invited Speaker: Tameem Albash Tunneling is often claimed to be the key mechanism underlying possible speedups in quantum optimization via the quantum adiabatic algorithm. Restricting ourselves to qubitpermutation invariant problems, we show that tunneling in these problems can be understood using the semiclassical potential derived from the spincoherent path integral formalism. Using this, we show that the class of problems that fall under Reichardt's bound (1), i.e., have a constant gap and hence can be efficiently solved using the quantum adiabatic algorithm, do not exhibit tunneling in the large systemsize limit. We proceed to construct problems that do not fall under Reichardt's bound but numerically have a constant gap and do exhibit tunneling. However, perhaps counterintuitively, tunneling does not provide the most efficient mechanism for finding the solution to these problems. Instead, an evolution involving a sequence of diabatic transitions through many avoided levelcrossings, involving no tunneling, is optimal and outperforms tunneling in the adiabatic regime. In yet another twist, we show that in this case, classical spinvector dynamics is as efficient as the diabatic quantum evolution (2).\\ (1) B. W. Reichardt, in Proceedings of the Thirtysixth Annual ACM Symposium on Theory of Computing, STOC ’04 (ACM, New York, NY, USA, 2004) pp. 502–510.\\ (2) S. Muthukrishnan, T. Albash, D.A. Lidar, arXiv:1505.01249. [Preview Abstract] 
Monday, March 14, 2016 3:06PM  3:18PM 
C45.00002: Understanding Quantum Tunneling through Quantum Monte Carlo Simulations Sergio Boixo, Sergei Isakov, Guglielmo Mazzola, Vadim Smelyanskiy, Zhang Jiang, Hartmut Neven, Matthias Troyer The tunneling between the two ground states of an Ising ferromagnet is a typical example of manybody tunneling processes between two local minima, as they occur during quantum annealing. Performing quantum Monte Carlo (QMC) simulations we find that the QMC tunneling rate displays the same scaling (in the exponent) with system size, as the rate of incoherent tunneling. The scaling in both cases is $O(\Delta^2)$, where $\Delta$ is the tunneling splitting. An important consequence is that QMC simulations can be used to predict the performance of a quantum annealer for tunneling through a barrier. Furthermore, by using open instead of periodic boundary conditions in imaginary time, equivalent to a projector QMC algorithm, we obtain a quadratic speedup for QMC, and achieve linear scaling in $\Delta$. We provide a physical understanding of these results and their range of applicability based on an instanton picture. [Preview Abstract] 
Monday, March 14, 2016 3:18PM  3:30PM 
C45.00003: Coupled Quantum Fluctuations and Quantum Annealing Layla Hormozi, Jamie Kerman We study the relative effectiveness of coupled quantum fluctuations, compared to single spin fluctuations, in the performance of quantum annealing. We focus on problem Hamiltonians resembling the the SherringtonKirkpatrick model of Ising spin glass and compare the effectiveness of different types of fluctuations by numerically calculating the relative success probabilities and residual energies in fullyconnected spin systems. We find that for a small class of instances coupled fluctuations can provide improvement over single spin fluctuations and analyze the properties of the corresponding class. Disclaimer: This research was funded by ODNI, IARPA via MIT Lincoln Laboratory under Air Force Contract No. FA872105C0002. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of ODNI, IARPA, or the US Government. [Preview Abstract] 
Monday, March 14, 2016 3:30PM  3:42PM 
C45.00004: Performance of error suppresion schemes for adiabatic quantum computation in the presence of Markovian noise Milad Marvian, Daniel Lidar We investigate the performance of error suppression schemes for adiabatic quantum computation. Assuming a Markovian environment and using an adiabatic master equation we compare the rate of excitation from the ground subspace of the encoded Hamiltonian during the evolution to that of the unprotected Hamiltonian. For different forms of Markovian environments — such as subOhmic, Ohmic and superOhmic — we identify the parameter thresholds for which encoding starts exhibiting its benefits. [Preview Abstract] 
Monday, March 14, 2016 3:42PM  3:54PM 
C45.00005: Coping with noise in programmable quantum annealers Alejandro PerdomoOrtiz Solving realworld applications with quantum annealing algorithms requires overcoming several challenges, ranging from translating the computational problem at hand to the quantummachine language, to tuning several other parameters of the quantum algorithm that have a significant impact on performance of the device. In this talk, we discuss these challenges, strategies developed to enhance performance, and also a more efficient implementation of several applications. For example, in http://arxiv.org/abs/1503.05679 we proposed an method to measure residual systematic biases in the programmable parameters of largescale quantum annealers. Although the method described there works from a practical point of view, a few questions were left unanswered. One of these puzzles was the observation of a broad distribution in the estimated effective qubit temperatures throughout the device . In this talk, we will present our progress in understanding these puzzles and how these new insights allow for a more effective bias correction protocol. We will present the impact of these new parameter setting and bias correction protocols in the performance of hard discrete optimization problems and in the successful implementation of quantumassisted machinelearning algorithms. [Preview Abstract] 
Monday, March 14, 2016 3:54PM  4:06PM 
C45.00006: Does finitetemperature decoding deliver better optima for noisy Hamiltonians? Andrew J. Ochoa, Kohji Nishimura, Hidetoshi Nishimori, Helmut G. Katzgraber The minimization of an Ising spinglass Hamiltonian is an NPhard problem. Because many problems across disciplines can be mapped onto this class of Hamiltonian, novel efficient computing techniques are highly sought after. The recent development of quantum annealing machines promises to minimize these difficult problems more efficiently. However, the inherent noise found in these analog devices makes the minimization procedure difficult. While the machine might be working correctly, it might be minimizing a different Hamiltonian due to the inherent noise. This means that, in general, the groundstate configuration that correctly minimizes a noisy Hamiltonian might not minimize the noiseless Hamiltonian. Inspired by rigorous results that the energy of the noiseless groundstate configuration is equal to the expectation value of the energy of the noisy Hamiltonian at the (nonzero) Nishimori temperature [J. Phys. Soc. Jpn., 62, 40132930 (1993)], we numerically study the decoding probability of the original noiseless ground state with noisy Hamiltonians in two space dimensions, as well as the DWave Inc.~Chimera topology. Our results suggest that thermal fluctuations might be beneficial during the optimization process in analog quantum annealing machines. [Preview Abstract] 
Monday, March 14, 2016 4:06PM  4:18PM 
C45.00007: Estimation of effective temperatures in a quantum annealer: Towards deep learning applications John RealpeG\'omez, Marcello Benedetti, Alejandro PerdomoOrtiz Sampling is at the core of deep learning and more general machine learning applications; an increase in its efficiency would have a significant impact across several domains. Recently, quantum annealers have been proposed as a potential candidate to speed up these tasks, but several limitations still bar them from being used effectively. One of the main limitations, and the focus of this work, is that using the device's experimentally accessible temperature as a reference for sampling purposes leads to very poor correlation with the Boltzmann distribution it is programmed to sample from. Based on quantum dynamical arguments, one can expect that if the device indeed happens to be sampling from a Boltzmannlike distribution, it will correspond to one with an instancedependent effective temperature. Unless this unknown temperature can be unveiled, it might not be possible to effectively use a quantum annealer for Boltzmann sampling processes. In this work, we propose a strategy to overcome this challenge with a simple effectivetemperature estimation algorithm. We provide a systematic study assessing the impact of the effective temperatures in the quantumassisted training of Boltzmann machines, which can serve as a building block for deep learning architectures. [Preview Abstract] 
Monday, March 14, 2016 4:18PM  4:30PM 
C45.00008: Hard scheduling problems for early quantum annealer ZHIHUI WANG, Tony Tran, Bryan O'Gorman, Minh Do, Jeremy Frank, Eleanor Rieffel We present a parameterized family of single machine scheduling problem that exhibits an easyhardeasy phase transition. As the parameter is varied, the problem goes through a fast transition from being almost trivial to find a solution to almost always has no solution, this sharp transition accompanies a peak in computational effort. While implementing realisticsized problems on an early quantum annealing device is still a challenge in near future, using a benchmarking problem set of small size but in a welldefined hard family, one can gain insight to a how the solving time scales for the whole family.[1] We will report quantum annealing results on this and other related problems. [1] E. G. Rieffel, D. Venturelli, B. OGorman, M. B. Do, E. M. Prystay, and V. N. Smelyanskiy, Quantum Information Processing 14, 1 (2015). [Preview Abstract] 
Monday, March 14, 2016 4:30PM  4:42PM 
C45.00009: Accurate Variational Description of Adiabatic Quantum Optimization Giuseppe Carleo, Bela Bauer, Matthias Troyer Adiabatic quantum optimization (AQO) is a quantum computing protocol where a system is driven by a timedependent Hamiltonian. The initial Hamiltonian has an easily prepared groundstate and the final Hamiltonian encodes some desired optimization problem. An adiabatic time evolution then yields a solution to the optimization problem. Several challenges emerge in the theoretical description of this protocol: on one hand, the exact simulation of quantum dynamics is exponentially complex in the size of the optimization problem. On the other hand, approximate approaches such as tensor network states (TNS) are limited to small instances by the amount of entanglement that can be encoded. I will present here an extension of the timedependent Variational Monte Carlo approach to problems in AQO. This approach is based on a general class of (JastrowFeenberg) entangled states, whose parameters are evolved in time according to a stochastic variational principle. We demonstrate this approach for optimization problems of the Ising spinglass type. A very good accuracy is achieved when compared to exact timedependent TNS on small instances. We then apply this approach to larger problems, and discuss the efficiency of the quantum annealing scheme in comparison with its classical counterpart. [Preview Abstract] 
Monday, March 14, 2016 4:42PM  4:54PM 
C45.00010: Optimizing Quantum Adiabatic Algorithm Hongye Hu, Biao Wu In quantum adiabatic algorithm, as the adiabatic parameter $s(t)$ changes slowly from zero to one with finite rate, a transition to excited states inevitably occurs and this induces an intrinsic computational error. We show that this computational error depends not only on the total computation time $T$ but also on the time derivatives of the adiabatic parameter $s(t)$ at the beginning and the end of evolution. Previous work (Phys. Rev. A 82, 052305) also suggested this result. With six typical paths, we systematically demonstrate how to optimally design an adiabatic path to reduce the computational errors. Our method has a clear physical picture and also explains the pattern of computational error. In this paper we focus on quantum adiabatic search algorithm although our results are general. [Preview Abstract] 
Monday, March 14, 2016 4:54PM  5:06PM 
C45.00011: Learning quantum annealing Elizabeth Behrman, James Steck We propose and develop a new quantum algorithm, whereby a quantum system can learn to anneal to a desired ground state. We demonstrate successful learning of entanglement for a twoqubit system, then bootstrap to larger systems. We also show that the method is robust to noise and decoherence. [Preview Abstract] 
Monday, March 14, 2016 5:06PM  5:18PM 
C45.00012: Josephson Circuits as Vector Quantum Spins Gabriel Samach, Andrew J. Kerman While superconducting circuits based on Josephson junction technology can be engineered to represent spins in the quantum transversefield Ising model, no circuit architecture to date has succeeded in emulating the vector quantum spin models of interest for nextgeneration quantum annealers and quantum simulators. Here, we present novel Josephson circuits which may provide these capabilities. We discuss our rigorous quantummechanical simulations of these circuits, as well as the larger architectures they may enable. This research was funded by the Office of the Director of National Intelligence (ODNI) and the Intelligence Advanced Research Projects Activity (IARPA) under Air Force Contract No. FA872105C0002. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of ODNI, IARPA, or the US Government. [Preview Abstract] 
Monday, March 14, 2016 5:18PM  5:30PM 
C45.00013: Distortion of a reduced equilibrium density matrix Iris Schwenk, Michael Marthaler We study a system coupled to external degrees of freedom, called bath, where we assume that the total system, consisting of system and bath is in equilibrium. An expansion in the coupling between system and bath leads to a general form of the reduced density matrix of the system as a function of the bath selfenergy. The coupling to the bath results in a renormalization of the energies of the system and in a change of the eigenbasis. We study the influence of bosonic degrees of freedom on the state of a six qubit system similar to the eight qubit unit cell of a quantum annealing processor examined by Lanting et al.\footnote{T. Lanting et al., Phys. Rev. X 4, 021041 (2014).}. [Preview Abstract] 
Monday, March 14, 2016 5:30PM  5:42PM 
C45.00014: Quantum annealing via quantum diffusion mediated by environment vadim Smelyanskiy, Davide Venturelli, Alejandro PerdomoOrtiz, Sergei Knysh, Mark Dykman We show that quantum diffusion near the quantum critical point can provide an efficient mechanism of opensystem quantum annealing. The analysis refers to an Ising spin chain in a slowly decreasing transverse field coupled to bosonic heat bath. The diffusion facilitates recombination of collective (multispin) excitations in the chain. It sharply slows down as the system moves away from the quantum critical region, leading to significant spatial fluctuations even in the absence of disorder. The excitation density reached by then nonmonotonically depends on the annealing rate. We find that obtaining an approximate solution via diffusionmediated quantum annealing can be faster than via classical Glauber dynamics or the closedsystem KibbleZurek mechanism. We study the scaling of the excitation density with the temperature and coupling constant to environment. [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. 
© 2023 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