Quantum Algorithms

Polynomial-time quantum algorithm for the simulation of chemical dynamics

2008-12-03T12:08:00.002+10:00

Via ars technica's Noble Intent,
Polynomial-time quantum algorithm for the simulation of chemical dynamics:

Building on prior work in quantum computing algorithms, the researchers here developed an algorithm capable of computing the wavefunction of a chemical system some arbitrary time t after the simulation begins at time t=0. The algorithm requires a relatively small number of qubits.

Saving the Planet, One Line of Code at a Time

2007-04-12T15:30:00.000+10:00

Surely us lowly computer programmers can't do much about climate change, right? I mean, maybe we could drive a Prius to work, or work for Google, but short of that, code is code, isn't it? Well maybe not. Here are a few things programmers could do to fight global warming:

* Boycott Windows Vista. Windows Vista is an energy-wasting nightmare, requiring grunty graphics cards and cutting edge CPUs just to perform basic windowing operations. By writing PC and web applications that deliberately don't work with Vista, you can help cajole users into running a less resource intensive operating system.
* Don't ouput blank or nearly-blank pages to the printer. Have you ever printed a document from Word and got a completely blank page at the end (except for maybe a page number)? Or have you ever printed something from an email application or web site and gotten a final page containing almost nothing but a useless footer? This type of waste must add up. Sure you can recycle the paper, but recycling takes energy. Better to not print the page in the first place. If the user really needs that last bit of information printed out, they can opt-in and get it printed. But tree-saving mode should be enabled by default.
* Write more efficient code. A CPU running at 100% capacity is sure to draw more current than a CPU with less load. So code more efficiently and use less electricity. (Of course if hardly anyone uses your software, and reducing clock cycles requires you to drive to work more or keep the lights on later, this could be counter-productive)
* Support older computers. Older computers have cooler processors and less memory and therefore use less electricity than newer ones (especially if they're connected to an LCD monitor). By coding for them, you encourage their use. Recent versions of Linux should run happily on older computers that wouldn't support Windows 2000, let alone XP or Vista.

Got any more ideas?

On D-Wave

2007-04-11T13:48:00.000+10:00

The D-Wave announcement and flood of articles and postings that have come from it sheds some light on the uneasy intersection of academic research and cutting edge private research.

Companies, being profit oriented, need to maintain a certain level of honesty if they want credibility with their potential customers and investors. They also need to carefully frame their announcements and dealings with the press in order to maximize their attractiveness, without crossing the line into outright deceit.

Scientists, being truth oriented, need to meet a higher level of honesty, the kind that includes bending over backwards to show how they might possibly be wrong.

Few companies could go very far if they attained academic-grade honesty, since exposing all their weaknesses would scare off potential investors. In a world where everyone exaggerates and everyone assumes everyone exaggerates, being very modest as a company is tantamount to admitting failure.

D-Wave doesn't have to please academics, because academics are not investors nor potential customers (on any significant scale). For D-Wave, exposing their technology to academic-grade scrutiny can only be bad: either it will reveal that the emperor is wearing no clothes (i.e. they have essentially built an expensive, 16 bit classical computer) or else they are really onto something, and their ideas will be revealed to potential competitors.

More on My Ideal CS Cirriculum

2006-11-03T10:47:00.000+10:00

Alice had some interesting things to say about my previous post. Instead of responding to Alice's comment as a comment, I thought I'd make it an entry by itself.
She wrote:

"I go to a school where there is no computer science department, and thus all of the "computer science" courses I've taken have actually been math courses. I don't exactly think I've somehow satisfied the requirements for a undergrad degree in CS, but I am hoping to persuade some CS PhD programs to let me in anyway. I like the idea of a CS degree as fundamentally distinct from software engineering or what have you, though it is kind of strange for me to actually have this degree given the current expectations of graduate programs."

From my understanding of the current climate, I think you'll find graduate CS programs put a lot of value on applicants who have mathematical maturity. This would be especially true if your interests are more on the theoretical side than applied CS. See this discussion on Lance's blog.

"I found that understanding object oriented programming helped me when I got to my programming languages class. The concept of an object helped ease in things like functions being first order in SML (or really in lambda calculus). Would you really not want to teach this? Or just teach it conceptually, leaving out many of the details of implementation?"

Object oriented style programming is found pretty much everywhere to a degree, even in simple functional languages and plain C. But getting very deep into OOP very early is a distraction from more fundamental principles which should be learned first. A lot of huge and successful software has been written without the benefit of explicit object oriented programming. Also, most research on the theory side is completely orthogonal to anything object oriented.

I've been influenced a bit by Alexander Stepanov, the creator of the STL (Standard Template Library of C++) which is one of the most useful and well written libraries I have ever used. You might find this interview with him interesting. He finds absolutely no value in things like inheritance and virtuals. I'm not as extreme as him, but I do think that these concepts are overused.

"Most of my classes have had some programming projects, but we weren't really taught to program so much as sent off to make something that worked in the language of our choice. Often we would modify existing code, so the projects were smaller but more focused on the theoretically significant bits. Would the theory courses have programming components?"

Yes they would, which is one reason why I think a functional language should be taught from early on. Many theoretical concepts can be illustrated in languages like Scheme or ML without too much extra baggage.

"I'm kind of surprised that you leave automata to the third sequence - this was actually the first thing I learned in college CS class, concurrent with an overview of very simple programming structures (variables, loops, etc) in java. What's the rational for this?"

It's interesting you learned it so early; I can certainly see the appeal of learning it alongside your first language. But I left it until a bit later because I think a certain degree of mathematical and computer science maturity is needed to appreciate and understand automata.

A Better CS Degree?

2006-03-06T23:54:00.000+10:00

Reading a recent post on Can't Count Sheep got me reflecting on my own CS degree (obtained nearly 6 years ago). My course work seemed to be about half practical and half theoretical, which added up to very little. I have no one to blame but myself for what I didn't learn, but my ideal degree would cover a lot more fundamentals and a lot fewer applications. I'd say it's more valuable for a CS graduate to be comfortable with Knuth than object-oriented Java.

My ideal CS curriculum
My ideal CS degree is basically an algorithms degree, with abstract problem solving as an overarching sub-text. Programming languages and mathematics are taught for the sole purpose of enhancing understanding of algorithms.

Topics like databases, compilers, AI, networking, graphics, operating systems, object-oriented programming, robotics, etc are not included. (Undergraduate HCI will be moved to the communications department.) Yes, on one level most of these types of courses are about special classes of algorithms and data structures. But it's important that more fundamental notions are well understand first before writing FTP clients and OpenGL based games. My view is applications should be learned on the job, through projects, or in a masters program, but should not displace fundamentals.

The curriculum is divided into 6 sequential lots. Classes in a lot may be taken in parallel, and there are no electives. Each lot, excepting the first, requires a project. At least 2 of the projects undertaken by each student must be software systems, and at least 2 must be theoretical research projects. The students may choose their own projects, but they are supervised by grad students and have various deliverables. Students may work individually or in groups of 2 or 3, but proportionally more is expected out of multi-person groups. Projects are also required to be increasingly sophisticated as students advance.

Most classes would involve components of theoretical coursework (i.e. problem sets) plus programming with both Scheme and C. The types of programs required would not be large and complex, but instead short and very challenging. Both C and Scheme are emphasized because they encourage thinking in two very different perspectives. Programming is included even for traditionally theoretical courses.

I thought it would be better to err on the side of too much math and not enough EE or Physics (actually none).

First lot:
00] Intro to programming with C (like Stanford's 106x when it was C based)
01] Intro to programming with Scheme (like MIT's 6.001)
02] CS Math 1 (discrete mathematics) (i.e. Stanford's CS 103x)
0x] Non-CS specific math (i.e. calculus, linear algebra, basic
statistics)

