Daniel Gottesman!
Quantum Book
Somewhere along the line I missed that Susan Loepp and William Wootters’ book on quantum cryptography, quantum computation, and quantum error correction had been published. Protecting Information: From Classical Error Correction to Quantum Cryptography
Postdocs Obey a Perimeter Law?
Postdocs, postdocs, everywhere and not a faculty job to seek (just kidding….or am I 😉 )
Institute for Quantum Computing, University of Waterloo
Applications are invited for postdoctoral positions in any area of quantum information. The starting date of the appointment is open.
A Ph.D. and proven ability, or the potential, for excellent research is required. Successful candidates will be joining a substantial research and training centre in quantum information at Institute for Quantum Computing (IQC). Information about IQC personnel and activities can be found at www.iqc.ca. The IQC is based at the University of Waterloo, and includes, at present, more than a dozen researchers from the Faculties of Engineering, Mathematics and Science. The candidates will also have the opportunity to interact with scientists at the nearby Perimeter Institute for Theoretical Physics, and UW’s Centre for Applied Cryptographic Research.
If interested please go to our application form on-line. https://www.iqc.ca/positions/postdocapp/postdocapp.php
The deadline for receiving applications is 15 November 2006.
Applications may be processed as they are received. Late applications will be accepted as long as positions are still available.
and, hoisted from the comments,
Perimeter Institute for Theoretical Physics is seeking postdoctoral applicants in the areas of:
o Quantum Information Theory
o Quantum Gravity
o String Theory
o Cosmology
o Foundations of Quantum Theory
o Condensed Matter Physics
o Elementary Particle Physics
Perimeter Institute is located in Waterloo, Ontario, Canada and offers a dynamic, multi-disciplinary research environment with much freedom. Successful candidates will benefit from mentorship by Faculty, ability to invite visitors, opportunity to organize innovative conferences and workshops, access to substantive travel funds, supervision of students, optional participation in scientific committees, assistance from PI’s administrative team, as well as enjoying the productive research atmosphere and amenities of the award winning facility.
The postdoctoral positions are normally for a period of three years. Outstanding candidates may also be considered for a senior postdoctoral position with a five-year term. Exceptional applicants are encouraged to apply by November 15th, 2006. Full details and application forms are available at www.perimeterinstitute.ca.
The Institute is presently staffed with 61 resident researchers including 10 Faculty and 8 Associate Members. Currently, there is a complement of 28 Postdoctoral Researchers and a very active Visitor Program including 15 Long Term Visitors with expectations of hosting some 300 scientists throughout this academic year. A list of Visitors and other researchers is available at www.perimeterinstitute.ca/people/
Help feed the blackberry hole!
Measurement-Based Conference
The fact that you can perform unitary quantum evolutions using simple (adaptive) measurements is, to a physicist, an unexpected result. Indeed, it could be that there is no unitary evolution in the universe, only measurements! If you’re interested in measurement based quantum computing, you might be interested in conference advertised below:
International Workshop on Measurement-based Quantum Computation (MBQC07)
St. John’s College, Oxford
18 – 21 March 2007
http://www.qunat.org/workshop/
Measurement-based quantum computing (MBQC) is an active and rapidly growing area of research. The formalism of graph states (or cluster states) has proven to be a powerful way of describing the essential entanglement resources needed to perform quantum information processing tasks. Initially conceived for systems such as optical lattices and linear optical computing, this theory is now shaping the latest experimental proposals across the full spectrum of QIP technologies. A key theme of this workshop will be to foster dialog between theoreticians involved in MBQC and the experimentalists who are positioned to embrace and implement the new ideas.
Registration is open until November 30th and the number of participants will be limited to 50.
SFI Postdocs
This is a bit late being posted, but the Santa Fe Institute is running their postdoc search this year. SFI has always had a running interesting the border between physics and computer science and was even crazy enough to hire a crazy theorist like me as a postdoc. Oh, how I miss those green chiles. Here is the information for the positions, which I highly recommend quantum computing people to consider as an option. Plus you’ll get to live in New Mexico and eat lots of awesome New Mexican food and go skiing at the ever awesome Taos ski area (not to mention that the UNM and Los Alamos quantum computing groups are but a short drive away):
POSTDOCTORAL FELLOWSHIP OPPORTUNITIES
The Santa Fe Institute (SFI) anticipates offering several Postdoctoral Fellowships to begin in September 2007.
The Postdoctoral Fellowship program provides up to three years of support for independent research at SFI. Postdoctoral Fellows are encouraged to engage research questions of their own design, and to form collaborations with members of the faculty, other SFI postdocs, and researchers from around the world. Fellows pursue research that lies at the boundaries of the traditional academic disciplines, and that creates new fields of inquiry.
In addition to salary, health benefits, and retirement contributions, Fellows have access to funds to support travel to meetings, to visit collaborators at other institutions, and to bring collaborators to visit SFI. Fellows are encouraged to participate in all SFI activities, to invite speakers for the colloquium series, and to organize workshops and working groups.
Research at SFI is integrative, and there are no formal programs or departments. Individual research projects draw input from a variety of fields, including biology, chemistry, computer science, physics, mathematics, economics, sociology, anthropology, and political science. We welcome applications from any of these fields, as well as others not listed here. Descriptions of the research interests of the faculty and current Postdoctoral Fellows can be found at http://www.santafe.edu/research/researchers.php. Most research at SFI focuses on theoretical and computational approaches, although applicants whose research includes an experimental or data-collection component in collaboration with off-site colleagues are also encouraged to apply.
Candidates should have a Ph.D. (or expect to receive one by September 2007), a strong academic record, and a proven ability to work independently. We are particularly favorable toward applicants with an interest in trans-disciplinary interactions and collaboration, and who have demonstrated the potential to think outside traditional paradigms.
Applications are welcome from candidates in any country. Women and minorities are especially encouraged to apply. Successful foreign applicants must acquire an acceptable visa (usually a J-1) as a condition of employment
TO APPLY: Please view the full position announcement and application instructions at http://www.santafe.edu/education/postdocinst07.php. For full consideration, please submit all application materials, including three letters of recommendation, by November 15, 2006. For further information, please e-mail postdocinfo[at]santafe.edu.
QIP 2007 Deadlines Approaching
Michel Nielsen passes along and email detailing the fact that the deadlines for QIP 2007, to be held in Brisbane, Australia, are fast approaching:
QIP 2007
The tenth QIP (Quantum Information Processing) Workshop is to be held in
Brisbane, Australia, from January 30 through February 3, 2007. QIP covers
theoretical aspects of quantum information science, including quantum
computing, quantum cryptography, and quantum information theory.
The deadline for abstract submission for contributed talks (long and
short) and for posters is 4 November, 2006.
The deadline for early bird registration is 24 November, 2006.
Some partial support available for students and postdocs will be available
(see the website).
Full details are available at the workshop website:
http://qipworkshop.org/
Links to past QIP workshops (including programs) are available at the
website. Note that this year’s program will follow a similar format to
QIP 2006, with approximately 10 invited talks, and 30 contributed talks.
Hope to see you in Brisbane in 2007!
I have to decide whether I’m going to be able to make it this year as I’m teaching Data Structures next term. Two years in a row missing QIP sounds really bad to me.
A PR Battle Worth Fighting?
Yoinked from the comments of my post laugh therapy, John Preskill weighs in with a wise remark:
…But actually it is nice, for those of us who may have come to take the theory of quantum fault tolerance for granted, to be reminded of how truly remarkable and marvelous it is. This paper does not lay a glove on the theory. Even so, let’s be careful not to be too smug. We sure have a long way to go toward turning the theory into practice.
Indeed! My first reaction is always to act like I’m a book critic, and to crank up my hyperbole meter to overdrive. But I certainly agree with John that we should not be too smug. To destroy a line from a baseball movie, “Until we build it, they won’t come.” Indeed to me the best critique of quantum error correction is simply “you haven’t done it yet” to which I can only nod my head in agreement and then run over to the experimentalists and cheer them along.
But John’s comment got me thinking (again) about the relationship quantum computing theory has with the physics community. Certainly I don’t think there has been much of a change in the hiring practices of U.S. physics departments when it comes to quantum computing theorists. In two words: “not good.” And I wonder if perhaps one of the reasons for this is that the central message of the threshold(s) theorem(s) has not penetrated into physics. Indeed, in my mind, the threshold theorem for quantum computation is essentially a statement about a new phase of many-body quantum systems. But to many physicists, I’ll bet that the result, if they’ve heard anything about it at all, sounds more like a strange engineering/computer science result, and the inclussion of the word “theorem” sets off their antimathematical radar detection system.
In some ways what I’m saying is that it feels like we’ve lost the public relations battle in publicizing the significance of the threshold theorem to physics departments. Perhaps part of this is because the language used to describe the theorem is more often devoid of terms physicist would like to see. Indeed when I talk about the threshold theorem I always always immediately transport myself into computer science speak. But that doesn’t mean that there isn’t a beautiful way to cast the result in terms of the physics of many-body quantum systems. Should we be making fault-tolerance more accessible to physicists? Maybe this is a PR battle we should be trying harder to overcome!
Okay this is strange. Just as I was about to post this, an email popped into my inbox about the APS March meeting:
TGQI is also organizing a tutorial on Quantum Error Correction and Fault-Tolerant Quantum Computation, which will be given on Sunday, March 4, with Daniel Gottesman of the Perimeter Institute as the instructor. To attend a tutorial, you must pre-register for the Meeting.
Sounds like a good way to convert some physics skeptics!
Not as Bad as the Best Expert
Tuesday I went to a cool talk by Sanjeev Arora on the multiplicative weight method and, because I should be working on a different calculation, I thought I’d write up a description of a basic version of this algorithm (Mmm…I love the smell of procrastination in the morning.)
Suppose that there is a stock exchange where each day you can bet on whether a stock will go up or down that day. Of course you want to bet correctly on this stock every day so as to earn the maximum amount of moolah. But you don’t know much about stocks and are a bit lazy. But you do have access to a group of [tex]$n$[/tex] experts. Everyday you get to learn these experts predictions for that days movement of the stock price. Now of course, since these are experts, you’d like to do as well as the best of these experts. So what should you do? It seems that knowing what the experts predict shouldn’t help you perform as well as the best of these experts, right? I mean how would you know who the best of these experts is?
Well, it turns out that there is a way to guarantee performing almost as well as the best expert in this game. This is the heart of the multiplicative weight algorithm. Begin by assigning a weight to every expert. Since we don’t know anything at the time of our first bet we might as well assign a weight of one to every expert. Now intuitively what we are going to do is to increase the weight of experts when they correctly predict the outcome of a days movement. Thus we will update our weights as follows. If an expert got the prediction correctly, then we do nothing to the weight. If, on the other hand, the expert was wrong then we multiply the experts corresponding weight by [tex]$1-epsilon$[/tex] where [tex]$0< epsilon< frac{1}{2}$[/tex] is a small number which we will discuss later. Okay, so the weights will now begin to favor experts who are right more. Now how should we exploit this in our own playing of the game? Well each expert will have a prediction for the movement of the stock. What we do is we take a weighted majority of these predictions. That is if the weight of the experts predicting the stock will go up is more than half the total weight of all experts, then we will bet on up. If the weight of the experts predicting the stock will go down is more than half the total weight of all experts, then we will bet on down. A pretty simple algorithm, no? As a we play the game, we change the weights of the experts and bet depending on what the weighted majority of them predict. That's among the simplest strategies we could imagine…so how well does it work?
Now here is the cool thing. Suppose that we play the game [tex]$t$[/tex] times. Let [tex]$m(t)$[/tex] denote the number of times we, using the above algorithm, guess incorrectly (our number of mistakes). Further, let [tex]$m_i(t)$[/tex] denote the number of times expert [tex]$i$[/tex] guesses incorrectly. Then we claim that, for all experts the above algorithm satisfies [tex]$m(t) leq {2 log n over epsilon} +2(1+epsilon) m_i(t)$[/tex]. We'll prove this in a second but note that since this holds for all experts (for all [tex]$i$[/tex]), this means that it holds, in particular for the best expert. In other words, the number of mistakes we make is (ignoring for the moment the first term) at most roughly twice that of the best expert! Pretty cool, no?
How do you prove this? Well it's fairly straighforward. Note that the weight of the [tex]$i$[/tex]th expert after playing [tex]$t$[/tex] times is [tex]$w_i(t)=(1-epsilon)^{m_i(t)}$[/tex]. Define the "potential" function [tex]$phi(t)=sum_i w_i(t)$[/tex] (so that [tex]$phi(1)=n$[/tex].) Now what happens to the potential function as a function of time? Well the potential will always decrease as long as there is one expert who is wrong. What we are interested in is how it will decrease when we make a mistake in our guess, i.e. when by following the weighted majority we are wrong. In this case, at least half of the total weight is decreased by [tex]$1-epsilon$[/tex]. Thus in this case the potential will decrease by at least [tex]$frac{1}{2}+frac{1}{2}(1-epsilon)=1-frac{epsilon}{2}$[/tex]. Thus if we have made [tex]$m(t)$[/tex] mistakes at time [tex]$t$[/tex], this means that the potential at that time must satisfy [tex]$phi(t) leq nleft(1-frac{epsilon}{2} right)^{m(t)}$[/tex]. Now since the weights remain postive the potential function is always as great as one of its constituent weights: [tex]$phi(t) geq w_i(t)$[/tex] for all [tex]$i$[/tex] so that [tex]$w_i(t) leq nleft(1-frac{epsilon}{2} right)^{m(t)}$[/tex]. Putting this together with [tex]$w_i(t)=(1-epsilon)^{m_i(t)}$[/tex] we thus find that [tex]$(1-epsilon)^{m_i(t)} leq nleft(1-frac{epsilon}{2} right)^{m(t)}$[/tex]. Taking the log of this expression we obtain [tex]$m_i(t) log(1-epsilon) leq log n + m(t) log left(1-frac{epsilon}{2} right)$[/tex] and using [tex]$- log(1-x) < x+x^2$[/tex] for [tex]$0<x<frac{1}{2}$[/tex] plus throwing away some [tex]$epsilon$[/tex] corrections, we obtain our desired expression [tex]$m(t) leq {2 log n over epsilon} +2(1+epsilon) m_i(t)$[/tex].
So what use is this multiplicative weight algorithm? Well that was the subject of Sanjeev's talk, describing all sorts of cool applications of this algorithm, including boosting in machine learning theory, approximately solving semidefinite programs, approximately solving fraction packing and covering problems, and online convex optimization. These later tasks were the subjecto Sanjeev's talk and the interested reader is directed to this survey paper.
Pre-Dewiging Pictures
Last week, after going to Innsbruck, I attended the QIPC Workshop in London. The workshop was held at the Royal Society of London and the theme was “Physicists and Computer Scientists Unite!” Scott Aaronson and I were asked to open up the workshop, and, because we are two entirely shameless people we decided that the best way to do this was, given the locale, to replace the debate between physicists and computer scientists with an opening debate between Newton and Leibnitz. Scott has posted our opening dialogue here and the talk which followed it here. And, even more importantly, and to most embarass ourselves, I now present to you incriminating evidence (thanks Viv!) that Scott and I are indeed crazy enough to mock these two great scientists by wearing the appropriate attire:
If you look closely at the following picture, you’ll see that Scott is on the ground groveling before Newton:
And finally, here we make fun of a cookie name
Laugh Therapy
Oh, my brain is sore. Why, oh why do I get suckered into reading things like quant-ph/0610117? Now I could go on and on about this paper, but instead I thought I’d cut and past my favorite parts. The parts that didn’t make me want to send my head straight through my monitor. Mother always said if you can’t say anything nice about a paper, cut and paste the better parts and make funny statements about them. Call it laugh therapy, if you will.
Okay, let’s begin the therapy. This part is funny. It gives what I call an “argument by ignorance”:
On the other hand, the heavy machinery of the theoretical quantum computation with its specific terminology, lemmas, etc, is not readily accessible to most physicists, including myself.
So you want to criticize fault-tolerant quantum computation, but you readily admit that you do not understand it? Ha! That just cracks me up. Is this sort of like the arguments that “math is useless” because “I haven’t used math in years?” Oh, and having read the literature, I’m pretty sure that even a physicist should be able to understand it. I mean, I’m a physicist and I understand it…and I’m not even a string theorist.
Another good part of the paper is reference [19]:
The future quantum engineer is a mythical personage, who will finally achieve factorization of numbers like [tex]$10^{260}$[/tex].
Now, if I hadn’t just read the statement of ignorance which opens up this paper, I might assume that this is an ironic statement. But just having stated that things like “lemmas” are too complicated, I just can’t make that assumption. And when you say that factoring “requires” exponential time, I can’t assume that you know pretty much anything about computer science or discrete math. So I’d like to say that even today there are engineers who can factorize these numbers. Indeed [tex]$10^{260}=2^{260} times 5^{260}$[/tex].
Here is another good one:
Alicki [21] has made a mathematical analysis of the consequences of finite gate duration. I am not in a position to check his math, but I like his result: the fidelity exponentially decreases in time.
Sweet. That’s an argument by ignorance followed by an argument by “I like it!”
A Fox News bifecta!
Argh. #@%@!! Yep, that’s about all I can say.