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".

Improve this question
$\endgroup$
5
  • $\begingroup$ Thanks. So you question is part of my question: to what extent do CIMs and QAs operate over the real. I guess they are not considered to operate over the reals however their "physics" is. So where is the failure? And yes, for example Gitta Kutyniok's work often cites CIMs and QCs as potential solution for undecidable problems however they never go into the problem you pose: universal QCs are Turing machines, AQC is equivalent to the circuit model and QA is a subset of AQC, so where is the "potential" hope? $\endgroup$
    – Marion
    Sep 11 at 11:19
  • $\begingroup$ Not sure if you downvoted or not but the question asks for clarity either via references or via some formalities. In other words, this hand-waving question, does it bear some formal relevance or validity? If so, how? $\endgroup$
    – Marion
    Sep 11 at 11:20
  • $\begingroup$ What is the problem for somebody asking the community about these vague connections? I see you are a professor. Are you treating students with "vague questions" or even non-well defined questions like this or by providing references? $\endgroup$
    – Marion
    Sep 11 at 12:04
  • $\begingroup$ Really bad attitude. I pitty your students the reason being that vague question shuld be fine question where you can refine it. This is not a math question, in the sense of precision, rather a reference request question for clarifications as to if this vagueness even makes sense. You represent the worst of academia I am afraid. "analog quantum computation, performs computation over the reals" is in quotation marks and I also provide a reference later. I provide two in total and I am seeking for clarifications, not ego-queens. $\endgroup$
    – Marion
    Sep 13 at 9:03
  • $\begingroup$ 1) The adiabatic process is a continuous process. Thus why often I see comments or remarks of an analog/real (i.e. not fixed precision arithmetic) computation. 2) The question is totally valid for this forum, maybe not formulated precisely for it, in which case you could contribute in helping a) for a better and precise formulation or b) explain the fallacies. Definitely not c) suggest to ask Gitta for an answer in a very sarcastic way. The question does not ask if AQC is equivalent to a Blum–Shub–Smale machine. It asks to what extent, IF ANY, it can be considered over $\mathbb{R}$. $\endgroup$
    – Marion
    Sep 13 at 9:16

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

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

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