Bulletin of the American Physical Society
APS March Meeting 2015
Volume 60, Number 1
Monday–Friday, March 2–6, 2015; San Antonio, Texas
Session Q38: Focus Session: Ground State Quantum Computing and Quantum Annealing |
Hide Abstracts |
Sponsoring Units: GQI Chair: Ryan Babbush, Harvard University Room: 212B |
Wednesday, March 4, 2015 2:30PM - 3:06PM |
Q38.00001: The Space-Time Circuit-to-Hamiltonian Construction and Its Applications Invited Speaker: Barbara Terhal We discuss how the dynamics of a D-dimensional quantum circuit can be captured in the ground-state of a D$+$1-dimensional space-time Hamiltonian. The action of this Hamiltonian restricted to space-like surfaces (as given by the causal structure of the quantum circuit) is again D-dimensional and fully captures the interaction structure of the original quantum circuit. We show how one can use this construction for D$=$1 to do universal adiabatic computation using a 2D interacting particle Hamiltonian. [Preview Abstract] |
Wednesday, March 4, 2015 3:06PM - 3:18PM |
Q38.00002: Dimensionality reduction for adiabatic quantum optimizer in presence of local disorder Gian Giacomo Guerreschi, Salvatore Mandr\`a, Al\'an Aspuru-Guzik Adiabatic quantum optimization (AQO) is a procedure to solve a vast class of optimization problems by slowly changing the Hamiltonian of a quantum system. The evolution time necessary for the algorithm to be successful scales inversely with the minimum energy gap encountered during the dynamics. Unfortunately, the direct calculation of such gap is strongly limited by the exponential growth in dimensionality of quantum systems. Although many special-purpose methods have been devised to reduce the effective dimensionality of the Hilbert space, they are strongly limited to particular classes of problems with evident symmetries. Here, we propose and implement a reduction method that does not rely on any explicit symmetry and which requires, under certain but quite general conditions, only a polynomial amount of classical resources. A natural and important application is the analysis of AQO in presence of local disorder. In this respect, we show that AQO, even when affected by random noise, can still be faster than any classical algorithm. [Preview Abstract] |
Wednesday, March 4, 2015 3:18PM - 3:30PM |
Q38.00003: Best-case performance of quantum annealers on native spin-glass benchmarks: How chaos can affect success probabilities Zheng Zhu, Andrew J. Ochoa, Firas Hamze, Stefan Schnabel, Helmut G. Katzgraber Recent tests performed on the D-Wave Two quantum annealer reveal no clear evidence of speedup over conventional technologies. Here, we present results from classical parallel-tempering Monte Carlo simulations of the archetypal benchmark problem, an Ising spin glass, on the native chip topology. Using realistic uncorrelated noise models for the D-Wave Two quantum annealer, we study the best-case fidelity, i.e., the probability that the ground-state configuration is affected by random fields and random bond fluctuations found on the chip. We compute upper-bound success probabilities for different instance classes based on these simple error models and present strategies on how to develop robust and hard benchmark instances. [Preview Abstract] |
Wednesday, March 4, 2015 3:30PM - 3:42PM |
Q38.00004: Role of Classical Hardness for Quantum Annealers Itay Hen, Victor Martin-Mayor The D-Wave Two chip presumably exploits quantum annealing effects to solve optimization problems. Whether D-wave's quantum annealer is capable of achieving real speedup over classical thermal annealers is a matter of investigation. In this context, specifically of importance is the question of how well quantum annealers perform on instances with rugged free-energy landscapes for which simulated annealing methods are expected to fail. I will describe attempts to identify very hard D-Wave-specific instances exhibiting ``temperature chaos'' by means of state-of-the-art methods (multi spin coding, parallel tempering simulations and stochastic time-series analysis), and present results pertaining to the performance of classical algorithms and the D-wave Two chip on these. [Preview Abstract] |
Wednesday, March 4, 2015 3:42PM - 3:54PM |
Q38.00005: Benchmarking using Frustrated Ising Problems with Planted Solutions Joshua Job, Itay Hen, Tameem Albash, Troels R{\O}nnow, Matthias Troyer, Daniel Lidar We introduce a method for generating families of benchmark problems that have a certain degree of tunable ``hardness,'' achieved by adjusting the amount of frustration. We construct such frustrated problems around ``planted solutions,'' representing a known ground state configuration. We construct such problems on the Chimera graph and use them to benchmark various optimization algorithms: simulated annealing (SA), simulated quantum annealing (SQA), the Shin-Smolin-Smith-Vazirani thermal rotor model (SSSV), and the Hamze-Freitas-Selby (HFS) algorithm, as well as the D-Wave device (DW2). We observe a universal hardness peak for all methods, and we observe that the optimal time for the numerical methods scales exponentially with the problem size. [Preview Abstract] |
Wednesday, March 4, 2015 3:54PM - 4:06PM |
Q38.00006: Annealing of Embedded Spin Glasses Salvatore Mandra, Davide Venturelli, Sergey Knysh, Vadim Smelyanskiy We discuss recent results on thermal and quantum annealing of random spin glasses on fully-connected graphs and on fully-connected bipartite graphs. After the description of the embedding of their classical Hamiltonian onto Chimera graphs, we discuss what are the optimal embedding parameters, in relation with the signatures of the quantum phase transitions occurring during the annealing. Finally, we compare numerical simulations and analytical expectations for both the embedded spin glass models with results on the non-embedded models and with runs on D-Wave Machine installed at NASA Ames. [Preview Abstract] |
Wednesday, March 4, 2015 4:06PM - 4:18PM |
Q38.00007: Quantum annealing of a semiclassical spin chain with defects Mark Dykman, Vadim Smelyanskiy We consider an Ising chain of ferromagnetically coupled large spins in a varying transverse magnetic field $H\equiv H_x$. The analysis is semiclassical. When the transverse field is strong, the energy spectrum has a gap. Once this gap goes to zero with decreasing $H$, for $H=H_c$ there is formed a Bogoliubov-type spatially uniform ``condensate", where the spin projections on the $z$-axis are $\propto (H_c-H)^{1/2}$. This opens a gap for excitations $\propto H_c-H$. We then consider a point defect that corresponds to the change $\delta J_n$ in the coupling constant between $n$ and $n+1$ spins. For $\delta J_n>0$, there emerges a pair of localized excitations for large $H$. As $H$ decreases, for some $\delta J_n$-dependent $H>H_c$ there is formed a local cloud of spins with nonzero $z$-component around the defect. It grows with further decreasing $H$. Remote defects interact very weakly. For small but nonzero temperatures, different defects should be able to align in the opposite directions, leading to nucleation of kinks between them. We study the evolution of the system as $H$ decreases, the possibility of forming kinks, kink tunneling, and the ultimate approach of the system to the ground state. We also study the case of antiferromagnetic defects. [Preview Abstract] |
Wednesday, March 4, 2015 4:18PM - 4:30PM |
Q38.00008: Investigations of a D-Wave Two: Ground States of Random Spanning Trees J.S. Hall, M.A. Novotny, T. Neuhaus, Kristel Michielsen The performance of a 496 qubit D-Wave Two quantum computer was investigated for two problems. The chip has a Chimera interaction graph G, an 8x8 lattice of clusters of 8 qubits. 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 G. Output is returned in terms of a spin configuration $\{s_j\}$, with $s_j$$=$$\pm 1$. We investigated spanning tree problems. A tree is a connected, undirected subgraph of G that contains no cycles, and a spanning tree is a tree which includes all of the vertices of G. We generated random spanning trees (RSTs), uniformly distributed over all spanning trees of G. In the first study, 100 RSTs with random $J_{i,j}$$\in$$\{-1,1\}$ and $h_j=0$ were generated on the full 8x8 graph G of the chip. Each RST problem was solved up to 100 times and the number of times the ground state energy was found was recorded. This procedure was repeated for square subgraphs G', with dimensions ranging from 2x2 to 7x7. In the second study, the ground state was randomly chosen to be $s_j$$=$$\pm 1$, the $J_{i,j}$ and $h_j$ strengths were calculated from a quadratic Hamiltonian that had the given ground state, and the probability that the D-Wave Two found the ground state was measured. [Preview Abstract] |
Wednesday, March 4, 2015 4:30PM - 4:42PM |
Q38.00009: Reexamining classical and quantum models for the D-Wave One processor Tameem Albash, Troels Ronnow, Matthias Troyer, Daniel Lidar We revisit the evidence for quantum annealing in the D-Wave One device (DW1) based on the study of random Ising instances. We consider measures that account for ground state degeneracy and the distributions of excited states, and present evidence [1] that for these new measures neither SQA nor the classical rotor model correlate perfectly with the DW1 experiments, despite both models correlating very well with the DW1 ground state success probabilities[2,3]. We thus provide evidence that SQA and the classical rotor model, both of which are classically efficient algorithms, do not satisfactorily explain all the DW1 data. \\[4pt] [1] T. Albash, T. F. R{\o}nnow, M. Troyer, and D. A. Lidar, arXiv:1409.3827. \\[0pt] [2] S. Boixo, T.F. R{\o}nnow, S.V. Isakov, Z. Wang, D. Wecker, D.A. Lidar, J.M. Martinis, M. Troyer, Nat. Phys. 10(3), 218 (2014).\\[0pt] [3] S. W. Shin, G. Smith, J. A. Smolin, and U. Vazirani, arXiv:1401.7087 (2014). [Preview Abstract] |
Wednesday, March 4, 2015 4:42PM - 4:54PM |
Q38.00010: Optimal quantum annealing in p-spin model Kostyantyn Kechedzhi, Vadim Smelyanskiy In this work we are looking to understand the physical mechanisms of quantum speedup in quantum annealing devices. We consider a simplified Hamiltonian that can be addressed analytically using a semiclassical approximation. The Hamiltonian models a typical potential barrier that can trap the system in a metastable state and thus prevent it from reaching the ground state. This situation is common in complex optimization problems such as a spin glass. The model we consider consists of Ising spins forming a fully connected graph with interaction energy proportional to a product of p individual spin operators (p=2 would correspond to the pair interaction in, for example, a ferromagnet). At p $>$ 2 this model demonstrates 1st order phase transition associated with exponential scaling of the quantum annealing computation time with the system size. We analyze the characteristics of the potential barrier that determine the efficiency of quantum annealing. We also identify the optimal regime for quantum annealing. [Preview Abstract] |
Wednesday, March 4, 2015 4:54PM - 5:06PM |
Q38.00011: Isothermal quantum annealing of the 1D transverse Ising chain Davide Venturelli, Vadim Smelyanskiy, Alejandro Perdomo-Ortiz, Sergei Isakov, Sergey Knysh, Mark Dykman We present a quantum annealing strategy to solve optimization problems that relies on the effect of the external environment on the quantum system (isothermal protocol). We define the isothermal complexity as the scaling of the longest instantaneous relaxation time with the number of qubits in the region after the critical point where the first excitation gap equals to the temperature. We calculate this complexity for the case of 1D transverse field Ising chain coupled to the bosonic environment. We show that the quantum annealing complexity bottleneck is determined by the quantum diffusion limited recombination of the fermions that represent system excitations. We present the analytical results as well as numerical study of the system dynamics and annealing complexity. [Preview Abstract] |
Wednesday, March 4, 2015 5:06PM - 5:18PM |
Q38.00012: Computational Role of Collective Tunneling in a Quantum Annealer Hartmut Neven, Vadim Smelyanskiy, Sergio Boixo, Alireza Shabani, Sergei Isakov, Mark Dykman, Vasil Denchev, Mohammad Amin, Anatoly Smirnov, Masoud Mohseni We show that quantum resources in the D-Wave Two processor enhance the probability to reach the global minimum of an optimization problem. We implemented a series of structural primitives on the device governed by non-convex optimization landscapes consisting of just one global and one false local minima. The quantum adiabatic evolution path over product states connects the initial global minimum with the final false minimum. The final global minimum can only be reached by traversing an energy barrier. Experimentally we found that the D-Wave Two quantum annealer returns the solution that minimizes the energy with consistently higher probability than physically plausible models of the hardware that only employ product states and thermal activation over the barrier and do not allow for multiqubit tunneling transitions. On the contrary open system quantum mechanical models are in very close correspondence with the hardware data without using any fitting parameters. We additionally performed a series of experiments in which we varied the temperature of the chip. We find that the observed correlation between the temperature and success probability is consistent only with quantum models. We also demonstrate that the success probabilities of path integral Monte Carlo are consistently lo [Preview Abstract] |
Wednesday, March 4, 2015 5:18PM - 5:30PM |
Q38.00013: Collective disispative tunneling during quantum annealing on D-Wave II device Vadim Smelyanskiy, Sergio Boixo, Alireza Shabani, Sergey Isakov, Mark Dykman, Vasil Denchev, Mohammad Amin, Anatoly Smirnov, Masoud Mohseni, Hartmut Neven We develop theory based on NIBA Quantum Master Equation to describe the multiqubit tunneling in the evolution of a programmable quantum annealer. We describe D-Wave II performance in the non-convex problems realized by frustrated networks of qubit clusters with strong intra-cluster coupling. We show that the collective effect of the environment is suppressed near the avoided crossing leading to coherent tunneling in that region. In a later stage of the annealing z-magnetizations of qubit clusters increase steeply as a manifestation of the spontaneous symmetry breaking giving rise to a substantial polaronic effect. Transition to the final solution state proceeds via tunneling of one of the qubit clusters as a whole, accompanied by the reorganization of the environmental degrees of freedom and absorption of the residual energy from the qubit system. Transition rate decreases exponentially fast with time after avoided crossing leading to the freezing of the portion of population in the local minimum. We used noise parameters from the single qubit MRT experiments taken on the same device. Model predictions for multiqubit quantum annealing on the above problems are in a very close correspondence with the data collected on D-Wave II device without using any fitting parameters. [Preview Abstract] |
Wednesday, March 4, 2015 5:30PM - 5:42PM |
Q38.00014: Optimising simulated quantum annealing, simulated annealing and a mean-field algorithm to find ground states of Ising spin glasses Damian S. Steiger, Troels F. R{\O}nnow, Matthias Troyer We report on benchmarks of finding the ground states of Ising spin glasses on chimera graphs using simulated annealing, simulated quantum annealing and a mean-field quantum annealing algorithm. We analyze the performance of these algorithms by calculating the empirical time-to-solution distribution function and extrapolating their tails, which describe the hard instances. All algorithms show an increasing fat-tail with larger system size, and therefore the average time-to-solution is dominated by the run-times of the hard instances. These tails can be significantly reduced by optimizing the annealing time and temperature. Especially the hard instances of simulated quantum annealing are solved much faster by using a shorter annealing time or higher temperature. [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. |
© 2020 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
1 Research Road, Ridge, NY 11961-2701
(631) 591-4000
Office of Public Affairs
529 14th St NW, Suite 1050, Washington, D.C. 20045-2001
(202) 662-8700