ToN Quantum Paper Online

Our Transactions on Networking paper, "System Design for a Long-Line Quantum Repeater," is now available in final form in the IEEE's Digital Library. Print edition is not due until August 2009. Thanks as always to Thaddeus, Bill and Kae for their hard work on it.

MARA in Infocom!

Congratulations to Yasu Ohara and Shinji Imahori! Yasu's paper (on which Imahori-san and I are coauthors), "MARA: Maximum Alternative Routing Algorithm", was accepted to INFOCOM 2009, one of 282 acceptances out of 1,435 submissions. This work is follow-through on Yasu's Ph.D. thesis, completed and defended in our lab last academic year. It's good work on how to do route calculations to support multipath forwarding in a network.

A trip to Rio for Yasu next April!

New Campus Web Site

For those who aren't allergic to Flash, our campus has a new website for faculty & research profiles. Check it out, let me know what you think.

Tell Me a Story

What he said. Robert Krulwich, you da man.

Now, if only I could write like that...I can't, but sign me up, I'm willing to give it a shot.

Sustainable Sushi

...is largely a hopeless prospect in this country (let alone the rising appetite for it world-wide, especially in China) for the foreseeable future, but: the Monterey Bay Aquarium's sustainable sushi guide is a win.

A translation to both Japanese language and Japanese market availability would be a plus...

FWIW, a sushi bar here is actually a reasonable place to take a non-squeamish vegan. At a good place, there are a number of pure vegetable rolls. Not clear how much goodwill you earn with the sushi chef that way, but it's a much better menu bet than a tonkatsu (deep-fried pork) restaurant.

I can't promise perfection, but I can promise to do my best to follow the guide.

Now, how to popularize the ideas here?

Give Us This Day Our Daily Banana

In English, "bread" can be a synonym for "meal" or "food" (and for "money", though that's a later innovation), as evidenced by the line from the Lord's Prayer, "Give us this day our daily bread."

In Japanese, "gohan" is both (cooked) "rice" and "meal": "Gohan wo tabeta?" "[Have you] eaten a meal?" (Transliterated; a more natural rendering would be "Have you eaten?")

An article in a recent issue of Science, talking about bananas, informs me that in Uganda the word for "banana" is the same as the word for "food". Sadly, the article didn't give the word for it, or even name the language (presumably Swahili).

I read the article on the train on the way home yesterday, and when I got home I was dying for a banana. Fortunately, Mayumi had bought bananas. Unfortunately, my girls managed eat all of them before I got home :-).

