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.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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 Paper
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
Funding AgencyGrant Number
Samsung ElectronicsUNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
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
Record Number:CaltechAUTHORS:20220802-839191000
Persistent URL:
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.
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:116055
Deposited By: George Porter
Deposited On:03 Aug 2022 15:49
Last Modified:03 Aug 2022 15:49

Repository Staff Only: item control page