2
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ I think this older paper by Matt Hastings addresses exactly the question you are asking: arxiv.org/abs/1302.5733 $\endgroup$ Jan 16 at 12:53

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ I thought quantum Monte Carlo was a classical heuristic that was informed by quantum mechanics, and it wasn’t a gate-based quantum algorithm, no? $\endgroup$ Apr 25, 2022 at 2:37
  • $\begingroup$ @MarkS: In QA you have a classical optimization cycle, so QA algorithms are hybrid, i.e. those you call quantum mechanics informed. However, QMC is purely quantum computing algorithm utilizing gate-based model. $\endgroup$ Apr 25, 2022 at 6:09
  • $\begingroup$ @MarkS: A paper on QMC implementation on IBM Q: nature.com/articles/s41534-019-0130-6 $\endgroup$ Apr 25, 2022 at 8:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.