Name
Abstract | ||
|---|---|---|
We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-39206-1_10 | ICALP |
Keywords | Field | DocType |
query complexity,quantum walk algorithm,quantum walk,quantum walk search framework,time-efficient quantum,nested updates,electric network,time complexity,facilitates quantum | Discrete mathematics,Graph,Combinatorics,Upper and lower bounds,Quantum walk,Tilde,Quantum algorithm,Time complexity,Mathematics | Conference |
Volume | ISSN | Citations |
7965 | 0302-9743 | 5 |
PageRank | References | Authors |
0.42 | 16 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aleksandrs Belovs | 1 | 131 | 14.50 |
| A. M. Childs | 2 | 590 | 52.47 |
| Stacey Jeffery | 3 | 207 | 16.16 |
| Robin Kothari | 4 | 196 | 21.05 |
| Frédéric Magniez | 5 | 570 | 44.33 |