Bulletin of the American Physical Society
APS March Meeting 2014
Volume 59, Number 1
Monday–Friday, March 3–7, 2014; Denver, Colorado
Session T35: Focus Session: Quantum Computing Architectures and Algorithms: Quantum Algorithms |
Hide Abstracts |
Sponsoring Units: GQI Room: 702 |
Thursday, March 6, 2014 11:15AM - 11:51AM |
T35.00001: Exponential improvement in precision for Hamiltonian-evolution simulation Invited Speaker: Dominic Berry We provide a quantum algorithm for simulating the dynamics of sparse Hamiltonians with complexity sublogarithmic in the inverse error, an exponential improvement over previous methods for Hamiltonian simulation. Specifically, we show that a d-sparse Hamiltonian H can be simulated for time t with precision eps using O(T log($\tau$/eps)/loglog($\tau$/eps)) queries, where T = d$^2$ $||$H$||$ t. The algorithm is also time efficient. Unlike previous approaches based on product formulas, its query complexity is independent of the number of qubits acted on and its time complexity is only logarithmic in the norm of the derivative of the Hamiltonian. Our algorithm is based on a significantly improved simulation of the continuous- and fractional-query models using discrete quantum queries, showing that the former models are not much more powerful even for very small error. We also dramatically simplify the analysis of this conversion, avoiding the need for a complex fault correction procedure. Our simplification relies on a new form of ``oblivious amplitude amplification'' that can be applied even though the reflection about the input state is unavailable. Finally, we prove lower bounds showing that, surprisingly, our algorithms are optimal as a function of the error. [Preview Abstract] |
Thursday, March 6, 2014 11:51AM - 12:03PM |
T35.00002: Finding structural anomalies in star graphs by quantum walks: A general approach Seth Cottrell, Mark Hillery We develop a general theory for a quantum-walk search on a star graph. A star graph has $N$ edges each of which is attached to a central vertex. A graph $G$ is attached to one of these edges, and we would like to find out to which edge it is attached. This is done by means of a quantum walk, a quantum version of a random walk. This walk contains $O(\sqrt{N})$ steps, which represents a speedup over a classical search, which would require $O(N)$ steps. The overall graph, star plus $G$, is divided into two parts, and we find that for a quantum speedup to occur, the eigenvalues associated with these two parts in the $N\rightarrow\infty$ limit must be the same. Our theory tells us how the initial state of the walk should be chosen, and how many steps the walk must make in order to find $G$. [Preview Abstract] |
Thursday, March 6, 2014 12:03PM - 12:15PM |
T35.00003: Renormalization for Quantum Walks Stefan Falkner, Stefan Boettcher, Renato Portugal Quantum walks have been studied extensively on regular lattices over the last 20 years. Generally, two remarkable differences to the classical random walk emerge: the quantum walk spreads faster and can also be partly localized, even in the unbiased case [1]. But so far, only translational invariant lattices allow analytical insights into the underlying mechanisms. We propose a renormalization group treatment for the quantum walk to study its behavior on self-similar graphs [2]. It allows us to obtain large system sizes numerically and to gain insights by analyzing a set of recursion equations asymptotically. On the dual Sierpinsky gasket, we find a rich phenomenology for the spreading in a system without translational invariance. The quantum interference localizes the walk such that the access probability declines as a power law from the initial site, fully localizing the walk in the infinite system limit. But, for finite systems, a small fraction of the wave function spreads faster than the corresponding classical random walk through the entire system.\\[4pt] [1] N. Inui, et. al., Phys. Rev. E 72.5 (2005)\\[0pt] [2] S. Boettcher, et. al., arXiv:1311.3369\\[0pt] [3] A. Ambainis, et al., Proceedings of the thirty-third annual ACM symposium on Theory of computing. ACM, 2001 [Preview Abstract] |
Thursday, March 6, 2014 12:15PM - 12:27PM |
T35.00004: Open Quantum Walks with Noncommuting Jump Operators Roland Cristopher Caballar, Francesco Petruccione, Ilya Sinayskiy We examine homogeneous open quantum walks along a line, wherein each forward step is due to one quantum jump operator, and each backward step due to another quantum jump operator. We assume that these two quantum jump operators do not commute with each other. We show that if the system has $N$ internal degrees of freedom, for particular forms of these quantum jump operators, we can obtain exact probability distributions which fall into two distinct classes, namely Gaussian distributions and solitonic distributions. We also show that it is possible for a maximum of 2 solitonic distributions to be present simultaneously in the system. Finally, we consider applications of these classes of jump operators in quantum state preparation and quantum information. [Preview Abstract] |
Thursday, March 6, 2014 12:27PM - 1:03PM |
T35.00005: Performance of simulated annealing, simulated quantum annealing and the D-Wave devices on hard spin glass instances Invited Speaker: Matthias Troyer Quantum annealing - a finite temperature version of the quantum adiabatic algorithm - combines the classical technology of slow thermal cooling with quantum mechanical tunneling, to try bring a physical system towards its ground state. The Canadian company D-Wave systems has recently built and sold programmable devices that are designed to use this effect to find solutions to optimization problems. These devices raise many questions, in particular whether they outperform classical algorithms and show quantum speedup. To address this question I will start with an overview of simulated annealing (SA) and simulated quantum annealing (SQA). SA is a classical optimization method in which the cost function to be optimized is viewed as the energy of a physical system which is simulated in a Monte Carlo simulation. Slowly lowering the temperature in the simulation brings the system into a (local) energy minimum. SQA is a similar process, but where instead of lowering the temperature a control parameter is varied in quantum Monte Carlo (QMC) simulation, which (at constant temperature) brings a quantum system from the simple ground state of an initial Hamiltonian to a low-energy state of the final model implementing the same cost function. I will review evidence on the question whether SQA (or QA) is better at finding low energy states that classical SA. I will then present new results which show that SQA has problems in solving hard instances of spin glass problems: the distribution of times to solution exhibit very fat tails with slow power-law decays, indicating the presence of extremely hard to solve instances with the mean time to solution being dominated by rare instances. In SA, while there are also fat tails, they drop faster than in SQA, thus giving SA the edge when considering hard problem instances. Analyzing the performance of a 512-qubit D-Wave Two device we find the same issues with hard instances as in SQA and find no evidence for quantum speedup when comparing the performance on random spin glass instances to that of an optimized SA algorithm. [Preview Abstract] |
Thursday, March 6, 2014 1:03PM - 1:15PM |
T35.00006: The quantum fractional Fourier transform Nga Nguyen, Rolando Somma The Fourier transform (FT) is ubiquitous in signal processing, as it can be used to filter noise. The digital version, often named the discrete Fourier transform, when formulated on a basis of quantum states, is the quantum Fourier transform (QFT). The efficiency in the implementation of the QFT is the main reason for several quantum speedups, including the one for factoring and the one in phase estimation at the Heisenberg limit. The fractional FT (frFT) is a generalization of the FT. The frFT has recently gained attention in signal analysis as it can filter noise in scenarios where the FT is not useful. Quantum frFTs (QfrFTs), however, have never been proposed, constructed, or applied. In this work we propose a QfrFT and show that a good approximation of this transformation can be implemented on a quantum computer with exponentially less resources than those required for its conventional implementation. We then analyze some problems in signal analysis for which our defined QfrFT is useful. [Preview Abstract] |
Thursday, March 6, 2014 1:15PM - 1:27PM |
T35.00007: Implementing quantum Fourier transform with integrated photonic devices Gelo Noel Tabia Many quantum algorithms that exhibit exponential speedup over their classical counterparts employ the quantum Fourier transform, which is used to solve interesting problems such as prime factorization [1]. Meanwhile, nonclassical interference of single photons achieved on integrated platforms holds the promise of achieving large-scale quantum computation with multiport devices [2]. An optical multiport device can be built to realize any quantum circuit as a sequence of unitary operations performed by beam splitters and phase shifters on path-encoded qudits. In this talk, I will present a recursive scheme for implementing quantum Fourier transform with a multimode interference photonic integrated circuit. \\[4pt] [1] P.W. Shor, SIAM J. Comput. 26, 1484-1509 (1997).\\[0pt] [2] A. Politi, M. J. Cryan, J. G. Rarity, S. Yu, J. L. O'Brien, Science 320, 646-649 (2008). [Preview Abstract] |
Thursday, March 6, 2014 1:27PM - 1:39PM |
T35.00008: Quantum Inference on Bayesian Networks Theodore Yoder, Guang Hao Low, Isaac Chuang Because quantum physics is naturally probabilistic, it seems reasonable to expect physical systems to describe probabilities and their evolution in a natural fashion. Here, we use quantum computation to speedup sampling from a graphical probability model, the Bayesian network. A specialization of this sampling problem is approximate Bayesian inference, where the distribution on query variables is sampled given the values $e$ of evidence variables. Inference is a key part of modern machine learning and artificial intelligence tasks, but is known to be NP-hard. Classically, a single unbiased sample is obtained from a Bayesian network on $n$ variables with at most $m$ parents per node in time $\mathcal{O}( n m P(e)^{-1/2})$, depending critically on $P(e)$, the probability the evidence might occur in the first place. However, by implementing a quantum version of rejection sampling, we obtain a square-root speedup, taking $\mathcal{O}(n 2^m P(e)^{-\frac12})$ time per sample. The speedup is the result of amplitude amplification, which is proving to be broadly applicable in sampling and machine learning tasks. In particular, we provide an explicit and efficient circuit construction that implements the algorithm without the need for oracle access. [Preview Abstract] |
Thursday, March 6, 2014 1:39PM - 1:51PM |
T35.00009: A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators Zhe Wang, Alireza Marandi, Kai Wen, Robert L. Byer, Yoshihisa Yamamoto A degenerate optical parametric oscillator network is proposed to solve the NP-hard problem of finding a ground state of the Ising model. The underlying operating mechanism originates from the bistable output phase of each oscillator and the inherent preference of the network in selecting oscillation modes with the minimum photon decay rate. Computational experiments are performed on all instances reducible to the NP-hard MAX-CUT problems on cubic graphs of order up to 20. The numerical results reasonably suggest the effectiveness of the proposed network. [Preview Abstract] |
Thursday, March 6, 2014 1:51PM - 2:03PM |
T35.00010: Quantum Game of Life Aaron Glick, Lincoln Carr, Tommaso Calarco, Simone Montangero In order to investigate the emergence of complexity in quantum systems, we present a quantum game of life, inspired by Conway's classic game of life. Through Matrix Product State (MPS) calculations, we simulate the evolution of quantum systems, dictated by a Hamiltonian that defines the rules of our quantum game. We analyze the system through a number of measures which elicit the emergence of complexity in terms of spatial organization, system dynamics, and non-local mutual information within the network. [Preview Abstract] |
Thursday, March 6, 2014 2:03PM - 2:15PM |
T35.00011: Embedding Quantum Simulator Roberto Di Candia, Bernab\'e Mejia, Hernan Castillo, Julen Simon Pedernales, Jorge Casanova, Enrique Solano We introduce the concept of embedding quantum simulator, a paradigm allowing efficient computation of dynamical quantities requiring full quantum tomography in a standard quantum simulator (one-to-one quantum simulator). The concept consists in the suitable encoding of a simulated quantum dynamics in the enlarged Hilbert space of an embedding quantum simulator. In this manner, non-trivial quantities are mapped onto physical observables, overcoming the necessity of full tomography, and reducing drastically the experimental requirements. As examples, we discuss how to evaluate entanglement monotones and time correlation functions, each in a suitable embedding quantum simulator. Finally, we expect that the proposed embedding framework paves the way for a general theory of enhanced one-to-one quantum simulators. [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