Bulletin of the American Physical Society
APS March Meeting 2014
Volume 59, Number 1
Monday–Friday, March 3–7, 2014; Denver, Colorado
Session J35: Focus Session: Quantum Computing Architectures and Algorithms: Adiabatic Quantum Computation |
Hide Abstracts |
Sponsoring Units: GQI Room: 702 |
Tuesday, March 4, 2014 2:30PM - 2:42PM |
J35.00001: Symmetry-Protected Quantum Adiabatic Transistors Dominic J. Williamson, Stephen D. Bartlett An essential development in the history of computing was the invention of the transistor as it allowed logic circuits to be implemented in a robust and modular way. The physical characteristics of semiconductor materials were the key to building these devices. We aim to present an analogous development for quantum computing by showing that quantum adiabatic transistors (as defined by Flammia et al.) are built upon the essential qualities of symmetry-protected (SP) quantum ordered phases in one dimension. Flammia et al. and Renes et al. have demonstrated schemes for universal adiabatic quantum computation using quantum adiabatic transistors described by interacting spin chain models with specifically chosen Hamiltonian terms. We show that these models can be understood as specific examples of the generic situation in which all SP phases lead to quantum computation on encoded edge degrees of freedom by adiabatically traversing a symmetric phase transition into a trivial symmetric phase. This point of view is advantageous as it allows us to readily see that the computational properties of a quantum adiabatic transistor arise from a phase of matter rather than due to carefully tuned interactions. [Preview Abstract] |
Tuesday, March 4, 2014 2:42PM - 2:54PM |
J35.00002: Graph isomorphism and adiabatic quantum computing Frank Gaitan, Lane Clark In the Graph Isomorphism (GI) problem two N-vertex graphs G and G' are given and the task is to determine whether there exists a permutation of the vertices of G that preserves adjacency and maps G $\to $ G'. If yes (no), then G and G' are said to be isomorphic (non-isomorphic). The GI problem is an important problem in computer science and is thought to be of comparable difficulty to integer factorization. We present a quantum algorithm that solves arbitrary instances of GI, and which provides a novel approach to determining all automorphisms of a graph. The algorithm converts a GI instance to a combinatorial optimization problem that can be solved using adiabatic quantum evolution. Numerical simulation of the algorithm's quantum dynamics shows that it correctly distinguishes non-isomorphic graphs; recognizes isomorphic graphs; and finds the automorphism group of a graph. We also discuss the algorithm's experimental implementation and show how it can be leveraged to solve arbitrary instances of the NP-Complete Sub-Graph Isomorphism problem. [Preview Abstract] |
Tuesday, March 4, 2014 2:54PM - 3:06PM |
J35.00003: Improved Bounds for Eigenpath Traversal Hao-Tien Chiang, Guanlei Xu, Rolando Somma We present an improved bound on the length of the path defined by the ground states of a continuous family of Hamiltonians in terms of the spectral gap $\Delta$. We use this bound to obtain a better cost of recently proposed methods for quantum adiabatic state transformations and eigenpath traversal. In particular, we prove that a method based on evolution randomization, which is a simple extension of adiabatic quantum computation, has an average cost of order $1/\Delta^2$, and a method based on fixed-point search has a maximum cost of order $1/\Delta^{3/2}$. Additionally, if the Hamiltonians satisfy a frustration-free property, such costs can be further improved to order $1/\Delta^{3/2}$ and $1/\Delta$, respectively. Our methods offer an important advantage over adiabatic quantum computation when the gap is small, where the cost is of order $1/\Delta^3$. [Preview Abstract] |
Tuesday, March 4, 2014 3:06PM - 3:18PM |
J35.00004: Period Finding with Adiabatic Quantum Computation Itay Hen We outline an efficient quantum-adiabatic algorithm that solves Simon's problem, in which one has to determine the ``period,'' or xor-mask, of a given black-box function. We show that the proposed algorithm is exponentially faster than its classical counterpart and has the same complexity as the corresponding circuit-based algorithm. Together with other related studies, this result supports a conjecture that the complexity of adiabatic quantum computation is equivalent to the circuit-based computational model in a stronger sense than the well-known, proven polynomial equivalence between the two paradigms. We also discuss the importance of the algorithm and its implications for the existence of an optimal-complexity adiabatic version of Shor's integer factorization algorithm and the experimental implementation of the latter. [Preview Abstract] |
Tuesday, March 4, 2014 3:18PM - 3:30PM |
J35.00005: Distinguishing graphs with a quantum annealer using susceptibility measurements Matthew Wittmann, Itay Hen, A.P. Young Recently it has been proposed~[1] that the Graph Isomorphism (GI) problem could be solved using a quantum annealer. This is done by encoding the graphs into Ising Hamiltonians, identifying the vertices with spins and the edges with antiferromagnetic interactions. The idea is that measurements of simple observables during and at the end of the annealing process should distinguish non-isomorphic graphs. The first experimental study of the GI problem using D-Wave's quantum computer has been carried out by Vinci et al.~[2], utilizing measurements taken at the end of the annealing process. Here, we will present preliminary evidence that measurements taken part way through the annealing process, now obtainable using state-of-the-art devices, may offer better distinguishing capabilities.\\[4pt] [1] I. Hen and A. P. Young, Physical Review A \textbf{86} (2012).\\[0pt] [2] W. Vinci et al., arXiv:1307.1114. [Preview Abstract] |
Tuesday, March 4, 2014 3:30PM - 3:42PM |
J35.00006: Assessing claims of quantum annealing: Does D-Wave have a quantum computer? John Smolin, Graeme Smith There has recently been much publicity surrounding D-Wave's so-called quantum computing machines. Though there is little reason to expect that their highly decoherent devices actually perform quantum computation, they have persisted in making strong claims about the performance of their system in the scientific literature and to the press. Here we focus on showing that the evidence of quantumness given in the literature is extremely weak and is consistant with an effective classical description. We further show by comparing to the performance of classical simulated annealing that the idea that their current machines outperform a classical computers is unfounded. [Preview Abstract] |
Tuesday, March 4, 2014 3:42PM - 4:18PM |
J35.00007: Error Corrected Quantum Annealing with Hundreds of Qubits Invited Speaker: Kristen Pudenz Physical realizations of quantum computing are always threatened by decoherence, especially as the scale of the device increases. This makes the implementation of error correction crucial. We have developed error correction techniques tailored to quantum annealing using superconducting adiabatic quantum optimization processors. I will show experimental results for computations using up to 448 physical qubits on the D-Wave Two device. Scaling of code performance on both antiferromagnetic chains and random 2D Ising problems will be addressed, along with insights into device error mechanisms and choices of decoding strategy. The error correction substantially enhances the observed success probabilities. [Preview Abstract] |
Tuesday, March 4, 2014 4:18PM - 4:30PM |
J35.00008: Thermal Quantum Annealing on the D-Wave device Anurag Mishra, Walter Vinci, Tameem Albash, Paul Warburton, Daniel Lidar We report on new experimental results supporting previous work concluding that the D-Wave processor implements quantum annealing. We introduce techniques adopted to the D-Wave programmable annealer to correct for systematic fabrication and control errors. Correcting for systematic errors allows us to explore the behavior of the annealer at low energy scales, which were previously inaccessible. We describe the behavior of the annealer as we investigate the effect of thermal noise on the programmed Ising Hamiltonian. Thermal noise becomes dominant when we scale down the overall energy of the final-time Ising Hamiltonian, or increase the total annealing time. We found three qualitatively different thermal noise regimes; a high energy scale where ground state statistics dominates, a moderate noise regime regime where low lying excited states contribute, and a high thermal noise regime where the system dynamics are dominated by thermalization effects. The qualitative results are robust to increasing the size (number of qubits) of the benchmark Hamiltonian. We additionally investigated auto-correlations in the final state statistics. [Preview Abstract] |
Tuesday, March 4, 2014 4:30PM - 4:42PM |
J35.00009: Simulations of Thermal Quantum Annealing on the D-Wave Device Tameem Albash, Walter Vinci, Anurag Mishra, Paul Warburton, Daniel Lidar We report on classical and quantum simulations to model the open-system dynamics of the D-Wave programmable annealer as we increase the thermal noise level on the device. We consider three models for the device: (1) the evolution is described by a classical simulated annealer acting on the final-time Ising Hamiltonian; (2) the evolution is described by an O(3) model with a time-dependent Hamiltonian; (3) the evolution is described by a quantum adiabatic Markovian master equation with a time dependent Hamiltonian. We increase the thermal noise level by either decreasing the overall energy scale of the final-time Ising Hamiltonian or by increasing the total annealing time. Using a benchmark Ising Hamiltonian, we show that all three models give distinct predictions for the behavior of the system as the noise level on the device is increased. The only model that captures the results of the device over the entire range of noise levels studied is the quantum master equation, ruling out the two classical models considered here. [Preview Abstract] |
Tuesday, March 4, 2014 4:42PM - 4:54PM |
J35.00010: Performance of quantum annealing on random Ising problems implemented using the D-Wave Two Zhihui Wang, Joshua Job, Troels F. R{\O}nnow, Matthias Troyer, Daniel A. Lidar Detecting a possible speedup of quantum annealing compared to classical algorithms is a pressing task in experimental adiabatic quantum computing. In this talk, we discuss the performance of the D-Wave Two quantum annealing device on Ising spin glass problems. The expected time to solution for the device to solve random instances with up to 503 spins and with specified coupling ranges is evaluated while carefully addressing the issue of statistical errors. We perform a systematic comparison of the expected time to solution between the D-Wave Two and classical stochastic solvers, specifically simulated annealing, and simulated quantum annealing based on quantum Monte Carlo, and discuss the question of speedup. [Preview Abstract] |
Tuesday, March 4, 2014 4:54PM - 5:06PM |
J35.00011: Benchmarking the D-Wave Two Joshua Job, Zhihui Wang, Troels R{\O}nnow, Matthias Troyer, Daniel Lidar We report on experimental work benchmarking the performance of the D-Wave Two programmable annealer on its native Ising problem, and a comparison to available classical algorithms. In this talk we will focus on the comparison with an algorithm originally proposed and implemented by Alex Selby. This algorithm uses dynamic programming to repeatedly optimize over randomly selected maximal induced trees of the problem graph starting from a random initial state. If one is looking for a quantum advantage over classical algorithms, one should compare to classical algorithms which are designed and optimized to maximally take advantage of the structure of the type of problem one is using for the comparison. In that light, this classical algorithm should serve as a good gauge for any potential quantum speedup for the D-Wave Two. [Preview Abstract] |
Tuesday, March 4, 2014 5:06PM - 5:18PM |
J35.00012: Performance of quantum annealing under different Ising mappings and graph embeddings Bryan O'Gorman, Eleanor Rieffel, Davide Venturelli, Vadim Smelyanskiy To apply quantum annealing (QA) to solve optimization problems, an Ising Hamiltonian must be derived that encodes the sought solution in its ground state, while respecting QA hardware constraints. In general, there are a variety of ways to obtain a Hamiltonian with quadratic spin interactions from a given problem (mapping), and to derive from it a Hamiltonian that fits the hardware graph (embedding). The probability quantum annealing finds the ground state depends on the spectral and relaxation properties of the quantum spin model derived from these mapping and embedding procedures. In this work, we classify mappings and embeddings into categories and we perform a rigorous study of these families on the performance of QA on the D-Wave II quantum annealer to check the validity of theoretical hypotheses. We also discuss the effect of noise on this performance under different choices. Our test set includes a collection of hard combinatorial optimization problems arising in the field of operational planning. Our results illustrate ways in which the efficacy of quantum annealing depends on both the mapping and the embedding, and paves the way to the formulation of general prescriptions for how to encode fruitfully combinatorial optimization problems into quantum annealers. [Preview Abstract] |
Tuesday, March 4, 2014 5:18PM - 5:30PM |
J35.00013: Probing for quantum speedup on D-Wave Two Troels F. R{\O}nnow, Zhihui Wang, Joshua Job, Sergei V. Isakov, Sergio Boixo, Daniel Lidar, John Martinis, Matthias Troyer Quantum speedup refers to the advantage quantum devices can have over classical ones in solving classes of computational problems. In this talk we show how to correctly define and measure quantum speedup in experimental devices. We show how to avoid issues that might mask or fake quantum speedup. [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