Tommaso Toffoli’s 3-input 3-output logic gate, central to the theory of reversible and quantum computing, recently featured on a custom cake made for his 70’th birthday.
Nowadays scientists’ birthday celebrations often take the form of informal mini-conferences, festschrifts without the schrift. I have had the honor of attending several this year, including ones for John Preskill’s and Wojciech Zurek’s 60’th birthdays and a joint 80’th birthday conference for Myriam Sarachik and Daniel Greenberger, both physics professors at City College of New York. At that party I learned that Greenberger and Sarachick have known each other since high school. Neither has any immediate plans for retirement.
Resolution of Toom's rule paradox
A few days ago our Ghost Pontiff Dave Bacon wondered how Toom’s noisy but highly fault-tolerant 2-state classical cellular automaton can get away with violating the Gibbs phase rule, according to which a finite-dimensional locally interacting system, at generic points in its phase diagram, can have only only one thermodynamically stable phase. The Gibbs rule is well illustrated by the low-temperature ferromagnetic phases of the classical Ising model in two or more dimensions: both phases are stable at zero magnetic field, but an arbitrarily small field breaks the degeneracy between their free energies, making one phase metastable with respect to nucleation and growth of islands of the other. In the Toom model, by contrast, the two analogous phases are absolutely stable over a finite area of the phase diagram, despite biased noise that would seem to favor one phase over the other. Of course Toom’s rule is not microscopically reversible, so it is not bound by laws of equilibrium thermodynamics.
Nevertheless, as Dave points out, the distribution of histories of any locally interacting d-dimensional system, whether microscopically reversible or not, can be viewed as an equilibrium Gibbs distribution of a d+1 dimensional system, whose local Hamiltonian is chosen so that the d dimensional system’s transition probabilities are given by Boltzmann exponentials of interaction energies between consecutive time slices. So it might seem, looking at it from the d+1 dimensional viewpoint, that the Toom model ought to obey the Gibbs phase rule too.
The resolution of this paradox, described in my 1985 paper with Geoff Grinstein, lies in the fact that the d to d+1 dimensional mapping is not surjective. Rather it is subject to the normalization constraint that for every configuration X(t) at time t, the sum over configurations X(t+1) at time t+1 of transition probabilities P(X(t+1)|X(t)) is exactly 1. This in turn forces the d+1 dimensional free energy to be identically zero, regardless of how the d dimensional system’s transition probabilities are varied. The Toom model is able to evade the Gibbs phase rule because
- being irreversible, its d dimensional free energy is ill-defined, and
- the normalization constraint allows two phases to have exactly equal d+1 dimensional free energy despite noise locally favoring one phase or the other.
Just outside the Toom model’s bistable region is a region of metastability (roughly within the dashed lines in the above phase diagram) which can be given an interesting interpretation in terms of the d+1 dimensional free energy. According to this interpretation, a metastable phase’s free energy is no longer zero, but rather -ln(1-Γ)≈Γ, where Γ is the nucleation rate for transitions leading out of the metastable phase. This reflects the fact that the transition probabilities no longer sum to one, if one excludes transitions causing breakdown of the metastable phase. Such transitions, whether the underlying d-dimensional model is reversible (e.g. Ising) or not (e.g. Toom), involve critical fluctuations forming an island of the favored phase just big enough to avoid being collapsed by surface tension. Such critical fluctuations occur at a rate
Γ≈ exp(-const/s^(d-1))
where s>0 is the distance in parameter space from the bistable region (or in the Ising example, the bistable line). This expression, from classical homogeneous nucleation theory, makes the d+1 dimensional free energy a smooth but non-analytic function of s, identically zero wherever a phase is stable, but lifting off very smoothly from zero as one enters the region of metastability.
Below, we compare the d and d+1 dimensional free energies of the Ising model with the d+1 dimensional free energy of the Toom model on sections through the bistable line or region of the phase diagram.
We have been speaking so far only of classical models. In the world of quantum phase transitions another kind of d to d+1 dimensional mapping is much more familiar, the quantum Monte Carlo method, nicely described in these lecture notes, whereby a d dimensional zero-temperature quantum system is mapped to a d+1 dimensional finite-temperature classical Monte Carlo problem. Here the extra dimension, representing imaginary time, is used to perform a path integral, and unlike the classical-to-classical mapping considered above, the mapping is bijective, so that features of the d+1 dimensional classical system can be directly identified with corresponding ones of the d dimensional quantum one.
MIT + postdoc opening
After 8 years at MIT, and a little over 7 years away, I will return to MIT this January to join the Physics faculty. I love the crazy nerdy atmosphere at MIT, and am really excited about coming back (although I’ll miss the wonderful people at UW).
Even if Cambridge doesn’t quite look like Sydney, it’s a magical place.
Combined with my fellow CTPers Eddie Farhi and Peter Shor, I will also have funding to hire a postdoc there. The other faculty doing the theory side of quantum information at MIT include Scott Aaronson, Ike Chuang, Jeffrey Goldstone and Seth Lloyd; and that’s not even getting into the experimentalists (like Orlando and Shapiro), or the math and CS people who sometimes think about quantum (like Kelner and Sipser).
The application deadline, including letters, is December 1.
You can apply here. Note that when it asks for “three senior physicists”, you should interpret that as “three strong researchers in quantum information, preferably senior and/or well-known.”
Plagiarism horror story
Halloween is my favorite holiday: you aren’t strong armed into unhealthy levels of conspicuous consumption, the costumes and pumpkins are creative and fun, the autumn colors are fantastic, and the weather is typically quite pleasant (or at least it was in pre-climate change/hurricane Sandy days.) You don’t even have to travel at all! So in honor of Halloween, I’m going to tell a (true) horror story about…
Back in August, I was asked to referee a paper for a certain prestigious physics journal. The paper had already been reviewed by two referees, and while one referee was fairly clear that the paper should not be published, the other gave a rather weak rejection. The authors replied seeking the opinion of a third referee, and that’s when the editors contacted me.
I immediately noticed that something was amiss: the title of the paper was nearly identical to a paper that my co-authors and I had published in that same journal a couple of years earlier. In fact, out of 12 words in the title, the first 9 were taken verbatim. I’m sorry to say, but it further raised my hackles that the authors and their universities were unknown to me and came from a country with a reputation for rampant plagiarism. Proceeding to the abstract, I found that the authors had copied entire sentences, merely substituting some of the nouns and verbs as if it were a Mad Lib. Scrolling further, the authors copied an entire theorem, taking the equations in the proof symbol-by-symbol and line-by-line!
I told all of this to the editor and he of course rejected the paper, providing also an explanation of why and what constitutes plagiarism. A strange twist is that my original paper was actually cited by the copy. Perhaps the authors thought that if they cited my paper, then the copying wasn’t plagiarism? They had even mentioned my paper directly in their response to the original reports as supporting evidence that their paper should be published. (“You published this other paper which is nearly identical, so why wouldn’t you publish ours?”) Thus, at this point I was thinking that it’s possible they simply didn’t understand that their actions constituted plagiarism, and I was grateful that the editor had enlightened them.
Fast forward to today.
I receive another email from a different journal asking to referee a paper… the same paper. They had changed the title, but the abstract and copied theorem were still there. Bizarrely, they even added a fourth author. The zombie paper is back, and it wants to be published!
Of course, I can also raise my previous objections, and re-kill this zombie paper. And I’m considering directly contacting the authors. This clearly isn’t a scalable strategy, however.
It got me thinking. Is there a better way to combat plagiarism of academic papers? One thing that often works in changing people’s behavior is shame. My idea is, perhaps if we build a website where we publicly post the names and affiliations of offenders, then this will cause enough embarrassment to stem the tide. Sort of like the P vs. NP site for erroneous proofs.
What’s your best idea for how to deal with this problem?
12 things a quantum information theorist should do at least once
By popular demand…
- prove (or disprove) something by going to the Church of the Larger Hilbert Space
- apply amplitude amplification in a non-trivial way
- convince yourself you’ve proven that NP is contained in BQP, or at least that you have a poly-time quantum algorithm for graph isomorphism or dihedral HSP
- upper- or lower-bound a fault-tolerance threshold
- use the stabilizer formalism
- make use of convexity
- pick a random state or unitary from the Haar measure
- use an entropic quantity
- estimate or compute a spectral gap
- impress people in field X with your knowledge of something that everyone in field Y takes for granted, where X and Y are chosen from {CS, physics, some area of math, etc.}.
- confuse people in field X about the point of what you’re doing, when it’s a common goal in field Y.
- have a paper unjustly rejected or accepted by PRL.
Thanks to Ashley Montanaro for suggesting the first three.
A way around Nobel's 3-person limit
Most fields of science have become increasingly collaborative over the last century, sometimes forcing the Nobel Prizes to unduly truncate the list of recipients, or neglect major discoveries involving more than three discoverers. In January we pointed out a possible escape from this predicament: choose three official laureates at random from a larger list, then publish the entire list, along with the fact that the official winners had been chosen randomly from it. The money of course would go to the three official winners, but public awareness that they were no more worthy than the others might induce them to share it. A further refinement would be to use (and perhaps publish) weighted probabilities, allowing credit to be allocated unequally. If the Nobel Foundation’s lawyers could successfully argue that such randomization was consistent with Nobel’s will, the Prizes would better reflect the collaborative nature of modern science, at the same time lessening unproductive competition among scientists to make it into the top three.
Rogue Downloader Prosecuted; Rogue Banks Off the Hook
As a researcher, I can breathe safely posting my papers online, knowing that the federal government will do its best to stop anyone from downloading them in a way that violates a website’s terms of use. According to Wired,
Federal prosectors added nine new felony counts against well-known coder and activist Aaron Swartz, who was charged last year for allegedly breaching hacking laws by downloading millions of academic articles from a subscription database via an open connection at MIT.
Swartz, the 25-year-old executive director of Demand Progress, has a history of downloading massive data sets, both to use in research and to release public domain documents from behind paywalls. He surrendered in July 2011, remains free on bond and faces dozens of years in prison and a $1 million fine if convicted.
Thank goodness, because without the royalty checks from my articles, I’m not sure how I would be able to keep myself afloat.
I am also grateful that federal prosecutors have had the time they need to concentrate on important cases like these, instead of wasting time on small fry like Goldman Sachs.
Instruments for Natural Philosophy
Thomas B. Greenslade, emeritus physics professor at Kenyon College in Gambier, Ohio, USA, has amassed (both physically and virtually) a fascinating and expertly curated collection of old physics teaching equipment. Among my favorite items are Bernard H. Porter’s 1939 map depicting Physics as a continent, with rivers corresponding to its principal branches.
good news for quantum computing?
Once large-scale quantum computers exist and can break RSA, of course everyone will switch to a quantum-resistant cryptosystem. Sure, the work that classical computers do to encode and decode will be polynomially higher, but on the other hand, all of the code-breaking advantages of quantum computers will be nullified, and we’ll be stuck trying to explain to the NSA why they should fund simulations of benzene.
Or will we?
One thing we’ve learned from the (semi-)recent hack of stratfor.com (a “subscription-based provider of geopolitical analysis”) is that even though the importance of salts has been known since at least the days of the Enigma machine, it doesn’t mean people will actually use best practices, and stop storing things like credit card numbers in the clear.
So don’t worry: even after “post-quantum” crypto has been developed, and large-scale quantum computers are common, there should be plenty of RSA around to crack.
QIP 2012 videos!
The long awaited videos from QIP 2012 are now online.
Somewhat. If you see a video that you want that isn’t online, then tell the speaker to sign the release form! I’m looking at you Bravyi, Greiner, Landahl and Popescu! (And others.)
If you haven’t seen them before, then you should check out the talks by Haah (on 3-d local stabilizer codes) and Arad (on an improved 1-d area law).