What does this mean? After making the state preparation assumption, the classical algorithm can be of same complexity? Or the classical algorithm does not depend on state preparation?
In the classical case we stipulate a model of data access (eg., a Random-Access-Model) which enables calculating a "time-complexity" (performance) of the algorithm.
In the quantum case it appears that where such models exist they haven't been carefully compared to the classical ones.
It seems here the claim is that when you do this comparison carefully, you find most of the speed up of the algorithm comes from a stipulated data access model -- rather than "a more powerful sequencing of actions".
The proof appears to involve a means of stating equivalent classical assumptions about the data access model; and showing under these assumptions, many key quantum algorithms have "time-similar" classical versions (ie., the time-complexity difference isnt expotential, as previously claimed).