Posters For Some, Minature American Flags for Others

“Ideal conversation must be an exchange of thought, and not, as many of those who worry most about their shortcomings believe, an eloquent exhibition of wit or oratory”
– Emily Post(er)

As a literature major physicist, one of the biggest culture shocks I’ve encountered when attending theory computer science conferences (STOC and FOCS) is the lack of a poster session at these conferences (or at least the ones I attended, which, truth be told, is not many.) Admittedly, I’m a sucker for free wine, beer, and cheese (or at least a cash bar peoples) and some of my warmest thoughts are of the science projects I did growing up (though I still think my eighth grade project was wrongly not awarded grand prize because the judges didn’t think I could have done the project.) But truthfully, I think I get more out of posters at conferences than most of the talks. And, in some deep sense, I find the lack of a poster session at these conferences nearly…anti-scientific. There. I’ve said it. Anti-scientific, Pontiff? Really? Well yeah I am prone to hyperbole.
Yes, I know that getting a paper into a top CS theory conference is the mark of acceptance and praise and “yes you are one of us” for the theoretical computer science community. And while I think that this system is inherently troubling for a few reasons, it doesn’t disturb me nearly as much as the suppression of ideas which are just “not good enough” or “too far on the fringe.” As far as I can tell, the inclusion of a poster session is strictly a positive: it gives students chance to discuss their work, it encourages breadth for a conference by allowing in submissions that might not fit with what is “in” at the moment, it is perhaps the best place I know to start a collaboration, and it encourages civil discussion of results that are…wrong.
Which brings me to my final point. I’ve been on the QIP program committee for two years now, and blessedly QIP does have a poster session (perhaps due to its hybrid nature combining physics and computer science.) This is great…for example in Santa Fe last year I learned about some very cool work the Dorit Aharonov and collaborators were doing from her poster (and a yelling match we had driving from ABQ to Santa Fe :)) as well as about some new results on the hidden subgroup problem over the Heisenberg group (okay I’ll admit that one is only really exciting to me!) In the course of these years we have, on the program committee, rejected posters from the conference. Now there are certain reason why I can imagine doing this, but it doesn’t really make me happy. For me, the only reason why one should reject a poster is that the poster should be off topic. For posters, because they’re just posters, damnit, I don’t even use the requirement that the paper is correct (sorry.) If QIP gets a paper on nonlinear fluid dynamics, then certainly reject the poster, but if you get a poster on P=NP? I say accept it as a poster (and I mean, it could be useful for the author to hear repeatedly why he or she is incorrect.)
So, if the QIP business meeting gets boring, and you want to stir up some debate, I suggest that someone raise the following question: what are our standards for poster session and are they ones that the conference should have? This might be especially relevant for QIP, which is increasingly computer science oriented (I said increasingly, not solely), and where there are certainly, say, implementation papers, that might get rejected (and I would argue they should be accepted: the beauty of quantum information science it’s crossing disciplines, and to cut of completely one discipline is like chopping your arm off.)
(One interesting issue for QIP is that for posters one submits the same 3 page brief note about the research that speakers submit. In most physics conferences when you submit a poster all you submit is an abstract, from which it is nearly impossible to judge whether the work is relevant/correct and so more posters are included.)
So, posters for all, says this scientific popularist.

QIP Talks That Have arXiv Papers

QIP 2010 talks and associated papers if I could find them (amazing how almost all papers for this conference are available, for free, online at one location….also interesting how papers seem to cluster in the 10-12 months of the listings 🙂 ) If anyone has corrections please leave a comment.

