Answers.Body: <blockquote>
  <p>Generally, if one googles &quot;quantum machine learning&quot; or anything similar the general gist of the results is that quantum computing will greatly speed up the learning process of our &quot;classical&quot; machine learning algorithms.</p>
  </blockquote>
  <p>This is correct. A lot of machine learning methods involve linear algebra, and it often takes far fewer quantum operations to do things in linear algebra than the number of classical operations that would be needed. To be more specific, for a matrix of size <span class="math-container">$N\times N$</span>, if a classical computer needs <span class="math-container">$f(N)$</span> operations to do some linear algebra operation, such as diagonalization which can take <span class="math-container">$f(N)=\mathcal{O}(N^3)$</span> operations on a classical computer, a quantum computer would often need only <span class="math-container">$\log_2 f(N)$</span> operations, which inn (in and only in) the language of computational complexity theory, means <em><strong>exponential speed-up</strong></em>. The &quot;only in&quot; part is there because we have made here an assumption that &quot;fewer quantum operations&quot; means &quot;speed-up&quot;, which for now is something we only know to be true in the world of &quot;computational complexity theory&quot;.</p>
  <blockquote>
  <p>However, &quot;speed-up&quot; itself does not seem very appealing to me as the current leaps made in AI/ML are generally due to novel architectures or methods, not faster training.</p>
  </blockquote>
  <p>I disagree. Take vanilla deep learning for example (without GANs or any of the other things that came up in the last decade). Hinton and Bengio had been working on deep learning for decades, so why did interest in deep learning <em>suddenly</em> start growing so much from 2011-2014 after a roughly monotonic curve from 1988-2010? Not that this rise started before newer advances such as GANs and <a href="https://arxiv.org/abs/1608.06993" rel="nofollow noreferrer">DenseNet</a> were developed:</p>
  <p><a href="https://i.sstatic.net/kgC7s.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kgC7s.png" alt="enter image description here" /></a></p>
  <p><br><br>
  Notice also the similarity between the above graph and these ones:</p>
  <p><a href="https://i.sstatic.net/xf4k0.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xf4k0.png" alt="enter image description here" /></a></p>
  <p>These days pretty much everyone doing deep learning uses GPUs if they have access to GPUs, and what is possible to accomplish is <em><strong>extremely</strong></em> tied to what computing power a group has. I don't want to undermine the importance of new <em>methods</em> and new <em>algorithms,</em> but GPUs did play a big role for at least some areas of machine learning, such as deep learning.</p>
  <blockquote>
  <p>Are there any quantum machine learning methods in development that are fundamentally different from &quot;classical&quot; methods?</p>
  </blockquote>
  <p>I think you mean: &quot;Most quantum machine learning algorithms are simply based on classical machine learning algorithms, but with some sub-routine sped-up by the QPU instead of a GPU -- are there any quantum algorithms that are not based on classical machine learning algorithms, and are entirely different&quot;.</p>
  <p>The answer is yes, and more experts might be able to tell you more <a href="https://quantumcomputing.stackexchange.com/questions/ask">here</a>.</p>
  <p>One thing you might consider looking at is <a href="https://arxiv.org/abs/1601.02036" rel="nofollow noreferrer">Quantum Boltzmann Machines</a>.</p>
  <p>Another things I'll mention is that a child prodigy named <a href="https://en.wikipedia.org/wiki/Ewin_Tang" rel="nofollow noreferrer">Ewin Tang</a> who began university at age 14, discovered at around the age of 17 some <em><strong>classical algorithms</strong></em> that were inspired by quantum algorithms rather than the other way around, and
  the comments on the Stack Exchange question <a href="https://quantumcomputing.stackexchange.com/q/5525/2293">Quantum machine learning after Ewin Tang</a> might give you more insight on that. This is related to something called <em><strong>dequantization</strong></em> of quantum algorithms.</p>
  <blockquote>
  <p>By this I mean that these methods are (almost*) impossible to perform on &quot;classical&quot; computers. *except for simulation of the quantum computer of course</p>
  </blockquote>
  <p>Unfortunately quantum computers can't do anything that's impossible for classical computers to do, apart from the fact that they might be able to do some things faster. <em><strong>Classical computation is Turing complete, meaning anything that can be computed can be computed on a big enough classical computer.</strong></em></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-01T07:09:39.723Z
