Seems I’ve been missing out on Ian Durham’s blog, Quantum Moxie. I’ve just added it to my blogroll. It’s well worth a look. I’ve spent a large chunk of an otherwise productive day reading back-posts.

If anyone is interested, I’ve finally uploaded my D.Phil. thesis. It’s still not on the arXiv, but I’ll eventually get around to doing that. It’s taken me the best part of a year to get it on-line, so I wouldn’t hold my breadth. In the mean time, enjoy!

Last Thursday our group had a visit from Herb Martin and Mohammad Amin of D-Wave. The point of the visit appeared to be largely to give our group a presentation on D-Wave’s progress towards building a commercially viable quantum computer. Although I had heard Dr. Amin speaking before at QEC 07, this talk was a little more expansive, and there was plenty of time for a question and answers session after the talk. Dave Bacon and Scott Aaronson have both been quite vocal in their criticism of D-Wave, so (Geordie’s blog aside) I’ve been waiting to hear the other side of the story.

Following the meeting I scribbled down my impressions of the current state of D-Wave’s efforts:

• D-Wave have constructed several device consisting of up to 28 noisy quantum bits (or qubits). Their internal roadmap apparently puts them at approximately 2000 qubits by the end of 2008. It is reasonable to expect that commercial applications will require on the order of 10,000 qubits or more.

• D-Wave have done a significant amount of theoretical work on understanding effect of noise on their system. While I find their noise model to be somewhat incomplete, they appear to have made reasonable approximations. It is not, however, clear to me that this tells us anything particularly useful about whether they should expect a speed-up over classical approaches.

• D-Wave appear to be ignoring the need to make adiabatic quantum computers fault tolerant. While their theoretical results show that a certain amount of noise be present without significant adverse affect, it has been known for years that such noise must scale proportional to the inverse of the total number of qubits. Above this threshold the device will give an incorrect answer. A part of the system noise will no doubt come from the fact that the system is operating at finite temperature. In order to continue to suppress errors, it is likely that the operating temperature of the device will have to drop proportional to approximately 1/N, where N is the number of qubits in the device. As the system is occasionally yielding incorrect results already, it seems unlikely that the noise can be sufficiently suppressed to allow systems of thousands of qubits to operate. Even if this can be achieved for large numbers of qubits, it will eventually fail, as field stability and other problems become the dominant sources of error. For this reason, systems which require the noise rate to scale as a function of the numbers of qubits are considered to be not scalable. Recently there has been a significant amount of work done on making adiabatic quantum computers fault-tolerant, however it is not clear that D-Wave has any plans to attempt to reach the required noise thresholds or adapt their architecture as necessary for fault-tolerant implementations.

• D-Wave have publicly demonstrated their system being used to solve a number of optimization problems, but have not yet made sufficient information available to determine whether their system is operating in the quantum regime. It is important to note here that getting the correct result is not an indication that the device is functioning as a quantum computer. Each of the problems they solve can be solved with a classical technique known as simulated annealing. As it turns out, replacing all of the qubits with classical bits (as happens if there is sufficiently high noise) converts an adiabatic quantum computation into classical simulated annealing, and should still yield the correct result with high probability. The main difference here is the time required to reach the final state. It is expected that adiabatic quantum computing offers a substantial saving (square root of the classical case) in scaling of time required as a function of the total number of bits/qubits. It is however impossible to tell which regime the device is operating in simply be measuring the time required to solve problems of a given size. (It would be necessary to know how that time changes as a function of input size). As a result, from the few experimental results made publicly available, it is impossible to tell whether D-Wave has produced a functioning adiabatic quantum computer or rather an expensive classical computer. The decoherence times given for their qubits are sufficiently small compared to the length of computation that it is seems very likely that their device is operating in the classical regime, rather than the quantum regime, and so is not a quantum computer.

• The device D-Wave has built is not a general purpose quantum computer, even if the effects of decoherence is ignored. Their current architecture is not capable of simulating the circuit model of quantum computation and so can not be used as a factoring machine, for example. D-Wave, however, do appear to have plans to extend their architecture to plug this gap.

• It appears that the current device solves problems by expressing them in terms of an NP-complete problem (this is essentially the hardest type of problem for which you can verify your answer quickly). For problems which are not actually this hard, expressing them as an NP-complete problem may slow down the process of finding a solution.

• It is clear from talking to Herb Martin and Mohammad Amin that D-Wave would be quite happy with producing a device which offers a factor of, say, 1000 speed-up versus a similarly priced classical computer. If this is the case, then the quantum advantage in scaling is beyond what they actually require, and so concerns about noise and fault-tolerance are less important. It should be clear, however, that if this is what D-Wave are aiming for, it is not a quantum computer but rather a special purpose classical computer. With a special purpose classical computer, it seems unlikely that they will be able to keep pace with Moore’s law, regarding the increasing speed of conventional semiconductor architectures.

I may have missed or misremembered something, as I only kept rough notes. The slides from the talk aren’t publicly available at the moment, but they were very similar to those used in the QEC talk, available here.