Monday

  • Daniel Gottesman and Sandy Irani
    The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems
    arXiv:0905.2419
  • Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang
    On the power of a unique quantum witness
    arXiv:0906.4425
  • Scott Aaronson and Andrew Drucker
    A full characterization of quantum advice
    No paper found
  • Rahul Jain (invited talk)
    QIP = PSPACE
    arXiv:0907.4737
  • Antonio Acin, Antoine Boyer de la Giroday, Serge Massar, and Stefano Pironio
    Random numbers certified by Bell’s theorem
    arXiv:0911.3427
  • Dave Bacon and Steve Flammia
    Adiabatic gate teleportation
    arXiv:0905.0901 (see also arXiv:0912.2098)

Tuesday

  • Ben Reichardt (invited talk)
    Span programs and quantum algorithms
    A series of papers, including the 70 pager arXiv:0904.2759
  • David Gross, Yi-Kai Liu, Steven Flammia, Stephen Becker, and Jens Eisert
    Non-commutative compressed sensing: theory and applications for quantum tomography
    arXiv:0909.3304 (see also the followup arXiv:0910.1879 update: and the paper referred to in David’s talk as arXiv.to.day arXiv:1001.2738)
  • Norbert Schuch, J. Ignacio Cirac, Dorit Aharonov, Itai Arad, and Sandy Irani
    An efficient algorithm for finding Matrix Product ground states
    arXiv:0910.5055 and arXiv:0910.4264
  • Dominic W. Berry and Andrew M. Childs
    The query complexity of Hamiltonian simulation and unitary implementation
    arXiv:0910.4157
  • Maarten Van den Nest
    Simulating quantum computers with probabilistic methods
    arXiv:0911.1624
  • Philippe Corboz (invited talk)
    Simulation of fermionic lattice models in two dimensions with tensor network algorithms
    arXiv:0912.0646
  • Boris Altshuler, Hari Krovi, and Jérémie Roland
    Adiabatic quantum optimization fails for random instances of NP-complete problems
    arXiv:0908.2782
  • Kristan Temme, Tobias Osborne, Karl Gerd Vollbrecht, David Poulin, and Frank Verstraete
    Quantum metropolis sampling
    arXiv:0911.3635
  • Sergey Bravyi, David Poulin, and Barbara Terhal
    Tradeoffs for reliable quantum information storage in 2D systems
    arXiv:0909.5200

Wednesday

  • André Chailloux (invited talk)
    Quantum coin flipping
    arXiv:0904.1511
  • Matthias Christandl, Norbert Schuch, and Andreas Winter
    Highly entangled states with almost no secrecy
    arXiv:0910.4151
  • Anindya De and Thomas Vidick
    Improved extractors against bounded quantum storage
    arXiv:0911.4680
  • Ivan Damgård, Serge Fehr, Carolin Lunemann, Louis Salvail, and Christian Schaffner
    Improving the security of quantum protocols via commit-and-open
    arXiv:0902.3918
  • Robert Koenig, Stephanie Wehner, and Juerg Wullschleger
    Unconditional security from noisy quantum storage
    arXiv:0906.1030 and arXiv:0911.2302
  • Pablo Arrighi, Vincent Nesme, and Reinhard Werner
    Unitarity plus causality implies localizability
    arXiv:0711.3975

Thursday

  • Aram Harrow (invited talk)
    Quantum algorithms for linear systems of equations
    arXiv:0811.3171
  • Stefano Chesi, Beat Röthlisberger, Daniel Loss, Sergey Bravyi, and Barbara M. Terhal
    Stability of topological quantum memories in contact with a thermal bath
    arXiv:0907.2807
  • Robert Koenig, Greg Kuperberg, and Ben Reichardt
    Quantum computation with Turaev-Viro codes
    No paper found
  • Mark Howard and Wim van Dam
    Tight noise thresholds for quantum computation with perfect stabilizer operations
    arXiv:0907.3189
  • Prabha Mandayam and Hui Khoon Ng
    A simple approach to approximate quantum error correction
    arXiv:0909.0931
  • Sergey Bravyi, Cristopher Moore, Alexander Russell, Christopher Laumann, Andreas Läuchli, Roderich Moessner, Antonello Scardicchio, and Shivaji Sondhi
    Random quantum satisfiability: statistical mechanics of disordered quantum optimization
    arXiv:0903.1904 and arXiv:0907.1297
  • Julia Kempe (invited talk)
    A quantum Lov√°sz Local Lemma
    arXiv:0911.1696