Second lot:
10] Deeper C (similar to the first half of Stanford's old CS 107. Also includes enough Unix API to serve later classes, and a small bit of assembly)
11] Introduction to algorithms and data structures (i.e. Stanford's CS 161)
12] CS Math 2 (logic and proofs)
13] Project 1

Third lot:
20] Automata and Complexity Theory (i.e. Stanford's CS 154)
21] Parallel and Distributed Algorithms
22] CS Math 3 (set theory, number theory)
23] Project 2

Fourth lot:
30] Intro to NP Completeness
31] Tree, Graph and Network Algorithms
32] Intro to Information Theory (similar to MIT's 6.050J)
33] Project 3

Fifth lot:
40] Searching and Sorting
41] Intro to Randomized algorithms
42] Intro to Quantum Computing
43] Project 4

Sixth lot:
50] Quantum Algorithms
51] Heuristic Algorithms
52] Provably Correct Programs (using the Z language)
53] Project 5

Notes
Course [21] might seem too specialized to be taken so early, but is placed here so later courses can take advantage of parallel and distributed algorithms. Both are becoming more and more important as multi-core processors and networking become ever more pervasive in systems.

Course [22] would include some of the theory covered in intro and mid level database classes.

Course [31] will not be the student's first exposure to graphs and trees, but will be a chance to go deeper than most undergraduate programs go in these topics.

It's a shame that freshman level courses like [32] seem to exist nowhere but MIT.

Course [40] will delve deep into searching and sorting, perhaps using Knuth vol III as a textbook.

Course [51] would include some of the more fundamental algorithms from traditional robotics and AI courses.

I'm not sure if courses like [52] exist anywhere. Even though Z is not commonly used, I think it would be great if a CS degree meant you could write 100% provably correct code, given enough time, if need be.

If someone would feel ill prepared for the job marketplace without being Java experts, they could do something Java related for all 5 of their projects (they could research garbage collection and just-in-time compilation for their research projects, and write Java applications for their 3 programming projects)

Substitute Universities for Those Displaced by Hurricane

2005-09-04T11:31:00.000+10:00

Suresh passes on word that university students displaced by the Hurricane may be offerred temporary places at universities around the country. Stanford is not on the list, which is unfortunate because most departments start classes on September 26, much later than most other schools. However, Stanford has a short message about possible admission for a small number of law students, and indicate that they are assessing the situation for other types of students.
Update 05 Sep 2005: The message has been updated: "Stanford will be admitting academically qualified students from these universities as non-matriculated students for the fall quarter, which starts on September 26 and ends on December 16. [...] Preference will be given to students from the San Francisco Bay Area. [...] Stanford will provide housing on campus for students who are accepted."
End Update

Although it doesn't really have a place here, it's difficult to not mention the shameful and tardy response by the US federal government in helping flood victims. It's not a big surprise in the light that emergency efforts were led by a man who's previous job was attorney for the International Arabian Horse Association, which he was essentially fired from in 2001.

Promoting intelligent design and ignoring warnings about looming natural threats are both endemic of anti-science thinking. Don't believe the line that no one expected this.

Update 06 Sep 2005: More commie liberal fear-mongering from several years ago here and here.

Evolution and Quantum Computing

2005-08-30T18:42:00.000+10:00

This editorial by Lee Spector in the Boston Globe talks about using genetic algorithms to evolve quantum circuits, and its consequences to understanding Darwinism.

If it takes a computer program to convince someone evolution is real, then either their educators have failed them miserably, or they have been severely misled by radical (but increasingly mainstream) institutions. But it's still good to see Lee Spector speaking up, since many scientists probably feel its pointless to get into the whole debate, since it essentially pits reason against fairy tales. But the more quiet the rational side is, the more it will seem that evolution is controversial, since the wing nuts now have a voice through all levels of politics, business, and the media in the United States. After two years in Australia I don't think the situation is much different here, except the Aussies are a lot more laid back about the whole thing.

Maintenance

2005-08-07T13:06:00.000+10:00

For those not using an RSS feed reader, the site should look a bit better now (thanks to Altman). I've let the qualgorithm.com domain expire, and moved the few non-blog resources (Peter Shor interview, Best of QC) to quantum.atticrose.com. The decidedly non-quantum Attic Rose is a side-venture which happens to have a lot of disk space and excess capacity. Right now it only has a small gallery with paintings of roses and bugs, but maybe I can convince the artist to paint something a little more quantum-ey.

blogger weirdness

2005-06-25T09:48:00.000+10:00

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.

D-Wave Systems

2005-06-21T22:22:00.000+10:00

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.

New Paper With Huge Claims (Debunked?)

2005-06-21T16:14:00.000+10:00

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.

Qudit Naming

2005-06-19T00:23:00.000+10:00

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.

42 Quantum Questions

2005-06-15T21:20:00.000+10:00

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)