I’ve just installed a GreaseMonkey script which should now allow me to post on Blogger using LaTeX. Below is a sample of the output:

Example equation:

Not perfect, but not too bad either.

My wonderful girlfriend Amy has pointed out that I don’t have a link to her blog. Now I do!

A friend of mine, Jane Shuyska, has started a new blog called “Learning about (e-)learning“. I’ve added it to my blogroll. Do take a look. She has a really cool HDR picture she took.

Bruce Schneier points to post on Emergent Chaos, which gives a very bleak outlook for quantum computers being used to break public key cryptosystems.

The crypto-obviating algorithms in question are Shor’s algorithm for factoring and an algorithm he developed for discrete logs. I was surprised to learn that Shor’s algorithm requires 72k³ quantum gates to be able to factor a umber k bits long. Cubed is a somewhat high power. So I decided to look at a 4096-bit RSA key, which is the largest that most current software supports — the crypto experts all say that if you want something stronger, you should shift to elliptic curve, and the US government is pushing this, too, with their “Suite B” algorithms.
To factor a 4096-bit number, you need 72*4096³ or 4,947,802,324,992 quantum gates. Lets just round that up to an even 5 trillion. Five trillion is a big number. We’re only now getting to the point that we can put about that many normal bits on a disk drive. The first thing this tells me is that we aren’t going to wake up one day and find out that someone’s put that many q-gates on something you can buy from Fry’s from a white-box Taiwanese special.

So what’s wrong with this? The Quantum Pontiff defends the faith.

There is however one point which he, and apparently everyone commenting on this story, missed. The slow part of Shor’s algorithm is the modular exponentiation (which conveniently is also required by RSA itself). The claim that it is necessarily O(k³) is simply wrong. The Schönhage-Strassen algorithm can be used to implement modular exponentiation in O(k²) log(k) log(log(k)))!

But the really sad part of this is that Peter Shor says exactly this in his paper.

Asymptotically, the best classical result for gate arrays for multiplication is the Schonhage–Strassen algorithm [Schonhage and Strassen 1971, Knuth 1981, Schonhage 1982]. This gives a gate array for integer multiplication that uses O(l log l log log l) gates to multiply two l-bit numbers. Thus, asymptotically, modular exponentiation requires O(l² log l log log l) time. Making this reversible would na¨ıvely cost the same amount in space; however, one can reuse the space used in the repeated squaring part of the algorithm, and thus reduce the amount of space needed to essentially that required for multiplying two l-bit numbers; one simple method for reducing this space (although not the most versatile one) will be given later in this section. Thus, modular exponentiation can be done in O(l² log l log log l) time and O(l log l log log l) space.
While the Schonhage–Strassen algorithm is the best multiplication algorithm discovered to date for large l, it does not scale well for small l. For small numbers, the best gate arrays for multiplication essentially use elementary-school longhand multiplication in binary. This method requires O(l²) time to multiply two l-bit numbers, and thus modular exponentiation requires O(l³) time with this method. These gate arrays can be made reversible, however, using only O(l) space.

Does nobody read their references anymore?

If you ever use the phrase ‘Darwinist’ to refer to people who accept that evolution is the best explanation for how complex organisms arose on Earth, please stop.

We don’t use the phrase ‘Einsteinist’ or ‘Newtonist’ to refer to those who accept that gravity is the reason we stick to the ground. We don’t use ‘Leibnizist’ or ‘Maxwellist’ to refer to people who are confident that no matter how cleverly you arrange the magnets you can’t get more violate conservation of momentum. And we don’t use ‘Copernicist’ or ‘Keplerist’ to refer to those who deny the Earth is what planets orbit. There are people who use these terms, and we do have a word for those people; ‘crackpots’. The use of these phrases implies disagreement within the scientific community which is simply not there. It essentially equates these stances to subscribing to a philosophical school, implying that the there is no evidence to justify these positions. Reality has a well-known scientific bias! (With apologies to Stephen Colbert)

So why use ‘Darwinist’? Using it implies that there is some reasonable controversy over the validity of evolution within the scientific comunity, and there simply isn’t.

There is a reason we don’t have terms for the consensus position of the scientific community on these matters, and it’s the same reason we don’t have a specific word for somebody who does not believe in the Flying Spagetti Monster. It’s ridiculous to label everybody who is NOT in a specific microscopically small minority group.

With that in mind, I’m not too keen on ‘evolutionist’ either, but at least it avoids the connotation that we blindly follow the teachings of some guy called Darwin.

While over in Singapore, I was sharing an office with Pieter Kok, and a rather amazing thing happened. When he connected his new ipod to his laptop, iTunes managed to fill it with music, and by that I mean 0kb free. I was utterly amazed at this, since it essentially requires solving the subset sum problem, which is NP-complete. Anyone know if and how iTunes cheats?

Earlier this evening I went to the first event of the Ig Nobel tour of the UK. I’d been once before, and so Peter Rohde and I made about 20 paper airplanes waiting for the event to start (it’s a tradition!). We didn’t want to be the first to throw one, and so we waited for someone else to start. No one did! My disappointment knows no bounds.