Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userQuantum Walk Sampling by Growing Seed Sets
72
0
0.0
(
0
)
Authors
Simon Apers
Ask ChatGPT about the research
No Arabic abstract
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as $widetilde{O}(m^{1/3} delta^{-1/3})$, with $m$ the number of edges and $delta$ the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for $st$-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an $n$-node graph in time $widetilde{O}(2^{n/3})$, surpassing the $Omega(2^{n/2})$ barrier set by index erasure.
rate research
Read More
Expansion testing aims to decide whether an $n$-node graph has expansion at least $Phi$, or is far from any such graph. We propose a quantum expansion tester with complexity $widetilde{O}(n^{1/3}Phi^{-1})$. This accelerates the $widetilde{O}(n^{1/2}Phi^{-2})$ classical tester by Goldreich and Ron [Algorithmica 02], and combines the $widetilde{O}(n^{1/3}Phi^{-2})$ and $widetilde{O}(n^{1/2}Phi^{-1})$ quantum speedups by Ambainis, Childs and Liu [RANDOM 11] and Apers and Sarlette [QIC 19], respectively. The latter approach builds on a quantum fast-forwarding scheme, which we improve upon by initially growing a seed set in the graph. To grow this seed set we use a so-called evolving set process from the graph clustering literature, which allows to grow an appropriately local seed set.
The main results on quantum walk search are scattered over different, incomparable frameworks, most notably the hitting time framework, originally by Szegedy, the electric network framework by Belovs, and the MNRS framework by Magniez, Nayak, Roland and Santha. As a result, a number of pieces are currently missing. For instance, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements. In recent work by Ambainis et al., this problem was resolved for the more restricted hitting time framework, in which quantum walks must start from the stationary distribution. We present a new quantum walk search framework that unifies and strengthens these frameworks. This leads to a number of new results. For instance, the new framework not only detects, but finds marked elements in the electric network setting. The new framework also allows one to interpolate between the hitting time framework, which minimizes the number of walk steps, and the MNRS framework, which minimizes the number of times elements are checked for being marked. This allows for a more natural tradeoff between resources. Whereas the original frameworks only rely on quantum walks and phase estimation, our new algorithm makes use of a technique called quantum fast-forwarding, similar to the recent results by Ambainis et al. As a final result we show how in certain cases we can simplify this more involved algorithm to merely applying the quantum walk operator some number of times. This answers an open question of Ambainis et al.
We provide numerical evidence that the nonlinear searching algorithm introduced by Wong and Meyer cite{meyer2013nonlinear}, rephrased in terms of quantum walks with effective nonlinear phase, can be extended to the finite 2-dimensional grid, keeping the same computational advantage BHg{with} respect to the classical algorithms. For this purpose, we have considered the free lattice Hamiltonian, with linear dispersion relation introduced by Childs and Ge cite{Childs_2014}. The numerical simulations showed that the walker finds the marked vertex in $O(N^{1/4} log^{3/4} N) $ steps, with probability $O(1/log N)$, for an overall complexity of $O(N^{1/4}log^{7/4}N)$. We also proved that there exists an optimal choice of the walker parameters to avoid that the time measurement precision affects the complexity searching time of the algorithm.
We give a quantum algorithm for finding a marked element on the grid when there are multiple marked elements. Our algorithm uses quadratically fewer steps than a random walk on the grid, ignoring logarithmic factors. This is the first known quantum walk that finds a marked element in a number of steps less than the square-root of the extended hitting time. We also give a new tighter upper bound on the extended hitting time of a marked subset, expressed in terms of the hitting times of its members.
In some of the earliest work on quantum mechanical computers, Feynman showed how to implement universal quantum computation by the dynamics of a time-independent Hamiltonian. I show that this remains possible even if the Hamiltonian is restricted to be a sparse matrix with all entries equal to 0 or 1, i.e., the adjacency matrix of a low-degree graph. Thus quantum walk can be regarded as a universal computational primitive, with any desired quantum computation encoded entirely in some underlying graph. The main idea of the construction is to implement quantum gates by scattering processes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