Friday

  • Marcin Pawlowski
    Information causality
    arXiv:0905.2292
  • Salman Beigi, Sergio Boixo, Matthew Elliot, and Stephanie Wehner
    Local quantum measurement and relativity imply quantum correlations
    arXiv:0910.3952
  • David Gross, Markus Mueller, Roger Colbeck, and Oscar Dahlsten
    All reversible dynamics in maximally non-local theories are trivial
    arXiv:0910.1840
  • Michael Wolf, David Perez-Garcia, and Carlos Fernandez
    Measurements incompatible in quantum theory cannot be measured jointly in any other no-signaling theory
    arXiv:0905.2998
  • Toby Cubitt, Jens Eisert, and Michael Wolf
    Laying the quantum and classical embedding problems to rest
    arXiv:0908.2128
  • Salman Beigi, Peter Shor, and John Watrous
    Quantum interactive proofs with short messages
    No paper found.
  • Scott Aaronson (invited talk)
    New evidence that quantum mechanics is hard to simulate on classical computers
    No paper found.
  • Julia Kempe and Oded Regev
    No strong parallel repetition with entangled and non-signaling provers
    arXiv:0911.0201
  • Toby Cubitt, Debbie Leung, William Matthews, and Andreas Winter
    Zero-error channel capacity and simulation assisted by non-local correlations
    arXiv:0911.5300
  • Jianxin Chen, Toby Cubitt, Aram Harrow, and Graeme Smith
    Super-duper-activation of the zero-error quantum capacity
    arXiv:0906.2547 and arXiv:0912.2737

Bacon Brains

Jorge sends along an almost timely piece:

The traditional English breakfast is not normally associated with good health.
But scientists have found that eating a plate of bacon and eggs could help pregnant women boost the intelligence of their unborn child.
Women are usually given a list of foods to avoid during pregnancy and it is well documented that a pregnant woman’s diet can affect her unborn baby.
Scientists have found that eating a plate of bacon and eggs could help pregnant women boost the intelligence of their unborn child

Does baby Bacon get the benefits by just being a Bacon? (When I was growing up every time we had bacon my father would say “check your toes!”)

Entangled in the Membrane, Entangled in the Brain?

Bad New Scientist has an article up today entitled Brain ‘entanglement’ could explain memories, which certainly must have sent Roger Penrose’s brain into a state of multiple correlated back-flips (twistor flips?) However, from the article:

Subatomic particles do it. Now the observation that groups of brain cells seem to have their own version of quantum entanglement, or “spooky action at a distance”, could help explain how our minds combine experiences from many different senses into one memory.

First of all, damnit New Scientist, entanglement is not just between “subatomic particles.” Second of all, the effect described is as similar to spooky action at a distance as the fact that when you look at my feet you’ll most likely see that I have the same color sock on both of my feet. To suggest that the effect described in this PLOS biology paper where they observed correlated local field potential mesurements in a monkey’s brain has got anything to do with quantum entanglement is…well…just plain wrong.
(Which is not to say that quantum effects might not arise in the brain: we simply don’t have any evidence of such effects and speculations about such effects arising are, so far, physically implausible. I.e. that’s how a scientist says: probably not, but I’m always ready to change my opinion with some good hard evidence.)

arXiv Funding

Missed this over the break: a facebook note about the future of funding of the arXiv. The post points to two documents of interest, the first a statement about support:

…We intend to establish a collaborative business model that will engage the institutions that benefit most from arXiv — academic institutions, research centers and government labs — by asking them for voluntary contributions.

and also a handy dandy FAQ about the changes.

On the Turing Away

