{"id":140,"date":"2004-10-27T21:36:08","date_gmt":"2004-10-27T11:36:08","guid":{"rendered":"http:\/\/michaelnielsen.org\/?p=140"},"modified":"2004-10-27T21:36:08","modified_gmt":"2004-10-27T11:36:08","slug":"quantum-computing-one-step-at-a-time","status":"publish","type":"post","link":"https:\/\/michaelnielsen.org\/blog\/quantum-computing-one-step-at-a-time\/","title":{"rendered":"Quantum computing, one step at a time"},"content":{"rendered":"

For anyone interested in when we\u2019ll have large-scale quantum computers, there was a very striking paper<\/a> released today, by Manny Knill.<\/p>\n

To explain Knill\u2019s paper, I need to give a little background.<\/p>\n

Just a little over ten years ago, quantum computing suddenly took off when Peter Shor announced his fast algorithm for quantum factoring.<\/p>\n

In 1994, large-scale quantum computing looked like a pipe dream. Several people said publicly (and far more said it privately): \u201cyou\u2019ll never ever be able to build a device like that\u201d.<\/p>\n

The most common criticisms ran something like this: \u201cto quantum compute, you need to do Y and Z. At the moment in the lab, you can\u2019t even do A and B. Therefore, you\u2019ll never be able to quantum compute.\u201d<\/p>\n

The tempting response is to say \u201cwell, we\u2019re just about to do C and D, and E and F look pretty likely as well in a few years time. So maybe X and Y aren\u2019t so unrealistic.\u201d<\/p>\n

That\u2019s a tempting response, and it\u2019s how I used to respond to this sort of criticism. But it\u2019s turned out that neither the criticism nor the response is accurate.<\/p>\n

What\u2019s wrong with the argument is not (or not only) that it doesn\u2019t take account of technological progress from A to B to C and so on.<\/p>\n

No, the main thing wrong with the argument has turned out to be that it doesn\u2019t take enough account of theoretical<\/em> progress.<\/p>\n

Sure, over the years experimentalists have moved from A to B to C to D, and they\u2019re getting on to E and F.<\/p>\n

But in the meantime, theorists have shown that, actually, you only need to do J and K to quantum compute.<\/p>\n

(Alphabet not to scale. At least, not as far as I know.)<\/p>\n

In short, lots of discussions of the future of quantum computing are framed as though it\u2019s a fixed target<\/em>, like building a teraflop laptop.<\/p>\n

But it\u2019s not. It\u2019s a fluid target<\/em>, and pure theory can move us a lot closer to the target, without technology improving a whit.<\/p>\n

What\u2019s this all got to do with Knill\u2019s paper?<\/p>\n

To go back to 1994 again, one of the first responses to Shor\u2019s paper was numerous claims, some of them public, that quantum computing would never be possible because of the effects of noise.<\/p>\n

Roughly speaking, the argument was that quantum states are analogue beasts, and it\u2019s very difficult or impossible to protect analogue information against the effects of noise. Therefore, quantum computers will inevitably be overwhelmed by the effects of noise.<\/p>\n

In late 1995 and early 1996, Peter Shor and Andrew Steane independently showed that quantum information, despite appearances to the contrary, actually behaves much more like digital information. In particular, it turns out that the analogue continuum of errors apparently afflicting quantum states can effectively be digitized, and this enables error-correction techniques to be applied to protect against the effects of noise.<\/p>\n

I\u2019d like to emphasize, by the by, that this ability to digitize is a deep result, not at all obvious, and depends critically on certain special properties of quantum mechanics. It\u2019s difficult to give a short pat explanation, even to experts on quantum mechanics, and I won\u2019t try to explain it here.<\/p>\n

The error-correction techniques were quickly extended to an entire theory of fault-tolerant quantum computation<\/em>. I won\u2019t try and name names here, as a very large number of people were involved. Indeed, the development of fault-tolerance meant that 1996 was, perhaps the one year in the last ten in which progress toward quantum computing really did seem rapid!<\/p>\n

Roughly speaking, the takeaway message from all this work went something like this, circa the end of 1996:<\/p>\n

\u201cSuppose I can build individual quantum computer elements so they work with an accuracy of 99.9999% – the so-called threshold<\/em> value. Without error-correction, if I put 10 million together, there will probably be a few total failures that screw everything up. But I can use error-correction to reduce my error rate as low as I like, provided all my elements work better than that threshold. Whatsmore, this is true no matter how large the computation.\u201d<\/p>\n

This idea of a threshold for quantum computing<\/em> is an incredibly important one, and there\u2019s been quite a bit of work on trying to improve that number (99.9999%).<\/p>\n

Knill\u2019s paper is the latest in that line of work, improving the threshold.<\/p>\n

What\u2019s Knill\u2019s value?<\/p>\n

His threshold value is 97%. Or 99%, with more modest resource requirements in terms of number of gates, memory steps, etcetera.<\/p>\n

To state the obvious, having to do things to an accuracy of 97% (or 99%) is a far more encouraging state of affairs than 99.9999%.<\/p>\n

There’s a lot of caveats. The 97 \/ 99% number is for a rather artificial error model. Real physical systems don\u2019t behave like Knill\u2019s model. Indeed, it\u2019s not really clear what that number translates into in terms of actual physical parameters \u2013 heating rates, dephasing times, and so on. And Knill uses a model satisfying some assumptions that may not be such a good approximation in real physical systems; indeed, they may even fail completely. (This is true of all the threshold results, although there\u2019s been extremely encouraging recent progress<\/a> on this front too.) Finally, Knill’s approach has a rather high resource overhead.<\/p>\n

All the same, no matter how you look at it, moving from 99.9999% to 97 \/ 99% is pretty darn encouraging, despite the caveats. And I do wonder just how high the threshold can go.<\/p>\n","protected":false},"excerpt":{"rendered":"

For anyone interested in when we\u2019ll have large-scale quantum computers, there was a very striking paper released today, by Manny Knill. To explain Knill\u2019s paper, I need to give a little background. Just a little over ten years ago, quantum computing suddenly took off when Peter Shor announced his fast algorithm for quantum factoring. In… Continue reading Quantum computing, one step at a time<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-140","post","type-post","status-publish","format-standard","hentry","category-3","entry"],"_links":{"self":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/140","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/comments?post=140"}],"version-history":[{"count":0,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/posts\/140\/revisions"}],"wp:attachment":[{"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/media?parent=140"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/categories?post=140"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/michaelnielsen.org\/blog\/wp-json\/wp\/v2\/tags?post=140"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}