(This posting is primarily for readers in the Tokyo area, but if you're into jazz, you might want to find the CDs anyway.)
Robbie Belgrade is a pal of mine. We met a couple of years ago on the way to Kodo's Earth Celebration. Robbie's a professional jazz musician, playing percussion and woodwinds. He studied tablas under Zakir Hussain, one of the most influential tablas players in the world.
Robbie's band Tatopani (which means "hot water" in Nepali) will be playing a release party for their new CD "Azure" in Roppongi on 11/24.
I haven't heard this particular band; like most jazz musicians, Robbie plays with many groups. The times I've heard him play have been quite enjoyable. The instrumentation is often very "world music"; in addition to Robbie's tablas, pandeiro and assorted percussion, the leader of Candela plays the shakuhachi (Japanese flute), for example, but the tunes are mostly pretty straight up jazz. Makes for pleasant sounds outside the usual tonal palette. The bands have been pretty tight, and the solos thoughtfully constructed (and sometimes humorous).
Tokyo, in general, is a good place to hear live jazz. Come out and support live music. Hope to see you there...
Sunday, October 30, 2005
Friday, October 28, 2005
MS+S2006: quantum computing conference in Japan
I just got a flier in the mail for MS+S2006, the International Symposium on Mesoscopic Superconductivity and Spintronics, sponsored by NTT and JST.
Sounds esoteric, but I went in 2004 (it's biannual), and about a third of the presentations and posters were explicitly quantum information processing, and at least another third were of some interest to QIP folks; last year the subtitle was even "In the light of quantum computation". (My paper was a somewhat abstract one on balancing quantum and classical computation, for example.)
It's a physics conference, so acceptances are based on abstracts submitted shortly before the conference, and many of the participants who aren't selected for the oral program present posters. The proceedings, with full papers, are published long after the conference. This all seems odd to those of us used to ACM and USENIX conferences, where full papers are reviewed, acceptance is extremely competitive for many of the conferences, and full proceedings are handed out at the conference itself.
NTT does an excellent job of hosting the conference, and I met a number of important researchers there (Martinis, Lloyd, Tsai, Nakamura, Mooij, to name a few); they get quite the list of attendees and speakers.
Abstracts due Jan. 23, conference Feb. 27-Mar. 2.
Anyway, consider coming, and I look forward to seeing you there!
Sounds esoteric, but I went in 2004 (it's biannual), and about a third of the presentations and posters were explicitly quantum information processing, and at least another third were of some interest to QIP folks; last year the subtitle was even "In the light of quantum computation". (My paper was a somewhat abstract one on balancing quantum and classical computation, for example.)
It's a physics conference, so acceptances are based on abstracts submitted shortly before the conference, and many of the participants who aren't selected for the oral program present posters. The proceedings, with full papers, are published long after the conference. This all seems odd to those of us used to ACM and USENIX conferences, where full papers are reviewed, acceptance is extremely competitive for many of the conferences, and full proceedings are handed out at the conference itself.
NTT does an excellent job of hosting the conference, and I met a number of important researchers there (Martinis, Lloyd, Tsai, Nakamura, Mooij, to name a few); they get quite the list of attendees and speakers.
Abstracts due Jan. 23, conference Feb. 27-Mar. 2.
Anyway, consider coming, and I look forward to seeing you there!
Wednesday, October 26, 2005
Bad News and Good News
No, nothing personal or professional - Bad News is the name of Tom Fenton's book. It's a rant about the decline of the media, especially broadcast news. It's a pretty good rant, but as a proposal for fixing the system, leaves a lot to be desired.
Fenton is a (now retired) foreign correspondent for CBS News. He's from the heyday of foreign correspondents - the 1970s - when money wasn't an object, and foreign correspondents were respected and enabled inside their organizations. He rants about all the usual suspects - the discovery that news can make money, the rise of the bean counters, sycophantic White House reporters, lazy reporters, dumb (or myopic) producers, and a public that would rather be entertained than informed.
Fenton believes, and I agree, that foreign news is incredibly important and that it's drastically underplayed in American media, even including the New York Times, but especially broadcast television news, which is where he spent his career. I also agree that there's no substitute for boots (or birkenstocks or galoshes or whatever foreign correspondents wear) on the ground, and that building an understanding of a culture takes time and effort - years, in fact, maybe decades.
But his proposed solution is backwards-looking. He mentions bloggers several times, talks about how laptops and DVD camcorders make filing reports from the field cheaper. But he demonstrates in his proposals that he Just Doesn't Get It about how completely the world has changed. I'm not talking about U.S. politics, geopolitics, or the news business, I'm talking about the technology.
I'm not totally enamored of all the things the brave new world we're creating bring us (see David Brin's Transparent Society), but I'm pretty certain that a great many of them are going to happen anyway. And most of the ones affecting news are going to be good (I've got a good rant on how narrowcasting means that the world doesn't appear the same to any two people, but we'll do that one another time). The problem is, Fenton has no particular plans to take advantage of anything but the most basic advances.
Fenton's proposals amount to, roughly, three things:
That's about it. None of them are bad things (and all have been tried, to one extent or another), but none of them demonstrate the least grasp of what is about to happen to media over the next decade or two.
For an extremely crude idea, see, say, the New York Times' coverage of Harriet Miers' nomination to the Supreme Court, or CNN's web site every day. Text stories, photos, multimedia slide shows with audio, video clips, and links to background data, both inside and outside their own websites. (Don't get me started ranting about proprietary data formats.)
Now project out a decade (don't put too much faith into that timeline). How about this:
It's six ten, and you sit down in your car to drive home (we'll assume one of those old-fashioned drive-it-yourself cars). It's a forty minute commute, and you always do the evening news. You don't sweat the fact that the broadcast started ten minutes ago, your in-car box time shifts. You get forty minutes of radio, pausing to take a phone call and replaying part of one story, so you only cover thirty minutes of the broadcast.
You pull into the driveway, go inside the house and start cooking dinner. The box in the kitchen offers to pick up where you left off on the radio broadcast and give you the last half hour, or go back and show you the video clips associated with the stories you heard in the car. You elect the video clips; the box plays them with abbreviated commentary, since it has kept track of what you've already heard. You take a couple of the offered backgrounders, getting several minutes on, say, the political flap over Koizumi's visits to Yasukuni Shrine back when China and Japan were rivals. Partway through, your spouse comes in with kids, so you switch it off.
After the kids are in bed, as you're getting ready for bed, you catch the last few minutes. You tell the box to compress down to five minutes, you're tired. It edits down several stories, including a brief update on one of the ones you heard earlier.
Would I commit an hour a day to media like that? You bet. I don't do much TV, but I probably spend better than an hour a day with the Daily Yomiuri and the New York Times, my two top sources.
Fenton needs to realize that the network news broadcast is an anachronism. It'll be gone before he cashes his first social security check. Here's what I think a news package delivered to the viewer needs:
There have been lots of other discussions on how searchable and customizable it has to be; I won't go into those. Nick Negroponte has been talking since the founding of the Media Lab about viewing a baseball game from the point of view of the baseball; toss that in, too.
What does a news organization need to provide this kind of content? A few tools, especially for creating the rich, variable depth. Nothing I don't expect to come along - advertisers will enjoy having that at least as much as news producers. Those are technical considerations, what about the people? A foreign correspondent is no longer the source of much original content, even today, let alone a decade from now, when raw footage will coming from everyone with a cell phone with a camera. What a foreign correspondent is is a guide to the torrent of available information. He or she organizes it, makes a story out of it, culls the important material, knows who the people are. That's what takes a truly broad and deep understanding of the issue at hand. Much of that work can, in theory, be done in London or New York, but you won't build the personal relationships and gut-level feel for the places, people and events without being there.
Anyway, just a few thoughts about the future of the news. Fenton has lots of worthwhile anecdotes on how sordid the behavior is on all sides of the Middle East and Central Asia theaters, but I'll leave those for another time, too.
Fenton is a (now retired) foreign correspondent for CBS News. He's from the heyday of foreign correspondents - the 1970s - when money wasn't an object, and foreign correspondents were respected and enabled inside their organizations. He rants about all the usual suspects - the discovery that news can make money, the rise of the bean counters, sycophantic White House reporters, lazy reporters, dumb (or myopic) producers, and a public that would rather be entertained than informed.
Fenton believes, and I agree, that foreign news is incredibly important and that it's drastically underplayed in American media, even including the New York Times, but especially broadcast television news, which is where he spent his career. I also agree that there's no substitute for boots (or birkenstocks or galoshes or whatever foreign correspondents wear) on the ground, and that building an understanding of a culture takes time and effort - years, in fact, maybe decades.
But his proposed solution is backwards-looking. He mentions bloggers several times, talks about how laptops and DVD camcorders make filing reports from the field cheaper. But he demonstrates in his proposals that he Just Doesn't Get It about how completely the world has changed. I'm not talking about U.S. politics, geopolitics, or the news business, I'm talking about the technology.
I'm not totally enamored of all the things the brave new world we're creating bring us (see David Brin's Transparent Society), but I'm pretty certain that a great many of them are going to happen anyway. And most of the ones affecting news are going to be good (I've got a good rant on how narrowcasting means that the world doesn't appear the same to any two people, but we'll do that one another time). The problem is, Fenton has no particular plans to take advantage of anything but the most basic advances.
Fenton's proposals amount to, roughly, three things:
- Recreate the foreign bureaus of the major news organizations.
- Build a grassroots organization that will monitor and push for quality of news reporting.
- Extend the nightly news to an hour, so there's room for in-depth reporting.
That's about it. None of them are bad things (and all have been tried, to one extent or another), but none of them demonstrate the least grasp of what is about to happen to media over the next decade or two.
For an extremely crude idea, see, say, the New York Times' coverage of Harriet Miers' nomination to the Supreme Court, or CNN's web site every day. Text stories, photos, multimedia slide shows with audio, video clips, and links to background data, both inside and outside their own websites. (Don't get me started ranting about proprietary data formats.)
Now project out a decade (don't put too much faith into that timeline). How about this:
It's six ten, and you sit down in your car to drive home (we'll assume one of those old-fashioned drive-it-yourself cars). It's a forty minute commute, and you always do the evening news. You don't sweat the fact that the broadcast started ten minutes ago, your in-car box time shifts. You get forty minutes of radio, pausing to take a phone call and replaying part of one story, so you only cover thirty minutes of the broadcast.
You pull into the driveway, go inside the house and start cooking dinner. The box in the kitchen offers to pick up where you left off on the radio broadcast and give you the last half hour, or go back and show you the video clips associated with the stories you heard in the car. You elect the video clips; the box plays them with abbreviated commentary, since it has kept track of what you've already heard. You take a couple of the offered backgrounders, getting several minutes on, say, the political flap over Koizumi's visits to Yasukuni Shrine back when China and Japan were rivals. Partway through, your spouse comes in with kids, so you switch it off.
After the kids are in bed, as you're getting ready for bed, you catch the last few minutes. You tell the box to compress down to five minutes, you're tired. It edits down several stories, including a brief update on one of the ones you heard earlier.
Would I commit an hour a day to media like that? You bet. I don't do much TV, but I probably spend better than an hour a day with the Daily Yomiuri and the New York Times, my two top sources.
Fenton needs to realize that the network news broadcast is an anachronism. It'll be gone before he cashes his first social security check. Here's what I think a news package delivered to the viewer needs:
- It must work across all media - text, images, sound, video - and all viewing and delivery platforms - HDTV, cell phone video, cell phone audio, PDA text, car radio. (Call this variable width, if you like.)
- It has to retain context as you move from box to box (car radio to kitchen TV) and session to session (e.g., updates without repeating the whole story the next morning).
- It has to offer variable depth; the same story should be available in one-, three-, and ten-minute formats. Creating and managing this variable depth is critical and difficult.
- It has to offer still more depth, including the provenance of all of the data, access to multiple viewpoints on the same events, multiple translations of foreign-language text and speech, as well as the originals. For edited video of, say, a riot, the fifteen seconds shown in the organized report should link back to the hour of raw footage in a useful fashion.
There have been lots of other discussions on how searchable and customizable it has to be; I won't go into those. Nick Negroponte has been talking since the founding of the Media Lab about viewing a baseball game from the point of view of the baseball; toss that in, too.
What does a news organization need to provide this kind of content? A few tools, especially for creating the rich, variable depth. Nothing I don't expect to come along - advertisers will enjoy having that at least as much as news producers. Those are technical considerations, what about the people? A foreign correspondent is no longer the source of much original content, even today, let alone a decade from now, when raw footage will coming from everyone with a cell phone with a camera. What a foreign correspondent is is a guide to the torrent of available information. He or she organizes it, makes a story out of it, culls the important material, knows who the people are. That's what takes a truly broad and deep understanding of the issue at hand. Much of that work can, in theory, be done in London or New York, but you won't build the personal relationships and gut-level feel for the places, people and events without being there.
Anyway, just a few thoughts about the future of the news. Fenton has lots of worthwhile anecdotes on how sordid the behavior is on all sides of the Middle East and Central Asia theaters, but I'll leave those for another time, too.
Saturday, October 22, 2005
The Scariest Thing I've Ever Read
Just in time for Halloween...
Stephen King called The Hot Zone "one of the most horrifying things I've ever read." I would hand that title instead to David Goodstein's Out of Gas (he has also lectured on this topic; you can get RealVideo here). Goodstein's concern is not the possible deaths of millions of people due to Ebola and Marburg. It's not the Bush administration paving over Yosemite. It's not even anthropogenic global warming and a piddling few degrees' increase in average temperatures. He's worried about whether or not we will run out of fossil fuels before we figure out how to live sustainably, and consequently whether civilization as we know it will come to an end.
Goodstein is a physics professor at Caltech. In the book, he heads straight for the basics: we're consuming energy that was stored in the ground long ago. We are consuming it far faster than it replenishes itself. It will run out; what are we to do when it does?
Goodstein covers the well-known Hubbert peak, and suggests that we are now at the world-wide peak of petroleum production, give or take a decade or so. When we hit that peak, we are about half way done with the amount of oil we can successfully extract and use. But that doesn't mean we have another 150 years to go before problems occur; because demand is increasing and production is flat to declining as we pass the peak, serious shortages are likely to begin within a decade or two at most. Such shortages will lead to price instability, and are especially problematic since petroleum is such a flexible, useful material. We use it in plastics, fertilizers, and more, as well as burning the stuff directly, so a shortage has the potential to threaten such fundamental societal requirements as food production.
He discusses where oil comes from, how inefficient it is to use oil shale, how natural gas, coal, and even accessible supplies of fissionable uranium will run out, and relatively soon. Each of those supplies is worth a few decades, given reasonable projections about population growth, energy consumption, and the fraction of the resource that is recoverable at reasonable economic and thermodynamic returns. All told, if we are flexible enough about our fuels, we have maybe until the end of the century. Then what?
Our only choice is fusion. We can either get our energy indirectly, by creating solar cells that ultimately derive the power they deliver from the sun's fusion, or we can figure out how to run fusion here on earth - but we haven't been very successful at that yet.
What to do, what to do?
Stephen King called The Hot Zone "one of the most horrifying things I've ever read." I would hand that title instead to David Goodstein's Out of Gas (he has also lectured on this topic; you can get RealVideo here). Goodstein's concern is not the possible deaths of millions of people due to Ebola and Marburg. It's not the Bush administration paving over Yosemite. It's not even anthropogenic global warming and a piddling few degrees' increase in average temperatures. He's worried about whether or not we will run out of fossil fuels before we figure out how to live sustainably, and consequently whether civilization as we know it will come to an end.
Goodstein is a physics professor at Caltech. In the book, he heads straight for the basics: we're consuming energy that was stored in the ground long ago. We are consuming it far faster than it replenishes itself. It will run out; what are we to do when it does?
Goodstein covers the well-known Hubbert peak, and suggests that we are now at the world-wide peak of petroleum production, give or take a decade or so. When we hit that peak, we are about half way done with the amount of oil we can successfully extract and use. But that doesn't mean we have another 150 years to go before problems occur; because demand is increasing and production is flat to declining as we pass the peak, serious shortages are likely to begin within a decade or two at most. Such shortages will lead to price instability, and are especially problematic since petroleum is such a flexible, useful material. We use it in plastics, fertilizers, and more, as well as burning the stuff directly, so a shortage has the potential to threaten such fundamental societal requirements as food production.
He discusses where oil comes from, how inefficient it is to use oil shale, how natural gas, coal, and even accessible supplies of fissionable uranium will run out, and relatively soon. Each of those supplies is worth a few decades, given reasonable projections about population growth, energy consumption, and the fraction of the resource that is recoverable at reasonable economic and thermodynamic returns. All told, if we are flexible enough about our fuels, we have maybe until the end of the century. Then what?
Our only choice is fusion. We can either get our energy indirectly, by creating solar cells that ultimately derive the power they deliver from the sun's fusion, or we can figure out how to run fusion here on earth - but we haven't been very successful at that yet.
What to do, what to do?
Friday, October 14, 2005
More on the Myth
Okay, this one's not really about Shor and QKD, but it is about the authenticated channel for QKD.
I said the physicists underplayed the importance of the authenticated channel in operational practice, and was (rightly) chastened by Dave Bacon and Daniel Gottesman. In the interests of equal time, here's proof that not everyone in the computer networking community gets it:
A thread on an Internet Draft (= proposed RFC) on using QKD for key exchange for PPP. Here's a link to the Internet Draft itself (warning, that link will probably go stale in April 2006, and may or may not properly track revisions to the draft, depending on whether or not I picked up the right link). The email thread seems a little fragmented, part of the conversation appears to be taking place elsewhere.
I haven't actually read the draft (the "view document" link at the IETF site appears broken?!?), but from the email thread, it appears that Mr. Sfaxi either does not understand or cannot explain the use of the classical authenticated channel. Remember, gang: QKD requires access to an authenticated classical channel.
Stay tuned for more late-breaking news from the exciting world of IETF...
[I've you've just come into this conversation, I recommend reading this posting, this posting, and especially quant-ph/0406147.]
I said the physicists underplayed the importance of the authenticated channel in operational practice, and was (rightly) chastened by Dave Bacon and Daniel Gottesman. In the interests of equal time, here's proof that not everyone in the computer networking community gets it:
A thread on an Internet Draft (= proposed RFC) on using QKD for key exchange for PPP. Here's a link to the Internet Draft itself (warning, that link will probably go stale in April 2006, and may or may not properly track revisions to the draft, depending on whether or not I picked up the right link). The email thread seems a little fragmented, part of the conversation appears to be taking place elsewhere.
I haven't actually read the draft (the "view document" link at the IETF site appears broken?!?), but from the email thread, it appears that Mr. Sfaxi either does not understand or cannot explain the use of the classical authenticated channel. Remember, gang: QKD requires access to an authenticated classical channel.
Stay tuned for more late-breaking news from the exciting world of IETF...
[I've you've just come into this conversation, I recommend reading this posting, this posting, and especially quant-ph/0406147.]
Thursday, October 13, 2005
Quantum Time Machines: What? Why? and (maybe) How?
Tim Ralph is in Tokyo this week, and is giving a talk today. Here's
the abstract:
Title: Quantum Time Machines: What? Why? and (maybe) How?
Abstract:
Whether time travel into the past is possible is an undecided physical
question [1]. Recently it has been noted that certain models of time
travel for quantum particles do not lead to the same difficult
paradoxes that arise for classical particles [2]. Furthermore the
types of quantum evolutions predicted for these "quantum time
machines" could give rise to a "super" quantum computer, able to solve
problems thought to be intractable by any other means [3]. In this
talk I will discuss time machines in general, how quantum mechanics
avoids the paradoxes and the unusual evolutions predicted. I will
then argue that the requirements for realizing such machines are not
as stringent as previously thought and I will propose "horizon
technology" experiments which could test these ideas [4].
With an abstract like that, you'd have to beat with me a stick to keep me away from the talk. Now, I only know a little about relativity - what every Caltech freshman knows (special relativity) and any fan of popular science writing knows (e.g., Kip Thorne's fabulous Black Holes and Time Warps). I know squat about the real math of general relativity, but I'm familiar with the basic implications of the curvature of space, black holes, wormholes, etc. So, should be a fun but challenging talk.
To prepare, I spent a little time this morning reading Tim's paper (quant-ph/0510038) and took a quick look at Dave Bacon's recent paper. Dave's paper is apparently a pretty major one. Building on work by Deutsch, Brun, and others, he shows that the existence of closed timelike curves (CTCs) would allow NP-complete problems to be solved on a quantum computer using only polynomial resources.
What the heck is a closed timelike curve? It's a path through a wormhole that comes back to where you started. Special relativity treats space and time as a four-dimensional space called spacetime, and establishes rules for paths in that space. You can never reach another point in spacetime that would require you to travel faster than light to get there. General relativity, which introduces the curvature of space, in its extreme appears to allow the creation of wormholes - places in space that, if you step through, take you to another distant point in space. Travelling through a wormhole can allow you to travel into your own past, coming back to where you started, and creating a "closed timelike curve". So Dave showed that travelling through a wormhole will allow you to solve NP-complete problems efficiently on a quantum computer. (We won't talk about grandfather paradoxes and the like, but apparently quantum mechanics helps there.)
Moving on, Tim's paper is lucid and remarkably easy to read for a non-specialist like me. He shows that you can take an entangled pair of quanta (an EPR pair), relativistically accelerate one and bring it back to the starting point, and like the pedagogical twins, one particle will now be "older" than the other. Using the standard quantum techniques of teleportation, he then creates a state that's something a little like a wormhole, essentially a loop in time. You can't use this to violate causality or learn about the future, but it does allow nonlinear evolution of the quantum system. Dave's system depends on the nonlinearity created by the wormhole; here Tim has done it without one. Fascinating.
Okay, time to pack up and head to the seminar and see whether I've correctly interpreted Tim, and what other features of this there are that I haven't thought of...
(From this point, it's just the notes I typed during the seminar, so apologies if they seem a little abrupt or semi-coherent.)
Morris, Thorne, Yurtsever, PRL 61
Where are all the time tourists? There's a plaque in Perth that says, "In the event that the transportation of life from the future" becomes possible, please show up at March 31, 2005, in Perth. No one did. (Reminds me of the MIT conference.) Requiring that a time machine receiver be built first eliminates the problem of the lack of visible travellers, but still doesn't eliminate the standard causality problems.
Tim actually likes Sagan's Contact. Wormholes were developed by Einstein and Rosen, so they are also called Einstein-Rosen bridges, but in their solution the wormhole collapses too quickly to be used. Kip Thorne showed that if you thread a wormhole with exotic matter, it might stay open long enough to let regular matter pass through. Thorne showed that many of the possible paradoxes resolve themselves, but whether they all resolve comfortably is unknown.
You get a nice little paradox if you use classical bits and a CNOT gate. Start with a one on the target bit, run it through the CNOT gate, and take that output rho, shove it through your time machine into the past, then use that as the control line for the CNOT gate. There's no possible consistent result. (Think about the states where rho comes out of the time machine as a one or a zero.)
However, if you do this with qubits, there is a solution. rho = 1/2(|0><0| + |1><1|) works. Deutsch then generalized and showed that any unitary evolution U has a solution without creating classical paradoxes, provided that you keep your particle that goes through the wormhole in a box and neither measure nor prepare it during the time travel interval.
The wormhole introduces a nonlinearity. Non-relativistic ("classical") quantum mechanics, of course, is linear. So is there a way to use that nonlinearity now added? Yes, in certain regions, it creates a faster growth of the trace distance between two states. This is where the power comes from that Bacon used to solve NP-complete problems.
Of course, we don't have a source of wormholes to experiment with, and don't even know how to build them. So what about a stochastic time machine? One that lights up one of four possible lights (labeled I, X, Z, and XZ) every time you shove a particle into to send it into the past. If you're familiar with quantum teleportation, you'll immediately recognize those as the operators you need to apply to retrieve the teleported state, once you've measured the qubit at the source.
During the time travel interval (between the past time where you receive the particle, and the future time where you sent it), what you have is a mixed state. Now there are no paradoxes, even if you observe the particle. And you can compute with it. But your real, true final answer isn't known until after the (local) time that you sent the particle into the time machine.
Teleportation can be considered a "stochastic wormhole". Do the same thing you would with a real wormhole - accelerate one of the particles at relativistic speeds for a while, then bring it back where you started - and you have a stochastic time machine.
What does it all mean? It seems that quantum systems are better behaved with respect to time travel than classical machines. A stochastic quantum time machine still leads to interesting and potentially useful quantum evolutions whilst avoiding ad hoc assumptions. Teleportation using time displaced entanglement appears equivalent to a stochastic time machine. These experiments are hard, but not too hard.
Question:What does increasing the overlap do to security proofs of QKD and things of that nature? Answer:Don't know. Would be interesting to check...
Question:Increasing the overlap, doesn't that have implications for cloning and superluminal communication? Answer:You essentially "lose contact" with other qubits (you have to trace out over other qubits, because the operation is on the reduced density operator). So, no, you don't get superluminal. (See Deutsch.)
It startles and intrigues me no end that quantum mechanics, information theory, and general relativity converge in such interesting ways.
See this auction!
the abstract:
Speaker: Prof.Tim C. Ralph
Centre for Quantum Computer Technology,
University of Queensland,
Australia.
Title: Quantum Time Machines: What? Why? and (maybe) How?
Abstract:
Whether time travel into the past is possible is an undecided physical
question [1]. Recently it has been noted that certain models of time
travel for quantum particles do not lead to the same difficult
paradoxes that arise for classical particles [2]. Furthermore the
types of quantum evolutions predicted for these "quantum time
machines" could give rise to a "super" quantum computer, able to solve
problems thought to be intractable by any other means [3]. In this
talk I will discuss time machines in general, how quantum mechanics
avoids the paradoxes and the unusual evolutions predicted. I will
then argue that the requirements for realizing such machines are not
as stringent as previously thought and I will propose "horizon
technology" experiments which could test these ideas [4].
[1] M.S.Morris, K.P.Thorne and U.Yurtsever, Phys.Rev.Lett.61, 1446 (1988).
[2] D.Deutsch, Phys.Rev.D 44, 3197 (1991).
[3] D.Bacon, Phys.Rev.A, 70, 032309 (2004).
[4] T.C.Ralph, quant-ph/0510038.
With an abstract like that, you'd have to beat with me a stick to keep me away from the talk. Now, I only know a little about relativity - what every Caltech freshman knows (special relativity) and any fan of popular science writing knows (e.g., Kip Thorne's fabulous Black Holes and Time Warps). I know squat about the real math of general relativity, but I'm familiar with the basic implications of the curvature of space, black holes, wormholes, etc. So, should be a fun but challenging talk.
To prepare, I spent a little time this morning reading Tim's paper (quant-ph/0510038) and took a quick look at Dave Bacon's recent paper. Dave's paper is apparently a pretty major one. Building on work by Deutsch, Brun, and others, he shows that the existence of closed timelike curves (CTCs) would allow NP-complete problems to be solved on a quantum computer using only polynomial resources.
What the heck is a closed timelike curve? It's a path through a wormhole that comes back to where you started. Special relativity treats space and time as a four-dimensional space called spacetime, and establishes rules for paths in that space. You can never reach another point in spacetime that would require you to travel faster than light to get there. General relativity, which introduces the curvature of space, in its extreme appears to allow the creation of wormholes - places in space that, if you step through, take you to another distant point in space. Travelling through a wormhole can allow you to travel into your own past, coming back to where you started, and creating a "closed timelike curve". So Dave showed that travelling through a wormhole will allow you to solve NP-complete problems efficiently on a quantum computer. (We won't talk about grandfather paradoxes and the like, but apparently quantum mechanics helps there.)
Moving on, Tim's paper is lucid and remarkably easy to read for a non-specialist like me. He shows that you can take an entangled pair of quanta (an EPR pair), relativistically accelerate one and bring it back to the starting point, and like the pedagogical twins, one particle will now be "older" than the other. Using the standard quantum techniques of teleportation, he then creates a state that's something a little like a wormhole, essentially a loop in time. You can't use this to violate causality or learn about the future, but it does allow nonlinear evolution of the quantum system. Dave's system depends on the nonlinearity created by the wormhole; here Tim has done it without one. Fascinating.
Okay, time to pack up and head to the seminar and see whether I've correctly interpreted Tim, and what other features of this there are that I haven't thought of...
(From this point, it's just the notes I typed during the seminar, so apologies if they seem a little abrupt or semi-coherent.)
Morris, Thorne, Yurtsever, PRL 61
Where are all the time tourists? There's a plaque in Perth that says, "In the event that the transportation of life from the future" becomes possible, please show up at March 31, 2005, in Perth. No one did. (Reminds me of the MIT conference.) Requiring that a time machine receiver be built first eliminates the problem of the lack of visible travellers, but still doesn't eliminate the standard causality problems.
Tim actually likes Sagan's Contact. Wormholes were developed by Einstein and Rosen, so they are also called Einstein-Rosen bridges, but in their solution the wormhole collapses too quickly to be used. Kip Thorne showed that if you thread a wormhole with exotic matter, it might stay open long enough to let regular matter pass through. Thorne showed that many of the possible paradoxes resolve themselves, but whether they all resolve comfortably is unknown.
You get a nice little paradox if you use classical bits and a CNOT gate. Start with a one on the target bit, run it through the CNOT gate, and take that output rho, shove it through your time machine into the past, then use that as the control line for the CNOT gate. There's no possible consistent result. (Think about the states where rho comes out of the time machine as a one or a zero.)
However, if you do this with qubits, there is a solution. rho = 1/2(|0><0| + |1><1|) works. Deutsch then generalized and showed that any unitary evolution U has a solution without creating classical paradoxes, provided that you keep your particle that goes through the wormhole in a box and neither measure nor prepare it during the time travel interval.
The wormhole introduces a nonlinearity. Non-relativistic ("classical") quantum mechanics, of course, is linear. So is there a way to use that nonlinearity now added? Yes, in certain regions, it creates a faster growth of the trace distance between two states. This is where the power comes from that Bacon used to solve NP-complete problems.
Of course, we don't have a source of wormholes to experiment with, and don't even know how to build them. So what about a stochastic time machine? One that lights up one of four possible lights (labeled I, X, Z, and XZ) every time you shove a particle into to send it into the past. If you're familiar with quantum teleportation, you'll immediately recognize those as the operators you need to apply to retrieve the teleported state, once you've measured the qubit at the source.
During the time travel interval (between the past time where you receive the particle, and the future time where you sent it), what you have is a mixed state. Now there are no paradoxes, even if you observe the particle. And you can compute with it. But your real, true final answer isn't known until after the (local) time that you sent the particle into the time machine.
Teleportation can be considered a "stochastic wormhole". Do the same thing you would with a real wormhole - accelerate one of the particles at relativistic speeds for a while, then bring it back where you started - and you have a stochastic time machine.
What does it all mean? It seems that quantum systems are better behaved with respect to time travel than classical machines. A stochastic quantum time machine still leads to interesting and potentially useful quantum evolutions whilst avoiding ad hoc assumptions. Teleportation using time displaced entanglement appears equivalent to a stochastic time machine. These experiments are hard, but not too hard.
Question:What does increasing the overlap do to security proofs of QKD and things of that nature? Answer:Don't know. Would be interesting to check...
Question:Increasing the overlap, doesn't that have implications for cloning and superluminal communication? Answer:You essentially "lose contact" with other qubits (you have to trace out over other qubits, because the operation is on the reduced density operator). So, no, you don't get superluminal. (See Deutsch.)
It startles and intrigues me no end that quantum mechanics, information theory, and general relativity converge in such interesting ways.
See this auction!
Friday, October 07, 2005
My First Perpetual-Motion Machine
A totally random anecdote...last night I recalled building my first perpetual motion machine. I don't have a clear idea of how old I was, but old enough to have my electronics science kit, including a small solar cell. Ten, perhaps?
My dad is big on O-gauge model trains, and they were set up in the basement. There were some lampposts with grain-of-wheat lightbulbs to go with it. The lampposts were intended to be battery-driven, but I had a better idea: I'd run them with my solar cell. I realized that they would need to be "primed"; I'd have to start with the battery hooked up, but then assuming all went well, I could unplug the battery and the solar cell would take over. Light from the lampposts themselves would drive the solar cell, which would drive the lampposts. Viola! Lighting for the trains, without a battery!
Needless to say, every time I unplugged the battery, the lampposts went out. I was smart enough to figure out that the solar cell needed more light, so I tried adding reflectors that would send back a greater percentage of the light to the solar cell. No joy. I think (though this part of the recollection is fuzzy) that I wound up trying a less ambitious system, with just the lightbulb directly in front of the solar cell, which of course failed, too.
And there this particular memory vignette fades to black. I have no particular recollection of realizing that what I was trying was theoretically impossible, only that the practical considerations were insurmountable. There were, in all probability, mechanical perpetual motion machines from about the same time frame. Something for me to try to dig out of that unreliable and fast-fading bank...
My dad is big on O-gauge model trains, and they were set up in the basement. There were some lampposts with grain-of-wheat lightbulbs to go with it. The lampposts were intended to be battery-driven, but I had a better idea: I'd run them with my solar cell. I realized that they would need to be "primed"; I'd have to start with the battery hooked up, but then assuming all went well, I could unplug the battery and the solar cell would take over. Light from the lampposts themselves would drive the solar cell, which would drive the lampposts. Viola! Lighting for the trains, without a battery!
Needless to say, every time I unplugged the battery, the lampposts went out. I was smart enough to figure out that the solar cell needed more light, so I tried adding reflectors that would send back a greater percentage of the light to the solar cell. No joy. I think (though this part of the recollection is fuzzy) that I wound up trying a less ambitious system, with just the lightbulb directly in front of the solar cell, which of course failed, too.
And there this particular memory vignette fades to black. I have no particular recollection of realizing that what I was trying was theoretically impossible, only that the practical considerations were insurmountable. There were, in all probability, mechanical perpetual motion machines from about the same time frame. Something for me to try to dig out of that unreliable and fast-fading bank...
Tuesday, October 04, 2005
100 Greatest Americans?
Rod & Ted's Alternate List of Greatest Americans
After reading the Discovery Channel's list of one hundred candidates for the Greatest American, Ted and I spent way too much time on creating our own version. We wound up throwing out more than half of the original list.
There was significant discussion over whether athletes and entertainers belonged on the list at all. They were certainly FAR over-represented in the original list. Probably none would be serious candidates for the single greatest American -- but the list of true candidates for that honor is very short, anyway. We settled on keeping representatives from almost the whole range of human endeavor. Most of the athletes, artists, musicians, and film actors/directors we kept were truly transformative, in our opinion. Feel free to argue!
Fields that we felt were egregiously underrepresented in the original list were writers, artists, jurists, scientists and engineers. In our current list, it's possible that business types are underrepresented. We wanted an educator, but couldn't come up with one.
In a few cases, we invoked executive privilege and listed two or three people as a single entry, when their names are rarely mentioned apart (or, in the case of Apollo 11, should be).
In a *very* few cases, the person in question is a putz. But, we felt their accomplishments were difficult to ignore, and in at least two cases, their putziness came into evidence later in life, after their accomplishments had already established their importance.
For your reading and arguing pleasure.
Keep (44):
New (51):
* = putz, but...
Our breakdown for the whole 100, by profession (totals exceed 100 because our list is actually slightly over 100, and some have two professions):
Eliminate (56):
Honorable Mentions:
After reading the Discovery Channel's list of one hundred candidates for the Greatest American, Ted and I spent way too much time on creating our own version. We wound up throwing out more than half of the original list.
There was significant discussion over whether athletes and entertainers belonged on the list at all. They were certainly FAR over-represented in the original list. Probably none would be serious candidates for the single greatest American -- but the list of true candidates for that honor is very short, anyway. We settled on keeping representatives from almost the whole range of human endeavor. Most of the athletes, artists, musicians, and film actors/directors we kept were truly transformative, in our opinion. Feel free to argue!
Fields that we felt were egregiously underrepresented in the original list were writers, artists, jurists, scientists and engineers. In our current list, it's possible that business types are underrepresented. We wanted an educator, but couldn't come up with one.
In a few cases, we invoked executive privilege and listed two or three people as a single entry, when their names are rarely mentioned apart (or, in the case of Apollo 11, should be).
In a *very* few cases, the person in question is a putz. But, we felt their accomplishments were difficult to ignore, and in at least two cases, their putziness came into evidence later in life, after their accomplishments had already established their importance.
For your reading and arguing pleasure.
Keep (44):
- Ali, Muhammad (a)
- Angelou, Maya (w)
- Anthony, Susan B. (l)
- Bell, Alexander Graham (i)
- Carnegie, Andrew (b)
- Carson, Johnny (f)
- Carver, George Washington (i)
- Chavez, Cesar (l)
- Disney, Walt (f,v,b)
- Douglass, Frederick (l)
- Edison, Thomas Alva (i)
- Einstein, Albert (i)
- Ford, Henry (b)
- Franklin, Benjamin (i,t)
- Gates, Bill (b)
- Glenn, John (e,t)
- Graham, Billy (r)
- Hamilton, Alexander (t)
- Jefferson, Thomas (pr,i)
- Keller, Helen (l)
- Kennedy, John F. (p)
- King Jr., Dr. Martin Luther (l)
- Lincoln, Abraham (p)
- Lindbergh, Charles (e)
- Malcolm X (l)
- Murphy, Audie (s)
- Owens, Jesse (a)
- Patton, George (s)
- Presley, Elvis (m)
- Roebling, John A. ?
- Robinson, Jackie (a)
- Roosevelt, Franklin D (p)
- Roosevelt, Theodore (p)
- Ruth, Babe (a)
- Salk, Jonas (i)
- Smith, Joseph (r)
- Tesla, Nikola (i)
- Tubman, Harriet (l)
- Twain, Mark (w)
- Washington, George (s,p)
- Wayne, John (f)
- Wright, Orville & Wilbur (i)
- Yeager, Chuck (e)
New (51):
- Ansel Adams (v)
- Apollo 11 crew (Neil Armstrong, Buzz Aldrin, & Michael Collins) (e)
- Louis Armstrong (m)
- Daniel Boone (e)
- Ray Bradbury (w)
- William Jennings Bryan (j)
- Alexander Calder (v)
- Johnny Cash (m)
- Vint Cerf (i)
- Edward Drinker Cope & Othniel Charles Marsh (i)
- Aaron Copland (m)
- Davy Crockett (e)
- Walter Cronkite (f)
- Glenn Curtiss (i,b)
- Virginia Dare (o)
- Clarence Darrow (j)
- Charles & Ray Eames (v)
- Richard Feynman (i)
- Bobby Fischer * (o)
- F. Scott Fitzgerald (w)
- Robert Fulton (i)
- Theodore Giesel (w)
- William Randolph Hearst (b)
- Ernest Hemingway (w)
- Sam Houston (e,s,t)
- Edwin Hubble (i)
- Andrew Jackson (s,p)
- Francis Scott Key (w)
- Meriwether Lewis & William Clark (e)
- Douglas MacArthur (s)
- George C. Marshall (po)
- John Marshall (j)
- Thurgood Marshall (j)
- Herman Melville (w)
- Gordon Moore (i,b)
- John Muir (e)
- James Naismith (a)
- John von Neumann (i)
- Sandra Day O'Connor (j)
- Robert Oppenheimer (i)
- Linus Pauling (i)
- Edgar Allen Poe (w)
- Sacajawea (e)
- Charles Schulz (v)
- William Shockley (i) *
- Siegel & Schuster (v)
- Henry David Thoreau (w)
- Andy Warhol (v)
- James Watson (i)
- Orson Welles (f)
- Walt Whitman (w)
- Frank Lloyd Wright (v)
* = putz, but...
Our breakdown for the whole 100, by profession (totals exceed 100 because our list is actually slightly over 100, and some have two professions):
p: presidents: 7
s: soldiers: 6
j: jurists/lawyers: 5
t: other politicians/statesmen: 5
l: labor/rights/activists: 7
e: adventurers/explorers/astronauts/pioneers: 13
i: scientists/inventors: 22
v: visual arts/design/architecture: 9
w: writers: 11
f: film/tv: 4
m: musicians: 4
a: athletes: 5
b: business: 5
r: religion: 2
o: other: 2
Eliminate (56):
- Armstrong, Lance
- Armstrong, Neil
- Ball, Lucille
- Bush, Barbara
- Bush, George H. W.
- Bush, George W.
- Bush, Laura
- Carter, Jimmy
- Charles, Ray
- Clinton, Bill
- Clinton, Hillary
- Cosby, Bill
- Cruise, Tom
- DeGeneres, Ellen
- Earhart, Amelia
- Eastwood, Clint
- Edwards, John
- Eisenhower, Dwight (s,pr)
- Favre, Brett
- Gibson, Mel
- Giuliani, Rudolph
- Hanks, Tom
- Hefner, Hugh
- Hepburn, Katharine
- Hope, Bob
- Hughes, Howard
- Jackson, Michael
- Jobs, Steve
- Johnson, Lyndon B.
- Jordan, Michael
- Kennedy, Robert F.
- Kennedy Onassis, Jacqueline
- Limbaugh, Rush
- Lucas, George
- Madonna
- McGraw, Dr. Phil
- Monroe, Marilyn
- Moore, Michael
- Nixon, Richard
- Obama, Barack
- Parks, Rosa
- Powell, Colin
- Reagan, Ronald
- Reeve, Christopher
- Rice, Condoleezza
- Roosevelt, Eleanor
- Sagan, Carl
- Schwarzenegger, Arnold
- Sinatra, Frank
- Spielberg, Steven
- Stewart, Jimmy
- Stewart, Martha
- Tillman, Pat
- Truman, Harry
- Trump, Donald
- Walton, Sam
- Winfrey, Oprah
- Woods, Tiger
Honorable Mentions:
- Isaac Asimov
- Carl Barks
- Vannevar Bush
- John Coltrane
- Charles Curtis
- Miles Davis
- Phillip K. Dick
- Elizabeth Dole
- Duke Ellington (m)
- Philo T. Farnsworth
- William Faulkner
- Geraldine Ferraroo
- Hal Foster
- Hugo Gernsback
- Samuel Gompers
- U.S. Grant
- Devil Anse Hatfield
- Nathaniel Hawthorne
- Robert Heinlein
- Frank Herbert
- Billie Holliday
- Harry Houdini
- Mother Jones
- Bob Kahn
- Bob Kane
- Chief Logan
- Mercury Seven, the rest
- Nancy Landon Kassebaum
- Walt Kelly
- Chief Logan
- Wilma Mankiller
- Winsor McKay
- Charlier Parker
- Frances Perkins
- Jon Postel
- James Randi
- Norman Rockwell
- Nellie Tayloe Ross
- Chief Seattle
- Claude Shannon
- Upton Sinclair
- Dr. Spock
- Jim Thorpe
- Gore Vidal
- Booker T. Washington
- Laura Ingalls Wilder
- Woodrow Wilson
- Woodward & Bernstein
- Daniel Carter Beard & William D. Boyce
Monday, October 03, 2005
Stop the Myth: QKD doesn't fix what Shor broke
[Update: See More on the Myth.]
There is a lot of confusion about the relationship between two of the most famous results in quantum information theory: Shor's algorithm for factoring large numbers on a quantum computer and quantum key distribution (QKD) (developed originally by Charles Bennett and Giles Brassard in 1984). Shor's algorithm, of course, has implications for public-key cryptography.
It's important to note that a) QKD does NOT solve what Shor's factoring algorithm broke, and b) key exchange/distribution is not the biggest security problem we have on the net (it might not even make the top ten). The primary use of public-key cryptosystems is distributed authentication. The primary use of QKD will be key generation/exchange. They serve very different roles in the Internet. A secure Internet communication consists of several distinct parts - authentication of the parties involved, generation of a secure session key, and then the data encryption itself.
Your Internet Explorer, Mozilla, or Firefox comes with Verisign's public key built in. This allows you to check that yes, indeed, Verisign signed the key that says it came from Amazon.com, and therefore you can believe that you are truly connected to Amazon. This is what we call authentication.
After this authentication step, you must create a shared, secret key to continue the communication. That key exchange is often done via Diffie-Hellman key exchange, which allows parts of the communication to be done in the open (unencrypted). D-H by itself is vulnerable to a man-in-the-middle attack, so it is used with some form of authentication to create a shared, authenticated secret key for your session.
The difficulty of cracking a Diffie-Hellman exchange is, I believe, founded on the difficulty of the discrete logarithm problem, and hence is vulnerable to Shor. HOWEVER, D-H is not the only classical method of doing key exchange. If you already have a shared secret, it is easy to negotiate a key without D-H. I used to work for a startup that did IPSEC gateways (though I am FAR FAR from an expert on this), and I believe most of our customers did their authentication via pre-shared secret key. Though the IKE (Internet Key Exchange) built on that secret key authentication does use D-H, that can be fixed (by modifying the RFCs); when you have a pre-shared secret, you can easily use it to encrypt a new key chosen by one of the parties.
So Shor breaks public-key (PK) crypto. What are the implications? Without PK, our key management headaches get worse, but there is (almost?) nothing we can do with public key we can't do with private key. The scalability of authentication servers is problematic and the number of keys you keep around on your systems grows, but in practice probably not nearly as much as people fear, since most people really only connect securely to a few places, anyway.
Okay, so can QKD take over the role filled by PK crypto? After all, the physicists talk about it being impossible to break because of the physics. Nope, and for a simple reason: QKD still requires a classically-authenticated channel; that is, it still requires the functionality that Shor broke! It doesn't fix Shor. But, if you have authentication you can trust today, regardless of whether it is PK or not, you're set; the authentication information is not used in the generation of the key used to encrypt the data.
I sat in on a talk on QKD by Todd Brun at ISI's div7, in front of thirty or forty of the planet's best networking researchers. They immediately started jumping up and down and stamping their feet about man-in-the-middle attacks and the need for the authenticated channel. Todd remarked something to the effect that the physicists, if they are aware of the problem at all, are much less cognizant of its operational implications. Paterson et al. wrote a nice paper on the implications of QKD, where much of what I've written here is discussed, and probably more coherently.
QKD's place is for the truly, truly paranoid: people who believe that their traffic is being snooped today, and that classical, symmetric crypto (3DES, AES) will fall to either mathematical advances or some further quantum computing advance sometime in the distant future, and don't want their traffic from TODAY read by somebody half a century from now. Authentication that is good enough TODAY, plus QKD, is good enough to guarantee that your data is safe for all time (modulo breakins/breakdowns at the end points).
In that case, your only operational choice is to use the QKD-generated key as a one-time pad, and discard; if you're really paranoid enough to want the QKD, don't use it to just generate keys for use with a symmetric crypto protocol. That means you need very high QKD bit-generation rates, and most are still in the kilobits/second. Some experiments have been done in the low megabits/sec., but that's pre-filtering, I believe, which costs you at least one order of magnitude in performance. I was at a talk by Tomita-san, one of NEC's QKD experts, just a couple of days ago, and he was talking about an experimental setup over 16km of real-world fiber on telephone poles that did QKD at an average rate of 13 kilobits/second. The most advanced engineering demonstration is the BBN/Harvard/Boston U. network, see some of Chip Elliott's papers.
I arrived at the party a little late to get in on the recent thread at Dave Bacon's Quantum Pontiff blog, but I did throw in my two cents anyway, see the comments here. There was also some discussion on Dave Farber's IP list, see here and search for quantum or Armstrong.
There is a lot of confusion about the relationship between two of the most famous results in quantum information theory: Shor's algorithm for factoring large numbers on a quantum computer and quantum key distribution (QKD) (developed originally by Charles Bennett and Giles Brassard in 1984). Shor's algorithm, of course, has implications for public-key cryptography.
It's important to note that a) QKD does NOT solve what Shor's factoring algorithm broke, and b) key exchange/distribution is not the biggest security problem we have on the net (it might not even make the top ten). The primary use of public-key cryptosystems is distributed authentication. The primary use of QKD will be key generation/exchange. They serve very different roles in the Internet. A secure Internet communication consists of several distinct parts - authentication of the parties involved, generation of a secure session key, and then the data encryption itself.
Your Internet Explorer, Mozilla, or Firefox comes with Verisign's public key built in. This allows you to check that yes, indeed, Verisign signed the key that says it came from Amazon.com, and therefore you can believe that you are truly connected to Amazon. This is what we call authentication.
After this authentication step, you must create a shared, secret key to continue the communication. That key exchange is often done via Diffie-Hellman key exchange, which allows parts of the communication to be done in the open (unencrypted). D-H by itself is vulnerable to a man-in-the-middle attack, so it is used with some form of authentication to create a shared, authenticated secret key for your session.
The difficulty of cracking a Diffie-Hellman exchange is, I believe, founded on the difficulty of the discrete logarithm problem, and hence is vulnerable to Shor. HOWEVER, D-H is not the only classical method of doing key exchange. If you already have a shared secret, it is easy to negotiate a key without D-H. I used to work for a startup that did IPSEC gateways (though I am FAR FAR from an expert on this), and I believe most of our customers did their authentication via pre-shared secret key. Though the IKE (Internet Key Exchange) built on that secret key authentication does use D-H, that can be fixed (by modifying the RFCs); when you have a pre-shared secret, you can easily use it to encrypt a new key chosen by one of the parties.
So Shor breaks public-key (PK) crypto. What are the implications? Without PK, our key management headaches get worse, but there is (almost?) nothing we can do with public key we can't do with private key. The scalability of authentication servers is problematic and the number of keys you keep around on your systems grows, but in practice probably not nearly as much as people fear, since most people really only connect securely to a few places, anyway.
Okay, so can QKD take over the role filled by PK crypto? After all, the physicists talk about it being impossible to break because of the physics. Nope, and for a simple reason: QKD still requires a classically-authenticated channel; that is, it still requires the functionality that Shor broke! It doesn't fix Shor. But, if you have authentication you can trust today, regardless of whether it is PK or not, you're set; the authentication information is not used in the generation of the key used to encrypt the data.
I sat in on a talk on QKD by Todd Brun at ISI's div7, in front of thirty or forty of the planet's best networking researchers. They immediately started jumping up and down and stamping their feet about man-in-the-middle attacks and the need for the authenticated channel. Todd remarked something to the effect that the physicists, if they are aware of the problem at all, are much less cognizant of its operational implications. Paterson et al. wrote a nice paper on the implications of QKD, where much of what I've written here is discussed, and probably more coherently.
QKD's place is for the truly, truly paranoid: people who believe that their traffic is being snooped today, and that classical, symmetric crypto (3DES, AES) will fall to either mathematical advances or some further quantum computing advance sometime in the distant future, and don't want their traffic from TODAY read by somebody half a century from now. Authentication that is good enough TODAY, plus QKD, is good enough to guarantee that your data is safe for all time (modulo breakins/breakdowns at the end points).
In that case, your only operational choice is to use the QKD-generated key as a one-time pad, and discard; if you're really paranoid enough to want the QKD, don't use it to just generate keys for use with a symmetric crypto protocol. That means you need very high QKD bit-generation rates, and most are still in the kilobits/second. Some experiments have been done in the low megabits/sec., but that's pre-filtering, I believe, which costs you at least one order of magnitude in performance. I was at a talk by Tomita-san, one of NEC's QKD experts, just a couple of days ago, and he was talking about an experimental setup over 16km of real-world fiber on telephone poles that did QKD at an average rate of 13 kilobits/second. The most advanced engineering demonstration is the BBN/Harvard/Boston U. network, see some of Chip Elliott's papers.
I arrived at the party a little late to get in on the recent thread at Dave Bacon's Quantum Pontiff blog, but I did throw in my two cents anyway, see the comments here. There was also some discussion on Dave Farber's IP list, see here and search for quantum or Armstrong.
Friday, September 23, 2005
measurement order in cluster states
I should have included a link to this paper by Michael Nielsen in my previous post. It's a more introductory paper, perhaps easier to follow. It also includes a review of the quantum circuit model that's good.
I wanted to discuss measurement order more in the last post, but it had gotten too long. Somewhere in your cluster state are qubits that are your "output" qubits. If you've simply followed the most straightforward method of mapping your circuit to the cluster state, they will be on the right-hand edge.
A fascinating fact: your output qubits are among the first to be measured! They go down in the first round, and you get back the answer to your computation. Viola! Done in one time step!
Well, not quite. The numbers you got back are related to the answer you want, but you don't yet know how they are related. Essentially, what you have is the answer, but encrypted. As you perform other measurements, you learn more information. You keep that data, and perform various bit flips on that data based on measurement outcomes. Eventually, your answer is "decrypted".
I wonder, idly, if you could use this as a form of quantum network security. Start with a big cluster state, send half to your partner. Now neither of you can do anything without the other. Probably theoretically possible, but not practically interesting.
I wanted to discuss measurement order more in the last post, but it had gotten too long. Somewhere in your cluster state are qubits that are your "output" qubits. If you've simply followed the most straightforward method of mapping your circuit to the cluster state, they will be on the right-hand edge.
A fascinating fact: your output qubits are among the first to be measured! They go down in the first round, and you get back the answer to your computation. Viola! Done in one time step!
Well, not quite. The numbers you got back are related to the answer you want, but you don't yet know how they are related. Essentially, what you have is the answer, but encrypted. As you perform other measurements, you learn more information. You keep that data, and perform various bit flips on that data based on measurement outcomes. Eventually, your answer is "decrypted".
I wonder, idly, if you could use this as a form of quantum network security. Start with a big cluster state, send half to your partner. Now neither of you can do anything without the other. Probably theoretically possible, but not practically interesting.
Thursday, September 22, 2005
Half Moon Bay: Mayumi's blog
Mayumi is also blogging these days. If you can't read Japanese, you won't follow the text, but she's posting pictures of the girls, which you might enjoy. Her blog is here. At the bottom of the page is a calendar with links to dates she has blog entries. You'll just have to skip around to find the pictures.
I really should add pictures of the girls to the web somewhere myself...
I really should add pictures of the girls to the web somewhere myself...
cluster state computing
David Deutsch, one of the preeminent quantum computing theorists, has suggested on his blog that recent advances in cluster state computing mean that it might be possible to actually build a quantum computer within the next few years. See here and here. I have studied cluster state computing a little (n.b.: this is COMPLETELY DIFFERENT from classical cluster computing), and I know one thing for sure:
I haven't the FOGGIEST notion how to build a machine to run such a computation.
Deutsch seems to think that this paper by Lim et al. is a serious, practical proposal. And, it happens to be, essentially, a form of quantum multicomputer, which is my thesis topic, so I'm very interested in this. But, before we can decide how practical Lim's proposal is, we need to know at least a little bit about cluster state computing.
Be warned: cluster state computing is mathematically difficult stuff, and even more important, a real mind-bender of an idea. It is important, though, and I think the basic idea can be comprehended without following the math, so I'm going to try to explain it. One particularly comprehensive paper on it is this one, but it's rough going. A better first step might be this one. Both of these are by the originators of the concept, Raussendorf and Briegel, and their collaborator Browne (we'll call them RBB). They sometimes call cluster state computing the "one-way quantum computer" and abbreviate it as QCc, a notation we'll adopt. Even if you follow little of the text and none of the mathematics, checking out their diagrams in those papers might be helpful, since I have none on this blog. There are many papers on QCc, including how to do fault-tolerant QCc; I have read only a few, and won't go into details here.
Okay, my totally inept attempt to explain a little about it, in layman's terms:
If you know how to build and program a classical computer, how to design circuits, you can use that knowledge with the "standard" (circuit-based) model of quantum computation. Mathematical physicists often deal more abstractly in the actual Hamiltonians involved, especially when they want to directly simulate another quantum system, rather than run what you and I think of as an "algorithm". But you can stick with the circuit model pretty comfortably for most purposes, and that's how I've done my work on e.g. how to do integeer arithmetic on a quantum computer. But there's a third way: cluster state computing.
If the circuit model is C or assembly language for a quantum computer, then QCc is Prolog. In QCc, you don't so much tell the computer what to do as you make statements about conditions the state of the computer fulfills.
Cluster state computation is "build a huge entangled state, then selectively measure some of the connections, and magically the state transforms to the result you're looking for". That's an egregious simplification, but it's the basic idea. It has been heralded, with good reason, as the biggest theoretical revolution in quantum computing in recent years.
I think the theorists are attracted by totally new paradigm (which is a wonderful new way to think - computation carried out strictly by measurement!). It is also supposed to open up entirely new avenues of thought and new ways to "program" a quantum computer. But let's stick to one particular path - how to map the circuits we know to QCc.
For QCc, you start with a set of physical qubits that are in a 2-D grid (logically or physically) and can connect to their Manhattan neighbors. You initialize them, then perform some local operations that entangle small groups into a specific state called the cluster state. You then probabilistically connect those small groups together to make larger groups, retrying until it works (it's probabilistic, but we know when it works and when it doesn't, so we can just keep retrying until it does). Eventually, your entire machine is in one VERY large entangled state. The work up to this point is independent of the computation (circuit or algorithm) you're going to execute - you don't need to know anything but how big a cluster state to build.
Now back up for a second. Those circuits we're talking about (for some examples, see my arithmetic page (which is out of date these days, but anyway...)) are drawn using horizontal lines and vertical line segments connecting some of those lines in particular patterns. Each line represents a qubit, and the vertical line segments are gates being executed on the connected qubits. Time flows left to right. The physical resources you need are the vertical axis (the number of lines) and the time you need is the horizontal axis. (It's also worth mentioning, if you're delving into the literature, that a circuit is often called a "network". This is network in the sense that you create a netlist when doing circuit design (VLSI or PCB layout), not network in the Internet sense. There is research (and even products already) in the quantum long-distance network sense, but that's not what we're talking about here.)
To turn a circuit into a cluster state computation, we are going to unroll the computation and lay it out flat on a large cluster state. The physically-laid out cluster state will look much like the complete circuit diagram, instantiated all at once. To start with, our cluster state is a featureless 2-D grid. The derivation of the rules for mapping a circuit to it is difficult, but their application is straightforward once you understand them. First, you cut out a number of the qubits, creating holes in the grid. This cutting is done by measuring those qubits along the z axis (recall that a single qubit state can be thought of as a point anywhere on the unit sphere - a unit vector - and that measuring the qubit along a particular axis forces the qubit into a state aligned along that axis in either the positive or negative direction).
At this point, we have a structure that is partially adapted to our planned circuit, but we haven't yet applied any of the gates. A "gate" in QCc is nothing but the measurement of a particular pattern of nearby qubits along a specific set of axes (that's why this is also sometimes referred to as "measurement-based computing"). The choice of which qubits to measure and along which axes will determine what gate is effectively executed.
So now we have a plan - we know, roughly, what measurements we are going to perform on which qubits and how that will get us where we want to go. Next question: in what order do we apply those measurements? Ah, that's where the magic of QCc really shines. You might intuitively think that we more or less follow the circuit, starting from the left, applying the measurements to effect the gates in more or less the order they appear in the circuit. Nope!
Some of the possible quantum gates fall into what is known as the Clifford group. This includes the control-NOT (CNOT) gate and a few single-qubit rotations such as NOT and Hadamard. It does not include the CCNOT (control-control NOT, or Toffoli) gate. All of the gates in your circuit that are in the Clifford group can be executed at the same time! That is, if your circuit consists of only Clifford group gates, the execution of your entire circuit takes one time step, regardless of the apparent dependencies among gates! This is one of the most exciting features of cluster state computing. We have just traded space for time in a way that should make any parallel-computing guru green with envy.
Ah, but there's a catch: the non-Clifford-group gates. We need the Toffoli gate to run addition, and there are non-Clifford-group gates in the quantum Fourier transform, as well. How do those work? Well, it turns out that the choice of which measurements to make (the choice of measurement axis, not which qubit to measure) depends on the results of previous measurements. It turns out that they become dependent in a way that has some relationship to the original circuit, but is not identical. For both the QFT and addition, the number of timesteps winds up being N for an N-bit computation. To quote RBB, "the temporal axis is converted into an additional spatial axis. The temporal axis in a QCc computation emerges anew."
For a Vedral-Barenco-Ekert (VBE) carry-ripple adder, QCc requires about 100x as many qubits as does the direct circuit implementation. However, it might be faster, depending on the relative difficulty of preparing the cluster state and making single-qubit measurements for the QCc versus the cost of Toffoli gates for the circuit implementation. This is a technology-dependent question.
Moreover, the cluster states are HUGE, requiring an entangled state that is on the order of the total number of GATES, not qubits, you would have in the circuit version of the problem. This is not practical, so you have to figure out how to buffer the state you need on a rolling basis with limited physical resources. This is understood, though I'm not familiar with the details, so that will have to wait for another time.
The theorists believe that QCc opens up new paths to finding quantum algorithms. So far, though, what is best understood is how to map the known circuits to QCc, and there, as we have seen, QCc's advantages are somewhat muted.
This brings us back to where we started - the Lim et al. proposal to implement a distributed cluster-state computer. But this posting has already gotten long, and I'm not through digesting the Lim paper yet, so it will also have to wait for another time.
Important theoretical advance? Heck, yeah. Faster path to real implementations? I'm not sure, but personally I kind of doubt it.
Of course, I hope to be part of the team that proves myself either right or wrong in short order :-).
I haven't the FOGGIEST notion how to build a machine to run such a computation.
Deutsch seems to think that this paper by Lim et al. is a serious, practical proposal. And, it happens to be, essentially, a form of quantum multicomputer, which is my thesis topic, so I'm very interested in this. But, before we can decide how practical Lim's proposal is, we need to know at least a little bit about cluster state computing.
Be warned: cluster state computing is mathematically difficult stuff, and even more important, a real mind-bender of an idea. It is important, though, and I think the basic idea can be comprehended without following the math, so I'm going to try to explain it. One particularly comprehensive paper on it is this one, but it's rough going. A better first step might be this one. Both of these are by the originators of the concept, Raussendorf and Briegel, and their collaborator Browne (we'll call them RBB). They sometimes call cluster state computing the "one-way quantum computer" and abbreviate it as QCc, a notation we'll adopt. Even if you follow little of the text and none of the mathematics, checking out their diagrams in those papers might be helpful, since I have none on this blog. There are many papers on QCc, including how to do fault-tolerant QCc; I have read only a few, and won't go into details here.
Okay, my totally inept attempt to explain a little about it, in layman's terms:
If you know how to build and program a classical computer, how to design circuits, you can use that knowledge with the "standard" (circuit-based) model of quantum computation. Mathematical physicists often deal more abstractly in the actual Hamiltonians involved, especially when they want to directly simulate another quantum system, rather than run what you and I think of as an "algorithm". But you can stick with the circuit model pretty comfortably for most purposes, and that's how I've done my work on e.g. how to do integeer arithmetic on a quantum computer. But there's a third way: cluster state computing.
If the circuit model is C or assembly language for a quantum computer, then QCc is Prolog. In QCc, you don't so much tell the computer what to do as you make statements about conditions the state of the computer fulfills.
Cluster state computation is "build a huge entangled state, then selectively measure some of the connections, and magically the state transforms to the result you're looking for". That's an egregious simplification, but it's the basic idea. It has been heralded, with good reason, as the biggest theoretical revolution in quantum computing in recent years.
I think the theorists are attracted by totally new paradigm (which is a wonderful new way to think - computation carried out strictly by measurement!). It is also supposed to open up entirely new avenues of thought and new ways to "program" a quantum computer. But let's stick to one particular path - how to map the circuits we know to QCc.
For QCc, you start with a set of physical qubits that are in a 2-D grid (logically or physically) and can connect to their Manhattan neighbors. You initialize them, then perform some local operations that entangle small groups into a specific state called the cluster state. You then probabilistically connect those small groups together to make larger groups, retrying until it works (it's probabilistic, but we know when it works and when it doesn't, so we can just keep retrying until it does). Eventually, your entire machine is in one VERY large entangled state. The work up to this point is independent of the computation (circuit or algorithm) you're going to execute - you don't need to know anything but how big a cluster state to build.
Now back up for a second. Those circuits we're talking about (for some examples, see my arithmetic page (which is out of date these days, but anyway...)) are drawn using horizontal lines and vertical line segments connecting some of those lines in particular patterns. Each line represents a qubit, and the vertical line segments are gates being executed on the connected qubits. Time flows left to right. The physical resources you need are the vertical axis (the number of lines) and the time you need is the horizontal axis. (It's also worth mentioning, if you're delving into the literature, that a circuit is often called a "network". This is network in the sense that you create a netlist when doing circuit design (VLSI or PCB layout), not network in the Internet sense. There is research (and even products already) in the quantum long-distance network sense, but that's not what we're talking about here.)
To turn a circuit into a cluster state computation, we are going to unroll the computation and lay it out flat on a large cluster state. The physically-laid out cluster state will look much like the complete circuit diagram, instantiated all at once. To start with, our cluster state is a featureless 2-D grid. The derivation of the rules for mapping a circuit to it is difficult, but their application is straightforward once you understand them. First, you cut out a number of the qubits, creating holes in the grid. This cutting is done by measuring those qubits along the z axis (recall that a single qubit state can be thought of as a point anywhere on the unit sphere - a unit vector - and that measuring the qubit along a particular axis forces the qubit into a state aligned along that axis in either the positive or negative direction).
At this point, we have a structure that is partially adapted to our planned circuit, but we haven't yet applied any of the gates. A "gate" in QCc is nothing but the measurement of a particular pattern of nearby qubits along a specific set of axes (that's why this is also sometimes referred to as "measurement-based computing"). The choice of which qubits to measure and along which axes will determine what gate is effectively executed.
So now we have a plan - we know, roughly, what measurements we are going to perform on which qubits and how that will get us where we want to go. Next question: in what order do we apply those measurements? Ah, that's where the magic of QCc really shines. You might intuitively think that we more or less follow the circuit, starting from the left, applying the measurements to effect the gates in more or less the order they appear in the circuit. Nope!
Some of the possible quantum gates fall into what is known as the Clifford group. This includes the control-NOT (CNOT) gate and a few single-qubit rotations such as NOT and Hadamard. It does not include the CCNOT (control-control NOT, or Toffoli) gate. All of the gates in your circuit that are in the Clifford group can be executed at the same time! That is, if your circuit consists of only Clifford group gates, the execution of your entire circuit takes one time step, regardless of the apparent dependencies among gates! This is one of the most exciting features of cluster state computing. We have just traded space for time in a way that should make any parallel-computing guru green with envy.
Ah, but there's a catch: the non-Clifford-group gates. We need the Toffoli gate to run addition, and there are non-Clifford-group gates in the quantum Fourier transform, as well. How do those work? Well, it turns out that the choice of which measurements to make (the choice of measurement axis, not which qubit to measure) depends on the results of previous measurements. It turns out that they become dependent in a way that has some relationship to the original circuit, but is not identical. For both the QFT and addition, the number of timesteps winds up being N for an N-bit computation. To quote RBB, "the temporal axis is converted into an additional spatial axis. The temporal axis in a QCc computation emerges anew."
For a Vedral-Barenco-Ekert (VBE) carry-ripple adder, QCc requires about 100x as many qubits as does the direct circuit implementation. However, it might be faster, depending on the relative difficulty of preparing the cluster state and making single-qubit measurements for the QCc versus the cost of Toffoli gates for the circuit implementation. This is a technology-dependent question.
Moreover, the cluster states are HUGE, requiring an entangled state that is on the order of the total number of GATES, not qubits, you would have in the circuit version of the problem. This is not practical, so you have to figure out how to buffer the state you need on a rolling basis with limited physical resources. This is understood, though I'm not familiar with the details, so that will have to wait for another time.
The theorists believe that QCc opens up new paths to finding quantum algorithms. So far, though, what is best understood is how to map the known circuits to QCc, and there, as we have seen, QCc's advantages are somewhat muted.
This brings us back to where we started - the Lim et al. proposal to implement a distributed cluster-state computer. But this posting has already gotten long, and I'm not through digesting the Lim paper yet, so it will also have to wait for another time.
Important theoretical advance? Heck, yeah. Faster path to real implementations? I'm not sure, but personally I kind of doubt it.
Of course, I hope to be part of the team that proves myself either right or wrong in short order :-).
Monday, February 21, 2005
1.0.5: hyperbolic spaces and the Internet
One of the most mind-opening talks I've ever been to was Tamara Munzner's talk at SIGGRAPH '95. In hyperbolic space, as you get closer to an object, it gets larger. Not just appears larger, gets larger. This is incredibly useful for visualizing very large networks.
Tamara kind of dropped off my radar for a few years, but if you look at her software page, there is cool, related stuff there, including an SGI tool for managing web content.
Question for Bill and Suz: does anybody in network management use this stuff, or related ideas?
Question for Wook: can we use this somehow to visualize the state of a quantum computer? This would be highly non-representational, I think, but so is the Bloch sphere (see this text description from Mathworld and this GUI and animation).
Tamara kind of dropped off my radar for a few years, but if you look at her software page, there is cool, related stuff there, including an SGI tool for managing web content.
Question for Bill and Suz: does anybody in network management use this stuff, or related ideas?
Question for Wook: can we use this somehow to visualize the state of a quantum computer? This would be highly non-representational, I think, but so is the Bloch sphere (see this text description from Mathworld and this GUI and animation).
Sunday, February 20, 2005
Qubit News, Qulink and the Quantum Pontiff
That last bit, on the Deloitte report, I cribbed from Qubit News, an excellent source of info on upcoming conferences and whatnot.
For what's up in the Kanto area (around Tokyo), see Kae Nemoto's Qulink.
A chattier resource is Dave Bacon's Quantum Pontiff.
For what's up in the Kanto area (around Tokyo), see Kae Nemoto's Qulink.
A chattier resource is Dave Bacon's Quantum Pontiff.
Deloitte on quantum computing
Deloitte has published a report titled, "TMT Trends: Technology Predictions 2005", and it includes quantum computing. PDF is here; they kind of buried the link.)
It's a tad breathless in its assessment, but they conclude in part, "Companies must start giving serious thought to the implications of quantum computing technology...Even during the development phase, the by-products of quantum computing research will have a significant impact on every aspect of computer technology...And when someone, somewhere produces the first commercially viable quantum computer - which is only a matter of time - it will change everything."
It's a tad breathless in its assessment, but they conclude in part, "Companies must start giving serious thought to the implications of quantum computing technology...Even during the development phase, the by-products of quantum computing research will have a significant impact on every aspect of computer technology...And when someone, somewhere produces the first commercially viable quantum computer - which is only a matter of time - it will change everything."
new single-photon source?
A Caltech press release from the Harry Atwater group touts a nanocrystal-based approach to creating photons in silicon structures, published in Nature Materials. A nanobead's size regulates the frequency of photon created, and the small size also makes it possible to inject single electrons and single holes to make photons one at a time - VERY useful for quantum computing.
The press release doesn't discuss the critical technical details of how accurately we can control the timing of the recombination of the electron and hole to create a photon - we want this in attoseconds, if possible, femtoseconds for sure. The other big question is how the direction of emission can be controlled.
I haven't read the actual paper yet, am looking forward to it...
The press release doesn't discuss the critical technical details of how accurately we can control the timing of the recombination of the electron and hole to create a photon - we want this in attoseconds, if possible, femtoseconds for sure. The other big question is how the direction of emission can be controlled.
I haven't read the actual paper yet, am looking forward to it...
Wednesday, January 05, 2005
1.0.4: A new analogy
It seems we're still having some trouble with the fundamental idea that a quantum register, the data storage part of a quantum computer, doesn't normally hold programs, and can only be looked at under tightly constrained conditions before the computation is complete. Let me try a new analogy:
Quantum computing is like CAM - computer aided manufacturing. Better yet, it's like the computed holograms of Mark Holzbach and company at Zebra Imaging. You have a program that runs on your (classical) computer that controls some physical devices such as lasers that illuminate parts of your output (the hologram, or our quantum register) and create interference patterns on the film or the quantum superposition. When you're done, you "develop" it (measure it, in quantum computing), and then you can look at the result.
The analogy isn't perfect; in a quantum computer, you can look at part of the register and get some information out. This is called taking a partial trace, and is critical for the implementation of quantum error correction. You can also use one or more qubits as control lines for gates, so there is a way to get some conditional behavior. However, at the level we are currently working, this is a very far cry from anything like a stored-program computer.
Link of the day: a table of quantum computer simulators from Julia Wallace. Some date as far back as 1994.
Quantum computing is like CAM - computer aided manufacturing. Better yet, it's like the computed holograms of Mark Holzbach and company at Zebra Imaging. You have a program that runs on your (classical) computer that controls some physical devices such as lasers that illuminate parts of your output (the hologram, or our quantum register) and create interference patterns on the film or the quantum superposition. When you're done, you "develop" it (measure it, in quantum computing), and then you can look at the result.
The analogy isn't perfect; in a quantum computer, you can look at part of the register and get some information out. This is called taking a partial trace, and is critical for the implementation of quantum error correction. You can also use one or more qubits as control lines for gates, so there is a way to get some conditional behavior. However, at the level we are currently working, this is a very far cry from anything like a stored-program computer.
Link of the day: a table of quantum computer simulators from Julia Wallace. Some date as far back as 1994.
Saturday, December 18, 2004
Blogalog 1.0.3: qubits v. quantum gates
There are a ton of interesting thoughts in Wook's latest posting. I think we'll leave the bigger issues of quantum architecture for a later posting, though I'm looking forward to that. In the meantime I'll encourage you to Google on "quantum Turing machine" and noodle on which parts of the TM need to be quantum. For some concrete stuff on where we are with this, see the references from my Aqua recommendations page and my arithmetic page.
One bit of terminology we ought to straighten out. There are two types of qubits, "flying qubits" and static ones. Flying qubits are typically something like photons. They pass through devices that cause computation, something like data values pass through gates in a classical circuit. Many quantum computing technologies use static ones, such as quantum dots or the spin of atomic nuclei. In that case, a qubit is like a bit in a register, and the "gates" (often microwave pulses) feel more like instructions to a classical computer architect. The "program" is usually called a quantum circuit in either case.
So, rather than saying that a PDP-8 takes 10k gates for its CPU, the question is, how many bits of storage does it have? A machine that can run a program might want, say, a few kilobytes.
In most quantum computing proposals, an underlying assumption is that all qubits are equal; any qubit storage location can be manipulated in an arbitrary way. It's like they are all bits in a classical register; there is no RAM/register distinction and no "load" instruction. One of the few proposals that separates qubit storage from "action" locations is the scalable ion trap processor from the Wineland group at NIST. See http://qubit.nist.gov/ and the Kielpinski Nature paper. We in the Itoh group have been thinking about how to combine different storage technologies into a larger device, like the difference between cache and RAM. Haven't gotten very far yet.
This has already gotten long, so I'll leave simulation and the qubit flythrough for another posting.
One bit of terminology we ought to straighten out. There are two types of qubits, "flying qubits" and static ones. Flying qubits are typically something like photons. They pass through devices that cause computation, something like data values pass through gates in a classical circuit. Many quantum computing technologies use static ones, such as quantum dots or the spin of atomic nuclei. In that case, a qubit is like a bit in a register, and the "gates" (often microwave pulses) feel more like instructions to a classical computer architect. The "program" is usually called a quantum circuit in either case.
So, rather than saying that a PDP-8 takes 10k gates for its CPU, the question is, how many bits of storage does it have? A machine that can run a program might want, say, a few kilobytes.
In most quantum computing proposals, an underlying assumption is that all qubits are equal; any qubit storage location can be manipulated in an arbitrary way. It's like they are all bits in a classical register; there is no RAM/register distinction and no "load" instruction. One of the few proposals that separates qubit storage from "action" locations is the scalable ion trap processor from the Wineland group at NIST. See http://qubit.nist.gov/ and the Kielpinski Nature paper. We in the Itoh group have been thinking about how to combine different storage technologies into a larger device, like the difference between cache and RAM. Haven't gotten very far yet.
This has already gotten long, so I'll leave simulation and the qubit flythrough for another posting.
Blogalog 1.0.2: Skin
We'll get to the latest questions on quantum computer architecture shortly. Meantime, a CG question:
What's the latest on human skin? I've heard (from you) that it's extremely tough because it's partially translucent; I assume the way it stretches, folds, and wrinkles are tough to get right, too.
What's the scoop? Is anyone making significant progress?
What's the latest on human skin? I've heard (from you) that it's extremely tough because it's partially translucent; I assume the way it stretches, folds, and wrinkles are tough to get right, too.
What's the scoop? Is anyone making significant progress?
Wednesday, December 15, 2004
blogalog on QC (quantum computing) & CG (computer graphics)
Wook and I are going to do a blogalog on quantum computing and computer graphics. He asks stupid questions about the former, I ask stupid questions about the latter, maybe a person or two learns something. Sometimes they'll be low-level questions, but I hope that sometimes they will also be thought-provoking.
All right, first question:
I'm doing some graphics for my quantum computing stuff, and I need to pick the location of the camera and which direction it is pointing in. I want all of my objects to appear at reasonable sizes, and the frame to be mostly full, and nothing to be cut off. My objects (just spheres and some pipes and some floating text) are of a fixed size, but the number and location vary according to the size of the quantum algorithm I'm animating, and the specific quantum computer topology. Often they are in a line, sometimes they are in a 2D grid, later they will be in more complex arrangements.
How do I pick my camera location and pointing direction?
All right, first question:
I'm doing some graphics for my quantum computing stuff, and I need to pick the location of the camera and which direction it is pointing in. I want all of my objects to appear at reasonable sizes, and the frame to be mostly full, and nothing to be cut off. My objects (just spheres and some pipes and some floating text) are of a fixed size, but the number and location vary according to the size of the quantum algorithm I'm animating, and the specific quantum computer topology. Often they are in a line, sometimes they are in a 2D grid, later they will be in more complex arrangements.
How do I pick my camera location and pointing direction?
Subscribe to:
Posts (Atom)