Upcoming Talks

Three talks (maybe four) coming up in the next few weeks have me attached at the hip to Microsoft Powerpoint. First up is the SQuInT conference in Tuscon Arizona where I will be talking Friday, Feb. 18 about my work with Andrew Childs and Wim van Dam on the optimal measurements for the dihedral hidden subgroup problem. Then it’s off to Washington State where I will be giving a Physics colloqium on Tuesday, Feb. 22. The title of this talk is “Quantum Computing in 2020.” Which led me to a very nice quote by Niels Bohr: “Predicition is very difficult, especially if it’s about the future.” After WSU, I’m off to Seattle where I will be giving a Computer Science and Engineering colloqium at the University of Washington on Thursday Feb. 24. The title of this talk is “How and What to Quantum Compute” and I have (ack!) boldly promised that I

…will draw insights from the vast knowledge base of theoretical and experimental physics, mathematics, engineering, and computer science. The talk will be accessible to practitioners from all of these fields and represents not just an opportunity to see the different fields interact, but also an invitation to participate in the intellectual and practical challenges of quantum information science.

This colloqium will probably be taped and put online in streaming format which I’m really looking forward to. Once I was taped teaching a section of an undergrad physics course at Berkeley. It was very informative to see all the places I was messing up and at least for the next few weeks I think I was a much better teacher. Ak, OK, enough distraction from the blog. Back to my best friend Powerpoint.

The Knuth Is We Fail

If you’ve ever been fascinated by how people approach solving problems, these notes from a “Programming and Problem Solving Seminar” taught by Donald Knuth at Stanford are an extremely interesting read. Knuth selected five (unsolved) problems for the class to work on (with an eye for problems that would lead to interesting subproblems) over the course of the semester. The problems are extremely interesting in their own right, but reading the way in which people attacked the problems is actually much more interesting. One gets the impression, sometimes, that theory is about solved problems, but actually it’s more about a lot of failures. Well, maybe this is my own predjudice due to the number of times I’ve failed, but I suspect I’m not the only one.

Physics and Engineering

This opinion article in Nature (433, 179 (2005)) is a bit rambling, but still very interesting.

