What would a nonstandard model which reproduces all experimental quantum data so far but still cause quantum computers to fail when implementing Shor's algorithm look like? Would it have to be very convoluted and conspiratorial, or are there natural models?


In order for Shor's algorithm to fail, you need only some source of fundamental decoherence that is visible for highly entangled many-qubit states, which is not visible for ordinary states.

You can model this decoherence source as a density matrix super-operator which reduces off-diagonal matrix elements. A quantum density matrix generally evolves with a unitary rule:

$$ i{\partial \rho \over \partial t} = [H,\rho] $$

(up to a sign), but there is no consistency restriction forbidding you from adding a decoherence operator to the right hand side, which is an arbitrary linear function of $\rho$. The consistency requires that the trace of $\rho$ is conserved, and there is a further constraint from the fact that the operator is positive no matter what the quantum system is entangled with. The experimental constraints on fundamental decoherence from ordinary quantum mechanical systems is far too weak to guarantee that quantum computers will work. This is the most natural generic modification.

A poor-man's model for this is to just do a partial Wick rotation. To reproduce quantum mechanics from a path-integral, you need to do an analytic continuation from imaginary time correlation functions (which are computable from monte-carlo and therefore incapable of quantum computation) to the exact real time axis. If you only do a continuation to the $(1+i\epsilon)$ real time axis, so that there is a tiny imaginary part, you can do the continuation computationally for any nonzero $\epsilon$, and therefore you don't get quantum computation. Because this is the wrong model (the right model is the previous one), the experimental constraints on $\epsilon$ are absurd, you have to hug the real axis to prevent violations of unitarity and conservation of energy. But because Shor's algorithm take many, many, operations, it is far more sensitive to a tiny $\epsilon$ than few-particle correlation functions which reproduce things like masses and interactions.

The natural models which lead quantum computers to fail are those which are realistic and holographic. There are no well accepted models of this sort, but t'Hooft has been struggling to make such models, and has provided solid intuition for how it should work, if it does work. In a holographic model, there is imagined to be order 1 bit per Planck area on the cosmological horizon, so order $10^{136}$ bits overall (this is more than $10^{36}$ bits per particle in the universe, so there is enough data to always be in essentially the continuum limit). If you make a model which is approximately quantum of this size, it must fail to reproduce quantum mechanics when factoring numbers where $10^{136}$ classical bits just can't do the search reasonably. Such numbers are less than 1,000 decimal digits in size, say 10,000 just to be sure, and are easily factored by a large quantum computer with some hundreds of kilobytes of quantum memory.

  • $\begingroup$ You are changing the rules of the game. If the evolution of a physical system didn't follow the evolution equation for the density matrix that you correctly wrote down i.e. if there were some extra "decoherence-like" effective terms, it wouldn't be a description of a quantum computer. It's like if someone asks whether glass may be almost transparent and you answer No, it possibly can't because you may contaminate the glass by black ink. Obviously, the freedom to contaminate glass has nothing to do with the existence of transparent glass. $\endgroup$ – Luboš Motl Aug 16 '12 at 19:32
  • $\begingroup$ Let me also mention that the fundamental equations of the Universe around us cannot have extra terms beyond the equation you wrote down – extra terms are inevitably "effective" and approximations only. It's because the extra terms would lead to a change of $\rho\ln(\rho)$ and a violation of CPT of the fundamental equations. However, the fundamental equations have to be CPT invariant due to the Lorentz symmetry. But even if one decided to deny the Lorentz symmetry, the extra terms in the fundamental equations - a loss of unitarity - would lead to inconsistencies. $\endgroup$ – Luboš Motl Aug 16 '12 at 19:47
  • 1
    $\begingroup$ @LubošMotl 1) The CPT theorem assumes locality. 2) Could you clarify this "extra terms would lead to a change of $\rho\ln (\rho )$ and a violation of CPT"? $\endgroup$ – Diego Mazón Aug 16 '12 at 20:04
  • $\begingroup$ @drake: Lubos is right that the extra terms generically lead to violations of time-reversal invariance, they must to produce decoherence, since decoherence increases entropy. This is something that needs experimental checking. Where he is not right is that they necessarily break CPT in the sense of breaking Lorentz invariance. CPT assumes that the theory is described by quantum mechanics, and then does rotation in imaginary time. The proof doesn't work in this modification, and you can break CPT in decoherence without breaking Lorentz invariance. $\endgroup$ – Ron Maimon Aug 17 '12 at 2:17
  • $\begingroup$ @RonMaimon I supposed that he was right, I was asking for an explanation. If the term increases the entropy I don't understand why it breaks T or CPT $\endgroup$ – Diego Mazón Aug 17 '12 at 3:45

