The Quantum Pontiff

Handwriting to LaTeX?

Thu, 04 Feb 2010 12:50:11 -0500

Anyone tried out MoboMath?

MoboMath lets you work with math on a computer exactly as you learned it -- by writing it. MoboMath translates your handwritten math input into a formatted layout that can be used in Microsoft Word, Maple, and many other popular applications.

Instead of struggling with keyboard and palette input, you can create and edit math expressions for technical documents, calculations, presentations, and web pages in your own handwriting. It's fast, simple, and intuitive.

Using a tablet PC or an external tablet, just write your expressions as you normally would with your tablet's pen. Then convert them to a formatted math layout with a single tap and copy or drag them into your documents or worksheets.

Don't have a tablet right now or I'd test it out.

Read the comments on this post...

Bacon Misc

Wed, 03 Feb 2010 12:36:20 -0500

Jorge and Mark send along some Bacon news:

NSFW: Effects of Bacon on Male Performance. Nuff said.

Bacon and Egg Sandwiches are the best. Ruminations
Bacon deserts. Mmm bacon toffee truffles.

Read the comments on this post...

Recent Progress in Quantum Algorithms

Mon, 01 Feb 2010 15:11:51 -0500

Shameless self-promotion: an article I wrote with Wim van Dam, "Recent Progress on Quantum Algorithms" has appeared in the Communications of the ACM. Indeed if you have a copy of the magazine you can check out an artists rendition of a quantum computer/quantum algorithm on the cover. Clearly quantum computing is the new string theory: so abstract that it must be represented by beautiful, yet incomprehensible, figures. Not sure if that's a good or bad thing. (The article was actually written quite a bit back, so "recent" is a bit off. If we had to write it today I'm guessing we would include the quantum algorithm for linear equations as well as the quantum Metropolis algorithm.)

Read the comments on this post...

Quantum Information Graduate Program at Waterloo

Fri, 29 Jan 2010 15:30:45 -0500

The University of Waterloo is adding a quantum information graduate program, one step closer to being able to get a Ph.D. purely in quantum information. Application details here. Description of the program below the fold.

Read the rest of this post... | Read the comments on this post...

NEC Summer Quantum Interns

Thu, 28 Jan 2010 12:51:17 -0500

Martin passes along information that the quantum group at NEC labs has openings for summer interns:

I wanted to let you know that the quantum group at NEC Labs America has openings for 2010 summer internships. If some of your students are interested, please refer them to
http://www.nec-labs.com/careers/internship.php
A typical duration of a summer internship is three months (end of May-end of August in most cases, but this is quite flexible). The compensation will be competitive with other industrial internships. We will start looking at resumes around February 15.

If you are interested in quantum algorithms or quantum error correcting codes, this is an incredible opportunity.

Read the comments on this post...

You Might Be a Theorist

Tue, 26 Jan 2010 18:30:54 -0500

If your work productivity is shaped by the type of pen you are currently using:

Read the comments on this post...

Some Wonderful Magical Animal

Mon, 25 Jan 2010 12:47:55 -0500

An entire world made of bacon and cold cuts (thanks Jorge) "Mmm ... unexplained bacon"

Read the comments on this post...

@dabacon Shameless Self-Promotion

Tue, 19 Jan 2010 14:49:21 -0500

The Shorty Awards have a category called "bacon." Your vote for @dabacon will, I promise, result in a great increase in your pork-based karma. And voting doesn't even clog your arteries!

Read the comments on this post...

QIP Bloggers

Mon, 18 Jan 2010 15:10:13 -0500

People I've found who are blogging about QIP:

Did I miss anyone?

Update: Oh and look photos are already up photogallery for QIP

Read the comments on this post...

Posters For Some, Minature American Flags for Others

Mon, 18 Jan 2010 13:27:06 -0500

"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.

Read the comments on this post...

QIP Talks That Have arXiv Papers

Fri, 15 Jan 2010 18:19:58 -0500

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

Read the comments on this post...

Bacon Brains

Thu, 14 Jan 2010 12:54:21 -0500

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!")

Read the comments on this post...

Entangled in the Membrane, Entangled in the Brain?

Wed, 13 Jan 2010 18:34:39 -0500

~~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.)

Read the comments on this post...

arXiv Funding

Wed, 13 Jan 2010 18:06:38 -0500

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.

Read the comments on this post...

On the Turing Away

Wed, 13 Jan 2010 14:29:54 -0500

"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. Read the rest of this post... | Read the comments on this post...