Recognition: unknown
Quantum Walks and Electric Networks
classification
🪐 quant-ph
keywords
quantumdistributiongraphinitialalgorithmapplicabledescribedetect
read the original abstract
We prove that a quantum walk can detect the presence of a marked element in a graph in $O(\sqrt{WR})$ steps for any initial probability distribution on vertices. Here, $W$ is the total weight of the graph, and $R$ is the effective resistance. This generalizes the result by Szegedy that is only applicable if the initial distribution is stationary. We describe a time-efficient quantum algorithm for 3-distinctness based on these ideas.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
Tight Quantum Lower Bound for k-Distinctness
A new quantum lower bound framework proves a tight bound for k-Distinctness.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.