Will QCs ever exist, and if so, how common will they become?
Where does the QC hype end, and reality begin?
Will writing QC software be fundamentally different to classical programming? What classical knowledge will carry over?
Will future programmers need to become well versed in quantum mechanics to understand and program QC's?
Will "Quantum Processors", if they come to exist, always be secondary to classical CPU's?
How many physical and logical qubits will be needed for "useful" quantum computation?
What is "useful" quantum computation?
How easy/hard is it to understand useful quantum algorithms, and the workings of QC hardware?
Are quantum computing pessimists on to something, or are they short-sighted? Or confused?
What computational problems are QC's poised to handle well?
What computational problems will QC's never be able to handle?
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?
Can quantum computers get us closer to proving P != NP?
How does one go about proving lower/upper bounds of QC algorithms? What implications does this have for classical algorithms?
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?
How are the various QC architectures advancing? What is the frontrunner?
When a clear favorite jumps ahead, will the other architecture programs disappear?
What is the trajectory of experimental quantum computing (i.e. how many qubits by 2010, 2015)? Is it too early to say?
What is the quantum analog to Moore'e Law?
Will quantum error correction work as advertised?
How important/useful are Grover's/Shor's algorithms really?
Were Grover's/Shor's algorithms low-hanging fruit, or the product of extreme insight and imagination?
Are there any recent advances on par with Grover's/Shor's algorithms?
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?
Is designing quantum algorithms difficult simply because it requires deep knowledge of several disciplines? Or is there something more to it?
What quantum physics experiments, specifically, could be simulated on a QC?
What will QC's mean for AI? Specifically: neural nets? Genetic algorithms? Something entirely different?
Will quantum computing have any impact on: Operating systems? Databases? The Internet? Games?
What classical models are most similar to quantum computer programming? i.e. parallel programming? Randomized algorithms? Nothing?
If a quantum algorithm produces only a sub-exponential speed gain over its classical counterpart, is it of any value?
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?
What can the idea of a quantum computer tell us about the universe?
What can quantum computing teach us about quantum mechanics (does it shed any light on entanglement? The measurement paradox? Teleportation?)?
What can quantum computing teach us about classical computing?
What can quantum computing teach us about the brain?
Is the universe a big quantum computer, and if so, how do we tap into its vast processing power?
Are there abstractions that will make programming QC's intuitive? Or is that fundamentally equivalent to making quantum mechanics intuitive, and therefore impossible?
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?
Is understanding continuous quantum mechanics necessary for fully understanding quantum computing?
Is it possible to follow all the important quantum computing developments if one does not have access to all the notable expensive academic journals?
Quantum information theory placeholder (lots more questions here, but I've probably already gone overboard).
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.

Weakest Link in First Generation Quantum Cryptographic Systems

2005-06-10T17:16:00.000+10:00

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.

Parallel Programming with Matrix Distributed Processing

2005-05-12T21:53:00.000+10:00

This paper describing a C++ parallel matrix library has some very impressive programs as examples, like a complete parallel version of the Game of Life, written in 39 lines of C++. I'm sure there are many other parallel matrix libraries out there, but this one seems worthy of consideration especially for anyone designing a parallel quantum computer simulator.

For those who think of parallel computers as being massively large and expensive machines in the basements of research labs, or world-wide Internet-based parallel programs like SETI@home, that image is going to be changing drastically over the next 5-10 years. Single core processors are getting too hot at high clock frequencies, so chip makers are currently moving to dual core designs. The forthcoming XBox 2 is apparently going to feature a triple-core CPU. If adding cores is the only way to maintain Moore's law for the near future, then it's pretty obvious what's going to happen, and in 10 years, 30-40 cores per desktop computer or video game console could be commonplace. This will have a huge impact on CPU-bound programs. In other words, most programmers will need to become very good at some form of parallel programming.

Although classical parallel programming is extremely different from quantum computer programming, maybe the paradigm shift will spur interest in what else is coming down the road, i.e. quantum computer programming. I hope the classical theoretical community is ready for the forthcoming upsurge of interest in parallel algorithms. They're going to need a model better than the PRAM.

(P.S. I forgot to keep track of the blog which linked to the aforementioned paper. My apologies)

Eugene Wigner

2005-03-08T09:40:00.000+10:00

When I was a kid, my uncle told me a great story from his freshman year at Princeton about a brilliant physicist who gave a guest lecture on diffraction. I couldn't remember who it was or what the details of the story were, so I asked him to email me the story:

The person who gave the lecture was Eugene Wigner, who a few months earlier, in 1963, had received the Nobel Prize. We knew that Wigner was going to give the lecture and we were anticipating it. When we entered the big old lecture hall, there was a pleasant looking, older gentlemen holding the door open for us. It didn't hit us at first who that man was, but that was the way that he wanted to introduce himself to us. Damned, pure genius looked like a guy that you would expect to see sipping coffee in a Viennese cafe. Pleasant as can be, unassuming, smiling pleasantly to each person as we passed by.

There were two large blackboard spaces that had two blackboards in each space, one forward and one behind. A lecturer could write on a blackboard and then save the writing by pushing that board up and hauling the other one down to continue the writing. Wigner had a hard time handing this set up. "Where did I write that?" "How does this work?" Which one should I write on first?" Practical problems like that. There was also a string that hung down in the middle of this confusing apparatus, that could be used to manually lower the projector screen. This last complication and visual interference was particularly troublesome and a source of continual irritation as equation were developed on either side of the string, sometimes causing the equation to be divided, not at the equal sign, but at an inconvenient place in the expression.

However, Wigner was still able to focus sufficiently to do things that I have never seen before or since. We knew that Wigner had developed the math Fermi needed to develop the first nuclear reactor (the "Pile" of carbon neutron moderator, boron neutron absorber, and uranium neutron producer and gama ray - energy- generator, that would be critical, but not supercritical, which is an exponential power spike that potentially could have quickly changed the configuration and location of that nice pile that was under the sports stands at the University of Chicago)

Wigner said that he had accepted this teaching challenge though he had no recollection of exactly what the phenomenon was when light when through space occupied with matter. Never the less, he accepted the assignment. He brought a dictionary which he used to look up "Diffraction", though, as I recall, he had as much trouble coming up with the correct spelling as I just had. He read the definitions, though he had to think for a while about which definition he should us--that had the promise to lead to clarifying the phenomanon, not confuse us, and no doubt him, further. "Ah hah", in that good-humored German accent, "this is the von to use". We were all thinking OK, if you say so.

Wigner started to crank out the equations, everything with triple integrals and more Greek letters than frat row, all written in a hand that made all of them look kind of similar, all like a variation of "Q". As he approached the end of his allowable space on the fourth black board he began to slow down and a scowl crossed his face. In mid equation he stood back and said "This cannot be right. Something is wrong." His hand passed over the equations, starting back from his last equation. He went back a few equations, then he slowly stood back from the board, pointing, and said, "That's it. That is the mistake." He erased the now obvious (to him) error, changed the appropriate place in the subsequent equations, and finished the last equation. He turned to us in the audience, a slow grin broke out on his face, and he said in a quiet manner, "That makes sense."

No one said anything. We were all trying to appreciate the moment and to store it in our long-term memory. We broke out in a respectful applause, not too much so we wouldn't embarass this sensitive man. We were a classroom of freshmen engineers, so an appreciation or understanding of the material presented to us was not possible for any of us. But we could appreciate seeing how a mind in tune with nature translates observation and logic into a mathematical model

Wigner flushed a little, bowed slightly, went to the door and held it open for us as we filed out, a little dazed, heading for our next class which had no hope of holding us enthralled as Mr.Wigner had.

Blog Market

2005-02-15T22:55:00.000+10:00

My collection of links on the right isn't very complete, but I had no idea how much was riding on it until I discovered Blog Shares, a stock market for blogs. Someone named Javier López actually owns 75% of the shares of this very blog, although I'm sure he'll eventually regret the purchase if he doesn't already. David Bacon own 20% of his own Quantum Pontiff blog, which is about to experience a modest increase in (virtual) valuation, thanks to the extremely overdue link I finally added. I wonder if blogshare money will ever have real world value. (If it sounds implausible, see EverQuest).

Some quantum or CS type blogs, and their valuations [Updated Feb-16, thanks Suresh]:
Computational Complexity Web Log: $12,029.76
Michael Nielson: $5,845.59
The Quantum Pontiff: $3,849.21
Quantum Algorithms: $3,816.68
Illuminating Science: $3,313.81
Quantum Bits: $2,709.12
Quantized Espresso: $1,664.65

Eye Opening Quote

2005-01-21T22:31:00.000+10:00

Chakra Yadavalli dug up a very interesting quote. Check out the original post, but I'm going to steal it because it's too good not to, and also so I can make a cheap point:

Question by Dr. Manickam, Pune University: There is an effort in Europe for secure Networking based on Quantum Computing. Why not such projects be initiated in India?

Answer By [Name Withheld (For Now)]: A Quantum computer is a device that harnesses physical phenomenon unique to quantum mechanics (especially quantum interference) to realize a fundamentally new mode of information processing. Encryption, however, is only one application of a quantum computer. In addition, a researcher has put together a toolbox of mathematical operations that can only be performed on a quantum computer, many of which he used in his factorization algorithm. Currently the power and capability of a quantum computer is primarily theoretical speculation; the advent of the first fully functional quantum computer will undoubtedly bring many new and exciting applications. Quantum computing is one of the areas, where India can contribute substantially. We are now working on a nano-technology mission which can make realizable quantum computers. The Conference can debate and make suggestions on how we can bring in synergy in this crucial area.

So guess who said this: Is it the head of a physics department at a top university in India? Maybe a government minister of science and technology?

How about: Abdul Kalam, the President of India.

As Chakra Yadavallia alluded to, imagine your favorite North American (or Australian) leader answering the same question, and think about how they'd respond.

Paltry competition aside, Kalam deserves recognition in his own right for being inquisitive enough to know this much. After looking at his background, his quote is not surprising at all...Kalam was a highly successful aerospace engineer before getting mixed up in politics. According to Wikipedia, the Presidency of India is a largely symbolic role, and the Prime Minister is the true seat of power. But no matter, with such a good scientist in a prominent role, it's no wonder India is ascending as a science and technology powerhouse.

As a nation that places such a high value on democracy, education, intellectuals, and fluency in English, India deserves all the white collar outsourcing they can get. This also solidifies my thinking that Americans have no right to complain about losing high tech jobs until they (well, okay, I admit: we) can elect a leader who understands technology. I'm not talking about enacting protectionism, but I mean investing in science and technology to secure a role in the future. Shrinking science budgets won't get the job done.

Waking Up QubitNews

2005-01-09T10:55:00.000+10:00

QubitNews is a pretty good way to keep up with newly available positions and the occasional conference in quantum computing. What would be even better is if it became the Slashdot of quantum computing...but that can only happen if people want to contribute. There are a couple of new discussion-friendly topics, here and here.

(Ideally, my blog will become completely redundant, replaced by a user supported community which contains all the same content with the added benefit of commentary and discussion by many experts active in the field)

October Wrap Up

2005-01-08T20:29:00.000+10:00

-Detecting a single spin
-Quantum Register Experiment with Neutral Atoms (more here)
-Device for splitting a stream of quantum objects

September Wrap Up

2005-01-08T19:54:00.000+10:00

Still in catch-up mode...
-Physicists Create Artificial Molecule On A Chip (more here)
-Researchers violate Bell’s inequality with an atom and a photon
-Encryption and the P=NP question
-Single photon source using polymers
-Data archiving network secured using quantum cryptography debuts (more here)

Proofs Over the Edge

2005-01-08T17:18:00.000+10:00

The Edge espouses the thesis that providing a forum for smart people discussing profound ideas is far more important than having a decently designed web site. Its latest contribution to mankind is very long, thought provoking, (mostly) accessible and unlike much of the stuff on the Internet, worthy of careful attention: They asked 120 notable thinkers the question, "What do you believe is true even though you cannot prove it?" A sampling of quotes can't really do it justice, but here's an attempt anyway.

Anton Zeilinger:

What I believe but cannot prove is that quantum physics teaches us to abandon the distinction between information and reality.

Lee Smolin:

I am convinced that quantum mechanics is not a final theory. I believe this because I have never encountered an interpretation of the present formulation of quantum mechanics that makes sense to me...I believe that the hidden variables represent relationships between the particles we do see, which are hidden because they are non-local and connect widely separated particles.

Leonard Susskind:

If I were to flip a coin a million times I'd be damn sure I wasn't going to get all heads. I'm not a betting man but I'd be so sure that I'd bet my life or my soul. I'd even go the whole way and bet a year's salary. I'm absolutely certain the laws of large numbers—probability theory—will work and protect me. All of science is based on it. But, I can't prove it and I don't really know why it works. That may be the reason why Einstein said, "God doesn't play dice." It probably is.

Freeman Dyson:

Since I am a mathematician, I give a precise answer to this question. Thanks to Kurt Gödel, we know that there are true mathematical statements that cannot be proved. But I want a little more than this. I want a statement that is true, unprovable, and simple enough to be understood by people who are not mathematicians. Here it is. [...] [I]t never happens that the reverse of a power of two is a power of five [...]

(I thought Goldbach's Conjecture met this criteria as well, but Dyson also provides a simple method for generating easy to grasp, non-provable probable mathematical truths)

Haim Harari:

The Atom, the nucleus and the proton, each in its own time, were considered elementary and indivisible, only to be replaced later by smaller objects as the fundamental building blocks. How can we be so arrogant as to exclude the possibility that this will happen again?

Asher Peres 1934-2005

2005-01-05T20:55:00.000+10:00

Asher Peres, recognized as one of the fathers of quantum teleportation, is remembered in the academic blogging community:
Computational Complexity, Michael Nielsen, David Bacon, QubitNews

Limits on Efficient Computation in the Physical World

2005-01-05T20:41:00.000+10:00

So you've completely mastered Nielsen and Chuang, where do you go next on the road to understanding quantum computing? I'll admit there's a lot more I could learn from the basic texts before entirely turning my attention to other things, and in the vast ocean of arxiv.org, it's hard to know where to go next.

But one wothwhile stop is here: The dissertation of Scott Aaronson: Limits on Efficient Computation in the Physical World (phD
candidate, UC Berkeley). It's a pretty interesting read that seems to cover a lot of central points in the computer science side of QC. Along with presenting some new results, it ties together many of Aaronson's (and others') previously published papers, giving a lot more context and motivation then what appears in the raw papers themselves.

From Chapter 1:

"For me, quantum computing matters because it combines two of the great mysteries bequeathed to us by the twentieth century: the nature of quantum mechanics, and the ultimate limits of computation. It would be astonishing if such an elemental connection between these mysteries shed no new light on either of them. And indeed, there is already a growing list of examples-we will see several of them in this thesis-in which ideas from quantum computing have led to new results about classical computation.
...
"[I]n this thesis I will show how adopting a computer science perspective can lead us to ask better questions-nontrivial but answerable questions, which put old mysteries in a new light even when they fall short of solving them."

What the Bleep?

2004-12-26T15:47:00.000+10:00

I haven't seen it yet, but there is an interesting and strange sounding semi-documentary movie "What the Bleep Do We Know", now available on DVD. At first I thought it would be up the same alley as Brian Greene's Elegant Universe PBS show, but hopefully not as mind-numbingly repetitive and slow. Instead, it seems to mix science with suspicious sounding mystical stuff in order to answer big questions like "why are we here?". If you have seen "What the Bleep Do We Know", please leave a comment with your opinion of the movie.

Quantum chip circuitry demonstrated

2004-11-24T21:32:00.000+10:00

EE Times - Quantum chip circuitry demonstrated: "Yale University researchers have demonstrated how to build a quantum computer operating on quantum bits, or qubits, which hold a superposition of quantum states. [...] The advantages of Yale's method include the relatively small size of its qubit repositories - about a square micron - and the ability to read a qubit's state without disturbing it - the bane of quantum computers to date. [...] The Yale approach stored qubits in a Cooper-box with over 1 billion superconducting aluminum atoms acting together, thereby providing a kind of quantum momentum that allowed a 'probing' photon to read out a qubit's state from the Cooper-box without changing its state."

Updates: I found this pdf to be a pretty good lightly-technical explanation of the experiment. Also, here [zhurnal.net] and here [www.lkb.ens.fr] are some interesting explanations of Quantum Non-Demolition.

The NSA Wants Your Quantum Algorithms

2004-11-24T21:04:00.000+10:00

NSA Funding Opportunity in Quantum Computing Algorithms: "The National Security Agency solicits proposals for one-year research grants in the area of Quantum Computing Algorithms. [...] We are not interested in funding work such as quantum error correction, which supports the 'infrastructure' of quantum computation but is not a quantum algorithm in our sense. We are more interested in algorithms related to number theory, algebra, and combinatorics than in topics such as physical modeling and database analysis."

Single Field Qubit Control

2004-11-14T01:17:00.000+10:00

Single field shapes quantum bits TRN 110304: "Researchers have recently realized that it may be possible to control the electrons in a quantum computer using a single magnetic field rather than having to produce extremely small, precisely focused magnetic fields for each electron"

Grover's Sampling Algorithm

2004-11-14T01:15:00.000+10:00

Quantum Sampling Algorithm TRN 062800: "The sampling algorithm, written by Bell Labs' researcher Lov K. Grover, enables three types of applications for quantum computing: statistical sampling, searching with sketchy information and Monte Carlo integration [...] Although the sampling algorithm is probably not as 'novel and exciting' as Grover's original search algorithm, no one doubts the importance of sampling on quantum computers"

Update: Sorry for not noticing sooner, but this story is fairly old (July 2000) which I should have at least mentioned.

Particle Physics for the Rest of Us

2004-11-06T16:28:00.000+10:00

Symmetry Magazine has recently debuted, which is a joint venture of SLAC and Fermi Lab. The editor, David Harris, also has a blog.

August Wrap Up

2004-11-02T22:06:00.000+10:00

-2 million correlated entangled photon pairs produced per second
-Entangled quantum dots
-New way to synthesize quantum dots (and more here)
-Photon teleportation over 600m
-Controlled emission rates of quantum dots
-Five photons entangled
-Open destination quantum teleportation

July Wrap Up

2004-10-21T22:46:00.000+10:00

-Particle Chains Quantum Register
-Quantum Computing Using Traditional Transistors
-Qubits in Carbon Nanotubes
-Single Atom Trapped in Microchip at Room Temperature

June wrap up

2004-10-21T21:49:00.000+10:00

-Entangled atomic clocks
-First quantum network
-Teleportation of photons
-Teleportation of atomic states

Return to Blogging

2004-10-21T21:11:00.000+10:00

I'd like to apologize for not updating the blog for so long...my laptop fried itself six months ago, and blogging from work is a bad habit, so I haven't been able to post. Everything's operational now, so I'll be posting semi-regularly again.

Entanglement beats the diffraction limit

2004-05-13T21:43:00.000+10:00

PhysicsWeb - Entanglement beats the diffraction limit: "Physicists have succeeded in 'entangling' more than two photons for the first time. A Canadian team has entangled three photons while an Austrian team have created a four-photon entangled state. The wavelengths of the entangled states are three and four times shorter than the original wavelengths of the photons. By overcoming the so-called diffraction limit, entangled photons could prove useful in a range of applications ranging from lithography to microscopy."

Comments Enabled

2004-05-11T13:03:00.000+10:00

Thanks to a new version of Blogger, user comments are now enabled. Feel free to add your own opinions, insights, and questions.

Quantum Pontiff: Thumbs up for Ion Trap QC's

2004-05-11T11:33:00.000+10:00

In The Quantum Pontiff: Focus, People! Dave Bacon has some observations from a QC workshop he attended, and he thinks Ion Traps are way ahead of any other implementation: "Ion traps rock. If [I] were a starting graduate student who wanted to do quantum computing and do some really rocking quantum computing experiments during my graduate career I would make a dash straight towards an ion trap quantum computing group. The era of NMR is over and a new era of Ion trap quantum computing has begun! "

Physics Researchers Find Striking Quantum Spin Behavior

2004-05-06T22:40:00.000+10:00

Physics Researchers Find Striking Quantum Spin Behavior: "Describing spinning bosons [...] requires a tensor polarization which has one more dimension than a vector polarization [...]. A speculative, but perhaps possible, application of this research comes from the spinning bosons’ extra dimension. This might make the still-speculative but promising quantum computers more effective, because much more information could be stored in the extra dimension"

QCs in Japan

2004-05-06T21:02:00.000+10:00

The Japan Times Online, Japan leading quest for first quantum computer: "NTT Basic Research Laboratories in Atsugi, Kanagawa Prefecture, whose quantum computer research is considered the most advanced in the world, has confirmed the superposition of quantum states -- the coexistence of 0s and 1s in a single quantum bit." The article mentions that the Japanese government does not have enough money to fund quantum computer research, so it will have to be led by corporations, in Japan at least.

Advance in Quantum Electronics

2004-05-01T18:08:00.000+10:00

From ABC Australia, News in Science - Faster electronics ahead, says new theory: "A new theory on how electrons behave in ultra small devices threatens to overturn one of the tenets of quantum electronics."

Optical Quantum Memory Designed

2004-05-01T17:31:00.000+10:00

From Technology Review, Optical Quantum Memory Designed: "The researchers' quantum transponder design calls for encoding pairs of quantum bits in sets of four photons in such a way that the two qubits can be read even if one of the four photons is lost. Qubits would be sent into a fiber loop and a simple quantum computer would correct for errors caused by photons being absorbed by the fiber. The design includes a device to generate single photons to replace lost photons."

Entangled Quantum Dots

2004-05-01T15:05:00.000+10:00

From AScribe.org, Quantum Computers Are a Quantum Leap Closer: "The team used eight tiny converging wires, or 'gates,' to deposit the electrons in the dots one by one and then electronically fine-tune the dots' properties so they would become entangled. With these gates, the team was able to slowly tune the interacting dots so they are able to exist in a mixed, down-up and up-down configuration simultaneously."

Quantum Money Transaction

2004-05-01T14:54:00.000+10:00

From the free section of Nature: Business goes quantum: Money changes hands in key bank transaction: "One of the most secure methods of quantum cryptography has been used commercially - for a single transaction, at least. On 21 April, Austrian scientists used the technique to transfer a 3,000 (US$3,500) donation to their lab."

Programming Matter - Quantum Dots

2004-04-27T22:41:00.000+10:00

Quantum Dots, from Computerworld: Programming Matter: "With programmable quantum dots, McCarthy says, you can create metal traces inside a solid object, create an electric circuit to perform a particular task and then erase it once it's complete."

IBM, Stanford Spintronics Partnership

2004-04-27T22:31:00.000+10:00

From Newsfactor: IBM, Stanford Turn to Spintronics: "IBM and Stanford University are putting their heads together on a new microelectronics technology dubbed "spintronics" [...] Magnetic RAM (MRAM) is the next spintronic device in the works. It has the potential to be a non-volatile memory that runs circles around non-volatile Flash memory"

Virtual Journal of Quantum Information--April 2004

2004-04-17T11:47:00.000+10:00

Found here: Virtual Journal of Quantum Information--April 2004. The one and only algorithm article from this issue can also be found here: Quantum algorithms for phase space tomography [arxiv.org]

Perimeter Institute

2004-04-11T19:00:00.000+10:00

From The Globe and Mail, a story about the Perimeter Institute in Waterloo, Ontario: "At present, the world's record is a device [...] that can generate seven qubits. This year, Dr. [Raymond] Laflamme [of the Perimeter Institute] is attempting to increase that to 10 [...]"

4 Qubit Search Implementation

2004-04-09T07:45:00.000+10:00

Technology Review: Sturdy Quantum Computing Demoed: "Researchers at the University of Toronto have built a prototype quantum computer that can execute a quantum search algorithm despite environmental noise. The computer uses protected logical qubits that are made from multiple physical qubits. The prototype has just four qubits, but the method has the potential to someday be used in practical quantum computers, which require thousands or millions of qubits. [...] The work appeared in the November 21, 2003 issue of Physical Review Letters."

Exploring the Classical/Quantum Boundary

2004-04-03T08:22:00.000+10:00

In PhysicsWeb - Physicists move closer to the quantum limit: "To find out whether or not the uncertainty principle extends up to the macroscopic world, Schwab and colleagues studied the motion of a vibrating mechanical arm made from silicon nitride."

Combatting Decoherence, Plus Low Overhead Error Correction

2004-04-02T23:37:00.000+10:00

The Economist.com has a story on Quantum computing. The first half is the standard intro, but some interesting new results are mentioned in the second half of the story:

"Chikako Uchiyama of Yamanashi University, in Japan, discussed how, in the general case, the application of very short pulses, poetically known as bang-bang pulses, at regular intervals can serve not only to suppress decoherence, but also to maintain entanglement—the quantum coupling between several qubits which allows computations to get done."

Also: "Kaveh Khodjasteh of the University of Toronto looked at a related question, focusing on decoherence rather than disentanglement. He showed how a quantum error-correcting code which introduced only one extra qubit for error correction would create a robust system for quantum computation which had tolerance for faults caused by spontaneous emission, another bizarre quantum effect."

Qudit Simulator...in Visual Basic

2004-03-31T23:03:00.000+10:00

It's not the coding envirionment I would personally choose for this, but no matter, someone has written a Qudit simulator in Visual Basic. (A qudit is a 'D' dimensional quantum unit, i.e. a qubit is 2-dimentional, qutrit 3-dimentional.)

Single Molecule Logic Gates

2004-03-30T21:25:00.000+10:00

In Molecular logic proposed, researchers explore single molecule logic gates. They don't seem to take advantage of entanglement, so it's a nanocomputer idea, not a quantum computer in the usual sense. "Practical applications for molecular electronics are more than a decade away."

Bennett and Shor on Quantum Channel Capacities

2004-03-30T20:46:00.000+10:00

Two big names together in one paper: Quantum Channel Capacities, Bennett CH, Shor PW. It appears in Science, but unfortunately seems to be one of the few quantum papers to not be found at arxiv.org.

Easy Quantum Circuit Drawing

2004-03-24T18:32:00.000+10:00

Michael Nielsen posts: "Ike Chuang has just released a package enabling quantum circuits for quantum computers to be drawn easily (link.)"

Bjarne Stroustrup on AT&T/Bell Labs

2004-03-22T16:50:00.000+10:00

I asked Dr. Stroustrup to elaborate on what he said in this article (see previous post) about some advantages AT&T Bell Labs had over universities, and he replied:

"I don't really want to be dragged into a debate, but think of this: AT&T Bell labs had 1,000 hand-picked PhDs concentrated in a few interrelated areas supported by development organizations consisting of many thousand good engineers (all with masters degrees). A good university department has maybe 30 to 60 PhDs, many closely focussed on getting tenure. It's a world of difference, except that the AT&T Bell Labs I describe no longer exists."

I also asked what specific reward mechanisms AT&T Bell Labs had that universities don't, and he replied:

"The reward mechanisms were just one thing, but compared to universities, there were a significantly higher emphasis (read money, status, job security) on doing something radically different, clean, but practical. The chance to see your work on a world scale was a huge motivator. The absence of "publish or perish" was a huge factor in being able to keep your eyes on the ball for years, rather than having to follow the raise and fall of fads and fashions. A very open community where you could always find someone really smart and experienced to discuss new ideas with was in itself a reward and a motivator. There's simply nothing like it. if you haven't seen it, you probably wont understand or believe it. And then you didn't have to struggle for promotion: staying technical was a real option.

I use the past tense thinking about AT&T Bell labs (and before that Bell telephone Labs, Inc.) at one of its heights - trying to stay out of the debates about the present at AT&T Labs and Lucent bell Labs."

(Thanks to Dr. Stroustrup for the prompt and thorough reply)

AT&T Labs Brain Drain

2004-03-22T10:25:00.000+10:00

Slashdot links to: Talent leak drains AT&T think tank. The article gives a sense that the whole (AT&T Labs) was greater than the sum of the parts (former AT&T researchers dispersed among academia posts). This will only be proven false if academic institutions can begin to make AT&T/Bell Lab size impacts on the world, i.e. coming up with the "next" Unix/C/C++, Shor's algorithm, Grover's algorithm, transistor.

I would like to know more about the management and reward mechanisms employed at AT&T/Bell Labs in their heyday (alluded to by Dr. Stroustrup in the article) and see how they contrast with the modern research university.

HAIT Journal of Science and Engineering

2004-03-19T10:35:00.000+10:00

New Journal: HAIT Journal of Science and Engineering. According to Open Access News, this new journal's "first issue features extensive papers on nanophysics and quantum information."

True Random Number Sequences Online

2004-03-19T08:59:00.000+10:00

This Press Release states: "The University of Geneva and the company id Quantique team to launch the first web site offering the possibility to download random numbers from quantum origin." The actual generator interface is here.

Virtual Journal of Quantum Information--March 2004

2004-03-17T09:03:00.000+10:00

Available now.

World Wide Telescope

2004-03-15T23:21:00.000+10:00

In [cs/0403018] The World Wide Telescope: An Archetype for Online Science, researchers Jim Gray and Alexander Szalay predict: "The World-Wide Telescope (WWT) will emerge from the world’s online astronomy data. It will have observations in all the observed spectral bands, from the best instruments back to the beginning of history...Today, you can find and study all the astronomy literature online with Google™ and AstroPh. In the future you should be able to find and analyze the underlying observational data just as easily."

BBC Audio Interviews

2004-03-14T08:47:00.000+10:00

The BBC has created a site with many short audio interviews, including a two minute clip with Werner Heisenberg. Let's hope they put more of the interview online eventually, and add many more like it (link via Neat New Stuff).

Quantum Crypto Reaches 150 km

2004-03-13T09:30:00.000+10:00

optics.org, News: "NEC’s record-breaking system relies on planar lightwave circuit (PLC) technology and a low-noise photon receiver....The system’s second plus-point is an alleged ten-fold increase in signal-to-noise ratio compared with current systems. This is largely thanks to the receiver’s increased sensitivity to photons that have been broadened by dispersion in the long fiber-optic link."

Single Atom Entangled With a Single Photon

2004-03-11T08:43:00.000+10:00

In Nature's free section (reg required), Quantum computing gets a step closer: Researchers have created the flying qubit: "Chris Monroe and colleagues from the University of Michigan used a cadmium atom trapped in an electric field to ‘store’ information about the atom's magnetic state. By pumping energy into the atom with a laser, they forced it to spit out a packet of light. That photon carried an imprint of the atom's information with it, which could be read by a detector."

Another MagiQ Story

2004-03-10T09:41:00.000+10:00

In BBC NEWS: Quantum codes debut in real world, MagicQ's CEO Bob Gelfond said "his company was working on quantum memory chips, single photon sources and quantum repeaters to help with its long-term goal of creating a commercial quantum computer."

Business Week on QC

2004-03-09T12:08:00.000+10:00

In Putting The Weirdness To Work, Business Week has their run-of-the-mill quantum computing overview article. Nothing new here, except one interesting tidbit: "The Pentagon's Defense Advanced Research Projects Agency is now beginning a major effort to construct a working quantum information processor." That's interesting, because DARPA's Deputy Director, Robert Leheny, was very pessimistic about Quantum Computing in this interview. (See Peter Shor's response to his doubts here.) Either Leheny's changed his tune, or maybe he'll play the pointy-haired-boss role to scientists involved in the project. But another implication is, the George Bush budget proposal only had about $16 million earmarked for Quantum Computing, but now that DARPA's on board with their project, does that mean that they'll end up with most or all of this money, as opposed to universities who have been working on this stuff for years?

Berkeley Groks

2004-03-08T10:26:00.000+10:00

"Berkeley Groks is a weekly radio science program broadcasting on KALX 90.7 FM in Berkeley, CA." Very college-radio-ish (because it is), but they interview Nobel Laureates, other eminent scientists, plus people like Stephen Wolfram. They don't have enough hard drive space for a complete mp3 archive of their shows, but an interesting selection is available here.

David Deutsch's Lectures on Quantum Mechanics

2004-03-05T22:01:00.000+10:00

Check out David Deutsch's Video Lectures on Quantum Mechanics. Only lecture 1 is there now (Quantum Computation)...hard to tell if this is a series in the making or if it's the scraps of an abandoned project.

New Laser Cooling Technique

2004-03-04T21:45:00.000+10:00

PhysicsWeb - Making atoms cooler: This technique is notable because apparently "it preserves the quantum state of the atoms."
Update [5-Mar]: Here's the actual paper.

UK Gov Backs Quantum Key Exchange

2004-03-02T12:17:00.000+10:00

Government backs quantum cryptography: "The [UK] government is putting its weight behind quantum cryptography as a key way of making communications hack-proof...It's not going to replace Secure Sockets Layer in a hurry; it's still a long way away before it becomes practical"

Black Holes May Preserve Information After All

2004-03-02T12:09:00.000+10:00

With help from string theory, (Newswise:) Study May Solve One of Great Mysteries of Black Holes: "Since Mathur’s conjecture suggests that strings continue to exist inside the black hole, and the nature of the strings depends on the particles that made up the original source material, then each black hole is as unique as are the stars, planets, or galaxy that formed it. The strings from any subsequent material that enters the black hole would remain traceable as well."

Bill Gates on QC

2004-03-01T21:42:00.000+10:00

From MIT Technology Review, The Ultimate Change Agent, Bill Gates mentions in a speech: "[Microsoft's quantum computing group's work most likely] won’t result in anything in the next decade--and there’s a reasonable chance that it won’t result in anything at all. Now if it does result in something, it’s mind-blowing, because it’s just a different paradigm for computing."

"Intellectual" Conservative on Quantum Theory

2004-02-27T19:56:00.000+10:00

From The Intellectual Conservative. The Divinity Case: Imposing Secular Dogmatism: "Today much of what we call 'science' is simply theory. Quantum mechanics, for example, has several different explanations for reality at the subatomic level. Mathematical models are useful, but imperfect, predictors of reality at that level. Quantum mechanics actually 'works' only at the scale of our perceptions, the ordinary world which we observe."

There's a lot wrong with this paragraph, but the last sentence is the most glaring: quantum mechanics does not apply at the scale of our perceptions. As far as the second to last sentence goes: Some quantum level experiments have agreed with theory to some rediculous number of decimal places. The different explanations he refers to are part of philosohpy, not the core of quantum mechanics.

Quantum Relays Using Classical Parts

2004-02-27T12:26:00.000+10:00

From Technology Review, quantum repeaters will extend the range of quantum networks, Simple Optics Make Quantum Relay: "The challenge was finding a way to preserve entanglement, which links particle properties like polarization regardless of the distance between the particles....It will be 20 years before the method can be used practically, according to the researchers."

Note to Feed Aggregator Users

2004-02-26T09:08:00.000+10:00

I updated this blog's template to play better with newsfeed aggregation software, but I had to change recent posts individually too, so sorry for the duplicates. For those of you who don't use an RSS/atom aggregator, you should try one. Bloglines is good, with minor problems. NetNewsWire for Mac is supposed to be the best, although I've never tried it, because for some reason I don't use Macs anymore.
Update [26-Feb]: Here is an auto-generated list of feeds I'm subscribed to.

Spin Valve Created

2004-02-26T08:20:00.000+10:00

PhysicsWeb - Spintronics goes organic: "Jing Shi and colleagues at the University of Utah in the US have made the first organic 'spin valve' - a device that changes resistance depending on the applied magnetic field. Previous spin valves were made from metals or insulators "

Quantum Channel Capacity

2004-02-24T10:29:00.000+10:00

From New Journal of Physics: "Channel capacity describes the size of the nearly ideal channels, which can be obtained from many uses of a given channel, using an optimal error correcting code. In this paper we collect and compare minor and major variations in the mathematically precise statements of this idea which have been put forward in the literature."

Knuth's Vacation Photos

2004-02-23T17:47:00.000+10:00

Do you ever wonder what geniuses do on vacation? Well for Mr. and Mrs. Donald Knuth, the answer is: take pictures of every diamond shaped road sign you see. It's surprisingly interesting to look at. At least *I* think so.

Church-Turing Thesis vs Quantum Measurement

2004-02-23T10:21:00.000+10:00

In this paper, [quant-ph/0402128] Computable Functions, the Church-Turing Thesis and the Quantum Measurement Problem, the authors argue that quantum mechanics cannot break the "Turing barrier." If true, on the one hand, it would be bit disappointing that quantum computers will never do anything truly new (only faster, in some cases. It was already known that qubit-based quantum computers cannot break the "Turing barrier," but quantum mechanics was an open question). On the other hand, it is exciting that the Church-Turing thesis would seem to be not just a statement on the limits of classical computation, but also a limit of physical reality.

The Best Quantum Computing Resources

2004-02-22T12:18:00.000+10:00

I have created a meta-resource for quantum computing newbies. It basically lists some of the best sites/books relating to quantum computing, in my opinion. Instead of being exhaustive, it only lists high quality resources.

New Supernova Findings Bolster Dark Matter

2004-02-22T09:44:00.000+10:00

From NY Times, New Data on 2 Doomsday Ideas, Big Rip vs. Big Crunch: "Models which predict wild dark energy densities which change a lot with time don't look so good," Dr. Yun Wang, a cosmologist at the University of Oklahoma, said. "Everybody will go back to the drawing board." Sounds like there's still lots of work to do, but the score over the past few months is: Dark Energy 1, no-Dark Energy 1.

Commerical Quantum Crypto

2004-02-20T20:57:00.000+10:00

From SmallTimes, brief summary of recent commercial developments

Decoherence of Matter Waves by Thermal Emission of Radiation Experiment Agrees With Theory

2004-02-20T20:41:00.000+10:00

New in Nature (not the free section), Decoherence of matter waves by thermal emission of radiation. From the abstract: "We find good quantitative agreement between our experimental observations and microscopic decoherence theory. Decoherence by emission of thermal radiation is a general mechanism that should be relevant to all macroscopic bodies." A draft is available here.
Update [23-Feb]: Article about this research from SF Chronicle. One person quoted says this is Nobel Prize quality stuff.

Feb VJ of Quantum Information

2004-02-18T10:43:00.000+10:00

The Feb issue contains the algorithm/computation papers "Simulation of quantum random walks using the interference of a classical field" and "Perturbative formulation and nonadiabatic corrections in adiabatic quantum-computing schemes" along with many others in different subfields.

Google Weirdness

2004-02-16T10:17:00.000+10:00

If you search for "quantum algorithm" or "quantum algorithms" right now on google, this blog comes up on about the fifth page or so. The weird thing is, only a week ago, this blog was the #1 hit for both those searches...now it's around #50. Very bizarre that it would fall so far so quickly.
Update [17-Feb]: This website is now completely off google, as far as I can tell. I'm glad I don't make my living from website traffic which would make me dependent on the whims of the google searchbots.
Update [20-Feb]: Google's searchbots "heard" me, so this blog is back on page two at least. Here is a short article, Keeping an Eye on Google, from Technology Review.

Quantum Atomic Clocks

2004-02-15T10:55:00.000+10:00

Very high level overview from science.nasa.gov: Spooky Atomic Clocks

Another Suspect Press Release

2004-02-14T22:52:00.000+10:00

From PRNewswire, ATMOL Inc. to Introduce the Remarkable Breakthrough of Technical Analysis 'J- CHART' at Traders EXPO in New York. "...J-Chart is able to avoid Random-Walk's effects. Furthermore, J- Chart utilizes the Pair Production Phenomenon of Quantum Physics as backbone for its ability of price forecasting."

It's one thing to use computing buzzwords to promote a product, but throwing in quantum physics appears disingenuous in this example. Perhaps they are using some mathematical formalism that has some strong resemblance to pair production in quantum mechanical equations, but that does not justify the above quote. It would be like someone having F = m*a; in their source code and claiming they use the power of Newtonian Mechanics in their software. Meaningless at best, misleading at worst.

Faster Than Light Inter-Galactic Email

2004-02-14T19:06:00.000+10:00

From NewsFactor Network - Quantum ComSat May Send Mail Faster Than Light Speed: "The use of entangled photons for quantum cryptography was shown experimentally by different groups for long distances using optical fibers," University of Geneva physicist Ivan Marcikic told NewsFactor. "By using satellites, this distance becomes several orders of magnitude longer. It is thus a new approach to increase the distance between two entangled photons."

You also need a non-faster than light classical communication channel in order to correctly interpret the results of the measurements...but maybe I'm missing something. This looks like the relevant paper. There's nothing in there about faster than light infomation travel, although it does have an interesting discussion of transmitting entangled qubits via satellites. The overhyping/lack of understanding by newsfactor isn't doing anybody any good.

Electricity Teleportation

2004-02-10T15:15:00.000+10:00

From Technology Review: Electricity Teleportation Devised: "The method could eventually be used to instantly transport information between the quantum bits, or qubits, of a quantum computer if electrons could be transported over distances of around 100 microns."
Update [15-Feb]: Another article on the topic here, from Physical Review Focus.

Securing eVoting with Quantum Cryptography

2004-02-10T12:14:00.000+10:00

From this Newswire Canada press release, via Cryptonomicon.Net: Swiss companies will use "this technology [...] to reinforce the security of E-Voting applications through tamper and eavesdropping detection via a Quantum Channel connecting the central Government's servers with local county servers."

New Issue VJ of Quantum Information

2004-02-10T11:33:00.000+10:00

Better late than never, Virtual Journal of Quantum Information--January 2004 came out today. It features a paper entitled "Quantum information and relativity theory" along with 8 algorithm and computation articles, including "Universal quantum interfaces".

Stroustrup's Foundations class at Texas A&M

2004-02-09T19:26:00.000+10:00

I'm sure just about every physicist wishes they could go back in time and sit in on the famous Feynman lectures during the 60's. Well right now, a lucky group of beginning engineering students are learning basic computer science from Dr Bjarne Stroustrup. There probably won't be a book series in 40 years to commemorate these lectures, but you can see the course website here: ENGR 112 - Foundations of Engineering II (B)

A New Kind of Science Online

2004-02-07T17:57:00.000+10:00

David Appell of Quark Soup points out here, "Stephen Wolfram's much discussed book A New Kind of Science is now freely available online."
Update [24-Feb]: There is a good review of the book here by Scott Aaronson, which concentrates on computational complexity and quantum physics related aspects.

Quantum Weight Loss

2004-02-07T16:52:00.000+10:00

I often get disappointed at scientists in various disciplines for not being more vocal when their field gets trampled through the media and the public gets a serious dose of mis-information. Well guess what, according to FemOne, their new "Lean Choices(TM) Weight Loss System" uses the "fascinating technology of quantum physics into a system that is simple and easy to live with." Wow really? I checked out their website, and I couldn't find much on this "quantum physics technology" they use, the best I could find was this here:

"Backed by quantum physics and thanks to cutting-edge technology, [Bio-Lean Energy Buttons] harmonize your body’s response to external stressors that bombard us everyday. Recent studies indicate that stress can negatively impact the body’s ability to absorb vital nutrients, which in turn leads to the inability to lose unwanted weight and is a contributing factor in stress related illness. There is also further proof that electromagnetic fields (EMFs) from cell phones, computers and other electronic devices stimulate stress responses in our bodies. Bio-Lean Energy Buttons are programmed to a “healthy frequency” and literally “harmonize” how EMFs affect the body."

More stuff here:

"This relates to research in quantum physics that proves that if external stressors are “neutralized,” or reduced, your body’s cells will resonate and “respond in harmony” to nutritional and lifestyle factors in a healthier way...."

No one has a copyright on quantum physics, so anyone can say anything they want about it. But that doesn't mean the quantum physics community should just sit back quietly as they do so. FemOne doesn't say enough about their product's use of quantum physics for me to say that they are explicitly misrepresenting their product, but I would definitely like to see some legitimate research backing up their claims.

Bush budget: $16.2 million for quantum computing and communications

2004-02-04T17:44:00.000+10:00

Out of the $60 billion of proposed for "IT spending" in the 2005 US budget, a full 0.027% is earmarked for "quantum-level computing and communications systems and other projects."

Galaxy Clusters and Dark Energy

2004-02-03T14:34:00.000+10:00

I don't have much evidence on my side, but I've long been a bit suspicious about the existence of dark energy. This recent development, upon much more analysis, could spell the beginning of the end for dark energy: Universe Today - Are Galaxy Clusters Corrupting Our View of the Big Bang?
Update [07-Feb]: Physics Web's take on this, which includes link to the original paper, which was originally published June 2003, and updated in Jan 2004.
Update [09-Feb]: Economist weighs in too

Fermionic Condensate Unveiled

2004-01-29T17:17:00.000+10:00

From the free section of Nature online (registration required) Fermions chill out: New form of quantum matter unveiled:
"Jin and her colleagues made the condensate by cooling a gas of about half-a-million potassium atoms to within 50 billionths of a degree above absolute zero, the coldest temperature possible. They used a magnetic field to coax the atoms to stand close together in pairs, although without actually bonding. These atomic pairs bear a good likeness to the electrons that produce superconductivity."
Update: Less experimental detail, but more background provided by this Physics News Update story.

2004-01-29T17:05:00.000+10:00

Entanglement Detection
An article entitled Technology Review: Technique Detects Quantum State has a brief summary of research originally published in the November 28, 2003 issue of Physical Review Letters:
"The researchers generated entangled photons using a crystal and a pair of laser beams. They showed that it was possible to detect entanglement using three independent local measurements. The method is particularly useful for determining if entanglement survived the transmission of photons over a fiber optic line."

2004-01-26T23:41:00.000+10:00

Prime Obsession: $20 book, free online
This still-in-hardcover book is available for free here: Nat'l Academies Press, Prime Obsession. The only catch, as far as I can[t] see, is that the small fuzzy font can cause eye strain (unless you download each individual page as a .pdf).

2004-01-24T16:15:00.000+10:00

Qubit Randomization
Technology Review: Quantum Dice Debut: "Researchers from the Massachusetts Institute of Technology and the National Atomic Energy Commission in Argentina have shown that short sequences of random operations—randomly shifting laser pulses or magnetic fields—acting on a string of quantum bits can, in effect, generate random configurations of qubits."
It's been long known how to randomize qubit states, so this new method must be much more time efficient to be of note...unfortunately this article does not mention the new algorithm's complexity. Anyone with a subscription to Science care to fill us in?

2004-01-22T10:02:00.000+10:00

Peter Shor's Quantum Computation Course
Peter Shor's been lecturing at MIT, and here are student-scribed notes for course number 18.435 / 2.111.