That's perhaps an allegory for what's happening worldwide: the Cavendish banana, the most common around the world, is under attack by a fungus all over the planet. The plant can be grown only by cloning (it's sterile) and since all the plants are genetically identical, they are all equally susceptible.

Other strains of bananas might be less vulnerable, but are suffering from neglect. (The most fragrant bananas I've ever had were in Nepal, some small variety that smelled of cinnamon.) Let's not let the world's fourth-most-important staple crop (behind rice, wheat and corn) get away from us, people!

guGUttara?

"To google" is now a verb in English (at least, the American (correct) form of the language, not sure about other parts of the diaspora). "He googled it," "I'm googling it now...," "Why don't you google it?" and more.

The same thing is true in Japanese. "Google" in Japanese is "GUUguru" (or "GU-guru"), written in katakana, the syllabary used for "loan" (imported) words, with a long "uu" and the unfortunate but necessary mangling of the pronunciation. (Not that Americans can come close to pronouncing Chinese or even French correctly, but that's not the point here.)

By fortunate coincidence, "-ru" is the common ending for verbs in Japanese, so conjugating it is natural and trivial, but the emphasized syllable changes: "guGUrimasu", "guGUrimashita". You almost never hear the formal form of it, though, you usually hear the informal form "guGUtta" ("googled") or "guGUtte iru" ("am googling/is googling"). Japanese has a verb form (not sure of the technical name in either Japanese or English) for "why don't you..." or "if you...", which usually ends in "-ttara".

And if you don't believe me, guguttara?

ORF: QKD with IPsec

Our campus (Keio's Shonan Fujisawa Campus) just finished our Open Research Forum, the annual two-day big exhibit of students' work. It was a blast, a lot of interesting people show up (including, if I understood him right, the director of "Godzilla versus Hedora", and it's great to see the work being done by students in other "kenkyuukai" (research groups), as well.

At our campus, undergrads, usually, starting in their second year, join the "lab" or kenkyuukai of a professor, and by the end of their four years, I would say that many students have done a third to a half of their total learning in the context of the kenykyuukai. Classes provide breadth and theory, the kenkyuukai provides depth.

My students in the AQUA group integrated IKE, the Internet Key Exchange protocol, with QKD (quantum key distribution), so that traffic between two networks can be encrypted using a key created via QKD. I'll post more about the technical work on it a little later, but thanks to Satoh and especially Nagayama for the hard work on both the implementation and the display.

Thanks to NEC for the loan of the QKD devices! We look forward to continuing to work with you.

Keio: Astronauts, Princes, Emperors, and Postage Stamps!

So, Saturday was the Keio University 150th anniversary ceremony. I didn't get to attend (there were only a few thousand tickets), and I found out about the live webcast after it was over. Oh, well.

I'm told that the Emperor made very nice remarks about the history of Keio.

Prince Charles also dropped by the Mita Campus on his visit to Japan a couple of weeks ago. There is a good photo of him examining a bamboo sword during a kendo demonstration. I heard that his talk was nice, as well.

Just as exciting, to me, was the talk that Akihiko Hoshide gave a few weeks ago. He was on the team that delivered the Kibo Laboratory module to the International Space Station this summer. He also took an aluminum soroban with him, made for him by our engineering department. Oh, Hoshide is a Keio grad -- at least the second to fly in space, after Chiaki Mukai. Hoshide-san gave a great, inspirational talk targeted at kids, and accessible to all ages. It was broadcast over the Internet, and translated into several languages in real time.

More to my surprise, the Japan Post Office has issued a commemorative stamp set. Now I know what I'm getting my great-aunt, the stamp collector, for Christmas.

New Papers

It occurs to me that I'm behind in doing the obligatory paper dance, as our pontiff would say. All from collaborators, one already published and two new submissions:

1. Byung-Soo Choi and Rodney Van Meter,
   Effects of Interaction Distance on Quantum Addition Circuits,
   submitted;
   available from the arXiv as quant-ph:0809.4317.
   


2. Liang Jiang, Jacob M. Taylor, Kae Nemoto, William J. Munro, Rodney Van Meter, and Mikhail D. Lukin,
   Quantum Repeater with Encoding,
   submitted;
   available from the arXiv as quant-ph:0809.3629.
   


3. W. J. Munro, R. Van Meter, Sebastien G. R. Louis, and Kae Nemoto,
   High-Bandwidth Hybrid Quantum Repeater,
   Phys. Rev. Letters 101, 040502, July 2008;
   available from the arXiv as quant-ph:0808.0307.
   Selected for Virtual J. Quantum Inf. 8(8), Aug. 2008.
   
   

More to come in the next couple of months, I hope, on both repeaters and arithmetic circuits; there is also a pile of systems work from last year's QEC conference and other places that needs to be polished up and submitted, as well as a stack of half-completed things...

...ah, for a trio of clones! Then one of us could teach, one could spend time with the family, one could do research, and one would have to do the drudge work. I suppose we'd have to rotate; I love all three of those first topics, but no one would want to be stuck with the paperwork forever :-).

Biden's Travels

I'm not going to get into politics on this blog, but one note: Joe Biden's team released a list of heads of state he has met with.

Now, the team claims the list is incomplete, but as an expat living where I do, there is a conspicuous hole: um, Japan? I realize that prime ministers here change often enough that it's difficult to keep up, but Japan is still the second biggest economy on the planet, and one of the U.S.'s top trading and defense partners.

Has Biden really not met with any Japanese leaders, or is the absence an oversight? It's not that he's shunning East, South, or Southeast Asia; he's met with leaders from almost every Asian country you can name, except Bangladesh and Thailand. Okay, he's allowed to not hit every single one; but still, Japan?

Likewise, another near the top of any U.S. list should be that Neighbor to the North, Canada. Hmm.

No Koike

Well, looks like no woman prime minister this time.

No comment?

I'm a little disappointed that my glamorous new profile photo here hasn't drawn the attention of Paris, Milan and New York runway talent scouts.

I'm also a little surprised by the lack of comments from the peanut gallery.

The Candidate of Change

No, for you myopic Americans, I'm not talking about Obama, McCain, or anyone else on that continent. I'm talking about Yuriko Koike, a candidate for president of the Liberal Democratic Party here in Japan. She has held several cabinet positions, and is fluent in both Arabic and English, having received her degree from Cairo University. She's a bit of a long shot, but is supported by Koizumi, the former prime minister, who is still very popular. And, she has been dubbed the candidate of change, which many people would agree is desirable in Japanese politics.

The LDP's internal presidential election is tomorrow (Monday), Japan time. The rules for that election are apparently variable from election to election, but involve mostly members of parliament, and some local leaders, I believe. Taro Aso is expected to win.

Because the LDP is still the largest and strongest political party here, the person elected president normally becomes prime minister. Could Japan wind up with a woman chief executive before America does? Stay tuned.

Quantum Arithmetic

I get occasional mail from people asking me about quantum arithmetic. I usually point them to the Qwiki page on arithmetic I created a couple of years ago, which is a list of useful papers, rather than an actual technical description.

Most of the papers there are about specific arithmetic circuits, building from binary integer addition to modular exponentiation, and include some examples of actual experimental implementations.

This morning, I ran across some lecture notes by Ekert, Hayden, and Inamori on "Basic concepts in quantum computation," at Quantiki. The notes contain a nice intro to the theory behind reversible, binary, modular arithmetic.

Competitiveness

BusinessWeek asks, "Is the U.S. Losing Its Edge in Tech?"

But their online article doesn't include an obvious link to the actual report from the Economic Intelligence Unit, sponsored by the Business Software Alliance. It's titled, How technology sectors grow: benchmarking IT industry competitiveness 2008", which tells you a little about their mindset.

Both the detailed data and their chosen methodology are interesting, though I haven't had time to digest them yet. The top 21 in their total index:

1. U.S.
2. Taiwan
3. U.K.
4. Sweden
5. Denmark
6. Canada
7. Australia
8. South Korea
9. Singapore
10. Netherlands
11. Switzerland
12. Japan
13. Finland
14. Norway
15. Ireland
16. Israel
17. New Zealand
18. Austria
19. Germany
20. France
21. Hong Kong

India, Russia, and China are 48, 49, and 50.

The disparities in "human capital" and "R&D environment" are interesting.

Even more telling are the drops from last year's index -- Japan fell from 2nd to 12th, South Korea from 3rd to 8th, due at least partly to shifts in their methodology. As always in some ranking system, you can engineer the results to fit your intuition :-).

Happy Anniversary

Today is the twentieth anniversary of the Morris Worm. At the time, I had recently moved from ISI's computing center into the MOSIS Project, giving up my position as a sysadmin and becoming a regular programmer on the research staff.

I did get called back in to help a little, but since we were using VMS, the fix for MOSIS was pretty easy: unplug the network, and go back to work. Other folks I worked with, including Dale Chase, Jim Koda, Tom Wisniewski, had a much rougher day, dealing with several BSD VAXen and a large number of Suns.

No Colbert on Linux, No Olympics on Windows

So, I'm trying to watch "The Colbert Report", which features Flash video, on my Fedora 9 laptop.

No joy. npviewer.bin, the Firefox plugin for Flash video, crashes reliably. A little googling turns up that I'm not the only one with this problem -- it has been The Daily Show's Developers' Blog. (Whine: why is it always me?)

A few weeks ago, I wanted to watch the Olympics in some fashion besides Japanese broadcast. Went to MSNBC.com...dang, Silverlight. I only run Linux on my laptop. Grumble. Dig out the Windows XP laptop I have at work for doing the obligatory Word documents. Download Silverlight. Install. Crashes. Reliably. (Whine: why is it always me?)

Have I mentioned that I hate computers?

Ten Million Bucks to Learn to Program...

...molecules.

Erik Winfree's DNA and Natural Algorithms Group at my alma mater is arguably already the best in the world at programming DNA; they publish in Nature and Science like clockwork. I don't know the U-Dub guys, but I assume they're good, too.

So, over the next few years, I expect marvelous advances. Good luck to them! We'll be watching and waiting.

Internet-connected Windshield Wipers

A couple of days ago, Vint Cerf appeared on The Guardian, talking about the future of the Internet (what else?). He mentioned that "Researchers in Japan recently proposed using data from vehicles' windscreen wipers and embedded GPS receivers to track the movement of weather systems through towns and cities with a precision never before possible. It may seem academic, but understanding the way severe weather, such as a typhoon, moves through a city could save lives."

That's the iCar project, headed by Kei Uehara, here in the Internet Research Lab at Keio's Shonan Fujisawa Campus. The project has been running for more than a decade, and has strong ties to industry groups. Current work includes industry standardization of the privacy aspects of information uploaded by probes attached to vehicles, and the like.

The particular tidbit about the windshield wiper info goes back to about the year 2000, I'm told. It has even been featured in short TV segments about the project.

The WIDE folks are visionaries, I tell ya :-).

Tom Sawyer in Tokyo, via Karachi

Hiya bibliophiles,

I bought an old, red, hardback copy of Tom Sawyer in Jimbocho, the famous used book district of Tokyo, and have been reading it to my nine-year-old daughter. (To my intense delight, she begs me not to stop reading.)



It's undated, and unillustrated, and includes a few typographic mistakes or omissions (such as saying, "See the next page" for some illustration which doesn't exist).

Mine appears to use the same chapter headings as the Random edition, according to Mark West. It does not, btw, say "complete and unabridged" anywhere, but it certainly feels complete.

My guess, based on the age and condition, is that it was printed in the 1920s or 30s. Here's the title page:



It also includes an embossed seal, which I'm guessing is a bookseller's:



Pan-American Commercial, Inc.
Elphinstone Street
Karachi

According to Wikipedia, the name of Elphinstone Street was changed to Zaibunnisa Street in 1970, so presumably my copy passed through Pakistan in the 1960s or earlier, before coming to Japan. Quite a trek for a book.

Thought you would enjoy the tale.

(Yes, I tinkered with the lighting on the second image using Gimp. Apologies for the generally poor image quality; those were taken hand-held in low light. The camera and lens are fine, but I didn't have a tripod available last night, and didn't mess with the in-camera choice of lighting adjustment.)

25th MSST

Don't forget to register for the 25th IEEE Symposium on Massive Storage Systems and Technologies!

This conference series has a long history, and has produced some fascinating discussions, especially about very large datasets (particle physics and the like). This year, the symposium is moving to a different format. See the web site for details.

Boost graph bundle + write_graphviz

I couldn't find a decent example of using the new Boost Graph library "bundle" functionality with write_graphviz, so I created one:

foo.cpp

// first, the standard libraries
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <set>
#include <map>
#include <cmath>
#include <iterator>
#include <vector>
#include <queue>

// boost and other semi-standards should go here
#include <boost/scoped_ptr.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/shared_array.hpp>
#include <boost/scoped_array.hpp>
#include <boost/graph/graphviz.hpp>

#include <sys/times.h>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

using std::string;
using std::vector;
using namespace boost;
using std::ostream;
using std::ofstream;
using std::multiset;
using std::pair;
using std::multimap;
using std::map;

struct City
{
  string name;
  int population;
  vector<int> zipcodes;
};
      
struct Highway
{
  string name;
  double miles;
  int speed_limit;
  int lanes;
  bool divided;
};
      
typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City, Highway> Map;
      
void outputgraph(Map&);

main()
{
        Map map; // load the map
        bool inserted;

        Map::vertex_descriptor v = add_vertex(map);
        Map::edge_descriptor e;

        map[v].name = "Troy";
        map[v].population = 49170;
        map[v].zipcodes.push_back(12180);
        tie(e,inserted) = add_edge(v, v, map);
        if (inserted) {
                map[e].name = "I-87";
                map[e].miles = 10;
                map[e].speed_limit = 65;
                map[e].lanes = 4;
                map[e].divided = true;
        }

        vector<double> distances(num_vertices(map));
        Map::vertex_descriptor from = *vertices(map).first;
        dijkstra_shortest_paths(map, from,
                                weight_map(get(&Highway::miles, map))
                                .distance_map(make_iterator_property_map(distances.begin(),
                                                                         get(vertex_index, map))));
        graph_traits < Map >::vertex_iterator vi, vend;
        for (tie(vi, vend) = vertices(map); vi != vend; ++vi) {
                std::cout << "name " << map[*vi].name <<
                        ", " << "population " << map[*vi].population;
        }
        std::cout << std::endl;

        outputgraph(map);
}

struct my_node_writer {
        // my_node_writer() {}
        my_node_writer(Map& g_) : g (g_) {};
        template <class Vertex>
        void operator()(std::ostream& out, Vertex v) {
                out << " [label=\"" << v << "\"]" << std::endl;
        };
        // bleah.  I can't get references right...
        // according to http://www.knowledgesearch.org/doc/examples.html
        // it should be a reference here, not the type itself.
        // but g++ either barfs, or the program segfaults.
        Map g;
};

struct my_edge_writer {
        my_edge_writer(Map& g_) : g (g_) {};
        template <class Edge>
        void operator()(std::ostream& out, Edge e) {
                // just an example, showing that local options override global
                out << " [color=purple]" << std::endl;
                out << " [label=\"" << e  <<":" << g[e].miles << "\"]" << std::endl;
        };
        Map g;
};

struct my_graph_writer {
        void operator()(std::ostream& out) const {
                out << "graph [bgcolor=lightgrey]" << std::endl;
                out << "node [shape=circle color=blue]" << std::endl;
                // just an example, showing that local options override global
                out << "edge [color=red]" << std::endl;
        }
} myGraphWrite;

void outputgraph(Map& map){
        std::ofstream gout;
        gout.open("graphname.dot");
        write_graphviz(gout,map,my_node_writer(map),my_edge_writer(map),myGraphWrite);
        // std::cout() << "done writing graph" << std::endl;
}

Dr. Bono

Sir Paul David Hewson was at Keio's Mita Campus today, picking up an honorary doctorate for his humanitarian work. He is in town for the TICAD IV conference on African development.

I caught only a few minutes of his talk, but he talked about the new ONE Campaign and about bringing it to Japan. He singled out Tadao Ando and a couple of others by name as artists with a conscience whom he admires. He also talked about how wonderful the young Japanese people are, humble and wanting to help the world (he must have been talking to SFC students :-).

Bono is smart, dedicated, inspired, and inspiring. With leadership like him, and enough inspired young people, we can make the world a better place.

Rikei Banare

Presented without comment, for the moment.

Japan is running out of engineers.

Recruiting Students

At our campus, Ph.D. students are admitted twice a year -- to start in September or in April. Although the official title is the "Graduate School of Media and Governance", we have many high-quality students (and faculty!) working in a wide variety of technical areas, some of which are showcased in the fall each year. There is spectacular work on electric vehicles, bacterial computing, smart fabrics, ubiquitous computing, and on and on.

The Internet Research Lab, of which I'm a part, does a variety of things, including iCar, mobile systems, SOI, and more.

I supervise or co-supervise students in those areas, but I especially focus on:

• Distributed Quantum Computing Systems (Japanese or English)
  
  
  
  • Architectures for quantum multicomputers
  
  
  • Quantum repeaters (physical simulation and especially network protocols and network architectures)
  
  
  • Quantum arithmetic
  
  
  • Entangled Quantum Internet
  
  
  • Quantum computer design tools
  
  
  
  
• All-IP Computer Architecture
  
  
  
  • iSCSI
  
  
  • USB/IP
  
  
  • Caching in wide-area computer systems
  
  
  • IP-based system bus architectures
  
  
  • Security and resource management
  
  
  • Human-centric dynamic system architectures
  
  
  
  

At SFC, recruiting of Ph.D. students is done very carefully, and in a very personal fashion. Prospective students are expected to find a faculty member they wish to work with and discuss possible research plans before completing the application process.

It's already very late to be starting that process if you are interested in starting this September; the application deadline is in just a week or so. But if you, or a student or acquaintance of yours, is interested in studying almost any networking-related topic, or quantum computing systems, drop me a line and let me know.

ASPLOS 2009

The ASPLOS 2009 CFP is out! Full papers due Aug. 7, 2008, conference Mar. 7-11, 2009, in Washington, DC.

Quantum Repeaters in ToN

A few hours ago, I received word that our paper System Design for a Long-Line Quantum Repeater has been accepted to IEEE/ACM Transactions on Networking, which, it could be argued, is the second-most influential venue in the computer networking community. I have updated arXiv:0705.4128v2 [quant-ph] with a paper that closely matches the accepted version.

Ostensibly, the paper presents some simulation results on cavity QED repeaters using our banded purification algorithm for scheduling purification operations. In the bigger picture, I think it points out the importance of scheduling (we picked up a factor of fifty over our prior results) as separate from the actual choice of physical operations for purification. It also provides, to the best of my knowledge, the first attempt to organize the behavior of repeater networks into protocol levels and divisions of responsibility, in the fashion that networking people are accustomed to.

Shor's Algorithm in Danger?

I wasn't going to post about this, planning to just sort of let it slide, but it has appeared on at least one crypto mailing list, and I feel like someone should address it before the meme that Shor's algorithm has been discredited takes root. So, here goes...

A paper titled Operator Imprecision and Scaling of Shor's Algorithm, by Hill and Viamontes, appeared on the arXiv about ten days ago. Naturally, I snapped it up and quickly read it. Here's what I think. Take it with an entire shaker full of salt...

If you want to cut to the chase and keep your workload down, there's a really good reason to postpone reading the paper: it hasn't been refereed yet. If you work in the area, you might care enough to read it anyway (and might even get asked to referee), if you don't, the simplest form of triage is to wait and see what expert opinion says, then decide whether you want to agree with the experts or not :-).

Anyway, in one sentence, my position on Shor's algorithm:

• There are very good reasons for taking a Missouri "show me" attitude toward Shor's algorithm, but this paper probably does not change the arguments, and a variety of people much smarter than me have analyzed the algorithm in more detail and are pretty convinced it's going to work with acceptable scaling.
  

And, a one-sentence summary of the paper:

• Quantum error correction doesn't work.

To believe that Shor's algorithm can't be run in the real world, you have to believe either that the algorithm doesn't really scale, or that quantum error correction doesn't work. (Scott Aaronson reduces the argument further to, "Either the Extended Church-Turing Thesis is false, or quantum mechanics must be modified, or the factoring problem is solvable in classical polynomial time." Personally, I think he's leaving out important real-world cheats, such as "Shor has a bug" and "There was a gotcha in QEC that no one had spotted" and "Noise turned out to be more of a problem than we thought". But, in theory, he's right, and he's a theorist, so there you go :-).)

Taking the concerns in order, Shor first:

I'm not a mathematician, cryptographer, theoretical computer scientist, or physicist; I'm a computer systems guy who happens to be working in quantum computing. I have written a series of papers (including my Ph.D. thesis) on how to implement Shor's algorithm, though I am far from satisfied with the depth of my understanding of the interaction of the algorithm with either noise or systematic errors. See, for example,
my thesis or some of
my
other
papers.

My reasoning for studying Shor's algorithm is the following: I am interested in quantum computer architectures, and I need a well-defined workload. Shor's is the most cleanly defined and potentially important (not to mention famous) of the existing algorithms. Moreover, Shor uses two very important building blocks, arithmetic and the quantum Fourier transform (QFT), that are likely to prove generally valuable, so studying their behavior is useful. I consider myself to have given "provisional assent" to the hypothesis that Shor's algorithm works with reasonable scalability, subject to the caveats in my thesis and other papers.

There have been a number of papers addressing the scalability of Shor's algorithm, and unfortunately, this paper doesn't really seem to discuss any of the other arguments, as presented by Barenco, Fowler, and others. The paper references a few of them, but doesn't really say why their analysis is different from those papers, so it's impossible to thoroughly assess if the authors understand what the arguments are, pro and con.

The success probability of Shor's algorithm is believed to decline with the length of the number being factored. The Barenco and Fowler papers arrive at different conclusions on the scalability of Shor, though both are some variant of sub-exponential (logarithmic or polynomial, actually, if memory serves, though it's been a while since I read the papers). They start from different assumptions about the mathematical relationships of, essentially, the parameters to the algorithm. The focus of both those papers is the behavior of the system with perfect gates but an incompletely-run QFT, the "approximate QFT", which is considered to be the preferred form,
avoiding exponentially-precise gates. The results seem related to the general problem of imperfections and Shor's algorithm, though.

Anyway, on to the paper:

I have read it, but not studied it in major detail yet. I don't know either of the authors personally, but the second author has done good work; he is certainly no dummy.

The argument is pretty straightforward, arguably naive. That doesn't mean it's wrong, but there are a lot of assumptions and simplifications in the work, and they need to be examined carefully.

Essentially, what they have done is a simple simulation of an imperfect inverter and extrapolated from that to the performance of a complete system. They suggest that logical states drift linearly from the desired state, given a certain over-rotation of the physical gates. That is inherently plausible, but I think they have under-estimated the ability of quantum error correction (QEC) to suppress those errors, and they haven't accounted for ordinary noise.
(One would hope that the first author understands the impact of measurement on the system, but it's not clear from the rather terse paper that he does.)

See Sec. 2.3.5 (p. 73 or 56, depending on which numbering you're looking at) of my thesis:
http://arxiv.org/abs/quant-ph/0607065/

I think, if the argument in my thesis is right (which is certainly open to question), that systematic over-rotation is suppressed to O(sin^2(epsilon)) where epsilon is the amount over-rotated by all of the gates.

So, a 1% error in rotation (Pi+2*Pi/100 rotation) would result in
Pi+2*Pi/10000 logical rotation, I think. Then the *second* level of QEC would result in 10^-8 logical error, if I've done it right -- the double-exponential suppression.

A physical over-rotation of 10^-3, then, would be 10^-12 with two layers, if I did that right. Thus, based on this analysis, QEC is capable of suppressing errors quite well.

The argument in my thesis is probably naive, but QEC has a *lot* of work behind it; if you are interested, there are tons of references in my thesis and elsewhere. Moreover, last December there was an entire conference dedicated to the topic.


Returning to Shor:

It's not possible to simulate the system for large enough cases to really confirm the validity of the derived expressions, and we're still a number of years from a system large enough to experimentally prove or disprove the proposition. Personally, I don't think the analysis considering noise, systemic errors, and the approximate QFT is complete yet. Most of the theoreticians are pretty satisfied, but we all know about the difference between theory and practice.


In summary, the paper in question (arXiv:0804.3076) would have broad implications for the ability of quantum computers to maintain state accurately enough to provide real-world acceleration over classical computers. It's a very legitimate concern, which gets raised occasionally by very smart people, and usually ends in a stalemate with the preponderance of quantum information people on the side of "don't worry, QEC works". But it's not yet clear that this paper really pushes the argument forward in either direction. The paper is also not yet refereed, and it will be interesting to see how it changes as a result of any referee's comments.

Useful references:

@Article{barenco:approx-qft,
author = {Adriano Barenco and Artur Ekert and Kalle-Antti Suominen
and P\"aivi T\"orm\"a},
title = {Approximate Quantum {Fourier} Transform and Decoherence},
journal = {Physical Review A},
year = 1996,
volume = 54,
pages = {139--146}
}

@Article{fowler04:_limited-rotation-shor,
author = {Austin G. Fowler and Lloyd C. L. Hollenberg},
title = {Scalability of {Shor's} algorithm with a limited set
of rotation gates},
journal = pra,
year = 2004,
volume = 70,
pages = 032329
}

@ARTICLE{devitt-2006-6,
author = {Simon J. Devitt and Austin G. Fowler and Lloyd C.~L. Hollenberg},
title = {Robustness of Shor's algorithm},
journal = {QUANT.INF.COMP.},
volume = {6},
pages = {616},
url = {http://www.citebase.org/abstract?id=oai:arXiv.org:quant-ph/0408081},
year = {2006}
}

(There are more, including some very early ones from before QEC was invented. Homework for the interested reader.)

Anyway, I hope this at least short-circuits any rush to burn Peter Shor in effigy. He's way too smart and sweet for that.

Congrats, Inaba-san!

Inaba-san, from our lab (specifically, Auto-ID Lab Japan) won Best Paper at IEEE International Conference on RFID 2008.

Moore's Law: Moving the Goalposts?

This posting at NextBigFuture has a fantastic set of slides from Intel about the "long" run, up to 2029 (which will still be before I retire, even optimistically).

There is a lot of material for thought in there, but the big picture is that they are shooting for a million-fold improvement in FLOPS applied to a single problem by 2029, to about a zettaFLOPS, 10^21 FLOPS. I haven't been through the numbers yet, but that seems plausible if you postulate a 1000x improvement in VLSI density (which is around the upper bound where you're building out of individual atoms), one to two orders of magnitude improvement in clock cycle, and make up the rest in increasing parallelism. Overall, it seems to be about the upper bound postulated by deBenedictis, but a detailed check (of both) is in order.

As the article notes, communication is the big deal, all throughout the system. I refer to it as, quite directly, a problem in special relativity. Networks exist both inside and outside the chip, making the physical boundary almost meaningless. This is part of what we are researching as an "All-IP Computer" here in the Murai Lab. (Sorry, the web pages are undergoing revision right now, and you might run into some rough spots; noticeably, the All-IP project doesn't have a web page at the moment...)

At any rate, Intel seems intent on keeping the goalposts as far away as possible, and continuing to grind downfield, a few yards at a time, so that progress over years is astonishing. Leapfrogging their progress is probably impossible, but I hope to be sitting by the side of the road (to mix a few metaphors) with a road sign pointing the way to some interesting areas when they get to atomic and quantum levels...

New Japanese Ambassador

The Japan Times reported today that Ichiro Fujisaki has been appointed to be the new ambassador from Japan to the United States, taking over from Ryozo Kato, who has been there six years.

At a faculty party this evening, I chatted with two faculty members who know Fujisaki-san personally. I'm told that he is a Keio graduate. Although he seems to (currently) have a low profile in the press, his resume is impressive, and includes time in Geneva and Washington since joining the Foreign Ministry in 1969.

Ion Trap Toffoli Gate

Whoo-hoo, an interesting looking paper from Reiner Blatt's group:

Realization of the quantum Toffoli gate with trapped ions.

Start of the Year

The new school year effectively starts today, though classes don't start for another week.

One of the first items on the agenda: searching for new members of your "circle", if you're a student. It's the equivalent of freshman rush at many colleges, or "Rotation" at Caltech, except that it's centered on particular activities.

So this week, there will be students packing the quad, wearing American football uniforms (complete with pads), karate gi, cheerleader uniforms, kendo getups, anything you can name. There will be concerts by the many music groups, frisbees flying overhead, many fliers handed out. And, as you can see, the sailplane flying club (and the race car club and yachting club) will parade their toys around for people to ooh and aah over. (The young man holding the wing is one of my students.)

It's an exuberant time, full of the enthusiasm of youth. I love it.

In a Japanese university (and, I think, high school), there are no "tryouts" for the basketball team. Anyone can join. So, the basketball team might have a hundred members. The difference is whether you're good enough to get picked to suit up for the actual games, and, when you're at the bottom of the heap, whether you're willing to put up with the long practices (and the usual forms of senior/junior reminders that you're at the bottom, carrying bags, fetching water, etc.). Those who don't get to suit up for the games are presumably expected to be in the stands, leading organized cheers. I have no idea how you manage practice for a basketball team with a hundred members...probably "varsity", "JV", and "dregs" have separate practice sessions, I would guess.

Speaking of which, in Japan, flying gliders is a competitive sport. The Keio team this year took second in the nationals, losing out to perpetual rival Waseda. Dang. I think we won the championship last year...

Ueno

Kamakura Cherry Blossoms in the Rain

Graduation!

Today was graduation for the graduate school (the undergrads had theirs earlier in the week). This evening, Murai Lab and Tokuda Lab had a shared party for all our graduates. Congratulations to everyone, but especially to the seven newly-minted Ph.D.s:

• funya
  
• kwkt
  
• yasu
  
• ako
  
• mitsuya
  
• hitomi
  
• yoko
  

We're all extremely proud of you (though I had little to do with the success of most of you, having been here only a year). We have an extraordinary variety of Internet-related theses this year, covering the gamut from "soft" uses of technology to "hard-core" networking: one on preservation of anonymity in medical systems, one on distance learning, one on mobile networking, one on RFID, one on improving the robustness of the packet forwarding plane of the Internet through appropriate tweaks to the routing protocols coupled with a mechanism for path selection...I'll try to post links to the theses later...

Apologies for the absolutely terrible pictures, taken with my keitai (cell phone) in low light and without the ability to tell how bad they are until I uploaded them. There were many real cameras present, I'm sure there are hundreds of good pictures floating around...

The present from the students to Murai-san was an effects pedal for his guitar, which was of course demonstrated.

For those of you still to come, I'm looking forward to the coming academic year, starting week after next.

Remembering Howard

Howard Gobioff, a prominent storage researcher and early Google employee, died last week at a tragically young age.

Howard was a friend of mine, though we didn't get to see each other as often as I would have liked.

He will be missed.

WIDE Area Director

I was just elected as an Area Director of the WIDE Project. WIDE is Jun Murai's umbrella organization for Internet research, education and operations here in Japan (with tendrils extending through much of Asia, and even the U.S.). Having just been elected, I still have no idea what kind of trouble I've gotten into :-).

WIDE has, I believe, more than 800 active members, about 200 of whom show up for any given WIDE Camp. WIDE Camps happen twice a year, and we are in the spring one right now. Unfortunately, on the shinkansen down here today, it was cloudy, and we couldn't see Mount Fuji. Too bad.

Anyway, it's a two-year term as an AD, and I'm very much looking forward to contributing to the growth and maintenance of WIDE.

NANOARCH

NANOARCH has its call for papers out. Papers are due March 28.

I attended NANOARCH in 2006, and it was intriguing, I'm really glad I went. There are a lot of ideas floating around for what to do when Moore's Law ends, or when we get to the atomic scale for computer architectures. The field is still young, but will become incredibly important in the next decade.

Not sure if I'm going to have a submission or not...

Caveat on the AR5418

A couple of days ago, I posted about success with the AR5418 and the madwifi driver. That initial success was with 802.11a and 802.11g networks.

This morning, I got it working with an 802.11b network, but not with NetworkManager. NetworkManager could see the access point, but for some reason was unable to actually get an IPv4 address via DHCP. I killed the NetworkManager (/etc/init.d/NetworkManager stop), and ran dhclient ath1 by hand (as root, of course), and it had absolutely no problem picking one up. Not sure why yet, but if you're using NetworkManager and having trouble, try it by hand and see what you get.

[root@localhost Desktop]# cd /etc/init.d
[root@localhost init.d]# ./NetworkManager stop
NetworkManager デーモンを停止中:                           [  OK  ]
[root@localhost init.d]# dhclient ath1
Internet Systems Consortium DHCP Client V3.0.6-Fedora
Copyright 2004-2007 Internet Systems Consortium.
All rights reserved.
For info, please visit http://www.isc.org/sw/dhcp/
wifi0: unknown hardware address type 801
wifi0: unknown hardware address type 801
Listening on LPF/ath1/00:19:7d:a:b:c
Sending on   LPF/ath1/00:19:7d:a:b:c
Sending on   Socket/fallback
DHCPDISCOVER on ath1 to 255.255.255.255 port 67 interval 7
DHCPOFFER from 210.x.y.z
DHCPREQUEST on ath1 to 255.255.255.255 port 67
DHCPACK from 210.x.y.z
bound to 10.0.1.3 -- renewal in 1402 seconds.

Hmm, actually, it occurs to me that I have my network at home set up with the same ESSID as the one here, just for simplicity's sake. It's possible that NetworkManager has cached some info (netmask, AP MAC addr, channel, modulation scheme, something) that doesn't match between the two. Worth looking into...

MadWifi, Fedora 8, AR5418 (Lenovo X60)

Okay, the WLAN is working now!

After finding something similar (not exact, as you'll) on the MadWifi forums, and finally figuring out that I needed madwifi-trunk (as distinct from "most recent release"), the instructions here worked like a charm.

It even works with NetworkManager. Haven't tried WEP yet...

This is with kernel-2.6.23.15-137.fc8 and a yum update as of Valentine's Day, with livna enabled as a yum repository.

[rdv@dhcp-148 ~]$ iwconfig
lo        no wireless extensions.

eth0      no wireless extensions.

irda0     no wireless extensions.

wifi0     no wireless extensions.

ath1      IEEE 802.11a  ESSID:"redacted"  Nickname:""
          Mode:Managed  Frequency:5.21 GHz  Access Point: redacted 
          Bit Rate:36 Mb/s   Tx-Power:13 dBm   Sensitivity=1/1  
          Retry:off   RTS thr:off   Fragment thr:off
          Power Management:off
          Link Quality=37/70  Signal level=-59 dBm  Noise level=-96 dBm
          Rx invalid nwid:113352  Rx invalid crypt:0  Rx invalid frag:0
          Tx excessive retries:0  Invalid misc:0   Missed beacon:0

Reversible/Quantum Arithmetic

Just noticed that Qwiki has moved to Stanford, dragging with it the page on quantum arithmetic. (As long as we're talking moving arithmetic pages, mine moved last year, too.)

As a Caltech alum, it saddens me that Hideo has moved. Ah, well, Pasadena's loss, Palo Alto's gain. As long as good research keeps rolling out of his lab, his team's making the world a better place. Good luck, Hideo.

Microcell at Home?

An article in the Feb. 8 Daily Yomiuri, which unfortunately appears not to be online, says that the government is considering rules to allow people to small cell phone base stations into their houses without a license, to improve reception in basements and houses where the signal is weak. My mother-in-law's house could certainly use one for FOMA...

Jazz in Tokyo

I don't get out to hear live music often enough, but I'm excited by the discovery of Tokyo Jazz Site nonetheless. It was profiled in the Japan Times the other day.

I have only a small fraction of the experience of James Catchpole, but I'll put in a plug for the Blue Note anyway. I happen to think that the food is pretty good; dinner of that quality will cost you 4-7,000 yen anywhere in Tokyo, about what it costs you at the Blue Note. Yes, the shows are expensive and the sets short; but the names are top drawer, and hearing oh, say, the late Oscar Peterson cost us $75 a head in New York ten years ago, and he was sold at $100 a head at Yoshi's Oakland a few years ago, so the difference in price doesn't seem as outrageous to me as it otherwise might. Yes, hearing live jazz is expensive, but even at that, the artists and clubs are mostly making a modest living.

Besides, even going out to the second-tier clubs is Tokyo ain't cheap most of the time. Cover charge for people you've never heard of can be 3-4,000 yen at an obscure club, where a mediocre dinner and overpriced drinks still run the tab to 6-8,000 yen a head. Yes, that's a big difference from the 10-12,000 yen you'll spend at the Blue Note, but the jazz and food will be a lot better. Catchpole gets out much more often than I do, and can afford to trade time for money looking for the exciting, obscure players in the good-for-the-money clubs, but I don't want to waste one of my few trips to a club a year on something disappointing.

Of course, now that I know about his web site, I should be able to improve my hit rate and economize at the same time. Looking forward to reading up on it!

Speaking of such things, a little hole in the wall here in Kamakura named Tipitina has bossa nova tonight. Hmm. I'm at home for the evening with my girls, though.

Traffic Monitoring Using Ubiquitous Computing

The most ubiquitous computing device in the world at the moment is probably the cell phone. Certainly it's the most common network connected device in the world, and it's pretty much always on.

One of the dreams of recent years has been to take advantage of that latent capability. Now Nokia and Berkeley are turning cell phones into traffic monitors.

Nice work.

Arithmetic on a Distributed-Memory Quantum Multicomputer

Huzzah, our paper in JETC is now available!

This paper is an extended version of our ISCA paper from 2006, and is also available on the arXiv.

More Snow in Kamakura

...or more pictures of yesterday's snow, anyway. This one is Honkouji. My great-aunt loves jigsaw puzzles, I may see if I can get this one printed onto a puzzle for her.

Doing Science on a Quantum Computer

Last week was The Third Workshop on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2008), held here in Tokyo. One of the invited speakers was Ignacio Cirac.

I asked the following question (first in dinner conversation, then during my presentation):

When will the first Science or Nature paper appear in which the results are calculated on a quantum computer, but the point of the paper is not the quantum computer?

That is, when will a quantum computer do science, rather than be science?

Ignacio answered, "If you include quantum simulations, within five years."

[In quantum simulation, which is something like Feynman's original vision of quantum computers, you set up your device so that it emulates the behavior of a different physical system -- like simulating a set of mechanical oscillators using an RLC circuit.]

Call me an optimist, but I'm with Ignacio.

Maybe we need a LongBet on this...

Snow in Kamakura!

Apparently a light dusting of snow happens most years, but today we're getting a substantial accumulation (15cm or more) of heavy, wet snow.

I used to look at ukiyo-e of snow in this country, or watch jidai-geki (period piece, meaning samurai) movies and wonder why people in this country used umbrellas in the snow, rather than putting on a decent coat and leaving it at that. In America, it's sort of rare for people to use umbrellas in the snow, but I now get it. Here, even up in Yuki-guni (Snow Country) parts of Japan, most of the time it's not really cold. It's right around freezing, which is not actually uncomfortable unless you're wet -- and the snow here will soak right through many a winter coat, where in a colder, drier climate you could brush the snow right off.

The Great Buddha has been sitting outside in the sun and snow for 510 years, now. He doesn't seem to mind, though in the snow I suspect it takes more willpower to remain so stoic.

Weird Real-World Pipeline

One of the things I asked my students to do when we studied pipelining was to find a real-world pipeline. I'm thinking, you know, the Model A assembly line, that kind of thing.

One of my students came up with this one.

A little context: this "Algorithm taisou" (exercise), invented here in Japan, as far as I know, is normally done by a couple of young guys in suits who go out into the real world and find a half a dozen people (firemen, factory workers) to do this little rhythmic routine with them to music. It's used as an interlude during an NHK kid's program.

You can argue pretty easily that this is a real, eight-stage pipeline. It even has structural hazards: the air between the people ("instructions") flowing through is a shared resource, and the pipeline is carefully constructed so that collisions ("pipeline stalls" or incorrect operation) never occur (as long as the dance is done right :-). I don't see any data or control hazards, though.

More on ZCAV

Disk zoning gets you a nice boost in both transfer rate and capacity, but it doesn't get enough attention as a factor in things like file system design. Russell Coker has written some nice utilities and even blogged about it. To be immodest for a second, I wrote a USENIX paper about the topic more than a decade ago.

What prompted the post was spotting a beautiful ZCAV (disk zoning) effect.

You can see the nice little arc in it, and looks like 16 zones for the Seagate drive.

I've been thinking about this recently, since I lectured about disks last week...and my own hard drive crashed. Yow. I'm think I'm cool, though. Not sure if it was hardware or software. My best guess is unwritten cache writes, but the logical volume manager info got trashed, and it shouldn't have been touched...

Spam From ISI?

No, not USC's Information Sciences Institute, where I used to work, but the other ISI. Did I sign up for this, or are they actually spamming people?

From:  ISI Research 
Reply-To:  ISI Research 
To:  R Van Meter 
Subject:  Breaking news for publishing authors
Date:  Wed, 16 Jan 2008 01:43:16 -0500 (15:43 JST)




As a publishing author represented within Current Contents (R),
Biosis Previews (R) and Web of Science, from ISI, you require 
the latest news and resources to stay current in your research. 
That's why we think you'll benefit from getting valuable research 
information right at your desktop -- for free.


>From time to time, you'll receive e-mails with:

* "Call for Papers" requests from scholarly publishers
* News related to your field of scholarly research
* Information about journals and books in your areas of interest
* New product information connected to your field of research

The information you receive will help you discover groundbreaking
ideas and track the progress of the latest developments. And it will
give you opportunities to try important, new resources that can
change the way you conduct research.


We hope you will find this information convenient and essential to
your work.


Sincerely,

George Kowal
Marketing Manager
Scientific Direct
3501 Market Street
Philadelphia, PA 19104

-----------------------------------------------------
You have received this e-mail in the genuine belief that its contents
would be of interest to you. To not receive these messages from
Scientific Direct or other carefully selected organizations, please go
to our preference page.

Anybody got George Kowal's address? ISI should be a better company than that...

Ryo "Oscar" Sakaguchi

As long as I'm singing the praises of our graduates, congratulations are definitely in order for Ryo Sakaguchi, who is sharing a Scientific and Technical Academy Award (Oscar) with Dr. Doug Roble and Nafees Bin Zafar for their work at Digital Domain (where they work with my pal Wook, who recently got married) on fluid simulations used in effects for e.g. "Pirates of the Caribbean".

Congratulations, Ryo!

You Go, Girl

I just found out that Yukari Yoshihara (nee Yukari Umezawa, the name she still uses on books and whatnot) is a graduate of Keio University's Shonan Fujisawa Campus, where I teach. Yukari is a 5-dan professional go player and holds the Women's Kisei title, making her one of the best women players in the country, indeed, probably the world.

Pro go players rarely graduate from college; they usually become "insei" (apprentice go players) at about fifteen, and some don't even bother to finish high school. She, like most pros, was recognized early for her genius.

Yukari is the official technical adviser to the "Hikaru no Go" series of manga. Reportedly, she likes teaching, which is one of the reasons she elected to graduate from college.

Although Keio is Japan's oldest (and, of course, best :-) private university (150 years old this year, making it older than either of my other two alma maters, Caltech and USC), but the SFC campus is only about 17 years old. Yukari, no surprise, was one of the founders of the SFC go club.

I must hang my head in shame that I haven't played a game at all in over six months. Moving, commuting, three trips to the U.S., piano lessons, and that minor thing called work got in the way of more important things, like family and go.