David sends me an article about $200 million spent to recruit 19 researchers to Canada via a program called the Canada Excellence Research Chairs. Two of these positions are, not too surprisingly, in quantum computing/communication: David Cory (formerly from MIT, now at Waterloo) and Bertrand Reulet (formerly from Université Paris-Sud XI, now at Université de Sherbrooke) Congrats to these two for receiving these chairs! Programs like this are always interesting and it will be fascinating to see how effective they are over time.
In related news, there is no such program in the United States. 🙂
Lidar Interview
Here’s an interview with Daniel Lidar whose was the postdoc who first taught me quantum error correction (and more.) No, not that LIDAR!
Note to all you job seekers, even in your darkest hours know that you have friends out there who are working to change the abysmal state of quantum computing hiring:
I would also hope to see a wave of new faculty positions at US institutions for quantum computation theoreticians and experimentalists. We now have the first generation of students and postdocs trained in this field, many of whom are finding it very difficult to land faculty positions in the US, and are forced to seek such employment in other countries. This is most unfortunate, and I hope that US universities will reverse this trend.
Quantum Hustles
Over at masteroftheuniverse, the master has posted a great list of prop bets. Among his bets is one that probably won’t work on many computer scientists (or it shouldn’t if they’ve had even a decent theory course) based upon the birthday problem. Sometimes the birthday problem is called the birthday paradox, but the problem is no more a paradox than the twin paradox is about twins. The birthday problem has to do with the probability that a set of randomly drawn people share a birthday. In other words, assuming that everyone in a group of N people has an equal probability of being born on a given day, what is the probability that at least two of these people share a birthday. Quite surprisingly, or at least surprising the first time you hear it, is that if N is 23, this probability is already greater than 50 percent. In computer science this type of process comes up all the time and is responsible for lots of square roots that one sees in running times of algorithms. The master’s blog post reminded me of a version of the birthday paradox that Wim van Dam once told me (if anyone knows its past history, please post a comment)…a quantum birthday paradox.
Here is the setup. Suppose that we are sampling from the set . In particular consider the situation, classically, where we are sampling from two distributions over this set, and . Both and are distributions which are on exactly N of the elements of and 0 on the rest of . I will guarantee you that either the distributions are equal, , or that when has weight on an element, then has weight 0. In other words, the probability vectors for these distributions are orthogonal, so I will denote this . So the problem is, given the ability to classically sample from these distributions, how many samples must one take to succeed in identifying which of these two cases, or , hold. One can easily see that this probability is like the birthday problem: by sampling from and one has to basically wait for a collision in order to determine that . Thus you can see that it would require about samples to distinguish these two cases. More specifically, to distinguish between these two cases with some constant probability, say a probability of 3/4, we need to sample times.
Okay so what does this have to do with a quantum birthday paradox. Well now consider the situation where instead being given two probability distributions and , one is given two quantum states, and , with the property that if you simply measure them in the computational basis you will obtain the classical distribution that behave like and . That is let and be superpositions over 2N computational basis states with the property that in this basis, they have exactly N amplitudes which are and N amplitudes which are zero. We are guaranteed that either or and the goal is, by using many copies of and to distinguish between these two cases. Now if one simply measures these states in the computational basis then one obtains probability distributions that are exactly like and . But this is the quantum world, so we don’t have to measure in this basis. So is there a basis that we can measure in which can lead to using less that copies of and to distinguish the two cases of versus ?
The answer is yes, indeed. Of course that’s the answer: why else would I be writing this blog post. In particular consider the fully symmetric or anti-symmetric subspaces of the two systems. In particular, define the states
if
if
and
if
These states form a complete basis for the two systems we are considering, with the states representing symmetric states and the states representing the anti-symmetric states. Suppose that on and we measure the above states. Now if , then we note that is symmetric under exchange of the two states subsystem. That is if we measure the above basis states we will only obtain basis states. If, on the other hand then it is straightforward to see that has support equally on symmetric and anti-symmetric states. In particular if
and
where , then we can expand as
From which we can see that we will obtain the symmetric and anti-symmetric states with equal probability.
Thus we have seen that by making a measurement which distinguishes between the symmetric and antisymmetric subspaces of our two systems, if we will only observe symmetric states and if we will observe symmetric states half the time and anti-symmetric states the other half the time. Thus we can reliably distinguish these two cases with a failure probability of for k repetitions of this setup. This is significantly better from the classical case! Indeed we have succeeded in distinguishing the states with probability 3/4 using only 2 repetitions of the setup. Thus we have gone from in the classical world to in the quantum world. Amazing! (Of course many will argue the setup is not fair: and yes I agree it is not fair when one side gets to use this powerful thing called quantum theory and the other side hides behind the computer science of the 20th century 🙂 ) Many of you will recognize that the above method for distinguishing states is nothing more than the quantum swap test.
So what is the moral of all this? Well, besides showing a cool case where quantum exponentially outperforms classical, it also tells you that you should be wary of quantum computers offering you bets. Indeed, I make it my own personal policy never to bet with quantum computers, and think that you should make it your policy as well.
March Meeting Quantum Computing Schedule
The APS March meeting is next week as 10000 physicists invade Portland, Oregon. I hope Powell’s bookstore has stocked their science sections well! GQI, the topical group on quantum information, sponsors a good number of sessions at the meeting including sessions with invited talks, focus sessions, and general sessions. Below the fold I’m assembling a list of quantum computing sessions, but before the fold I’d like to point out the invited sessions, which have longer speaking slots where one can actually learn more than the speakers name and research project title, that are sponsored or cosponsored by GQI (also below note the Focus sessions listed below have invited speakers)
- Monday, March 15 8:00am-11:00am Session A8: Quantum Opto-Mechanics
Room: Portland Ballroom 255
(Jointly sponsored with DAMOP)
Invited speakers: Jack Harris, Klemens Hammerer, Philipp Treutlein, Nathaniel Brahms, Keith Schwab - Monday, March 15 11:15am-2:15pm Session B6: Controlling Dissipation in Quantum Systems
Room: Portland Ballroom 253
(Jointly sponsored with DAMOP)
Invited Speakers: Frank Verstraete, Hans Peter Buechler, Matthias Lettner, Luis A. Orozco, Sergio Boixo - Monday, March 15 2:30pm-5:30pm Session D4: Quantum Computer Science
Room: Oregon Ballroom 204 Invited Speakers: Graeme Smith, Aram Harrow, Ben Reichardt, Sandy Irani, Stephanie Wehner - Thursday, March 18 11:15am-1:40pm Session W6: Superconducting Qubits
Room: Portland Ballroom 253
Invited Speakers: Radoslaw Bialczak, Franco Nori, Leonardo DiCarlo, Sahel Ashhab
Quantum Computing Postdoc at LPS
A theoretical condensed matter postdoc of interest to the quantum computing folks:
Postdoctoral Research Fellow in Theoretical Condensed Matter and Quantum Information Science at the Laboratory for Physical Sciences, University of Maryland.
Applications are being accepted for physics postdoctoral research positions in quantum information and device theory at the Laboratory for Physical Sciences (LPS) at the University of Maryland-College Park. Demonstrated expertise in one or more of the following categories is desired: semiconductor/condensed-matter physics, solid-state quantum computing (e.g. spins in semiconductors or diamond, superconductors, etc.), quantum information science, many-body condensed matter physics, simulation of quantum systems, computational physics, quantum error correction/prevention, quantum optics, and related subjects.
Positions are available immediately in the groups of Drs. Frank Gaitan, Ari Mizel, and Charles Tahan. Interested candidates are invited to seek more information or submit an electronic application addressed to Charles Tahan at ctahan [thisisanatsybol] lps.umd.edu. Applications should include a CV, a summary of research interests, publications list, and the electronic (email) contact details of two references.
The University of Maryland is an Affirmative Action/Equal Opportunity employer and particularly welcomes applications from women and members of minority groups.
QUANTUM COMPUTING AT LPS
The quantum computing group at LPS consists of both experimentalists and theorists focused on various aspects of solid-state quantum computers, condensed matter theory, and quantum information science. Opportunities to collaborate with researchers at the University of Maryland Physics Department, the Joint Quantum Institute, nearby NIST and NRL are ample.
ABOUT THE LABORATORY FOR PHYSICAL SCIENCES
Located adjacent to the University of Maryland’s College Park Campus, the Laboratory for Physical Sciences is a unique facility where university and federal government personnel collaborate on research in advanced communication and computer technologies. The Lab for Physical Sciences is also a member of the Joint Quantum Institute together with NIST and UMD.
Must Resist Joke Blog Post Title
Quantum Dating Market
Authors: O.G. Zabaleta, C.M. Arizmendi
Abstract: We consider the dating market decision problem under the quantum mechanics point of view. Quantum states whose associated amplitudes are modified by men strategies are used to represent women. Grover quantum search algorithm is used as a playing strategy. Success is more frequently obtained by playing quantum than playing classic.
Quantum Citation Survey
Thomson Reuter’s website Sciencewatch.com has a special section out on citation and paper data for the last ten years of quantum computing. More below the fold.
Continue reading “Quantum Citation Survey”
Some Quantum Events
Summer school:
We would like to inform you of the upcoming 10th Canadian Summer School on Quantum Information & Research Workshop.
Save the dates: July 17-30, 2010
Location: University of British Columbia, Vancouver, BC
For more information, visit our website: qi10.ca
Contact us: info [atatat] qi10.ca
This summer school on quantum information marks the 10th anniversary of the highly renowned series. This year the emphasis will be on quantum algorithms and models of quantum computation, with particular attention to mathematical methods. This summer school also includes a research workshop on quantum algorithms, computational models, and foundations of quantum mechanics, held during July 23 – 25. We would appreciate that you help to disseminate the information of this event to your colleauges, postdocs and students.
Confirmed speakers include:
* Boris Altshuler, Columbia University, New York, NY, USA
* Hans J. Briegel, Universität Innsbruck, Innsbruck, Austria
* Daniel E. Browne, University College London, UK
* Andrew Childs, University of Waterloo, Canada
* Steve Flammia,Perimeter Institute, Waterloo, ON, Canada
* Chris Godsil, University of Waterloo, Canada
* Daniel Gottesman, Perimeter Institute, Waterloo, ON, Canada
* Daniel Lidar, University of Southern California, Los Angeles, CA, USA
* Maarten van den Nest, Max-Planck-Institut für Quantenoptik, Garching, Germany
* David Poulin,Université de Sherbrooke, Sherbrooke, QC, Canada
* Frank Verstraete, Universität Wien, Austria
* Pawel Wocjan, University of Central Florida, Orlando, FL, USA
Please feel free to contact us if you have questions regarding the summer school and research workshop. For more information, visit our website at qi10.ca, or give us an email at info [at at at] qi10.ca.
Conference in Austria…looks like a very scenic location:
I would like to draw your attention to the upcoming ESF-FWF-LFUI Conference on Quantum Engineering of States and Devices, which will be held in Obergurgl, Austria, 5-10 June 2010.
The full conference programme is accessible online from http://www.esf.org/conferences/10312 and the closing date for applications is on 14 March.
SquINT 2010
The twelfth annual SqUINt conference is being held this week and unfortunately I’m missing my favorite conference (though a gaggle of grad students have been sent Santa Fe bound.) The schedule looks really good this year including a great list of invited speakers (Scott Aaronson (MIT), Rainer Blatt (Innsbruck), Matt Hastings (Station Q), Dieter Meschede (Bonn), Keith Schwab (Caltech), and John Watrous (Waterloo)). Notice the awesome mix of theory and experiment…good stuff. Hope everyone who is attending is having a fantastic time: have some green chiles for me please.
QIP Talks
It looks like the talks for QIP 2010 are now online.. Sweet, my television for the next few weeks. Well okay the Olympics may sneak in there (and jez NBC really stinks it up: I’ve never seen a network make men’s downhill so boring…if you’re going to short the west coast by not showing the events live don’t you have a responsibility to at least do a good job? Please, please, Olympic committee let ESPN get the next contract.)