Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
Do quantum computers only offer some computational benefit or advantage for complicated algorithms or would simple ordinary least squares solving or computing the maximum likelihood estimates or Newton Raphson also benefit?
Would Monte Carlo methods or Bayesian simulation based methods or Gibbs sampling be improved?
We can expect that quantum computers will provide a significant advantage in various machine learning classic algorithms, and theoretical results for some of them are already here. For example, the quantum EM algorithm for mixture of gaussian has been studied and the complexity of the computation is given In the article Quantum Expectation-Maximization Algorithm written by Hideyuki Miyahara (first author). Their main result is that the algorithm is exponentially faster in the number of sample than it's classical counterpart.
Quantum computers bring quadratic speed-up for Monte Carlo method. See for example Quantum Risk Analysis where the authors discussed application of Monte Carlo for risk management in finance.
