Shtetl-Optimized

The March 2007 issue of Notices of the American Mathematical Society is out. In it we find:

1. Fascinating conversations with three of the four Fields medalists (guess which one declined to be interviewed?)
2. An obituary of George Dantzig (linear programming pioneer), which I found incredibly frustrating for two reasons. First, the article repeatedly sidesteps the most interesting questions about Dantzig’s career: what were those open problems that he solved mistaking them for homework exercises? What impact did his WWII work actually have? Second, just as nothing in biology makes sense except in the light of evolution, so nothing in optimization makes sense except in the light of computational complexity — a topic this 19-page article somehow assiduously avoids.
3. A poem by Bill Parry (1934-2006), which stirred my soul as Walt Whitman never did back in 11^th-grade English, and which I here reproduce in its entirety.

Argument

As he cleaned the board,
chalk-dust rose like parched mist.
A dry profession, he mused as morosely
they shuffled settling tier upon tier.

Now, almost half-way through the course,
(coughs, yawns, and automatic writing)
the theorem is ready.

Moving to the crucial point,
the sly unconventional twist,
a quiver springs his voice and breast;

soon the gambit will appear
opposed to what’s expected.
The ploy will snip one strand
the entire skein sloughing to the ground.

His head turns sympathetically
from board to class.
They copy copiously.
But two, perhaps three pause and frown,

wonder will this go through,
questioning this entanglement
— yet they nod encouragement.
Then the final crux; the ropes relax and fall.

His reward: two smile, maybe three,
and one is visibly moved.
Q.E.D., the theorem is proved.

This was his sole intent.
Leaving the symbols on the board
he departs with a swagger of achievement.

Follow

Lately I’ve been getting emails from undergrads with stellar-looking résumés who want to be my summer students. My initial reaction was: “who, me? I’m barely more than a summer student myself!” But today a light bulb went off: “hey, if these ambitious whippersnappers really want to do my research for me, why shouldn’t I let them do it — thereby freeing up my own time for more important priorities like blogging?”

I’ve therefore decided to list three project ideas. If you’re an undergrad or grad student who wants to tackle one of them this summer at the University of Waterloo, email me (scott at scottaaronson dot com). Tell me about yourself and what you want to do, and attach a CV. I’ll pick up to two students. Deadline: Feb. 21 or until positions are filled.

Scott Aaronson is an equal opportunity employer. He doesn’t have his own funding, so if you can bring your own, great; if not, he’ll try to scrounge some from under Mike Lazaridis’s couch. If the projects listed below don’t interest you — or if you’re more interested in physics, engineering, or information theory than in quantum complexity — there are many, many potential supervisors at both the Institute for Quantum Computing and the Perimeter Institute who’d probably be a better match for you.

Project #1: The Learnability of Quantum States. For this project, you’d first read and understand my paper of the same name, ideally before the summer started. You’d then implement my quantum state reconstruction algorithm in Matlab, Mathematica, or any other environment of your choice, and study its performance with realistic physical systems. This is a crucial first step if experimentalists are ever going to be convinced to try my quantum state learning approach. (The fact that I proved it works is completely irrelevant to them…) There’s also plenty of scope for new theoretical ideas if you swing that way. The eventual goal would be to publish the results somewhere like Physical Review Letters. This project is highly recommended.

Project #2: Multiple Quantum Proofs. Today we believe that there are mathematical truths that you could efficiently verify if given a small quantum state, but that you couldn’t efficiently verify if given a short classical string. But what if you were given two quantum states, which were guaranteed to be unentangled with each other? Would that let you verify even more truths than you could with a single quantum state? The answer is, we have no idea! Nor do we know whether three quantum proofs are more powerful than two, etc. When it comes to the power of multiple quantum proofs, even the most embarrassingly simple questions are open. In this project, you’d work with me to try and sort out the mess. This project is only for students who are confident of their ability to do original research in theoretical computer science.

Project #3: Insert Your Own Project. Wow me. Dazzle me. Give me a specific, detailed idea for a research project in quantum complexity theory or a related area, and convince me that you’re ferocious enough to get somewhere with it in one summer. I’ll try to help where I can.

Follow

If no one else is going to highlight some results from the conference, I guess I’ll have to do it myself. More nuggets coming soon (i.e., as soon as I have my layovers in Auckland and LAX en route to Toronto) Nope, I was too lazy. Plus I caught a cold on the plane from which I’m just now recovering.

• Aram Harrow (joint work with Sean Hallgren) generalized the Recursive Fourier Sampling problem of Bernstein and Vazirani, to give superpolynomial quantum black-box speedups based not only on the Fourier transform, but on almost any unitary transformation.
• Falk Unger discussed his joint result with Richard Cleve, William Slofstra, and Sarvagya Upadhyay, that if Alice and Bob share unlimited quantum entanglement and are playing n Bell inequality games in parallel, then they might as well just play each game separately (i.e., there’s no advantage in correlating their strategies across multiple games). Surprisingly, this is provably false if Alice and Bob don’t share entanglement.
• Alexandra Kolla discussed her joint result with Sean Hallgren, Pranab Sen, and Shengyu Zhang, that any classical statistical zero-knowledge protocol can be made secure against quantum attacks. This generalizes a previous result of John Watrous (STOC’06), that certain specific SZK protocols can be made secure against quantum attacks. Shengyu was supposed to give the talk; Alexandra had to fill in for him on a few days’ notice since he couldn’t get a travel visa.
• Troy Lee discussed his new negative-weight adversary method for proving quantum lower bounds (joint work with Peter Høyer and Robert Špalek), which improves the previous methods of Ambainis, Zhang, and others, and finally breaks through the so-called certificate complexity barrier. Unfortunately, the new method is so non-intuitive that right now the authors can only apply it with the aid of semidefinite programming solvers. But this old lowerboundsgeezer is hoping that, once the young ‘uns get a better handle on their new toy, they’ll be able to use it to finally demolish some of the old open problems in quantum lower bounds.
• Daniel Gottesman proved (joint work with Dorit Aharonov and Julia Kempe) that finding the ground state of a one-dimensional spin chain with nearest-neighbor interactions is already QMA-complete. Since the analogous classical problem is solvable in polynomial time, it had been conjectured that the quantum version is too, but this intuition turns out to be wrong.
• Yi-Kai Liu showed (joint work with Matthias Christandl and Frank Verstraete) that several problems of longstanding interest to chemists are QMA-complete. These problems include deciding whether a set of local density matrices is compatible with some global density matrix; and the “N-representability” problem (namely, deciding whether a quantum state of two m-mode fermions is extendible to a state of N m-mode fermions, where m=O(poly(N)).
• Francois Le Gall gave an exponential separation between randomized and quantum space complexity in the online setting (that is, the setting where the input bits are fed to an algorithm one at a time, with no possibility of going backward).
• Gus Gutoski showed (joint work with John Watrous) that if two omniscient gods are playing a quantum chess game by shuttling qubits back and forth via a polynomial-time intermediary, who will measure the qubits at the end to decide the winner, then it’s possible in deterministic exponential time to decide which god will win. Or to say it much more clearly, QRG=EXP.
• Iordanis Kerenidis discussed his joint result with Dmitry Gavinsky, Julia Kempe, Ran Raz, and Ronald de Wolf, that there exists a partial Boolean function whose quantum one-way communication complexity is exponentially smaller than its randomized one-way communication complexity. Previously this was only known for relation problems.
• Ike Chuang gave an update on experimental quantum computing. His talk included a lot of graphs of damped sine curves.
• I gave my tired old talk on learnability of quantum states.

Follow