Year: 2005

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.

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.

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
Haim Watzman is a freelancer based in Jerusalem, Israel.
References
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.