What nonstandard theory forbids quantum computers?

Question

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?

Answer 1

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.

Answer 2

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.