Science is slow. You can do things like continue a conversation with yourself (and a few commenters) that started in 2005. Which is what I’m now going to do 🙂 The below is probably a trivial observation for one of the cardinals, but I find it kind of interesting.
Let’s begin by recalling the setup. Toom’s rule is a cellular automata rule for a two dimensional cellular automata on a square grid. Put +1 and -1’s on the vertices of a square grid, and then use the following update rule at each step: “Update the value with the majority vote of your own state, the state of your neighbor to the north, and the state of your neighbor to the east.” A few steps of the rule are shown here with +1 as white and -1 as blue:
As you can see Toom’s rule “shrinks” islands of “different” states (taking away such different cells from the north and east sides of such an island.) It is this property which gives Toom’s rule some cool properties in the presence of noise.
So now consider Toom’s rule, but with noise. Replace Toom’s update rule with the rule followed by, for each and every cell a noise process. For example this noise could be to put the cell into state +1 with p percent probability and -1 with q percent probability. Suppose now you are trying to store information in the cellular automata. You start out at time zero, say, in the all +1 state. Then let Toom’s rule with noise run. If p=q and these values are below a threshold, then if you start in the +1 state you will remain in a state with majority +1 with a probability that goes to one exponentially as a function of the system size. Similarly if you start in -1. The cool thing about Toom’s rule is that this works not just for p=q, but also for some values of p not equal to q (See here for a picture of the phase diagram.) That is there are two stable states in this model, even for biased noise.
Contrast Toom’s rule with a two dimensional Ising model which is in the process of equilibriating to temperature T. If this model has no external field applied, then like Toom’s rule there is a phase where the mostly +1 and the mostly -1 states are stable and coexist. These are from zero temperature (no dynamics) to a threshold temperature T, the critical temperature of the Ising model. But, unlike in Toom’s rule, if you now add an external field, which corresponds to a dynamics where there is now a greater probability of flipping the cell values to a particular value (p not equal to q above), then the Ising model no longer has two stable phases.
In fact there is a general argument that if you look at a phase diagram as a function of a bunch of parameters (say temperature and applied magnetic field strength in this case), then the places where two stable regimes can coexist has to be a surface with one less dimension than your parameter space. This is known as Gibbs’ phase rule. Toom’s rule violates this. It’s an example of a nonequilibrium system.
So here is what is puzzling me. Consider a three dimensional cubic lattice with +1,-1 spins on its vertices. Define an energy function that is a sum over terms that act on the spins on locations (i,j,k), (i+1,j,k), (i,j+1,k), (i,j,k+1) such that E = 0 if the spin at (i,j,k+1) is in the correct state for Toom’s rule applied to spins (i,j,k), (i+1,j,k), and (i,j+1,k) and is J otherwise. In other words the terms enforce that the ground state locally obey’s Toom’s rule, if we imagine rolling out Toom’s rule into the time dimension (here the z direction). At zero temperature, the ground state of this system will be two-fold degenerate corresponding to the all +1 and all -1 state. At finite temperature this model well behave as a symmetric noise Toom’s rule model (see here for why.) So even at finite temperature this will preserve information, like the d>2 Ising model and Toom’s CA rule.
But since this behaves like Toom’s rule, it seems to me that if you add an external field, then this system is in a bit of paradox. On the one hand, we know from Gibb’s phase rule, that this should not be able to exhibit two stable phases over a range of external fields. On the other hand, this thing is just Toom’s rule, laid out spatially. So it would seem that one could apply the arguments about why Toom’s rule is robust at finite field. But these contradict each other. So which is it?
4 Pages
Walk up to a physicist at a party (we could add a conditional about the amount of beer consumed by the physicist at this point, but that would be redundant, it is a party after all), and say to him or her “4 pages.” I’ll bet you that 99 percent of the time the physicist’s immediate response will be the three words “Physical Review Letters.” PRL, a journal of the American Physical Society, is one of the top journals to publish in as a physicist, signaling to the mating masses whether you are OK and qualified to be hired as faculty at (insert your college name here). I jest! (As an aside, am I the only one who reads what APS stands for and wonders why I have to see the doctor to try out for high school tennis?) In my past life, before I passed away as Pontiff, I was quite proud of the PRLs I’d been lucky enough to have helped with, including one that has some cool integrals, and another that welcomes my niece into the world.
Wait, wht?!? Yes, in “Coherence-Preserving Quantum Bits” the acknowledgement include a reference to my brother’s newborn daughter. Certainly I know of no other paper where such acknowledgements to a beloved family member is given. The other interesting bit about that paper is that we (okay probably you can mostly blame me) originally entitled it “Supercoherent Quantum Bits.” PRL, however, has a policy about new words coined by authors, and, while we almost made it to the end without the referee or editor noticing, they made us change the title because “Supercoherent Quantum Bits” would be a new word. Who would have thought that being a PRL editor meant you had to be a defender of the lexicon? (Good thing Ben didn’t include qubits in his title.)
Which brings me to the subject of this post. This is a cool paper. It shows that a very nice quantum error correcting code due to Bravyi and Haah admits a transversal (all at once now, comrades!) controlled-controlled-phase gate, and that this, combined with another transversal gate (everyone’s fav the Hadamard) and fault-tolerant quantum error correction is universal for quantum computation. This shows a way to not have to use state distillation for quantum error correction to perform fault-tolerant quantum computing, which is exciting for those of us who hope to push the quantum computing threshold through the roof with resources available to even a third world quantum computing company.
What does this have to do with PRL? Well this paper has four pages. I don’t know if it is going to be submitted or has already been accepted at PRL, but it has that marker that sets off my PRL radar, bing bing bing! And now here is an interesting thing I found in this paper. The awesome amazing very cool code in this paper is defined via its stabilizer
I I I I I I IXXXXXXXX; I I I I I I I ZZZZZZZZ,
I I IXXXXI I I IXXXX; I I I ZZZZ I I I I ZZZZ,
IXXI IXXI IXXI IXX; I ZZ I I ZZ I I ZZ I I ZZ,
XIXIXIXIXIXIXIX; Z I Z I Z I Z I Z I Z I Z I Z,
This takes up a whopping 4 lines of the article. Whereas the disclaimer, in the acknowledgements reads
The U.S. Government is authorized to
reproduce and distribute reprints for Governmental pur-
poses notwithstanding any copyright annotation thereon.
Disclaimer: The views and conclusions contained herein
are those of the authors and should not be interpreted
as necessarily representing the official policies or endorse-
ments, either expressed or implied, of IARPA, DoI/NBC,
or the U.S. Government.
Now I’m not some come-of-age tea party enthusiast who yells at the government like a coyote howls at the moon (I went to Berkeley damnit, as did my parents before me.) But really, have we come to a point where the god-damn disclaimer on an important paper is longer than the actual definition of the code that makes the paper so amazing?
Before I became a ghost pontiff, I had to raise money from many different three, four, and five letter agencies. I’ve got nothing but respect for the people who worked the jobs that help supply funding for large research areas like quantum computing. In fact I personally think we probably need even more people to execute on the civic duty of getting funding to the most interesting and most trans-form-ative long and short term research projects. But really? A disclaimer longer than the code which the paper is about? Disclaiming, what exactly? Erghhh.
The Quantum Interregnum Decoherence Continues
The College of Cardinals has been in conclave for over a month now and leaks to the public indicate that the cardinals are still stalemated. What does this portend for the world? The end? A new beginning? Only entropy (which others call time) will tell.
The Quantum Interregnum Continues
The College of Cardinals continues to meet in conclave. But alas after a week there is only….black smoke.
Quantum Interregnum!
The Vicar of Randomization hereby informs the readers of this blog that the Quantum Pontiff Dave Bacon XLII has decohered. He further informs the readers of this blog that the entire Quantum Pontiff blog is in Justitium and hopes that the readers will refrain from acting like Canucks fans after losing the Stanley Cup.
The College of Cardinals will begin conclave in the coming days, please stay tuned to this chimney.
Goodnight CSE
good night room
goodnight nom de plume
goodnight notebooks
goodnight tests
goodnight grants
goodnight Mike and goodnight Ike
goodnight publish
and goodnight perish
goodnight whiteboard
goodnight star, goodnight air
goodnight noises everywhere.
Oh the Places I've Been!
In 1996 I participated in Caltech‘s Summer Undergraduate Research Fellowship program under the direction of two postdocs, Nicolas Cerf and Chris Adami (their big boss now works the halls of D.C.) The research project I worked on was to try to see whether quantum computers could efficiently solve NP-complete problems. Or as I like to say, my SURF was spent bashing my head up against the wall (and getting damn good at tensor products and spotting non-linear transforms, as you can see from my SURF writeup. John Preskill told me after my talk, in the first words he ever uttered in my direction: “that was a hard problem you worked on.”)
My SURF project was not my first introduction to quantum computing, but it was the first time I’d gotten a chance to bash my head up against the field, and something must have stuck. Because when I went to grad school in Berkeley in 1997, after a year of taking astrophysics courses (if the cosmic microwave background was distributed this way or that way on the sky, this or that cosmological model could be ruled out, how cool is that!) I stumbled back into quantum computing through the group of Chemistry Professor K. Birgitta Whaley and her postdoc Daniel Lidar. My first paper in quantum computing was published in 1999, and I’ve been a proud participant in the growing field of quantum information science ever sense.
Now that I’ve decided that it is time for a change and I’m moving out of the ivory tower and into the real world (academics, you see, manufacture their own reality, which is why they call everything outside of academia “the real world”), I thought it would be fun to indulge in a little bit of egotistical self-reflection, cataloging the joys that a decade plus spent in quantum computing has given me. The joys of all of the papers I’ve written and all of the cool quantum computing stuff I’ve see? No, that would be too easy. Instead I thought it would be fund to think about the kind of crazy things that happen to you as life sweeps you along. Or, as I like to say it, “Oh the places I’ve been!”
[Warning: self-flattering ego-inflating stories ahead!]
Things I’ve gotten to do that were pretty damn awesome:
- I lectured a rich guy who’d just sold his company for many millions of dollars about quantum computing while standing on the walkway surrounding the 200-inch Hale telescope. This will definitely be the only time I’ve been driven to give a scientific talk in a limo!
- Parked my Mazda Miata with QUBITS license plate beside Murray Gell-Mann’s Range Rover sporting the license plate QUARKS while at the Santa Fe Institue. One day I missed a major missed opportunity because of this. Ben Schumacher was visiting the Santa Fe Institute… so I had the chance to get a picture of two people who have invented words that start with “Q”, that are in the dictionary, in front of two cars with license plates with those words! I shall never forgive myself for this missed opportunity.
- Played Isaac Newton to Scott Aaronson’s Gottfried Leibniz. Personally I think I got to play the more awesome scientist and damn if that Leibniz didn’t steal calculus from me.
- Gave a lecture at a summer school in Brisbane, Australia where I discussed a stabilizer code which contained the operators XXXX and ZZZZ. XXXX is the name of a beer in Australia, so I knew this would be awesome for jokes about beer and sleep. Unfortunately I didn’t notice that I had named the stabilizer group that these two operators generated Sex. The subsequent accident jokes had a few people rolling in the aisles.
- Participated in a joint US/Australia NSF workshop in which I got to see Andrew White grill Australia’s Minister for Industry, Science and Resources(?) about education policy. During that trip I also got my finger stuck in an eye bolt when we were out on a cruise of Sydney Harbor, and had to get unstuck with the help of a stick of butter and an NSF program manager. Oh, and I also got kicked into a nightclub on that trip.
- Quantum Beer Night in Berkeley (at the Albatross) became Quantum Margarita Night at Caltech, where it made the list of top geek hangouts in Popular Science!
- I got to hear Cormac McCarthy tell stories during SFI tea time, and found out that he deeply understands Bell inequalities. Also at SFI I tied myself up to the corners of the lecture hall during a talk to demonstrate how SU(2) is related to the real world.
- Got sick of looking at the arXiv every morning and so crowdsourced the daily task of filtering these posts by creating the website scirate.com. Thank you people for doing so much filtering for me, you really have saved me a lot of time.
- Gave a talk at Bungie about quantum video games.
- Gave a talk in which I tried to sound like Martin Luther King Jr (BOMB)
- Gave a talk that involved the use of subwoofers and speakers (sadly the file for this got corrupted and I no longer have the talk.)
- Kept students amused during their exams by drawing cartoons:
- Bought an iPhone and realized that it was a pain to surf for papers on the arXiv, so wrote an iPhone app for browsing the arXiv, arXiview.
- Got a comment on my blog from a Nobel prize winner in physics.
- Was once the top hit for the word “pontiff” on google. Take that Beattles!
- Had a word stolen from me by Stephen Colbert: “Jesi.” Okay, well maybe not, but the ensuing discussion of the proper plural of Jesus is amusing.
Ah the things I’ve got to do. So far. Kind of makes me look forward to what kind of craziness is going to happen next 🙂
QSpeak Announcements for Week Ending 6/3/2011
- Summer School on “Quantum Information meets Statistical Mechanics”
======================================================================= ANNOUNCEMENT Summer School on “Quantum Information meets Statistical Mechanics” —- QI&SM 2011 —- Universidad Complutense de Madrid El Escorial (Madrid), Spain 11 – 15 July 2011 http://www.ucm.es/info/giccucm/Escorial2011 ======================================================================= The Summer School will take place at El Escorial, Spain (http://www.euroforum.es/), … Continue reading →
- QCRYPT Deadline Tomorrow
Dear Colleague, the submission server for contributed talks will close in a few days: *Deadline for Submission of Abstracts for Contributed Talks: June 1, 2011* QCRYPT will take place on September 12-16, 2011 at ETH Zurich. The conference will feature … Continue reading →
My Favorite D-Wave Future
As many of you know, D-Wave has a nice paper out about some experiments on one of their eight qubit systems. In addition they have sold one of their systems to the military industrial complex, a.k.a. Lockheed Martin.
One of the interesting things about the devices they are building is that no one really knows whether it will provide computational speedup over classical computers. In addition to the questions of whether adiabatic quantum algorithms will provide speedups for useful problems, there is also the question of how this speedup will be affected when working at finite temperature. If I were an investor this would worry me, but as a scientist I find the question fascinating and hope they can continue to push their system in interesting directions. Of course if I were an investor I’d probably be some multimillionaire who probably has an odd risk aversion profile 🙂
A fun question to ponder, at least for me, is what will eventually happen to D-wave, in, say, ten years. Of course there are the most obvious futures. They could run out of funding and close their doors as a device maker and sell their patent porfolio. They could succeed and build machines that do outperform classical computers on relevant hard combinatorial problems. Those two are obvious. BORING.
But my favorite scenario is as follows. D-wave continues to build larger and larger devices. At the same time they perform even more exhaustive testing of their system. And in the process they discover that there are “noise” sources that they hadn’t really expected. Not noise sources that violate quantum theory or anything, but instead noise sources that end up turning their stoquastic Hamiltonian into a non-stoquastic Hamilotnian. While no one knows how to use the Hamiltonian of D-wave’s machine to build a universal quantum computer, it is entirely possible that such a machine, plus some crazy extra unwanted terms could end up being universal. So while the company is squarely behind the dream of a combinatorial optimizer, it’s not at all impossible that their machine could accidentally be useful for universal adiabatic quantum computation (and of course whether this can be made fault-tolerant is still a major open question, at least for the models with non-degenerate ground states.) Wouldn’t it be hilarious if the noise which most people believe will destroy D-wave’s computational advantage actually turns their machine into a universal quantum computer? Ha!
So which will it be? And what odds will you give me on each of these possible futures?
Hoisted From the Comments: Quantum Marriage
Charlie Bennett comments about an novel use of quantum entanglement:
Tracy Staedter describes a quantum wedding apparatus built by conceptual artist Jonathon Keats, which briefly entangles two people by illuminating them with entangled photons. Staedter quotes Keats as saying the resulting quantum marriage would literally be broken up by skepticism about it.
http://news.discovery.com/tech/let-quantum-physics-officiate-your-wedding-110510.html
Speaking of which, who was it who introduced the idea of monogamy of entanglement?
(Anyone want to go into business selling a device which shoots entangled photons at you and a nearby person? “The Quantum Entangler” could be used to entangle you with that nearby hottie who you really want to get to know 🙂 )