blogger weirdness
The blog template seemed to break overnight. Now, new posts seem to be disappearing...I'll fix it when things have stabilized a bit with the blogger system.
- posted by Jonathan @ 9:48 AM 1 comments

 
D-Wave Systems
MIT Technology Review has a short profile of D-Wave Systems, a company trying to become the first to sell quantum computers. The company's estimates for having a real product differ from what conventional wisdom would have: "The company plans to complete a prototype device by the end of 2006; a version capable of solving commercial problems could be ready by 2008, says president and CEO Geordie Rose. [...] D-Wave's first computer won't be able to accomplish the most widely touted payoff of quantum computing: factoring the extremely large numbers at the heart of modern cryptographic systems exponentially faster than any known computer. It will, however, be ideally suited to solving problems like the infamous traveling-salesman problem, in which a salesman searches for the optimal route among cities." From the article I don't understand their architecture at all; apparently instead of using entanglement, they use quantum tunneling, so I'm not sure in what sense their system will be a quantum computer.

[Update 2005-06-23] The Quantum Pontiff, reining in hyperbole like a black hole in a saddle shaped universe, pontificates that the D-Wave system will merely run quantum adiabatic algorithms.
- posted by Jonathan @ 10:22 PM 3 comments

 
New Paper With Huge Claims (Debunked?)
On 16 June 2005, Andreas de Vries released the paper: Fast quantum search algorithms by qubit comparisons exploiting global phase interference. The paper requires only basic understanding of quantum algorithms to follow. Assuming there's no fatal flaw somewhere, the results will have huge ramifications for quantum computation: The algorithm is able to find an item in an unsorted databse in O(log n) time, and implies that NP is in BQP. In other words, NP complete problems will be solvable in polynomial time on a quantum computer.

[Update 2005-06-23] According to the Quantum Pontiff himself, this paper is merely the latest in a long tradition to erroneously make these same grandiose claims. His post points out where he thinks the fatal flaw is, but adds more here.
- posted by Jonathan @ 4:14 PM 0 comments

 
Qudit Naming
Entanglement Made Simple (PhysicsWeb) begs the (un)important question -- what do you call qudits with more dimensions than 3?

The accepted names are:
2 (binary) qubit
3 (ternary) qutrit
D (arbitrary) qudit

Clearly the first two come from bit and trit, the common terms in the classical domain, which are loosely based (I assume) on the Latin names for bases:
2 binary
3 ternary
4 quaternary
5 quinary
6 senary
7 septenary
8 octal
9 nonary
10 decimal
11 undenary
12 duodecimal
16 hexadecimal
20 vigesimal
60 sexagesimal

(Eric W. Weisstein. "Base." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/Base.html)

If you took the boring route and named them after the Latin words, this is what you might get (your results on this [fairly pointless] exercise may vary)

4 quaternary: quatrit
5 quinary: quinit
6 senary: qusenit
7 septenary: quseptit
8 octal: quoctit
9 nonary: quonit
10 decimal: qudecit
11 undenary: qundenit
12 duodecimal: quduodecit
16 hexadecimal: quhexadecit
20 vigesimal: quvigesit
60 sexagesimal: qusexagesit

Those are mostly pretty terrible, almost as bad sounding as qualgorithm. So here's a modest proposal: instead of invoking Latin, replace the D in quDit with a number (but keep qubit and qutrit since they're pretty well accepted). e.g.:

2 (binary) qubit
3 (ternary) qutrit
4 (quaternary) qu4it
5 (quinary) qu5it
6 (senary) qu6it
10 (decimal) qu10it
16 (hexadecimal) qu16it

A bit hard to pronounce maybe, but easily recognizable in print.
- posted by Jonathan @ 12:23 AM 2 comments

 
42 Quantum Questions
I started this blog mainly to explore a variety of questions about quantum computer algorithms and related topics. This, I hoped, would foster some dialog in language that curious non-experts could mostly understand, while not offending the sensibilities of professional researchers. The contents of the blog have diverged pretty substantially from that, but I thought I'd list the types of questions I had in mind anyway (along with some I picked up along the way). Note there is lots of overlap, and the answers to some questions may conditionally make other questions moot. David Hilbert, I am not. (QC = quantum computer/computing)

1. Will QCs ever exist, and if so, how common will they become?
   
2. Where does the QC hype end, and reality begin?
   
3. Will writing QC software be fundamentally different to classical programming? What classical knowledge will carry over?
   
4. Will future programmers need to become well versed in quantum mechanics to understand and program QC's?
   
5. Will "Quantum Processors", if they come to exist, always be secondary to classical CPU's?
   
6. How many physical and logical qubits will be needed for "useful" quantum computation?
   
7. What is "useful" quantum computation?
   
8. How easy/hard is it to understand useful quantum algorithms, and the workings of QC hardware?
   
9. Are quantum computing pessimists on to something, or are they short-sighted? Or confused?
   
10. What computational problems are QC's poised to handle well?
    
11. What computational problems will QC's never be able to handle?
    
12. How do the computer science theory and physics communities regard quantum computing, i.e. As the inevitable future? A passing fad? An interesting but non-vital supplement to mainstream research?
    
13. Can quantum computers get us closer to proving P != NP?
    
14. How does one go about proving lower/upper bounds of QC algorithms? What implications does this have for classical algorithms?
    
