Related papers: (Sub)Exponential advantage of adiabatic quantum computation with no sign problem

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

URL: http://arxiv.org/abs/2011.09495v1
Date: Wed, 18 Nov 2020 19:04:51 GMT
Title: (Sub)Exponential advantage of adiabatic quantum computation with no sign problem
Authors: Andr\'as Gily\'en and Umesh Vazirani
Abstract summary: 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.
Score: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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. This strengthens the superpolynomial separation recently proved by Hastings. The Hamiltonian that exhibits this speed-up comes from the adjacency matrix of an undirected graph, and we can view the adiabatic evolution as an efficient $\mathcal{O}(\mathrm{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^\delta)$ using at most $\exp(n^\delta)$ queries for $\delta= \frac15 - 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.

Related papers

Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing. How to efficiently implement CTQWs is a challenging issue. In this paper, we study implementation of CTQWs on sparse graphs.
arXiv Detail & Related papers (2024-08-20T05:20:55Z)
Exponential Quantum Advantage for Pathfinding in Regular Sunflower Graphs [5.173438526554426]
We find a class of graphs that allows exponential quantum-classical separation for the pathfinding problem with the adjacency list oracle. We provide an efficient quantum algorithm to find an $s$-$t$ path in the regular sunflower graph while any classical algorithm takes exponential time.
arXiv Detail & Related papers (2024-07-19T15:21:13Z)
Quantum algorithms for Hopcroft's problem [45.45456673484445]
We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
arXiv Detail & Related papers (2024-05-02T10:29:06Z)
Hamiltonian simulation for low-energy states with optimal time dependence [45.02537589779136]
We consider the task of simulating time evolution under a Hamiltonian $H$ within its low-energy subspace. We present a quantum algorithm that uses $O(tsqrtlambdaGamma + sqrtlambda/Gammalog (1/epsilon))$ queries to the block-encoding for any $Gamma$.
arXiv Detail & Related papers (2024-04-04T17:58:01Z)
Parameter-free Regret in High Probability with Heavy Tails [45.11667443216861]
We present new algorithms for online convex optimization over unbounded domains. We obtain parameter-free regret in high-probability given access only to potentially heavy-tailed subgradient estimates.
arXiv Detail & Related papers (2022-10-25T21:43:44Z)
Multimarked Spatial Search by Continuous-Time Quantum Walk [0.0]
We describe a framework for determining the computational complexity of spatial search by continuous-time quantum walk on arbitrary graphs. The quantum walk is driven by a Hamiltonian derived from the adjacency matrix of the graph modified by the presence of the marked vertices.
arXiv Detail & Related papers (2022-03-27T20:22:17Z)
The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
Graph Neural Network (GNN) whose output is identical to the graph function? In this paper, we fully answer this question and characterize the class of graph problems that can be represented by GNNs. We show that this condition can be efficiently verified by checking quadratically many constraints.
arXiv Detail & Related papers (2022-02-17T18:54:27Z)
A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
arXiv Detail & Related papers (2022-01-31T22:19:49Z)
Spatial Search on Johnson Graphs by Continuous-Time Quantum Walk [0.0]
We show that spatial search on Johnson graphs by continuous-time quantum walk achieves the lower bound $pisqrtN/2$ with success probability $1$ally for every fixed diameter. The proof is mathematically rigorous and can be used for other graph classes.
arXiv Detail & Related papers (2021-08-04T12:16:24Z)
Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$. We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
arXiv Detail & Related papers (2020-05-13T14:53:36Z)
Can graph properties have exponential quantum speedup? [5.101801159418223]
In particular, it is natural to ask whether exponential speedup is possible for (partial) graph properties. We show that the answer to this question depends strongly on the input model.
arXiv Detail & Related papers (2020-01-28T18:45:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.