Bulletin of the American Physical Society
APS March Meeting 2015
Volume 60, Number 1
Monday–Friday, March 2–6, 2015; San Antonio, Texas
Session L38: Focus Session: Quantum Algorithms |
Hide Abstracts |
Sponsoring Units: GQI Chair: Nathan Wiebe, Microsoft Research Room: 212B |
Wednesday, March 4, 2015 8:00AM - 8:12AM |
L38.00001: Programming and Tuning a Quantum Annealing Device to Solve Real World Problems Alejandro Perdomo-Ortiz, Bryan O'Gorman, Joseph Fluegemann, Vadim Smelyanskiy Solving real-world applications with quantum algorithms requires overcoming several challenges, ranging from translating the computational problem at hand to the quantum-machine language to tuning parameters of the quantum algorithm that have a significant impact on the 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. Although we will focus on applications of interest to NASA's Quantum Artificial Intelligence Laboratory, the methods and concepts presented here apply to a broader family of hard discrete optimization problems, including those that occur in many machine-learning algorithms. [Preview Abstract] |
Wednesday, March 4, 2015 8:12AM - 8:24AM |
L38.00002: Improved mapping of the travelling salesman problem for quantum annealing Matthias Troyer, Bettina Heim, Ethan Brown, David Wecker We consider the quantum adiabatic algorithm as applied to the travelling salesman problem (TSP). We introduce a novel mapping of TSP to an Ising spin glass Hamiltonian and compare it to previous known mappings. Through direct perturbative analysis, unitary evolution, and simulated quantum annealing, we show this new mapping to be significantly superior. We discuss how this advantage can translate to actual physical implementations of TSP on quantum annealers. [Preview Abstract] |
Wednesday, March 4, 2015 8:24AM - 8:36AM |
L38.00003: Computational Bottlenecks of Quantum Adiabatic Annealing Sergey Knysh Quantum annealing in a transverse field with rate $d\Gamma/dt$ inversely proportional to the system size $N$ suppresses non-adiabatic transitions for fully connected spin glass such as the Sherrington-Kirpatrick (SK) model at the quantum critical point. This alone is not sufficient to ensure that the problem is solvable in polynomial time. I conjecture the appearance of small gaps associated with macroscopic tunneling events deep in the spin glass phase. This effect is demonstrated rigorously for the annealing of a toy model that shares a set of crtical exponents with SK model: Hopfield network with two Gaussian patterns. It presents with $0.15 \ln N$ additional bottlenecks with gaps that scale as a stretched exponential $\exp\bigl[-c(N\Gamma)^{3/4}\bigr]$. Further, I extend the analysis to the $\rho$-landscapes model (random energy model with correlations) which more faithfully represents real spin glasses. [Preview Abstract] |
Wednesday, March 4, 2015 8:36AM - 8:48AM |
L38.00004: ABSTRACT WITHDRAWN |
Wednesday, March 4, 2015 8:48AM - 9:00AM |
L38.00005: Quantum learning robust to noise John Smolin, Andrew Cross, Graeme Smith Noise is often regarded as anathema to quantum computation, but in some settings it can be an unlikely ally. We consider the problem of learning the class of n-bit parity functions by making queries to a quantum example oracle. In the absence of noise, quantum and classical parity learning are easy and almost equally powerful, both information-theoretically and computationally. We show that in the presence of noise this story changes dramatically. Indeed, the classical learning problem is believed to be intractable, while the quantum version remains efficient. Depolarizing the qubits at the oracle's output at any constant nonzero rate does not increase the computational (or query) complexity of quantum learning more than logarithmically. However, the problem of learning from corresponding classical examples is the Learning Parity with Noise (LPN) problem, for which the best known algorithms have superpolynomial complexity. This creates the possibility of observing a quantum advantage with a few hundred noisy qubits. The presence of noise is essential for creating this quantum-classical separation. [Preview Abstract] |
Wednesday, March 4, 2015 9:00AM - 9:12AM |
L38.00006: Quantum algorithm for topological and geometric analysis of data Seth Lloyd, Paolo Zanardi, Silvano Garnerone Topological methods for analyzing data sets provide a powerful technique for extracting useful information from data. Data that represents geometric features of the world typically gives a distorted picture of those features, if only because the devices and systems that sense the world and that generate the data by their very nature induce distortions. By definition, topological features are those that persist under continuous distortions of the data. Topological methods can therefore identify features of the real system from which the data was collected, but that have been distorted by the data collection process. Persistent homology is a sophisticated tool for identifying such topological features --connected components, holes, or voids -- and for determining how such features persist as the data is viewed at different scales. This talk presents quantum machine learning algorithms for calculating Betti numbers in persistent homology, and for finding eigenvectors and eigenvalues of the combinatorial Laplacian (the quantities that famously allow one to ``hear the shape of a drum''). The algorithms provide an exponential speedup over classical algorithms for topological and geometrical data analysis. [Preview Abstract] |
Wednesday, March 4, 2015 9:12AM - 9:24AM |
L38.00007: On the Chemical Basis of Trotter-Suzuki Errors in Quantum Chemistry Simulation Ryan Babbush, Jarrod McClean, Dave Wecker, Al\'an Aspuru-Guzik, Nathan Wiebe Although the simulation of quantum chemistry is one of the most anticipated applications of quantum computing, the scaling of known upper bounds on the complexity of these algorithms is daunting. Prior work has bounded errors due to Trotterization in terms of the norm of the error operator and analyzed scaling with respect to the number of spin-orbitals. However, we find that these error bounds can be loose by up to sixteen orders of magnitude for some molecules. Furthermore, numerical results for small systems fail to reveal any clear correlation between ground state error and number of spin-orbitals. We instead argue that chemical properties, such as the maximum nuclear charge in a molecule and the filling fraction of orbitals, can be decisive for determining the cost of a quantum simulation. Our analysis motivates several strategies to use classical processing to further reduce the required Trotter step size and to estimate the necessary number of steps, without requiring additional quantum resources. Finally, we demonstrate improved methods for state preparation techniques which are asymptotically superior to proposals in the simulation literature. [Preview Abstract] |
Wednesday, March 4, 2015 9:24AM - 10:00AM |
L38.00008: Simulating Hamiltonian Dynamics with a Truncated Taylor Series Invited Speaker: Rolando Somma One of the main motivations for quantum computers is their ability to efficiently simulate the dynamics of quantum systems. Since the mid-1990s, many algorithms have been developed to simulate Hamiltonian dynamics on a quantum computer, with applications to problems such as simulating spin models and quantum chemistry. While it is now well known that quantum computers can efficiently simulate Hamiltonian dynamics, ongoing work has improved the performance and expanded the scope of such simulations. In this talk, I will describe a very simple and efficient algorithm for simulating Hamiltonian dynamics on a quantum computer by approximating the truncated Taylor series of the evolution operator. This algorithm can simulate the time evolution of a wide variety of physical systems. The cost of this algorithm depends only logarithmically on the inverse of the desired precision, and can be shown to be optimal. Such a cost also represents an exponential improvement over known methods for Hamiltonian simulation based on, e.g., Trotter-Suzuki approximations. Roughly speaking, doubling the number of digits of accuracy of the simulation only doubles the complexity. The new algorithm and its analysis are highly simplified due to a technique for implementing linear combinations of unitary operations to directly apply the truncated Taylor series. \\[4pt] This is joint work with Dominic Berry, Andrew Childs, Richard Cleve, and Robin Kothari. [Preview Abstract] |
Wednesday, March 4, 2015 10:00AM - 10:12AM |
L38.00009: Scaling of Quantum Walks on Complex Networks Stefan Boettcher, Stefan Falkner, Renato Portugal I will describe the renormalization group method (RG) as applied to master equations with a unitary propagator. It allows to determine many asymptotic properties of quantum walks, although I will focus here on the walk dimension $d_w$, which describes the similarity solution, $\rho(x,t)\sim f\left(|x|^{d_w}/t\right)$, for the probability density function $\rho$. We can calculate $d_w$ to arbitrary accuracy for a number of networks, such as the dual Sierpinksi gasket, small-world Hanoi networks, or Migdal-Kadanoff lattices, which we have verified with direct simulations. However, due to unitarity, the asymptotic solution of the RG equations as well as procedures to implement RG approximately for arbitrary networks remain elusive. Yet, based on the exact RG for those fractal networks, we can conjecture a few general conclusions, for instance, that $d_w$ for a discrete-time quantum walk is always half of that for the random walk on the same $r$-regular network, when driven with the Grover coin. (This talk summarizes our work in http://dx.doi.org/10.1103/PhysRevA.90.032324 and http://arxiv.org/abs/1410.7034.) [Preview Abstract] |
Wednesday, March 4, 2015 10:12AM - 10:24AM |
L38.00010: An Easy Method for Finding the Scattering Coefficients of Quantum Graphs and Some Applications Seth Cottrell Quantum walks are roughly analogous to classical random walks, and like classical walks they have been used to find new (quantum) algorithms. When studying the behavior of large graphs or combinations of graphs it has often been useful to find the response of a subgraph to signals of different frequencies. In this talk I'll be presenting a simple technique for quickly finding the scattering coefficients of any quantum graph. This is done by imitating the scattering states using normalizable states on a modified version of the graph. These scattering coefficients can be expressed entirely in terms of the characteristic polynomial of the graph's time-step operator. With these coefficients in hand we can replace an entire subgraph with a single vertex whose behavior is frequency dependent. This gives us a powerful set of tools for rapidly understanding the behavior of more complex structures. Time permitting, I will apply these tools to several types of graphs (star, complete, tree) demonstrating how we can gain information about the structure of these graphs by bouncing signals off of them, describing the limitations on what information cannot be accessed, and even show how to construct some computations using quantum walks that can be run in faster than classical time. [Preview Abstract] |
Wednesday, March 4, 2015 10:24AM - 11:00AM |
L38.00011: Variational Quantum Eigensolver: How to Use Any Quantum Device in Your Lab to Perform Quantum Simulation Invited Speaker: Jarrod McClean Quantum devices offer a way to simulate and study states that currently cannot be efficiently stored or manipulated on classical computers. Unfortunately, many quantum algorithms designed to simulate such states are prohibitively expensive in terms of quantum resources such as coherence time. In this talk I will review a recently introduced technique, the Variational Quantum Eigensolver, that has minimal coherence and can utilize any quantum device capable of basic state preparation and measurement for a quantum advantage in the simulation of physical quantum states. I will also introduce the problem of simulation of molecular systems in quantum chemistry and discuss recent advances in understanding and reducing the costs associated with this problem in our and related algorithms. [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