I'm analyzing the paper "Quantum walk algorithm for element distinctness" by Ambainis and at the bottom of page 24 (the last line of "Additional requirements" in section 6.2) Ambainis requires that any classical subroutine must terminate in a fixed time $t$ so that it can be replaced by a $O(\mathsf{poly}(t))$ time quantum algorithm. He specifically notes that it cannot be $t$ on average but sometimes take longer.

How can we simulate any fixed time classical subroutine by such a polynomial time quantum algorithm?

For a more concrete example, I was looking into the algorithm for binary search. We have a list of integer registers $q_0,\dots,q_n$ containing a sorted list and want to find the position of some quantum number $x$ in that sorted list. Classically this takes time $O(\log n)$ but, if i'm not mistaken, any simulation on a quantum computer has to execute all the if-statements sequentially, thus taking time $O(n)$.

Examples and/or a reference to a paper containing an explanation would be greatly appreciated!


1 Answer 1


In talking to some professors I found the answer myself. The statement does indeed hold (and is probably proven using the universality of the Toffili gate). The reason I was confused with the binary search example is because I considered a slightly different problem. Consider the following 2 binary search types:

  1. Binary search over a classical sorted list $x_1,\dots,x_n$ given using a quantum oracle $|i\rangle|0\rangle\mapsto|i\rangle|x_i\rangle$.

  2. Binary search over a (normalized) superposition of sorted lists $\sum_{j}|q_j\rangle$ where $|q_j\rangle=|q_{j,1}\rangle|q_{j,2}\rangle\cdots|q_{j,n}\rangle$ is a sorted list.

I was trying to solve the second type of binary search, though the translation of classical binary search would be the first type. Thus, the $O(\mathsf{poly}(t))$ runtime doesn't necessarily apply in the second case (and I'm convinced you can do no better than $O(n)$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.