43
$\begingroup$

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?

Improve this question
$\endgroup$
8
  • 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 ♦
    Commented Feb 19, 2019 at 19:35
  • 6
    $\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
    Commented Mar 31, 2019 at 7:15
  • 4
    $\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 Spinelli
    Commented Aug 23, 2020 at 22:19
  • 1
    $\begingroup$ @MarkS perhaps this is true, however the algorithm you mention has substantial caveats outlined at the end of nature.com/articles/nphys3272 so I don't think it should be chosen as a flagship of hope... $\endgroup$
    – Condo
    Commented Sep 4, 2020 at 16:11
  • 2
    $\begingroup$ Note that there is at least one possible application of QML where the assumption that we begin by encoding classical data in a quantum state does not hold. Namely, using QML to process quantum rather than classical data. Note that many types of sensors exploit quantum effects. Rather than measuring such a sensor one could coherently couple it to a quantum computer and perform tasks such as state classification. $\endgroup$
    – Adam Zalcman
    Commented Dec 17, 2020 at 20:19

1 Answer 1

Reset to default
18
$\begingroup$

I am not an expert in the field but there are a few points that I am aware of:

  1. There are proofs that certain quantum machine learning algorithms cannot be efficiently simulated on a classical computer even if the classical computer has analogous sampling access to the data as the quantum algorithm does (i.e. they cannot be dequantized) [1-3]. However, there is no proof that these algorithms are better at learning to classify certain datasets than the best classical algorithms out there.
  2. There is one paper out there proving that a certain quantum machine learning algorithm cannot be simulated efficiently using a classical computer and can learn a specific classification task exponentially faster than any classical algorithm [4]. However it is important to state that the algorithm and specific classification task mentioned in the paper are very contrived and hence it is not a useful task. To summarize, they use an SVM with a very particular quantum kernel on a dataset generated by the discrete log problem. Nonetheless, it's a really neat proof-of-concept result and gives us some hope that quantum computing can bring a meaningful advantage to machine learning.
  3. As of today there is no example where we know that a quantum machine learning algorithm could outperform a classical machine learning algorithm in any meaningful task, but a recent paper has suggested a methodology for assessing the potential for quantum advantage in prediction on learning tasks [5]. However, the proofs in classical machine learning are also quite few and far in between, so given the above two points, people are hopeful that when quantum computers become powerful enough to try some QML algorithms out, we will've advanced in the field enough that we are likely to find some use cases where we find an advantage.

[1] https://www.nature.com/articles/s41586-019-0980-2
[2] https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.122.040504
[3] https://advances.sciencemag.org/content/4/12/eaat9004
[4] https://arxiv.org/abs/2010.02174
[5] https://arxiv.org/abs/2011.01938

Updates

Oct 2021 - a paper (still undergoing peer-review I think) came out taking the principle from [4] and applying it to reinforcement learning https://arxiv.org/abs/2103.05577v1

Dec 2021 - (1) the paper from the previous update (Oct 2021) has been published: https://proceedings.neurips.cc/paper/2021/hash/eec96a7f788e88184c0e713456026f3f-Abstract.html and (2) there is another pre-print (still under peer review) that proves exponential advantage in quantum machine learning if the training data that is generated comes from a quantum experiment: https://arxiv.org/abs/2112.00778. Note that if it takes exponential time to produce the initial quantum states that are used as training data, then there is no advantage: https://arxiv.org/abs/2112.00811

March 2022 - In August 2021 Ewin dequantized the quantum PCA and quantum nearest-centroid clustering algorithms. https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.127.060503. The very hand-wavy intuition is that if your quantum algorithm benefits only because it can access its inputs in superposition thanks to QRAM but that the algorithm itself has nothing particularly quantum about it, then it can be dequantized. For a much better explanation of this intuition, check out Ewin's STOC 2020 talk: https://www.youtube.com/watch?v=EsJEBJ2d1UY. Also, the first algorithm that was dequantized - the recommendation algorithm - was indeed found not to have an exponential speedup, but the quantum version still has a large (power of 8) speedup compared to the dequantized version (at least for now!).

September 2022 - The paper for demonstrating exponential advantage for quantum machine learning from the Dec 2021 update has been published: https://www.science.org/doi/10.1126/science.abn7293. The crux of is as follows: let's say you have an experiment that spits out a quantum state, and you want to know something about that state (or the experimental procedure), you can (1) make a bunch of copies of the state using your experiment, measure each copy (in whichever different bases you want), take all those (classical) measurement values and put them into a classical ML algorithm. Or you can (2) again make a bunch of copies of the state using your experiment, transfer those states (somehow in principle) into a quantum computer, and perform QML methods on those input states (including entangling those states together). This second method gives you an exponential speedup in 3 different learning tasks they describe in the paper.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.