3 ms·

This might be coming up again because the paper was finally published, like in a journal after peer-review, one month ago [1]. The pre-print has been available

This might be coming up again because the paper was finally published, like in a journal after peer-review, one month ago [1]. The pre-print has been available since 2018 [2]. [1]: https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.127.060503 https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.12... [2]: https://arxiv.org/abs/1811.00414 https://arxiv.org/abs/1811.00414

knuthsat 5y ago
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?
- 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).

3 ms·

This might be coming up again because the paper was finally published, like in a journal after peer-review, one month ago [1]. The pre-print has been available

by Strilanc 5y ago

knuthsat 5y ago
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?
- 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).