# Simulating any fixed time classical circuit in time poly(t) on a quantum computer

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. 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)$$).