15. If QC's never come to exist, will it be because something fundamental about physics makes them impossible? Or because they'll be too expensive to build? Or because there aren't enough potential applications to justify the effort?
    
16. How are the various QC architectures advancing? What is the frontrunner?
    
17. When a clear favorite jumps ahead, will the other architecture programs disappear?
    
18. What is the trajectory of experimental quantum computing (i.e. how many qubits by 2010, 2015)? Is it too early to say?
    
19. What is the quantum analog to Moore'e Law?
    
20. Will quantum error correction work as advertised?
    
21. How important/useful are Grover's/Shor's algorithms really?
    
22. Were Grover's/Shor's algorithms low-hanging fruit, or the product of extreme insight and imagination?
    
23. Are there any recent advances on par with Grover's/Shor's algorithms?
    
24. Do the papers that generalize aspects of Grover's and Shor's algorithms represent important powerful and practical extensions, or do they amount to trivial tweaking?
    
25. Is designing quantum algorithms difficult simply because it requires deep knowledge of several disciplines? Or is there something more to it?
    
26. What quantum physics experiments, specifically, could be simulated on a QC?
    
27. What will QC's mean for AI? Specifically: neural nets? Genetic algorithms? Something entirely different?
    
28. Will quantum computing have any impact on: Operating systems? Databases? The Internet? Games?
    
29. What classical models are most similar to quantum computer programming? i.e. parallel programming? Randomized algorithms? Nothing?
    
30. If a quantum algorithm produces only a sub-exponential speed gain over its classical counterpart, is it of any value?
    
31. Are there any efficient quantum algorithms that also run efficiently on classical computers, but are much easier to reason about in quantum terms than classical terms?
    
32. What can the idea of a quantum computer tell us about the universe?
    
33. What can quantum computing teach us about quantum mechanics (does it shed any light on entanglement? The measurement paradox? Teleportation?)?
    
34. What can quantum computing teach us about classical computing?
    
35. What can quantum computing teach us about the brain?
    
36. Is the universe a big quantum computer, and if so, how do we tap into its vast processing power?
    
37. Are there abstractions that will make programming QC's intuitive? Or is that fundamentally equivalent to making quantum mechanics intuitive, and therefore impossible?
    
38. What's the most efficient way to learn about quantum computing, for someone with: A computer science background? A physics background? A non-technical background?
    
39. Is understanding continuous quantum mechanics necessary for fully understanding quantum computing?
    
40. Is it possible to follow all the important quantum computing developments if one does not have access to all the notable expensive academic journals?
    
41. Quantum information theory placeholder (lots more questions here, but I've probably already gone overboard).
    
42. Does this line of questioning miss the point? What else should I/we be asking?
    

This blog has done a pretty terrible job of even discussing these questions. This is mainly because it's taken me a lot longer to really understand quantum computing than I expected, which will probably be the subject for a future post, if I can find the right way to put it.
- posted by Jonathan @ 9:20 PM 4 comments

 
Weakest Link in First Generation Quantum Cryptographic Systems
Peter Rohde accurately points out that the first generation quantum cryptographic systems do not exchange one time pads, as he assumed, but instead exchange keys for protocols such as triple-DES and AES. According to him, "Of course this completely undermines the security of QKD, since QKD inherently derives its security from the fact that the one-time pad is the only completely secure cipher."

Peter goes on to say: "My take on all this is that customers of current QKD systems are paying hundreds of thousands of dollars for cryptosystems no more secure than freely available software packages like PGP."

[Updated 2005-06-11] I responded to this in the comments section of his blog, which you can see along with Peter's response here (below the posting).

While the original designers of QKD might have had a one-time pad in mind for the key, current technology is not quite up to snuff to support the data rates one-time pad exchange would require for encrypting realistic amounts of data. So what's the point of QKD at all until the technology gets faster?

The benefit of today's QKD, which refreshes keys at the rate of 4 to 100 per second (depending on which company and press release you pay attention to) is a significant improvement over the classical alternative of today. Why? Well as engineers know, you never want a single point of failure in a system. But today's widely-used encryption protocols rely on just that -- a master key (usually an RSA private key) to exchange all the other keys. If that master key is ever stolen or deduced, than every transmission is compromised, until a new master key is issued.

In QKD, the master key is theoretically completely secure, so the weakest link of the system are the 4-100 keys that are exchanged every second. If someone was capturing all the data encrypted this way, they would need to break each key to see all the data being transmitted. Not theoretically impossible, but no more single point of failure either.

This might not sound great to some, but others are willing to pay tens of thousands of dollars to get top notch security, even if it isn't perfect. Those in the industry know that security is a relative concept.

This all gave me the idea for a feature that today's systems may be able to support: ability to send short one-time pads. If a brief, highly sensitive message needs to be sent, a few thousand bits of one-time pad could be distributed, before switching to back to triple-DES/AES mode for regular transmission.
[Updated 2005-06-11] (According to Peter, this already exists in some systems)

[Updated 2005-06-11] In a comment below his posting, Peter writes "Another point, which I didn’t mention, is that commercial QKD systems don’t actually implement ‘true’ BB84, since they don’t have true single photon sources. Instead they use attenuated coherent states which, at least in principle, introduces some room for intercept attacks." This is a good point, which actually makes it pretty difficult to truly compare first generation crypto systems with classical alternatives. A recent breakthrough will eventually fix this problem, but not for 2-3 years, according to the article, until it's commercially available.
- posted by Jonathan @ 5:16 PM 14 comments