The Case Against Quantum Computing

Let me present it a different way.

Someone comes to you with two formal models of computing. Both models involve representing the state of the computer as a vector of real numbers, they both involve finite dimensional subsystems combined with a tensor product, both involve gates defined over the reals also combined via the tensor product and so on. That is, both models are just about evolution of a vector in some (very high) dimensional real vector space according to gates acting on a small number of subsystems. In fact these two models are identical, except for the fact that in model A the readout procedure involves computing a property of the output vector with the 1-norm, while in model B the 2-norm is used.

This is not an analogy, these are valid mathematical formulations of classical and quantum computing, the correspondences (and differences!) are well understood and rigorous.

Now you read an IEEE article that vociferously objects to the feasibility of building a computer based on model B, but all the objections are to do with properties of model B that it fully shares with model A. And model A you know can be very well approximated already in the physical world, which means reality was somehow was not inhibited by those objections. To try and refute the physicality of model B with an argument based on premises already satisfied by model A is silly.

(Note that even if it were the case that complex numbers were necessary for quantum computing, which they are not - see eg. my book Q is for Quantum - you can map the quantum density matrix on n qubits to a real vector over the basis of Hermitian matrices).

Likewise, you don't ever explore the entire state space when you perform quantum computation. As it happens, most states are inaccessible. As shown by Poulin et al. in Physical Review Letters, 106, 170501 (2011), you can only ever explore a very small fraction of quantum states in polynomial time.

Edit: tezthenerd has said pretty much the same thing below. I just included the reference in case you'd like a formal proof.

There's a lot of misinformation in this space, so be careful who you listen to. I hope to say as few false things as possible, but I can offer no guarantees.

One source of confusion is that there are different types of proposed quantum computers. Some, like the D-wave machines, use stochastic measurement processes to arrive at probably-correct solutions. This is called "annealing", and it's a lot like what many machine learning algorithms do to try and find global minima in error function spaces, only the quantum mechanics gives it an edge in not getting stuck in local minima for various reasons.

These aren't universal computers - they only implement very specialized algorithms in a kind of abstract sense. It's sort of like how if you take a box of different sized rocks and shake it for a while, you'll eventually find that the small rocks have made their way to the bottom and the bigger rocks have drifted to the top (this is called granular convection). There's a sense in which this is like a search algorithm that helps you find the biggest rocks. The quantum version of this (very loosely speaking) would be if the rocks sorted themselves faster because the small rocks would sometimes just tunnel through the big rocks.

Using quantum effects to speed up annealing lets you do annealing faster than a classical simulation - but most problems aren't annealing problems. So present day quantum computers are specialized machines that do a kind of computation using quantum effects, but they can't run general purpose quantum algorithms. Think of them like co-processor chips that aren't quite CPUS.

That said, it's sort of hard to define what a general purpose quantum computer would even be (for various reasons), so maybe that's unfair. Anyway, D-wave machines can't run Shor's algorithm, which is one of the examples of the "exponential speedup" over classical computation.

The (claimed) algorithmic efficiency of quantum computing as it applies to quantum algorithms has to do with how much computation is done in each step.

We represent information in physical systems and process that information by making those physical systems interact in a way that affects a state space transformation. The amount of processing we can do in "one step" depends on the size of the state space of our data representation and the kinds of operations we can affect via physical interactions. Conventional computation involves a bunch of parallel systems that have 2 distinguishable states interacting pairwise through networks of logic gates that perform a limited number of transformations.

Systems of qubits have many more than 2^N distinguishable states (technically, an infinite number), and operations on them can be arbitrary linear transformations. So each quantum logic gate can do a lot more computation than a classical binary gate. Quantum algorithms basically translate information in the limited classical state space to the bigger quantum state space, do fancy operations, then project back into the classical space. It's sort of like data parallelism in the sense that if you can do a series of small operations or one big SIMD operation, the latter will generally be faster. Operations on qubits make use of physical parallelism that's only possible in the much bigger non-classical state space.

The argument here is nonsensical.

For example, "With what exactitude must, say, the square root of 2 (an irrational number that enters into many of the relevant quantum operations) be experimentally realized? Should it be approximated as 1.41 or as 1.41421356237? Or is even more precision needed? Amazingly, not only are there no clear answers to these crucial questions, but they were never even discussed!" This is completely wrong. Of course the field has studied this problem; people aren't idiots.

But your concern is also wrong. Preparing the initial state is easy; quantum algorithms generally start in the all-0s state. Even quantum devices like the D-Wave machine, for which there is considerable skepticism about its workings and power, can easily be initialized in the all-0s state.

(With error correction, one needs to prepare the encoded all-0s state, which is indeed difficult to prepare. But in principle it is doable.)

Black swans are rare.