Scalable quantum computation vs Uncertainty Principle

Question

tl;dr. : If we want the result of a quantum computation to have scalable more bits, we will need inner measurements to have scalable precision, if we already know the result of the computation (from a classical computer) then we could predict measurements with scalable precision! over the very physical system that constitutes the quantum computer, that seems to contradict uncertainty, and one of the two seem impossible.

---

Long Version

What does it means for a Quantum Computer to be scalable?

Let's suppose scalable QC means just to compute bigger numbers, scalable precision.

A QC should be able to give deterministic and correct result over classical computations (deterministic here means known classical algorithm, verifiable results with classical computers).

While the quantum computation is done through measurements, its result need to match deterministic classical results, so it would be equivalent to say that QC would need to predict that very specific "quantum measurements" with an 'scalable precision' (predict measurements used by that specific computation). And that's the issue.

Measuring

If we name a measuring device as "a measurement device" then physics say we can't predict the interaction with the measured system, but if we name it a "quantum computer" the interaction then seems to become predictable (and even with scalable precision!?)

In physics: a quantum physical system gives unpredictable outcomes (only predictable probabilities)

Quantum System => measuring device (not intended to do computations) => Measurement

In Quantum Computers : system gives scalable predictable outcomes.

Quantum System => measuring device (designed to compute + algorithm) => Measurement

Scaling vs Uncertainty

If scaling precision is to scale prediction, quantum uncertainty and quantum computing seems opposites, scaling in QC will be related with a reducing uncertainty in the measurement.

In the extreme case, if we can't eliminate uncertainty in the measurement, then QC would not be scalable (i.e there will be some problems or precisions where a QC won't scale, because if were scalable, it would let us to predict the outcomes of a measurement of any physical system or a specific system with scalable precision )

A classical computing analogy

In classical computers there is a threshold in its inner transistors, comparators, etc.. (to separate 1 from 0 and avoid quantum effects, noise, and so on), we use the probabilities of systems that we already know and carefully design, to mechanically compose an abstraction layer over them. Then to "scale" a classical computer, we have two ways:

1) just waiting the computer to spit more numbers.
2) making it bigger, scaling the amount of transistors, or faster, higher clock, lower threshold,etc..

But we don't scale precision by changing threshold in runtime, "by software", and QC would seem to do something like that, because as computation is done by the measurement itself, and not by any classical abstraction so prediction would depends of the precision we ask by software, as if we could change microprocessor to use 3.3v, 1.8v, or 0.00001v in Runtime depending on the input numbers!, if so where will they go the noise and uncertainty?

Answer 1

As far as I understood Quantum Computers they do not provide a deterministic solution, since the computation is undeterministic. However, they have a high(er) probability of finding a correct solution. Therefore, whenever the algorithm finishes you should check the result with a normal computer and decide whether you have to rerun the algorithm.

If you scale up your system you will have a bigger state, hence a higher probability of the algorithm failing. Still, due to being undeterministic it allows you to potentially solve a set of problems in a reasonable time which you cannot solve on a normal computer in a reasonable time.

Furthermore, the result should be easy to check per iteration e.g. as is the case with determining large prime factors: if you have two prime candidates it is trivial to check whether the multiplication yields the expected number.

For more info have a look at Shor's algorithm: http://en.wikipedia.org/wiki/Shor%27s_algorithm

Answer 2

It's hard to understand what exactly is being asked, so here is a first stab. I can update if further clarification is given.

First, yes a quantum computer can be used to do classical calculations. In this case there will be no entanglement, and so the result is not probabilistic (except for any issues caused by decoherence, but it is assumed this is sufficiently controlled over the course of a calculation so that this can even be considered a useful quantum computer in the first place).

I do not understand what you feel this has to do with scaling and the uncertainty principle. The uncertainty principle only limits how well we can simultaneously know non-commuting observables. The states of individual qubits are commuting observables, so it does not apply here.

The current experimental difficulties in building a quantum computer are to have the qubits strongly interacting enough to allow computations, while simultaneously being very insensitive to (non-interacting with) the environment to prevent decoherence. For example the polarization state of photons are amazingly insensitive to the environment, and have even been used in entanglement experiments separated by kilometers after traveling through many many atoms in the material of fiber optics. So photons are great for holding the state of a qubit, but it is hard to get photons to interact strongly enough to get non-linear effects for computation. The opposite is the case of using (as an example) flux states in super conducting rings as qubits. It is easy to get them to electronically interact, and we can just build electronic circuits to couple different qubits, however they interact with the environment too much and decohere too fast.

If your question is essentially: Are the engineering difficulties of building a quantum computer too large to overcome since scaling will make the decoherence problem greater? ... that, no one currently knows. There is however no theoretical limitation preventing this, and as explained above, especially not from the uncertainty principle.

Answer 3

I think this is the answer, pointed out by PeterShor.

Here an ironic summary from Scott Aaronson (emphasis added)

---

We know that analog computers are not that reliable, and can go haywire because of small errors. The argument proceeds to ask why a quantum computer should be any different, since you have these amplitudes which are continuously varying quantities. Anyone want to answer this one for me?

A: The Threshold Theorem?

Scott: Thank you.

That argument describes what people thought before we had the Threshold Theorem (also called the Quantum Fault-Tolerance Theorem), and yet people are still arguing about it ten years after the theorem.

Q: OK, so you have the Threshold Theorem, but then you have to do some error correction, right? Your computation becomes longer, right?

Scott: Yeah, but by a factor of polylog(n). This isn't challenging the Church-Turing Thesis, but yeah, that's true.

Q: I'm not sure if you'd have to perform another error correction as you proceed.

Scott:The entire content of the Threshold Theorem is that you're correcting errors faster than they're created. That's the whole point, and the whole non-trivial thing that the theorem shows. That's the problem it solves.

Q: Isn't there a Threshold Theorem for classical computing as well?

Scott: There is.

Q: Is there a Threshold Theorem for analog computers?

Scott: No, and there can't be. The point is, there's a crucial property that is shared by discrete theories, probabilistic theories and quantum theories, but that is not shared by analog or continuous theories. That property is insensitivity to small errors. That's really a consequence of linearity. When I think about the Threshold Theorem, I try to take a step back and ask "what does this really mean?" It's really a consequence of the linearity of quantum mechanics. If we want a weaker Threshold Theorem, we could consider a computation taking t time steps, where the amount of error per time step could be 1/t. Then, the Threshold Theorem would be trivial to prove. If we have a product of unitaries U1U1...U100, and each one were to be corrupted by 1/t (1/100 in this case), then we'd have a product like:

  (U1 + U'1/t) (U2 + U'2/t)... (U100 + U'100/t)

The product of all these errors still won't be much, again because of linearity. An observation made by Bernstein and Vazirani was that quantum computation is sort of naturally robust against one-over-polynomial errors. In principle, that already answers the question.