This topic comes up periodically but for me had always been one of those things I’d get around to understanding better someday. A recent blog in SemiWiki got me looking a little harder and determined to write a blog to get this out of my system, if for no other reason than getting rid of excess tabs on my browser. So here’s my quick review. Apologies as always to experts in the field.
Core Principle
If you have a little quantum physics background and a decent amount of imagination, this is pretty simple. Conventional computing relies on Boolean logic – bits are either 0 or 1. Quantum computing (QC) relies on bits (called qubits) based on things like electron spins which can be up or down (corresponding to 0 or 1) but can also be in superposition states, where say there is 50% probability a qubit is in one state and 50% probability it is in the other state.
Now put ‘n’ of these superposition states together and run an algorithm, say searching for all prime numbers representable in that set of qubits (up to 2[SUP]n[/SUP]). If you did this with conventional bits, you’d have to check each number serially (maybe a few numbers simultaneously on each pass if multi-processing). But with qubits you can check all 2[SUP]n[/SUP]possibilities simultaneously, at least in principle, because each qubit carries both a 0 state and a 1 state.
Who cares?
Since QC can reduce some high-complexity problems to very low complexity, it has the security industry concerned. Some popular encryption techniques exchange a public key which is the product of two large prime numbers. Decryption is only possible if you know the two prime numbers and security lies in the extreme difficulty of factoring in these cases.
But with QC, Shor’s algorithm has been shown to be able to factor large numbers with ~O(logN)[SUP]2[/SUP] complexity which would make standard encryption techniques easily crackable at any reasonable key size. (In fact all the standard techniques appear to be vulnerable to QC, not just the product of primes methods).
How does QC work?
Not much like Boolean logic; you have bits and gates but there the similarity ends. You’re working with superposition states so the logic looks quite different. A qubit is modeled as a 2-component vector, and a single-input logic function can be represented as a 2×2 matrix. One example is the Pauli-X gate, which is the QC equivalent of a Boolean invertor:
The input vector is transformed by the matrix and the output is a 2-component vector. For a 2-input quantum gate, each input requires a 2-component vector and the logic function has to grow to a 4×4 matrix. For example, a Controlled-NOT (CNOT) gate looks like:
Don’t worry about the math or the gate-types – what’s important is that the inputs are superposition states (2-component vectors per qubit) and the outputs also have to be superposition states. All QC gates can be reduced to a small set of universal quantum gates – from these you can build whatever logic you want. The math has been figured out, the best gates to build are known, now you just have to build them.
Implementation Realities
Before you get too excited, building a QC is not easy. There are at least 3 main problems: building the qubits themselves, building the logic and managing decoherence.
Building qubits is somewhat under control, at least in the lab (and D-Wave). Early mechanisms used superconducting Josephson junctions, but these commonly depend on fairly exotic materials like niobium-tin alloys or yttrium-barium-copper-oxide (YBCO) which makes them less than friendly to traditional semiconductor manufacturing flows.
More recently qubit implementation in quantum dots on silicon substrates has been demonstrated; this is closer to something that might eventually be manufactured in volume.
Logic gates have made similar progress, but only very recently (late last year) for 2-input gates in silicon, in which an Australian group demonstrated that a large number of 2-qubit operations could be completed within the “quantum coherence time”, making scalability look achievable.
This coherence time is critically important in the QC world. Superposition states are very fragile, so any uncontrolled interaction with the environment (through thermal noise for example) can cause a state to decohere into a single state or some unrelated superposition, destroying any progress made in calculation. This is why QCs run at very low temperatures (tenths of a kelvin or even milli-kelvins) – not to support superconductivity but to reduce thermal contributions to decoherence.
For silicon-based devices it is also important to use isotopically-purified silicon. [SUP]29[/SUP]Si nuclei (one neutron added to the more common [SUP]28[/SUP]Si) can spin-couple to qubits, causing decoherence. NIST has been working in this area and has now demonstrated purification to 99.9999%.
So there are probably no insuperable barriers in the silicon technology direction but the cooling requirement, at least in the mainstream, is substantial: liquid nitrogen to get down to 77K, liquid helium to get from there down to 4K and adiabatic demagnetization to get from there down to sub-K temperatures. And you have to vacuum pump the enclosure before you start cooling. (In fairness, there are mechanical alternatives to the first two steps but these generate significant vibration – also unfriendly to coherence – and are very power-hungry.)
This is not something you can shrink onto a chip. If you look at a picture of an any opened up QC, you see the kind of structure that sits inside an ultra-low temperature physics experiment. Most of the computer volume is going to be dedicated to cooling, a good piece of which is simply thermal separation between the part that has to get very cold and the rest of the ambient temperature world.
There is some intriguing work being done on electron cooling in quantum wells inside room-temperature semiconductors, though so far this only gets down to about 45K and probably not close to thermal capacities adequate to cool a full QC chip.
To be complete, there is a concept of quantum error correction which can help sustain coherence longer than might otherwise be possible. This is interesting technology in its own right – you can’t just look at qubits, figure out what’s wrong and correct them as in conventional EDC. Looking at a qubit constitutes measurement, which immediately causes collapse of the superposition into one of the measurable states. There’s some real cleverness in how this is done to avoid collapse. But this is just a way to extend coherence times – it’s not good enough to get rid of the need for cooling.
Summing up
QC is not even remotely close to a panacea – it’s good for solving problems which benefit from having bits in superposition states – list searching in general and related problems like factorization are good examples, also modeling certain quantum-mechanical problems beyond the reach of conventional computing.
But there are other encryption methods for which QC methods are not known to improve significantly over existing methods. A recent proof asserts that the very great majority of classical algorithms would not benefit at all (or only marginally) from QC. So even in principle, this will remain a special-purpose (though quite possibly highly valuable) form of computing.
The highest published successful factorization I have seen is for 56,153 (not on a D-Wave as far as I can tell) – not yet grounds for concern over security hacks. Of course, who knows what the NSA (or even Google) have not published. D-Wave claims a 512-bit qubit machine which in principle could do much better, though I would have thought universities would be eager to claim bragging rights for higher numbers and they’re not constrained by secrecy or manufacturability considerations.
The technology is advancing, still has a way to go on silicon, but cooling requirements will limit this for quite a while to installations that can support the liquid nitrogen and liquid helium infrastructure (perhaps eventually superior methods, but don’t bet on Peltier coolers – they’re not even close). Probably wise not to expect desktop versions in your lifetime…
You can learn more about Josephson qubits HERE, Quantum dot qubits in silicon HERE, Logic gates in silicon HERE, electron cooling in quantum wells HERE and the highest published QC factorization I could find HERE.
Share this post via:
Next Generation of Systems Design at Siemens