3 ms·

What does this mean? After making the state preparation assumption, the classical algorithm can be of same complexity? Or the classical algorithm does not depen

• Strilanc 5y ago
  The advantage of the quantum algorithm drops from exponential to polynomial, when the classical algorithm is able to query the data in the way it's being assumed the quantum algorithms can query the data.
• mjburgess 5y ago
  It is helpful to have a really clear idea of what a computer is: an algorithm is a sequencing of operations which take some time; important operations to sequence are memory (ie., data) access. 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).