“The miracle of the appropriateness of the language of mathematics for the formulation of the laws of physics is a wonderful gift which we neither understand nor deserve.”
E. P. Wigner

Our universe, or at least our understanding of the universe, appears to allow us to see its naked underbelly only through the use of mathematical reasoning. As Wigner says about this state of affairs, we neither understand nor deserve this. On the other hand, I’ve come to believe, this observation can also be a huge aid in describing the world of theoretical computer science. There is no doubt in most people’s opinion that theoretical computer science is mathematics of a highly sophisticated nature (or, well, sophisticated to this lowly physicist.) But theoretical computer science, unlike pure mathematics unfettered in its abstract glory, at its core must be concerned with the practical applicability of its reasoning. Here by practical I do not mean contributing to the better good of software development (though this may be important for the well being, read salary, of the practioners) but that at its core theoretical computer science must be about computers that exist in the real world. On the one hand, this observation leads direction to quantum computing. To paraphrase Feynman: the universe is quantum, damnit, so we better make our models of computing quantum. But it also should influence even our most basic classical computational models. In this vein, then, I would like to attack one of the most sacred holy cows of computer science, the holy mother cow of them all, the Turing machine.
Continue reading “On the Turing Away”

QIP 2010 Coming Up

As you can imagine, due to extenuating circumstances, I won’t be able to attend QIP in Zurich. Luckily my collaborator Steve Flammia will be there to give the talk on our recent work on adiabatic protocols (arXiv:0905.0901 and arXiv:0912.2098.) I know there will probably be a few bloggers attending QIP, but if anyone is interested in making guest posts here on the Pontiff about the conference (anonymously, using your real name, or any combination thereof) please send me an email (see contact tab above).
Anyone know if the conference talks will be taped? Enjoy Zurich all, but make sure to bring enough money 🙂

Quantum Cartoons

Richard, a long while back (yes, I’m cleaning my inbox!), sent me some cartoons that were apparently floating around in the 70s when he did his BS in Chemistry that are quite amusing:

Everday Orthogonality

Another one from Michael, who spotted an article about one of my favorite mathematical words to use in everyday speech (much the chagrin of non-scientists) used in the Supereme Court of the United States:

Supreme Court justices deal in words, and they are always on the lookout for new ones.
University of Michigan law professor Richard D. Friedman discovered that Monday when he answered a question from Justice Anthony M. Kennedy, but added that it was “entirely orthogonal” to the argument he was making in Briscoe v. Virginia.
Friedman attempted to move on, but Chief Justice John G. Roberts Jr. stopped him.
“I’m sorry,” Roberts said. “Entirely what?”
“Orthogonal,” Friedman repeated, and then defined the word: “Right angle. Unrelated. Irrelevant.”
“Oh,” Roberts replied.

“What was that adjective?” Scalia asked Monday. “I liked that.”
“Orthogonal,” Friedman said.
“Orthogonal,” Roberts said.
“Orthogonal,” Scalia said. “Ooh.”
Friedman seemed to start to regret the whole thing, saying the use of the word was “a bit of professorship creeping in, I suppose,” but Scalia was happy.
“I think we should use that in the opinion,” he said.
“Or the dissent,” added Roberts, who in this case was in rare disagreement with Scalia.

Of course last time I commented on using mathematical words outside of their natural habitat it spawned a comment thread with over 2000 comments.
Other favorites that I like to sneak into casual conversation are “canonical”, “dual”, and “asymptotic.” Other good scientific / math words that you like to use in everyday conversation?

Childish QKD

Michael sends along an entry in the best title ever competition, this time a special baby Bacon edition:

The pulse wave arrival time (QKd interval) in normal children
The Journal of Pediatrics, Volume 95, Issue 5, Pages 716-721
B. Bercu, R. Haupt, R. Johnsonbaugh, D. Rodbard

“In this household, young man, we will keep our quantum key distribution pulses above the rate of 1000 keys per second!”