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

CC BY-SA 4.0
2023-09-16T17:16:09.277Z
2023-09-17T12:24:09.913Z
2023-09-17T12:24:09.913Z
Peter Shor 
<p>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 &quot;slightly&quot; more powerful Turing machine and it is widely believe, therefore, that QCs cannot solve NP-Hard problems.</p>
<p>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 <span class="math-container">$\mathbb{R}$</span> such as the BSS machine.</p>
<p>In my mind, &quot;analog quantum computation, performs computation over the reals&quot;:</p>
<ul>
<li>quantum annealers</li>
<li>coherent Ising machines</li>
</ul>
<p>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: <a href="https://www.nature.com/articles/s41377-022-01013-1" rel="nofollow noreferrer">https://www.nature.com/articles/s41377-022-01013-1</a></p>
<p>It's a bit puzzling therefore whether the power of existing computers that seem to operate over the reals indeed are equivalent to the &quot;restricted&quot; universal quantum computers which are fundamentally digital and modelled after a Turing machine.</p>
<p>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.</p>
<p>To add some context, my question is also motivated by the intro of a significant paper by Lloyd and Braunstein (<a href="https://arxiv.org/abs/quant-ph/9810082" rel="nofollow noreferrer">https://arxiv.org/abs/quant-ph/9810082</a>) where they say &quot; In principle, a continuous
quantum computer could perform tasks that a discrete
quantum computer cannot&quot;.</p>

<cc.complexity-theory><quantum-computing><turing-machines>
A contradiction in the realm of quantum digital and analog computation
Marion
# A contradiction in the realm of quantum digital and analog computation

(Asked by: username_0 on 2023-09-11)

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

**Tags:** cc.complexity-theory, quantum-computing, turing-machines

---

## 1 answers

### Answer by username_1 on 2023-09-16. Score: 8 | Accepted answer

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.


---

