CaltechAUTHORS
  A Caltech Library Service

(Sub)Exponential advantage of adiabatic Quantum computation with no sign problem

Gilyén, András and Hastings, Matthew B. and Vazirani, Umesh (2021) (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. In: STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. ACM , New York, NY, pp. 1357-1369. ISBN 978-1-4503-8053-9. https://resolver.caltech.edu/CaltechAUTHORS:20220802-839191000

[img] PDF - Published Version
Creative Commons Attribution.

848kB
[img] PDF - Submitted Version
See Usage Policy.

751kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20220802-839191000

Abstract

We demonstrate the possibility of (sub)exponential quantum speedup via a quantum algorithm that follows an adiabatic path of a gapped Hamiltonian with no sign problem. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected graph whose vertices are labeled by n-bit strings, and we can view the adiabatic evolution as an efficient O(poly(n))-time quantum algorithm for finding a specific “EXIT” vertex in the graph given the “ENTRANCE” vertex. On the other hand we show that if the graph is given via an adjacency-list oracle, there is no classical algorithm that finds the “EXIT” with probability greater than exp(−n^δ) using at most exp(n^δ) queries for δ= 1/5 − o(1). Our construction of the graph is somewhat similar to the “welded-trees” construction of Childs et al., but uses additional ideas of Hastings for achieving a spectral gap and a short adiabatic path.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3406325.3451060DOIArticle
https://arxiv.org/abs/2011.09495arXivDiscussion Paper
ORCID:
AuthorORCID
Gilyén, András0000-0001-5992-5743
Additional Information:© 2021 Copyright held by the owner/author(s). Attribution 4.0 International (CC BY 4.0) Part of this work was done while visiting the Simons Institute for the Theory of Computing; we gratefully acknowledge its hospitality. A.G. acknowledges funding provided by Samsung Electronics Co., Ltd., for the project “The Computational Power of Sampling on Quantum Computers”, and additional support by the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). U.V. was supported by the Vannevar Bush faculty fellowship N00014-17-1-3025, and US DOE National Quantum Initiative Science Research Centers, Quantum Systems Accelerator (QSA).
Group:Institute for Quantum Information and Matter
Funders:
Funding AgencyGrant Number
Samsung ElectronicsUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
NSFPHY-1733907
Vannever Bush Faculty FellowshipN00014-17-1-3025
Department of Energy (DOE)UNSPECIFIED
Subject Keywords:adiabatic quantum computation, sign-problem-free, sparse Hamiltonian, stoquastic, welded-trees, glued-trees, quantum walk
DOI:10.1145/3406325.3451060
Record Number:CaltechAUTHORS:20220802-839191000
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20220802-839191000
Official Citation:András Gilyén, Matthew B. Hastings, and Umesh Vazirani. 2021. (Sub)-Exponential Advantage of Adiabatic Quantum Computation with No Sign Problem. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC ’21), June 21–25, 2021, Virtual, Italy. ACM, New York, NY, USA, 13 pages. https://doi.org/10.1145/3406325.3451060
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116055
Collection:CaltechAUTHORS
Deposited By: George Porter
Deposited On:03 Aug 2022 15:49
Last Modified:03 Aug 2022 15:49

Repository Staff Only: item control page