A Tiny Startup Racing Google to Build a Quantum Computing Chip

There are like 5 superconductor guys and 3 ion trapping guys, so I guess they're going for superconductor qubits. Unless they're doing way better than the superconductor groups in academia, I wouldn't hold your breath, it's still pretty far from a workable technology.

You can be damn sure that the NSA and the other three letter agencies are working hard on this problem, and definitely would not share if they get there first (if they haven't already).

In case this leads to the usual "what's so hard about quantum computing that these big companies are struggling with it, and how can a small company possibly hope to beat Google?" let me try to explain.

Quantum computers seem to do some stuff more efficiently than any classical computer can. Exact proofs are hard to come by. (The classes are BQP and BPP, with a straightforward proof that BPP is in BQP. We now have a bunch of oracles Q Such that BQP^Q /= BPP^Q, but that's not necessarily a proof because of course we now have oracles A and B such that P^A = NP^A but P^B /= NP^B. So we have "some evidence" that quantum computers can do things faster than classical computers, but it's not hard proof yet.) Those parenthesized concerns aside, quantum computers seem to be more efficient than classical ones at some tasks.

We call by the name "interference" this property which crucially dictates how quantum computers do stuff differently. Essentially, instead of using probabilities with real numbers between 0 and 1, quantum mechanics uses scaled rotation matrices, which we call "amplitudes" and often represent as complex numbers. We bound the scale factor between 0 and 1 and interpret its square as a probability, which yields the same result as multiplying the complex number by its complex conjugate, or multiplying the matrix by its transpose: these are all mathematically equivalent. In this framework, if the qubit |0> produces an amplitude-pattern f(z) on some screen (hence you'll see |f(z)|^2 as the pattern) and |1> evolves to g(z), then the "quantum superposition" a|0> + b |1> (where a, b are complex numbers) evolves to produce the pattern |a f(z) + b g(z)|^2, which might show some sort of "wavy interference pattern" wherever the original patterns |f(z)|^2 and |g(z)|^2 overlap.

These interference effects can also be seen over multi-bit quantum states like the system a|00> + b|11>. In such a circumstance we call those two parts "entangled", and we can prove that there is no precise quantum description which "separates" the two quantum-bits. However physicists have proven a crucial theorem in quantum mechanics: when you look at one of those entangled-parts in isolation, it behaves according to classical probability laws. This is derivable purely from the mathematics of these complex amplitudes and we usually call it "tracing out" the rest of the system, if you want a convenient jargon term.

What entangles a system with a quantum-bit? Anything which interacts differently based on whether the quantum-bit is 0 or 1. The intersection of these two concerns -- the universality of entanglement and the classicalness that entanglement creates -- is the thing which makes quantum computing complicated. The very interference effects which make quantum computing powerful disappear the moment that "anything else" entangles with our precious quantum bits: and this includes any part of the external world (so the quantum state needs to be well isolated from anything that is not its logic), but also the computer itself (the complicated "quantum gates" that we need to implement to guide the state in whatever direction it's going). If any of those things entangle passively with the quantum state, the parts that we can measure stop showing interference effects and start acting like classical probabilistic mixtures.

This problem in general is called "decoherence" and it is the hard problem in the "DiVincenzo Criteria", which are the 5 joint concerns of quantum computation. So there are basically 4 other things that you basically are not allowed to compromise to kill decoherence: (a) a qubit-centric system of states |00...0>, |00...1>, ... |11...1>, which (b) can be initialized to a known starting state |00...0>, and then (c) its qubits can be manipulated by a set of universal quantum gates, which then (d) are measured to be either 0 or 1.

So that's where somebody who has a really bright insight about solving this "decoherence" problem could really leap light-years ahead of a bunch of highly-paid engineers and scientists who lack the crucial insight.

[0] http://www.scottaaronson.com/