1
$\begingroup$

It is a well known result that the circuit model of Quantum Computing (QC) is equivalent to the adiabatic model. Furthermore, the former is nothing more than a "slightly" more powerful Turing machine and it is widely believe, therefore, that QCs cannot solve NP-Hard problems.

Now, in several works in classical optimization and classical complexity theory it is argued that while certain problems are undecidable in the Turing model, they could be computed or approximated in arbitrary precision using computation over $\mathbb{R}$ such as the BSS machine.

In my mind, "analog quantum computation, performs computation over the reals":

  • quantum annealers
  • coherent Ising machines

to name two examples. So I wonder if the statement above is fundamentally wrong. While annealers do operate with qubits, I would claim that their evolutions is continuous while the same can be 100% said for coherent Ising machines such as the one suggested here: https://www.nature.com/articles/s41377-022-01013-1

It's a bit puzzling therefore whether the power of existing computers that seem to operate over the reals indeed are equivalent to the "restricted" universal quantum computers which are fundamentally digital and modelled after a Turing machine.

I am pretty sure, that I make some logical fallacies or I am misinformed so I would like to have some clarifications or references discussing the (quantum or classical) analog computers that exist as of today.

To add some context, my question is also motivated by the intro of a significant paper by Lloyd and Braunstein (https://arxiv.org/abs/quant-ph/9810082) where they say " In principle, a continuous quantum computer could perform tasks that a discrete quantum computer cannot".

$\endgroup$
0

1 Answer 1

8
$\begingroup$

Blum-Shub-Smale machines manage to solve NP-complete problems by using an exponential number of the digits of precision. Nothing that you can do in a physics experiment uses more than thirty digits of precision (and that's a very optimistic number).

So while analog quantum computation models using real numbers might be more powerful in theory, they will almost certainly not be so in practice. Or at any rate, they cannot gain extra power by using real numbers the way Blum-Shub-Smale machines do.

$\endgroup$

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.