Some confusing headlines:
Quantum Theory’s Release Date Now ‘TBA’
Quantum Theory Faces Delay Due to Quality Reasons
Quantum Theory Delayed
Recent Progress in Quantum Algorithms
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.)
Quantum Information Graduate Program at Waterloo
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.
Continue reading “Quantum Information Graduate Program at Waterloo”
NEC Summer Quantum Interns
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.
QIP Bloggers
People I’ve found who are blogging about QIP:
Did I miss anyone?
Update: Oh and look photos are already up photogallery for QIP
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
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 🙂
In Defense of D-wave
The Optimizer has gotten tired of everyone asking him about D-wave and gone and written a tirade about the subject. Like all of the optimizer’s stuff it’s a fun read. But, and of course I’m about to get tomatoes thrown on me for saying this, I have to say that I disagree with Scott’s assessment of the situation. (**Ducks** Mmm, tomato goo.) Further while I agree that people should stop bothering Scott about D-wave (I mean the dudes an assistant professor at an institution known for devouring these beasts for breakfast), I personally think the question of whether or not D-wave will succeed is one of the most important and interesting questions in quantum computing. The fact that we interface with this black box of a company via press releases, an occasional paper, and blog posts at rose blog, for me, makes it all the funner! Plus my father was a lawyer, so if you can’t argue the other side of the argument, well you’re not having any fun! So, in defense of D-wave…
Continue reading “In Defense of D-wave”