2003/12/31 by Stephen Fenner, Stephen A. Fenner, Yong Zhang +2 · 1 citation
Computer Science · Physics and Astronomy · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0312230
3 pages, no figures
arxiv created 2003/12/31 · openalex publication_date 2003/12/31 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A recent paper on quantum walks by Childs et al. [STOC'03] provides an example of a black-box problem for which there is a quantum algorithm with exponential speedup over the best classical randomized algorithm for the problem, but where the quantum algorithm does not involve any use of the quantum Fourier transform. They give an exponential lower bound for a classical randomized algorithm solving the black-box graph traversal problem defined in their paper. In this note we give an improved lower bound for this problem via a straightforward and more complete analysis.