Unstructured Search by Random and Quantum Walk
- URL: http://arxiv.org/abs/2011.14533v2
- Date: Mon, 18 Oct 2021 15:20:55 GMT
- Title: Unstructured Search by Random and Quantum Walk
- Authors: Thomas G. Wong
- Abstract summary: Find an entry in an unsorted list of $N$ elements famously takes $O(N)$ queries to an oracle for a classical computer.
We derive how discrete- and continuous-time random walks and quantum walks solve this problem.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The task of finding an entry in an unsorted list of $N$ elements famously
takes $O(N)$ queries to an oracle for a classical computer and $O(\sqrt{N})$
queries for a quantum computer using Grover's algorithm. Reformulated as a
spatial search problem, this corresponds to searching the complete graph, or
all-to-all network, for a marked vertex by querying an oracle. In this
tutorial, we derive how discrete- and continuous-time (classical) random walks
and quantum walks solve this problem in a thorough and pedagogical manner,
providing an accessible introduction to how random and quantum walks can be
used to search spatial regions. Some of the results are already known, but many
are new. For large $N$, the random walks converge to the same evolution, both
taking $N \ln(1/\epsilon)$ time to reach a success probability of $1-\epsilon$.
In contrast, the discrete-time quantum walk asymptotically takes
$\pi\sqrt{N}/2\sqrt{2}$ timesteps to reach a success probability of $1/2$,
while the continuous-time quantum walk takes $\pi\sqrt{N}/2$ time to reach a
success probability of $1$.
Related papers
- Quantum spatial search with multiple excitations [0.28675177318965045]
We show that a continuous-time quantum walk in the $k$-excitation subspace of $n$ spins can determine the binary string of $k$ marked with fidelity in time $O(sqrtn)$
Numerically, we show that this algorithm can be implemented with interactions that decay as $1/ralpha$, where $r$ is the distance between spins, and an $alpha$ that is readily available in current ion trap systems.
arXiv Detail & Related papers (2024-10-08T11:53:57Z) - Quantum Speedups for Bayesian Network Structure Learning [0.0]
For networks with $n$ nodes, the fastest known algorithms run in time $O(cn)$ in the worst case, with no improvement in two decades.
Inspired by recent advances in quantum computing, we ask whether BNSL admits a quantum speedup.
We give two algorithms achieving $c leq 1.817$ and $c leq 1.982$.
arXiv Detail & Related papers (2023-05-31T09:15:28Z) - On the average-case complexity of learning output distributions of
quantum circuits [55.37943886895049]
We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model.
This learning model is widely used as an abstract computational model for most generic learning algorithms.
arXiv Detail & Related papers (2023-05-09T20:53:27Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods.
We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
arXiv Detail & Related papers (2023-03-03T18:23:20Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
We present a quantum algorithm that has rigorous runtime guarantees for several families of binary optimization problems.
We show that the algorithm finds the optimal solution in time $O*(2(0.5-c)n)$ for an $n$-independent constant $c$.
We also show that for a large fraction of random instances from the $k$-spin model and for any fully satisfiable or slightly frustrated $k$-CSP formula, statement (a) is the case.
arXiv Detail & Related papers (2022-12-03T02:45:23Z) - Improvement of quantum walk-based search algorithms in single marked
vertex graphs [0.0]
Amplitude amplification is usually used to amplify success probability, but the souffl'e problems follow.
In this work, we define generalized interpolated quantum walks, which can both improve the success probability of search algorithms and avoid the souffl'e problems.
arXiv Detail & Related papers (2022-09-09T07:43:46Z) - Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$.
We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM)
Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
arXiv Detail & Related papers (2022-06-07T18:00:01Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
Continuous-time quantum walks provide a framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search.
We present a new continuous-time quantum walk search algorithm that can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks.
arXiv Detail & Related papers (2021-12-23T17:57:49Z) - Random quantum circuits transform local noise into global white noise [118.18170052022323]
We study the distribution over measurement outcomes of noisy random quantum circuits in the low-fidelity regime.
For local noise that is sufficiently weak and unital, correlations (measured by the linear cross-entropy benchmark) between the output distribution $p_textnoisy$ of a generic noisy circuit instance shrink exponentially.
If the noise is incoherent, the output distribution approaches the uniform distribution $p_textunif$ at precisely the same rate.
arXiv Detail & Related papers (2021-11-29T19:26:28Z) - Quantum Time-Space Tradeoff for Finding Multiple Collision Pairs [0.0]
We study the problem of finding $K$ collision pairs in a random function $f : [N] rightarrow [N]$ by using a quantum computer.
We prove that the number of queries to the function must increase significantly when the size of the available memory is limited.
arXiv Detail & Related papers (2020-02-20T18:48:51Z) - Quantum Coupon Collector [62.58209964224025]
We study how efficiently a $k$-element set $Ssubseteq[n]$ can be learned from a uniform superposition $|Srangle of its elements.
We give tight bounds on the number of quantum samples needed for every $k$ and $n$, and we give efficient quantum learning algorithms.
arXiv Detail & Related papers (2020-02-18T16:14:55Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.