Einstein is dead
Until its next revolution, much of the glory of physics will be in engineering. It is a shame that the physicists who do so much of it keep so quiet about it.
Once upon a time there was (and still is) a multinational manufacturer of sheet metal whose researchers realized they could improve the reliability of its production processes. By solving the equations of heat transfer for the company’s rolling presses, and testing the solutions on scale models, they significantly reduced the margin of error in the thickness of the rolled sheet. Their prime customer, a manufacturer of metal cans, was delighted. Millions of pounds were saved in materials and rejected products, and (maybe) the reduced costs were passed on to the customer. Maybe, too, the physicists got bonuses.
How very far removed from the special theory of relativity and the world of quantum mechanics — the parallel revolutionary paradigms on which most of twentieth-century physics and related technologies were based. Now, 100 years after Einstein’s first pioneering papers in those disciplines, physicists worldwide are rightly going to town, with conferences, artistic commissions and games… They are doing their utmost to celebrate in the face of the relentless promotion of biology as the exciting science of the current century and despite declining interest in physics amongst the young.
Einstein is not only the patron saint of physics but also an icon of integrity and scientific pursuit for its own sake — and, for the wider public, an appealing elderly gentleman. Small wonder, then, that UK and Irish physicists opted to call 2005 ‘Einstein year’, rather than the ‘Year of physics’. But Einstein is long gone. His ideas, his style and his legacy still inspire, but his rejection of the quantum picture of reality and his dreams of the unification of forces have been replaced by the acceptance and exploration of quantum entanglement and highly esoteric (albeit potentially profound) attempts to derive twentieth-century laws from a deeper paradigm for the structure of space-time.
To hang a ‘Year of physics’ so centrally on Einstein is to miss the key lessons of the metal manufacturer: that physics is not only central to our understanding of the Universe (just what are dark matter and dark energy?), but is also central to making useful and sometimes inspiring things. Sheet metal is at the more prosaic end of the spectrum. At the other end, Steve Jobs, head of Apple, said at last week’s launch of the latest iPod: “Most people make the mistake of thinking design is what it looks like… Design is how it works.” In other words, sexy design is also about sexy engineering and the sexy science behind it.
And listen to theoretical physicist Michael Berry of the University of Bristol, UK, launching the competition “Physics for taxi drivers” (Physics World December 2004, p. 15; http://physicsweb.org/articles/world/17/12/2 ).He recalls how a description of a CD player and a satellite navigation receiver convinced a cab driver that physics is interesting. The worry is not so much that people cannot understand the relevance of physics — and credit to the ‘World Year of Physics 2005′ organizers for a poster competition for 10–16-year-olds to celebrate that. The worry is that in universities, and especially in schools, there is so little emphasis and imagination, either this year or ever, in celebrating physics’ relevance and, more importantly, sending the right career signals to young people.
Many young people today are as capable as previous generations of being inspired by the challenge of making things: engineering with unbelievable precision in the face of quantum uncertainties, creating elegance in functional design, and delivering innovative and useful — or even socially transforming — everyday things. Nature’s pages have included their share of the foundations of twenty-first-century manufacturing, with advances in the quantum control of atomic and molecular states, quantum information and optoelectronics.
Some of the authors of those papers have interesting engineering careers ahead of them. As surveys by learned societies repeatedly show, a large proportion of physics graduates find fulfilling and well paid employment in engineering and information technology. Those same societies, and governments and physicists generally, repeatedly fail to get that message across to the public or to kids in schools. Yet that is surely a more important challenge this year than reiterating in depth, appropriately but ineffectually, that Einstein was great.

Somedays, as a quantum information science researcher, I want to shout to physics and computer science departments: “Look at us! We are a legitimate intellectual pursuit!” It’s nice to see Nature doing the yelling for a change.

A Large Influence

At QIP, I was struck by something odd about the invited speakers. First, of course, was their age. The group of speakers was much younger than in previous years. Many of the speakers are from the second generation of the quantum information science revolution (we must compete with string theory, no?) But then it struck me: most of the speakers have spent a considerable length of time at the Institute for Quantum Information at Caltech. In fact 12 of the 22 invited speakers are IQI alumni in some manner. Now that’s a pretty amazing track record for a single institute.

QIP 2005 Trip Report

First, Boston was cold. Actually it wasn’t too much colder than Santa Fe, but the extra wetness and windiness made it feel much colder. Except one strange night, where, after embibing some refreshments at the “Miracle of Science” bar (this is M.I.T. you know), the walk home at midnight was filled with a strong, probably 55 degree breeze. Very strange.
There were a lot of good talks at QIP, but, like any conference, the talks do not fully make up the content of the conference. I had a good time talking to various people about the hidden subgroup problem and I am more optimistic about the problem than I have been in a long time. Expect a lot of good work to be reported in the next six months.
My favorite talk of the conference was probably Oded Regev’s talk on a new public-key cryptosystem. While previous lattice based public-key cryptosystems (like the one by Ajtai and Dwork and an improvement of this system by Oded himself) were based on a problem called the unique shortest vector in a lattice problem, breaking the new cryptosystem is based on the hardness of the shortest vector problem. The funny thing is that it is based not on the classical hardness of the shortest vector problem, but is based on the quantum hardness of the shortest vector problem. One intersting offshoot of this is that there is a learning problem whose solution will lead to a quantum algorithm for certain shortest vector in a lattice problems.
Another very interesting and entertaining talk was given by Scott Aaronson (quantum computing’s younger clown.) Scott talked about a model of quantum computation in which you get to postselect on the measurement outcome. In other words, you get to perform a quantum measurement and, instead of getting one of say two outcomes, you get to always assume that you got only one of the two possible outcomes. Postselection is, as far as we know, not possible, but you know computer scientists: always talking about crazy complexity classes whose practical value is dubious. But just because there is no practical value doesn’t mean that this craziness cannot lead to some astoundingly nice results. And this is exactly what Scott was able to show. In particular he showed that the model of quantum computation with postselection, postBQP, is exactly equal to the complexity class PP. The class PP (called, unfortunately, “probabilistic polynomial time”) is the class of problems solvable by a non-deterministic Turing machine such that if the answer is yes then at least 1/2 of the paths accept and if the answer is no then less than 1/2 of the computational paths accept. A comparison with NP is that in NP, the answer is yes if at least one of the paths accept and if the answer is no then none of the paths accept. One of the trickier properties to establish about PP is that it is closed under intersection. This was done by Beigel, Reingold, and Spielman in 1991. What is really cute about Scott’s result is that he is able to obtain this proof in a very very simple way from the fact that postBQP=PP. The technique also produces a lot of other previous results in a nice clean manner. Amazing how a quantum model of computation, with a crazy extra assumption (postselection) can make things so much clearer!
QIP 2006 will be held in Paris and QIP 2007 will be held in Brisbane, Australia.

Dihedral Hidden Subgroup Problem

Nothing like a little shameless self-promotion: quant-ph 0501044

Optimal measurements for the dihedral hidden subgroup problem
Dave Bacon, Andrew Childs, and Wim van Dam
We consider the dihedral hidden subgroup problem as the problem of distinguishing hidden subgroup states. We show that the optimal measurement for solving this problem is the so-called pretty good measurement. We then prove that the success probability of this measurement exhibits a sharp threshold as a function of the density nu=k/log N, where k is the number of copies of the hidden subgroup state and 2N is the order of the dihedral group. In particular, for nu<1 the optimal measurement (and hence any measurement) identifies the hidden subgroup with a probability that is exponentially small in log N, while for nu>1 the optimal measurement identifies the hidden subgroup with a probability of order unity. Thus the dihedral group provides an example of a group G for which Omega(log|G|) hidden subgroup states are necessary to solve the hidden subgroup problem. We also consider the optimal measurement for determining a single bit of the answer, and show that it exhibits the same threshold. Finally, we consider implementing the optimal measurement by a quantum circuit, and thereby establish further connections between the dihedral hidden subgroup problem and average case subset sum problems. In particular, we show that an efficient quantum algorithm for a restricted version of the optimal measurement would imply an efficient quantum algorithm for the subset sum problem, and conversely, that the ability to quantum sample from subset sum solutions allows one to implement the optimal measurement.

Profile of a Quantum Theorist

Nature (433, 8 (2005)) has an article profiling four young theorists, and among these theorists is quantum computing’s Dorit Aharonov:

A theorist of errors
Growing up on Einstein Street in Haifa, Israel, Dorit Aharonov was perhaps destined to study physics. But she pursued other interests before finally settling on quantum computation. Haim Watzman reports.
To enter Dorit Aharonov’s office is to experience a sudden transition between order and disorder. The corridors of the computer-science building at the Hebrew University of Jerusalem are stark, white and neat. Aharonov’s office is a jumble of red-and-orange patterned cushions, article reprints and wicker furniture. It’s an appropriate setting for a theorist who has proved that when disorder reaches a certain level, the physics of the quantum realm switches into the classical domain of the world we see every day.
Aharonov devotes herself to the theory behind quantum computers. As-yet unbuilt, these machines would harness the power of quantum mechanics to perform tasks that defeat conventional computers — such as factoring large numbers. Aharonov, now 34, has already made important contributions to this goal by showing that a quantum computer could perform reliably and accurately despite a ‘noisy’ environment.
Physics runs strong in Aharonov’s family. Her uncle, Yakir Aharonov, is a physicist at Tel Aviv University, and her father is a mathematician who taught her the beauty of numbers when she was little. She later chose physics and mathematics for her undergraduate studies, but the quantum world did not initially capture her imagination. She wanted instead to use physics to study the brain.
A chance encounter
“I wanted to solve the problem of consciousness,” she recalls. But she began to think that the problem was still beyond the reach of today’s science. “Then, one day, at a wedding, a friend asked me for advice about what direction to take in the study of the brain. I advised him to check out what people in computer science were doing,” she says.
Realizing she should take her own advice, Aharonov went to the Hebrew University’s computer-science building to find someone to talk to. She was directed to Michael Ben-Or and, as she knocked on his door, she says that she had a strong feeling something important was going to happen. It did. Ben-Or told her about quantum computation. “It fascinated me. It was mathematics, physics and philosophy all in one package,” she says.
Back then, in 1994, the problem facing theorists such as Ben-Or was how to prevent a quantum computer from crashing. All computers make errors when they operate, but quantum computers are more susceptible to failure. This is because the quantum states on which calculations depend are very delicate: complex phenomena, such as the spin states of atomic nuclei, can store quantum information but this data can easily be lost if the particles interact with their surroundings. A computer can never be perfectly isolated from its environment, so there will always be ‘noise’ in the system and, inevitably, errors will arise. Moreover, correcting such errors is almost as difficult as doing the calculation in the first place. So will it ever be possible to do a reliable quantum calculation?
“That was the problem I posed to Dorit,” says Ben-Or, who became Aharonov’s dissertation supervisor and later her collaborator. Working with Ben-Or, Aharonov proved that at a constant but low level of system noise, a quantum computer can still produce accurate results1.
“I consider her to be one of the most outstanding young people in this field,” says Peter Zoller, a theoretical physicist at the University of Innsbruck, Austria. Zoller wants to build a quantum computer, and he says that Aharonov has been instrumental in laying the theoretical foundations on which a real machine could be constructed. As well as her work on error tolerance, he cites an important proof2 Aharonov developed with Oded Regev and others while working at the University of California, Berkeley. The proof showed that two existing models for quantum computing are actually equivalent and, as a result, made writing quantum algorithms easier.
While at Berkeley, Aharonov extended her work on computers to address a fundamental puzzle presented by quantum mechanics — why its laws are evident in the world of elementary particles, but not in everyday life. At what point does the world switch from looking quantum to looking classical? Is it simply a matter of scale?
Aharonov showed that for many noisy quantum systems, there is a level of noise above which a transition to classical behaviour is inevitable. Such transitions are much sharper than expected from other theories that predict a gradual shift away from quantum behaviour3.
Ben-Or says that what sets Aharonov apart is her boldness. As a graduate student she was not shy about contacting leading figures in the field to discuss their work, he recalls. Zeph Landau, a mathematician at the City College of New York who collaborated with Aharonov on the model equivalence paper, says that she is focused but not single-minded, finding time to discuss other pursuits.
Aharonov says that balancing life and work is essential to her research. Like many theorists, she says that she has her best ideas when not thinking about work at all. Her daily yoga session is particularly rewarding, she says: “It disperses the fog. My intuition becomes sharper. When there is less struggle, ideas become clear.”
Eastern ideas about the interconnectedness of everything also influence her work. For instance, Aharonov is not fixated on the actual construction of a quantum computer. “The most interesting thing that might come out of an attempt to build one is the discovery that we can’t do it,” she says. By failing, she adds, we might discover some entirely new physics.
Haim Watzman is a freelancer based in Jerusalem, Israel.
1. Aharonov, D. & Ben-Or, M. Preprint at http://xxx.lanl.gov/quant-ph/9611025 (1996).
2. Aharonov, D. et al. Preprint at http://xxx.lanl.gov/quant-ph/0405098, (2004).
3. Aharonov, D. Phys. Rev. A 62, 062311 (2000).

I first heard Dorit speak at the QIP conference in Chicago in 1999. What I remember most about the talk was that all of the sudden the little I knew about quantum error correcting codes crystalized perfectly for me during her talk.

Asher Peres, 1934-2005

Sad news comes from via Lance Fortnow’s Computational Complexity:

Asher Peres, 1934-2005
By Netanel Lindner, Petra Scudo and Danny Terno via Christopher Fuchs
Quantum information science lost one of its founding fathers. Asher Peres died on Sunday, January 1, 2005. He was 70 years old.
A distinguished professor at the Department of Physics, Technion – Israel Institute of Technology, Asher described himself as “the cat who walks by himself”. His well-known independence in thought and research is the best demonstration of this attitude. Asher will be missed by all of us not only as a great scientist but especially as a wonderful person. He was a surprisingly warm and unpretentious man of stubborn integrity, with old-world grace and a pungent sense of humor. He was a loving husband to his wife Aviva, a father to his two daughters Lydia and Naomi, and a proud grandfather of six. Asher was a demanding but inspiring teacher. Many physicists considered him not only a valued colleague but also a dear friend and a mentor.
Asher’s scientific work is too vast to review, while its highlights are well-known. One of the six fathers of quantum teleportation, he made fundamental contributions to the definition and characterization of quantum entanglement, helping to promote it from the realm of philosophy to the world of physics. The importance of his contributions to other research areas cannot be overestimated. Starting his career as a graduate student of Nathan Rosen, he established the physicality of gravitational waves and provided a textbook example of a strong gravitational wave with his PP-wave. Asher was also able to point out some of the signatures of quantum chaos, paving the way to many more developments. All of these contributions are marked by a surprising simplicity and unbeatable originality.
Of all his publications, Asher was most proud of his book Quantum Theory: Concepts and Methods. The book is an example of Asher’s scientific style: an uncompromising and deep understanding of the fundamental issues expressed in a form which is as simple and accessible as possible. It took Asher six years to carefully weave the threads of his book together. The great quality of the work is acknowledged by anyone acquainted with the final result.
In a favorite anecdote, Asher told about a reporter who had interviewed him on quantum teleportation. “Can you teleport only the body, or also the spirit?” the reporter had asked. “Only the spirit,” was Asher’s reply. Our community has been privileged to know him and have been touched by his spirit.
I am the cat who walks by himself is a charming twelve-page autobiography covering his life from his birth in the village Beaulieu-sur-Dordogne in France until his meeting with Aviva on a train to Haifa. The rest of his story is in his formal CV.

Asher’s book, besides being a classic on foundational issues, profoundly influence much of the style of today’s quantum information science. One passage in particular was a favorite of mine which I accidentally quoted to Murray Gell-Mann the other day:

This mental prcoess can be repeated indefinitely. Some authors state that the last stage in this chain of measurements involves “consciousness,” or the “intellectual inner life” of the observer, by virtue of the “principle of psychophysical parallelism.”[3,4] Other authors introduce a wave function for the whole Universe[5]. In this book, I shall refrain from using concepts that I do not understand.
[3] J. von Neumann, Mathematische Grundlagen der Quantenmechanik, Springer, Berlin (1932) p. 223; transl. by E.T. Beyer: Mathematical Foundations of Quantum Mechanics, Princeton Univ. Press (1955) p. 418
[4] E.P. Wigner, Symmetries and Reflections, Indiana Univ. Press, Bloomington (1967)

Among all the papers which Asher wrote, I think my favorite would have to be a paper he wrote with Wootters: “Optimal Detection of Quantum Information,” Phys. Rev. Lett. 66, 1119-1122 (1991):

Two quantum systems are identically prepared in different locations. An observer’s task is to determine their state. A simple example shows that a pair of measurements of the von Neumann type is less effective than a sequence of nonorthogonal probability-operator measures, alternating between the two quantum systems. However, the most efficient set of operations of that type that we were able to design falls short of a single combined measurement, performed on both system together.