[miles7]

As one of the authors, I'm ok with reasonable disagreements (e.g. see D. Bacon's below) about whether our overall conclusions are justified. But I feel it important to point out that your comment above is just a pure misrepresentation of the procedure in our paper.

In a future draft we will bring out this point more clearly, but we do not unroll the post-oracle state into a vector of size 2^n and just look at the winners. We use a well-established sampling technique from the matrix product state literature (reference: https://arxiv.org/abs/1201.3974, also cited in the paper) which runs deterministically and always scales as log(N) = n. (This part is independent of the oracle used.)

Overall our approach scales as log(N) for cases where the oracle can be simulated in polynomial time. We give such a case explicitly in the paper. Of course for many oracles, applying the oracle will scale exponentially which we say, but we show that there exist quite a few instances (we could show many more) where the actual time is minutes or hours to sizes of qubits (e.g. 40 qubits) that would require a million iterations of Grover's algorithm if it were run on a physical quantum computer.