pith. machine review for the scientific record. sign in

arxiv: 1302.7316 · v1 · submitted 2013-02-28 · 🪐 quant-ph · cs.DS

Recognition: unknown

A Time-Efficient Quantum Walk for 3-Distinctness Using Nested Updates

Andrew M. Childs , Stacey Jeffery , Robin Kothari , Frederic Magniez
Authors on Pith no claims yet
classification 🪐 quant-ph cs.DS
keywords quantumwalkalgorithmcomplexitydistinctnessnestedupdatesapply
0
0 comments X
read the original abstract

We present an extension to the quantum walk search framework that facilitates quantum walks with nested updates. We apply it to give a quantum walk algorithm for 3-Distinctness with query complexity ~O(n^{5/7}), matching the best known upper bound (obtained via learning graphs) up to log factors. Furthermore, our algorithm has time complexity ~O(n^{5/7}), improving the previous ~O(n^{3/4}).

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Tight Quantum Lower Bound for k-Distinctness

    quant-ph 2026-04 unverdicted novelty 8.0

    A new quantum lower bound framework proves a tight bound for k-Distinctness.