Answers.Text: @DuttaA That's a fair point. The huge amount of data is certainly important, and smartphones/gadgets did help with that, though internet and smartphones did exist in the 90s (PalmPilot) and 2000s (BlackBerry) too. Basically everyone doing serious deep learning is doing it on GPUs though. Why is that? GPUs were indeed a game changer for deep learning, and GPU development skyrocketed last decade. Also about big data: Deep Learning was a topic of Hinton's research since the 80s, and even without smartphones we still had enough data to do deep learning. But more data in the last decade did help!
Answers.UserDisplayName: Nike Dattani
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-04T13:58:04.620Z
Answers.Text: Nice answer, but I disagree with your statement "_Unfortunately quantum computers can't do anything that's impossible for classical computers to do_". Quantum computers can do operations that are simply impossible for a classical computer to do (they can only be simulated). Turing complete unfortunately does not apply when comparing quantum and classical computers. So to rephrase my question: **I'm interested if there is a (complete) quantum machine learning algorithm that can only be simulated by classical computers.**
Answers.UserDisplayName: Thomas Wagenaar
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-04T17:30:33.247Z
Answers.Text: Unfortunately comments aren't saved the way answers are, so when my screen accidentally refreshed when I was almost done writing my ~400 character comment, what I wrote got permanently lost. In any case, what I wrote would have led to you asking further questions, and this might go for awhile, so I suggest you ping me at: https://chat.stackexchange.com/rooms/117114/hpqc-high-performance-quantum-computing where we can chat about this very intetesting question more smoothly.
Answers.UserDisplayName: Nike Dattani
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-01-01T05:57:36.803Z
Answers.LastActivityDate: 2021-01-01T05:57:36.803Z
Answers.UserDisplayName: Nike Dattani
Body: <p>Generally, if one googles "quantum machine learning" or anything similar the general gist of the results is that quantum computing will greatly <em>speed up</em> the learning process of our "classical" machine learning algorithms. However, "speed up" itself does not seem very appealing to me as the current leaps made in AI/ML are generally due to novel architectures or methods, <em>not</em> faster training.</p>
  
  <p>Are there any quantum machine learning methods in development that are <em>fundamentally</em> different from "classical" methods? By this I mean that these methods are (almost*) impossible to perform on "classical" computers. </p>
  
  <p><sub>*except for simulation of the quantum computer of course</sub></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-27T11:55:31.543Z
