Quantum Annealing vs Quantum Monte Carlo: can QMC do all that QA can?

Question

I'm working on an essay about quantum technology, and the connection between the annealing algorithm and quantum computing hardware is an important transition in the text. I'd like to know if there is an advantage to running quantum annealing on a quantum device, over implementing the quantum Monte Carlo method (path-integral MC, if I got it right) to simulate QA. I mean, advantages other than those from quantum computing, e.g.parallel information processing. Are there problems that QA can solve better than QMC?

Answer 1

First of all, quantum annealing is an concept of quantum computing which allows to solve only binary optimization problems, while quantum Monte Carlo is an algorithm which is run on gate-based universal quantum computers. However, there are algorithms (VQE or QAOA) running on the universal quantum computer and simulating quantum annealers.

A 'commercial' example of quantum annealer is a processor produced by D-Wave Systems. An example of gate-based processor is IBM quantum.

Concerning the speed-up provided by each of the algorithms. Quantum Monte Carlo provides quadratic speed-up in comparison with classical Monte Carlo (i.e. to get some accuracy of result we need $n$ operations on a classical computer, while only $\sqrt{n}$ ops. on a quantum computer. In case of quantum annealing, there is no proved speed-up over classical binary optimization, however, for some optimization tasks an empirical evidences reveal better performance of the quantum approach.

Lastly, lets have a look at the tasks which QA and QMC can solve. As mentioned above, QA is used for binary optimization problems or any other other tasks which can be expressed as a binary optimization problem. QMC is used for simulation of time evolution of a phenomena described by a statistical distribution, e.g. time development of share price or many other financial markets phenomenons. Of course, QMC is also used in modeling statistical phenomena in physics, e.g. finding thermodynamics equilibrium. So, you can see that each approach is intended for different type of task.