6533b83afe1ef96bd12a7be4

RESEARCH PRODUCT

Time-Efficient Quantum Walks for 3-Distinctness

Stacey JefferyRobin KothariFrédéric MagniezAleksandrs BelovsAndrew M. Childs

subject

Discrete mathematicsMatching (graph theory)0102 computer and information sciencesExtension (predicate logic)01 natural sciencesUpper and lower boundsTildeCombinatorics010201 computation theory & mathematics0103 physical sciencesQuantum algorithmQuantum walkConnection (algebraic framework)010306 general physicsTime complexityMathematics

description

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.

yearjournalcountryeditionlanguage
2013-01-01
https://doi.org/10.1007/978-3-642-39206-1_10