1
$\begingroup$

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?

$\endgroup$

migrated from cs.stackexchange.com Sep 6 '14 at 19:10

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ in a sense scalable means being able to represent bigger numbers, in essense it means being able to make a quantum computer with a large number of qubits which can do coherent computation in a given time interval before their states de-synchronise $\endgroup$ – Nikos M. Aug 19 '14 at 12:42
  • $\begingroup$ @NikosM if that's how we define scalable, I think we should be able to predict what the results will be (to a scalable precision) after decoherence, and there I see a conflict with QM in anticipating results. Except we define some kinds of thresholds (like in actual semiconductors) but in that case 'scalable' would have a different meaning, QC would be only scalable for certain algorithms and precision but not universally scalable, a "plug-in-hardware" for classic computing more than anything new. Does 'scalable' means other thing? Am I wrong by seeing a conflict with QM that is not there? $\endgroup$ – HDE Aug 19 '14 at 15:47
  • 1
    $\begingroup$ At the time of writing, there are three votes to close as unclear. As I know nothing about this field, could experts please indicate in a comment why they think it's unclear? Can you suggest ways in which this question could be improved? Do the technical terms in this question make sense? Is there an underlying confusion that could be clarified in an answer? Is the problem a lack of specificity around the notion of scalability? $\endgroup$ – Gilles Aug 20 '14 at 17:12
  • $\begingroup$ This site is for objectively answerable questions that admit a single right answer, and where one can judge the right answer based upon the question. It is not the site for a discussion. Personally, I can't tell what your question is -- I don't see a clear statement of the question. But if your question is "I would like to read some other views", that is not suitable for this site -- this is not a discussion forum, and not the place to request "other views". (Cc: @Gilles.) $\endgroup$ – D.W. Aug 26 '14 at 6:23
  • 1
    $\begingroup$ If I properly understand the question, the answer ies in the threshold theorem for fault-tolerance: if you can do single quantum gates with precision better than some threshold (say $10^{-4}$), then you can design quantum computers that will do arbitrarily long computations. You need to add more fault-tolerant overhead as the computations grow longer, but the amount is only polylogarithmic in the length of the computations. The threshold theorem isn't easy, and was counter to most people's intuition when it was proved. But if the universe works on quantum mechanics, it's true. $\endgroup$ – Peter Shor Sep 15 '14 at 2:54
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Uncertainty is fundamental in measurements, you could think on the decay of an individual atom, or quantum noise, this is not directly about simultaneous measurement, there is uncertainty in the measurement process, decoherence, you have uncertainty about the result being unpredictable. Agree about polarization, and other ways to control some degrees of freedom of the system to keep others non-interacting with the environment, but in the very moment of the measurement there is an intentional interaction, because it's when you get the result of the computation $\endgroup$ – HDE Sep 15 '14 at 13:18
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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