Recently, a series of research papers have been released (this, this and this, also this) that provide classical algorithms with the same runtime as quantum machine learning algorithms for the same purpose. From my understanding, the key to all the algorithms that have been dequantized is the same: the state preparation routine has been substituted by $\ell^2$-norm sampling.

A few questions arise: after these results, what are the expectations from the field? Since any quantum algorithm will need of state preparation at some point (in every algorithm we will have, at some point, to encode some classical data in a quantum state), can any quantum machine learning algorithm be dequantized using Tang's method? If not, which algorithms are expected to / do resist this dequantization?

  • 7
    $\begingroup$ in the case of HHL, the classical solution by E. Tang works for low-rank matrices while the original algorithm was for sparse ones, so at least in this case not quite the same problem is being solved. That said, this blog post by E. Tang explaining her technique might be of interest $\endgroup$ – glS Feb 19 '19 at 19:35
  • 4
    $\begingroup$ the expectation, voiced for example in arXiv:1811.04909 is that exponential quantum speed-ups are tightly related to problems where high-rank matrices play a crucial role, like in Hamiltonian simulation (quantum chemistry) or the Fourier transform (factorization). $\endgroup$ – Carlo Beenakker Mar 31 '19 at 7:15
  • $\begingroup$ @CarloBeenakker thanks for the great link! can you elaborate on the FT application? this paper postulates the equivalence between deep NNs and large-dimensional linear operations. Would that also apply here? $\endgroup$ – fr_andres Aug 7 '19 at 19:06
  • $\begingroup$ Are you asking about all quantum algorithms or just quantum machine learning algorithms? $\endgroup$ – Condo Jul 7 at 18:49
  • 2
    $\begingroup$ One algorithm that may be immune from dequantization is the quantum algorithms for topological and geometric analysis of big data (arxiv, Nature) of Lloyd, Garneroni, and Zanardi. $\endgroup$ – Mark S Aug 23 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.