A quantum computer running Shor's algorithm or any other quantum algorithm is only composed of simple quantum elementary building blocks of the same kind that can be experimentally tested – e.g. electrons' spins and procedures to transform them. It only differs from the case of several electrons by their large number.

So if a theory exactly agrees with the experimental tests of the predicted behavior of one electron's spin or two electrons' spins or several electrons' spins, its predictions inevitably agree with the predictions of quantum mechanics about quantum computers i.e. with the behavior of Shor's algorithm.

There exists no way to "cherry-pick" applications of quantum mechanics that should be confirmed and those that shouldn't. If a theory agrees with the experimental data about the microscopic world, it inevitably follows that it is a quantum theory and once it is a quantum theory, it inevitably predicts that cool enough etc. arrangements of the microscopic building blocks (I mean qubits) inevitably behave in the way in which quantum computers should behave.

The scenario you propose is exactly as impossible as the desire to construct a theory that predicts the same behavior of several transistors as proper theories underlying electronics but if you happen to combine the transistors to a computer, it doesn't work. Such a combination of facts simply isn't possible. The working of the computer fully boils down to the elementary building blocks – and this is true both for the classical computer composed of transistors as well as a quantum computer composed of spins or other qubits. The classical computer building as well as the "science of quantum computation" isn't a part of science that has the potential to modify the fundamental theories; instead, they are just examples of applied sciences or applied mathematics or engineering – something that uses known laws to create useful devices (in the case of quantum computation, on the paper only so far, but that's for technical reasons only and this fact plays no role in this discussion).

A theory is either correct – being quantum is a necessary condition for that – or incorrect. There can't be any "model" that would agree with the observations but that would also selectively modify some unwanted predictions of quantum mechanics. Quite generally, the term "model" is misleading and could apply to computer programming or set theory but not to physics. In physics, we only use the term "model" if we only modify some detailed technical properties of the laws we use to describe the Universe (or speculate how the Universe could work) but when we change the essential things, we talk about "theories". A framework that disagrees with the quantum mechanical predictions about simple objects such as spins or superposition of quantum states is an entirely different framework, a radically inequivalent theory, and surely cannot be described as "just another model". Such a radically different theory obviously disagrees with the observations, too.

  • 4
    $\begingroup$ -1: This is an incorrect answer--- in order for Shor's algorithm to work for a large system, there must be absolutely no decoherence in a hundred-thousand cubit system, or only such decoherence which can be fixed by Shor's error correction algorithm. It is an unwarranted (but reasonable) extrapolation that the parts of QM that can be tested imply that the untested parts work. One must keep an open mind until such time that they are tested. $\endgroup$ – Ron Maimon Aug 16 '12 at 17:43
  • $\begingroup$ Your objection makes absolutely no sense, @Ron. A quantum computer is defined as a device in which decoherence doesn't enter or is weak enough that it may be neglected and this property is guaranteed by having appropriately low temperatures and weak interactions with the environment etc. If those conditions aren't satisfied, then it's simply not a quantum computer. So your protests against the answer are based on distortions of the meaning of the words in the question. $\endgroup$ – Luboš Motl Aug 16 '12 at 19:22
  • $\begingroup$ Your are misintepreting the meaning of the term "quantum computer" and you are distorting the meaning of the term "decoherence", too. I mentioned the first: in contrast with your propositions, a gadget dominated by decoherence is not a quantum computer, by definition. Similarly, it is nonsensical to suggest that decoherence could be something we can't remove. Decoherence is, by definition, a process with completely well-known reasons, a process we understand, and we can prove that it disappears when $T=0$ etc. If it couldn't be suppressed in principle, it wouldn't be decoherence. $\endgroup$ – Luboš Motl Aug 16 '12 at 19:26
  • 4
    $\begingroup$ Using "quantum computer" solely for decoherence-free (or nearly so) devices is defining the problem away. As Ron points out, decoherence is well understood and tested but only for few-qubit systems - hence the current lack of a working quantum computer - and while we hope this remains the case for larger systems, we still need to check that. Reserving the term "decoherence" for what we theoretically understand is, again, defining the problem away, and would leave us in poor standing should that understanding not hold up for larger systems. $\endgroup$ – Emilio Pisanty Aug 16 '12 at 23:35
  • $\begingroup$ Please note, also, that I do think QM will prove accurate all the way up to the level where an actual, physical quantum computer gets built and works. Using the term for the blueprints of devices that exist currently only in our heads is, I believe, a disservice to the future physical devices we hope to build. $\endgroup$ – Emilio Pisanty Aug 16 '12 at 23:38

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.