Comments.Text: just a note: any quantum algorithm that is *not* "fundamentally different" from classical ones is totally useless. Quantum computing doesn't provide speed-ups due to faster processing, it does (if and when it does) due to its use of completely different ways of processing information. This said, I don't think there is any clear-cut answer to this question as of yet. You can find some links that might be of interest here https://quantumcomputing.stackexchange.com/a/1268/55
Comments.UserDisplayName: glS
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-04-27T12:02:33.607Z
Comments.Text: this question is also related: https://ai.stackexchange.com/q/36/4314
Comments.UserDisplayName: glS
Tags: <machine-learning><quantum-computing>
Title: Are there any novel quantum machine learning algorithms that are fundamentally different from "classical" ones?
UserDisplayName: Thomas Wagenaar
ThreadText: # Are there any novel quantum machine learning algorithms that are fundamentally different from "classical" ones?
  
  (Asked by: username_0 on 2020-04-26)
  
  Generally, if one googles "quantum machine learning" or anything similar the general gist of the results is that quantum computing will greatly *speed up* the learning process of our "classical" machine learning algorithms. However, "speed up" itself does not seem very appealing to me as the current leaps made in AI/ML are generally due to novel architectures or methods, *not* faster training.
  
  Are there any quantum machine learning methods in development that are *fundamentally* different from "classical" methods? By this I mean that these methods are (almost\*) impossible to perform on "classical" computers.
  
  \*except for simulation of the quantum computer of course
  
  **Tags:** machine-learning, quantum-computing
  > **Comments:**
  > **username_1**: just a note: any quantum algorithm that is *not* "fundamentally different" from classical ones is totally useless. Quantum computing doesn't provide speed-ups due to faster processing, it does (if and when it does) due to its use of completely different ways of processing information. This said, I don't think there is any clear-cut answer to this question as of yet. You can find some links that might be of interest here https://quantumcomputing.stackexchange.com/a/1268/55  
  > **username_1**: this question is also related: https://ai.stackexchange.com/q/36/4314  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-01-01. Score: 4
  
  > Generally, if one googles "quantum machine learning" or anything similar the general gist of the results is that quantum computing will greatly speed up the learning process of our "classical" machine learning algorithms.
  
  This is correct. A lot of machine learning methods involve linear algebra, and it often takes far fewer quantum operations to do things in linear algebra than the number of classical operations that would be needed. To be more specific, for a matrix of size $N\times N$, if a classical computer needs $f(N)$ operations to do some linear algebra operation, such as diagonalization which can take $f(N)=\mathcal{O}(N^3)$ operations on a classical computer, a quantum computer would often need only $\log\_2 f(N)$ operations, which inn (in and only in) the language of computational complexity theory, means ***exponential speed-up***. The "only in" part is there because we have made here an assumption that "fewer quantum operations" means "speed-up", which for now is something we only know to be true in the world of "computational complexity theory".
  
  > However, "speed-up" itself does not seem very appealing to me as the current leaps made in AI/ML are generally due to novel architectures or methods, not faster training.
  
  I disagree. Take vanilla deep learning for example (without GANs or any of the other things that came up in the last decade). Hinton and Bengio had been working on deep learning for decades, so why did interest in deep learning *suddenly* start growing so much from 2011-2014 after a roughly monotonic curve from 1988-2010? Not that this rise started before newer advances such as GANs and [DenseNet](https://arxiv.org/abs/1608.06993) were developed:
  
  [![enter image description here](https://i.sstatic.net/kgC7s.png)](https://i.sstatic.net/kgC7s.png)
  
  Notice also the similarity between the above graph and these ones:
  
  [![enter image description here](https://i.sstatic.net/xf4k0.png)](https://i.sstatic.net/xf4k0.png)
  
  These days pretty much everyone doing deep learning uses GPUs if they have access to GPUs, and what is possible to accomplish is ***extremely*** tied to what computing power a group has. I don't want to undermine the importance of new *methods* and new *algorithms,* but GPUs did play a big role for at least some areas of machine learning, such as deep learning.
  
  > Are there any quantum machine learning methods in development that are fundamentally different from "classical" methods?
  
  I think you mean: "Most quantum machine learning algorithms are simply based on classical machine learning algorithms, but with some sub-routine sped-up by the QPU instead of a GPU -- are there any quantum algorithms that are not based on classical machine learning algorithms, and are entirely different".
  
  The answer is yes, and more experts might be able to tell you more [here](https://quantumcomputing.stackexchange.com/questions/ask).
  
  One thing you might consider looking at is [Quantum Boltzmann Machines](https://arxiv.org/abs/1601.02036).
  
  Another things I'll mention is that a child prodigy named [Ewin Tang](https://en.wikipedia.org/wiki/Ewin_Tang) who began university at age 14, discovered at around the age of 17 some ***classical algorithms*** that were inspired by quantum algorithms rather than the other way around, and
  the comments on the Stack Exchange question [Quantum machine learning after Ewin Tang](https://quantumcomputing.stackexchange.com/q/5525/2293) might give you more insight on that. This is related to something called ***dequantization*** of quantum algorithms.
  
  > By this I mean that these methods are (almost\*) impossible to perform on "classical" computers. \*except for simulation of the quantum computer of course
  
  Unfortunately quantum computers can't do anything that's impossible for classical computers to do, apart from the fact that they might be able to do some things faster. ***Classical computation is Turing complete, meaning anything that can be computed can be computed on a big enough classical computer.***
  
  > **Comments:**
  > **username_2**: @DuttaA That's a fair point. The huge amount of data is certainly important, and smartphones/gadgets did help with that, though internet and smartphones did exist in the 90s (PalmPilot) and 2000s (BlackBerry) too. Basically everyone doing serious deep learning is doing it on GPUs though. Why is that? GPUs were indeed a game changer for deep learning, and GPU development skyrocketed last decade. Also about big data: Deep Learning was a topic of Hinton's research since the 80s, and even without smartphones we still had enough data to do deep learning. But more data in the last decade did help!  
  > **username_0**: Nice answer, but I disagree with your statement "_Unfortunately quantum computers can't do anything that's impossible for classical computers to do_". Quantum computers can do operations that are simply impossible for a classical computer to do (they can only be simulated). Turing complete unfortunately does not apply when comparing quantum and classical computers. So to rephrase my question: **I'm interested if there is a (complete) quantum machine learning algorithm that can only be simulated by classical computers.**  
  > **username_2**: Unfortunately comments aren't saved the way answers are, so when my screen accidentally refreshed when I was almost done writing my ~400 character comment, what I wrote got permanently lost. In any case, what I wrote would have led to you asking further questions, and this might go for awhile, so I suggest you ping me at: https://chat.stackexchange.com/rooms/117114/hpqc-high-performance-quantum-computing where we can chat about this very intetesting question more smoothly.  
  
  ---
  
  