As I am sure everyone has heard by now, there has been an enormous earthquake off the coast of North-East Japan, which (together with the tsunami caused by the quake) has lead to widespread distruction and loss of life. At the moment, however, there is concern over trouble at two nuclear power station. The amount of information coming out through the media is quite limited, and of course isn't easy to decrypt what experts are saying if you don't know what the terminology means.
Caveat: Although I am a physicist, I am the wrong type of physicist to be paricularly expert on nuclear safety. I am writing this simply so this to try to help non-physicists decipher what is going on at the moment in Fukushima.
The first thing you need to know is what a nuclear power plant actually does, and what radiation is. All atoms are composed of a cloud of electrons which surround a nucleous composed of neutrons and protons. The stability of the nucleus is what determines radioactivity, and is determined by the number of protons and neutrons contained in the nucleus. The interaction between these particles determine how tightly they are bound together.
The above diagram shows the relative stability of different atomic elements, running from lighter to heavier elements. As you can see, iron (Fe) has the highest binding energy (meaning that its nucleons are the most tightly bound). Nuclear reactions in which larger nuclei split apart are known as fission reactions (moving towards iron from the right), while reactions where smaller nuclei are combined to form a larger nucleus are called fusion reactions (moving towards iron from the left). All commercial reactors are at present fission reactors. These work by capturing the energy released by large nuclei splitting, usually using uranium as fuel. The reactors at Fukushima are boiling water reactors, which capture this energy by using it to boil water to produce steam used to drive a turbine, which in turn generates an electric current (producing electricity).
Different nuclei come apart in different ways, depending on their composition. Which element a nucleus is is governed by the total number of protons only, and this determines it's chemical properties. The nuclei of the same element can have different numbers of neutrons, and these different varieties are known as isotopes. The chart I showed above is of the most stable isotope for each element. How a particular radioactive element comes apart depends not on only on which element it is, but rather which isotope of that element. Below is a diagram showing how different nuclei decay.
Here the important unexplained types of decay are
The proposed Theoretical Physics stack exchange site has finished its definition phase and has now entered a commitment phase. What this means is that we need as many physicists as possible to agree (by signing up here) to participate in the beta and hopefully ask or answer 10 questions in the first 3 months. This shouldn't be a huge time commitment, but it is really important to get as many research physicists as possible early on. The reason for this is that the democratic nature of Stack Exchange sites means that the direction of the site is set by the participants. Obviously there are a lot more people interested in some aspect of theoretical physics than there are people who have some level of expertise in the field, and so it is important to get as many TP grad students, postdocs and faculty involved at an early stage to insure that the site becomes a TP version of MathOverflow and CSTheory, rather than becoming a site for people to post their pet crackpot theories or discuss pop science topics.
To help convince you to sign up, below are a list of the top 5 examples of both on-topic and off-topic questions chosen during the definition phase.
On-topic:
I've become totally enamored with the CSTheory stack exchange site. It's proving very addictive, but in exchange for the time I spend on the site I am finding that I am learning a lot of new things, and a few new tricks.
I had hoped that the Physics stack exchange site might become a similar resource for physicists (and I still very much self-identify as a physicist). Unfortunately this has turned out not to be the case. There was never a policy dictating that questions should be research level (as there was both for CSTheory and MathOverflow), and this has led to the majority of questions either being basic undergrad type questions or pop-sci question. As a result, there are also very many poor answers which contain common misconceptions, but which get up-voted. Consequently, I don't think the site is likely to be an attractive propositions for active researchers.
However, I don't want to just complain and not offer a solution, so I have set up a proposal for a Theoretical Physics stack exchange site. The aim of the site would be to provide a question and answers site aimed at research level questions only, akin to the CSTheory stack exchange site and MathOverflow. Personally I find both sites to be phenomenal resources, and I think it's high time we physicists had something similar.
The mathoverflow-like site for theoretical computer science which I blogged about earlier is about to go into public beta. The site aims to allow users to ask and answer research level questions in TCS, and I must say that my experience with the private beta has been excellent. I have received excellent answers to the 2 questions I asked, and have been able to give reasonable answers to 8 questions so far. It really is an excellent resource. Anyway, if you have an interest in TCS it is well worth participating in the site. It needs as many users as possible to make it a success.
To join the public beta, simply visit http://cstheory.stackexchange.com
A new paper has appeared from Vinay Deolalikar in HP Labs claiming to prove P is not equal to NP (in fact P≠NP is the title). Normally I ignore the constant stream of papers on the subject, but this work looks like a serious attempt and is being taken seriously by a number of people I respect, so it has jumped straight to the top of my reading list.
For more details see posts by the Pontiff, Greg Baker, and R J Lipton.
I really hadn't expected to see this proved within my life time, so I am of course skeptical. Still, even if there is an error, perhaps it opens up a new approach.
If you're a physicist, mathematician or computer scientist and haven't already seen MathOverflow then stop reading this post and go check it out. It is one of the best resources for research level math I have ever seen. It is absolutely shocking the speed and quality of responses to potentially very technical questions.
So, if you are still reading, I will presume you actually know the site. So why do I bring it up? Well, there is currently a proposal for a TheoryOverflow, aimed at Theoretical Computer Science, on the StackExchange site. Basically the way this works is that the people that produce the engine that powers the MathOverflow and StackOverflow websites are looking to produce similar sites in different areas. First an idea is proposed and fleshed out (Stage 1), once this is done it moves to a commitment stage where potential users are asked to commit to using the new site initially if it were made (Stage 2), either posting questions or answers. Finally it moves to a Beta (Stage 3). TheoryOverflow is currently in stage 2, and so needs support.
Rep, if you don't know, is basically reputation, and so people who have contributed to other such sites carry more weight than users who haven't. Different users have different amounts of rep depending on their level of contribution to StackOverflow and sister sites. Unfortunately more users seem to be necessary than usual, because most potential users committing to it seem to either be new or are coming from MathOverflow, and the StackExchange site doesn't care about your MathOverflow rep (though it does about StackOverflow rep).
So basically, TheoryOverflow needs more support. If it turns out even a tiny fraction as useful as MathOverflow, then it will be a fantastic resource. So please help make it happen. You can sign up here.
Nice article (and a pretty cool photo) in The Record about my dear friend and collaborator Anne Broadbent.
If you have heard me talk in the last couple of months you may know that I have been working on trying to characterize the power of quantum interactive proofs with multiple provers. Well, I am delighted to say that our paper is finally on the arXiv here. I am quite chuffed with it since it is the first time I have been able to use an equation as the title of a paper, and is also the first time one of my results can be neatly captured by a single simple equation. Some how I feel it lends me more cred as a theorist!
Recently Jain, Ji, Upadhyay and Watrous proved the rather amazing result (here) that interactive proofs with quantum verifiers can only prove problems in PSPACE, and so are identical in power to interactive proofs with classical verifiers. Our result proves an equivalent statement for interactive proofs with more than one prover, basically showing that any interactive proof with potentially entangled (but non-communicating) provers can be simulated using only a classical verifier and some extra entanglement. The case for non-entangled provers had previously been proved by Kobayashi and Matsumoto (here).
Taken together these three results show something interesting, and quite counter intuitive: the availability of quantum verifiers does not change the power of any interactive proof system. Now, this result doesn't necessarily hold when we fix the number of rounds (our MIP* protocols requires polynomially more rounds than than the equivalent QMIP protocol), but I find the symmetry in these three results pretty remarkable.
As Oded Regev pointed out to me on SciRate, some authors have used QMIP* to denote the quantum equivalent of MIP* and QMIP to denote the quantum equivalent of MIP. Although we were aware of this, there are at least two conflicting notations used, and we simply followed the convention used on the Complexity Zoo, to try to minimize confusion. One nice property of the notation Oded suggests, however, is that the three results mentioned above can be expressed as:
If you know me personally or follow me on twitter then this may not be a big surprise, but I thought I would repeat the news here, since I am so happy. On the 2nd of March I asked my wonderful girlfriend Amy to be my wife. I am delighted to say that she agreed!
We haven't set a date yet, but we are planning to get married in summer 2011. I will post more plans as we make them, in the mean time if you are bored, you can check out our new wedding blog here.
I'm back from the FOCS conference in Atlanta, and since Lance has pointed out the lack of blog posts about it, I thought I would try to say something about it.
For those of you who don't already know, FOCS is actually the IEEE Symposium on Foundations of Computer Science, and this year marks the 50th annual meeting. This was also my first time to attend FOCS, and it was a slightly odd experience. My background is in theoretical physics rather than theoretical computer science, so I am much more used to the physics model of conferences and publishing.
One thing I found particularly odd is that for such a prestigious conference with a rigorous review process they limited all the talks to 25 minutes including questions. Given the technical nature of many of the results this seems a little strange. Is there really a need to compress the conference into 3 days if it means having such little time to take in each of the results. This also seems to lead to a rather strange style of presenting, where some speakers seem to dive into the technical details without giving the intuition behind their approach. Maybe this is just a cultural difference between CS and physics, but I can't help thinking that the compact time frame for talks really limited how much I actually took in. There were a lot of very interesting results, and I really wish I had had more time to process these before moving on to a new topic.
The other thing I found strange, being used to physics conferences, was the lack of a conference dinner. I usually enjoy conference dinners as they tend to be a great way to meet other people in the field. While there were lunches on two of the days, these really did seem quite cliquey and so I mostly ended up meeting people who were connected to one of the other quantum speakers (we had our own clique!).
So now I've brought up two things I didn't like about the conference, perhaps I should focus on the things I really did enjoy: the talks. Keep in mind that I have a very different background to most of the attendants, so I am probably skipping over some other great talks. These are simply the ones that caught my imagination.
Day 0 of the conference was last Saturday. It wasn't part of the conference proper, and was open to the public. There were a series of public talks to mark the 50th anniversary of FOCS and the 20th anniversary of the algorithms, combinatorics and optimization program at Georgia Tech. Even though I ended up staying in the Hotel Palomar (which I thoroughly recommend) right beside the auditorium it took me nearly an hour to find the right place. In retrospect, it shouldn't have been hard to find at all, except that the map was somewhat inaccurate, and seemed to direct us to a building on the opposite side of the road.
There were four talks in total, from Richard Karp, Mihalis Yannakakis, Noga Alon and Manuel Blum. Unfortunately jet lag got the better of me, and I ended up missing the last talk. Of the first three, I particularly enjoyed Mihalis's talk on equilibria. Why? Well it seems that many of the equilibria problems he was discussing are of a similar form to the the equations that arise in dealing with closed timelike curves. This probably shouldn't be surprising, since Deutsch's consistency condition is effectively just enforcing equilibrium, but none the less I found the connection fascinating. Actually throughout the conference, I found that quite a number of talks dealt with issues that also arise in physics.
Sunday marked the star of the conference, and also the start of parallel sessions. As a result, I was constantly having to decide which session I wanted to attend, and so could only see half of the talks. In the morning I attended session 1B (see the program here), and got a good sampling of talks on complexity. I've been interested in a (quantum) communications complexity question for some time, so I particularly enjoyed Paul Beame's talk on multiparty communications complexity.
By far the highlight of the day for me, though, was session 2A, where we were introduced to the abstract tiling model model by David Doty, before Sandy Irani's excellent talk on the connection between this problem and Hamiltonian problems in quantum complexity. I really found this session to be eye opening, as I hadn't been aware of the abstract tiling model before, but it has really caught my interest. Sandy's talk in particular caught my interest, and I will be reading their paper in detail once I can get my current teaching backlog out of the way.
The other talk that I greatly enjoyed was on polynomial identity testing given by Shubhangi Saraf (particularly the colourful combinatorics!). Unfortunately by this stage I was pretty worn out, and didn't really take everything in. Another paper for the reading list.
The highlights of day 2 for me were talks by Alexander Sherstov on the intersection of half-spaces and by Vitaly Feldman on statistical query learning.
On Saturday myself and my co-author Elham had flipped a coin to decide who would give our talk, and I lost. On Monday evening we went out to my hotel to finish the slides and have a celebratory dinner to mark our first FOCS paper together. The Palomar, where I was saying, somehow seemed to be both cheaper than the conference hotel and much better. We sat beside a fire pit on the roof terrace, putting the last touches on the slides. Not a bad way to prepare for a talk!
Tuesday was the third and final day of the conference. The quantum session was in the morning, which unfortunately meant quite a low turnout. I have to say, I enjoyed all three of the other talks in the session. Our talk was first, at 9am, followed by André Chailloux talking about quantum coin flipping, then Sarvagya Upadhyay talking about quantum interactive proofs, and finally Ben Reichardt talking about quantum query complexity and span programs.
I found Sarvagya's talk particularly interesting, but also kind of strange. In his talk he was showing that two message quantum interactive proofs are in PSPACE. This was certainly a major result and I was very interested to hear the details fo the proof. What was strange, however, was that I know the same authors have proved the much stronger result that QIP=IP or equivalently QIP=PSPACE. It is a little strange to sit through what you know to be a talk about a weaker result, when you know the speaker has the stronger result ready to go. Oh well!
Unfortunately, after our session I realised that we could prove another result about interactive proofs, and spent the rest of the day working through the details with Elham, and so missed the later talks.
Despite my reservations about the structure of the conference, I very much enjoyed my first FOCS experience, and I'm hoping that we'll get the new results written up in time for STOC.
I'm now on twitter. It turns out to be a lot more interesting than I had been expecting, probably due to the relatively large number of QIPers/exQIPers (@dabacon, @mattleifer, @danbrowne77, @WaterlooIQC, @iqoqi, @coherence, @dwavesys, @rohde, @mickbremner, @michael_nielsen, @tobiasosborne and @seandbarrett).
No, not mine. My DPhil student Yuichiro Matsuzaki has just uploaded his first paper to the arxiv. It should appear in the quant-ph morning mailing. I might write something about it once it appears.
It seems that the UK government plans to limit freedom of expression for immigrants wishing to become citizens. The Guardian has the story. It seems if you voice opposition to government policy (and by this I mean the policy of the current party in power) you can be declined citizenship:
At the weekend stories attributed to government sources suggested that immigrants who took part in anti-war demonstrations could jeopardise their chances of qualifying for citizenship.
....
But, when it was pointed out that demonstrating was not illegal, Woolas suggested that an applicant could also lose points not just for breaking the law – but also for engaging in certain activities that were legal.
Sarah Montague, the presenter, asked: "Are you effectively saying to people who want to have a British passport, 'You can have one, and when you've got one you can demonstrate as much as you like, but until then don't'?"
Woolas replied: "In essence, yes. In essence we are saying that the test that applies to the citizen should be broader than the test that applies to the person who wants to be a citizen. I think that's a fair point of view, to say that if you want to come to our country and settle, you should show that adherence."
That's Phil Woolas, the immigration minister. Well, Phil, allow me to acquaint you with Article 10 of the European Convention on Human Rights:
I just noticed a friend's status update questioning whether global warming has stopped since 1998. This shocked me a little, since it is a patently ridiculous claim, but apparently one being made by the group of nutjobs and the willingly ignorant who style themselves "global warming skeptics". I think I prefer the term "reality denialists". I've just done a quick search on Google News, amd this claim is everywhere. Fortunately most of these claims turn out to be in the Letters to the Editor section of newspapers, but it has managed to wiggle its way into articles too. A few years ago, in 2006, the Telegraph ran a story with the headline "There IS a problem with global warming... it stopped in 1998". I guess this isn't surprising, since it is after all the Telegraph, but even so I am shocked that such a claim is propogating.
So, I thought I should at least look at the data to see where the claim was coming from. This chart taken from Wikipedia seems to explain it all:
In 1998 there was an enormous spike in the average global temperature far exceeding the temperature in either 1997 or 1999-2001. As you can see, it is an outlying data point about as far from the 5-year average as any point on the graph. The problem with taking yearly temperatures is that the data is very noisy and the temperatures jump about quite a lot from year to year, obscuring the trend at least over short intervals. The running 5-year average makes it clear that the average temperature is increasing sharply. So where does this claim about no global warming since 1998 come from? Well, if you look at the temperature in 1998 and compare it to the average temperature from 1999 onwards then they are about equal. But this is complete nonsense since we've cherry picked the outlying 1998 data point as our starting position. If we start on the 5 year average, then we see a dramatic increase. In fact we could play the same game in reverse and say that the average global temperature has rocketed up since 1999 at almost double the actual rate. The claim that the average global temperature has not increased since 1998 is a flagrant abuse of statistics. It works simply by picking the hottest year on record as the starting point and then only considering a short time period so that the regression to the mean increase more or less cancels the increase in the average temperature. It's a trick that preys on an ignorance of statistics. In five years the trick won't work, because the increase in the 5-year average will have brought us far above the 1998 data point. So the claim is bullshit, pure and simple.
What is particularly incidious about this clasim is that it has almost certainly been composed deliberately to trick people. It often comes accompanied by an assertion that climate models fail to predict this halt to global warming, which is of course true. It's true that none of the main climate models predict a halt or pause in global warming for the last decade, but that's probably just as well, since there hasn't been one. Should a climate model predict how people will abuse statistics? For me, predicting the climate change is enough and we can leave the precrime detection for the movies.
The list of accepted papers for FOCS has just been published. There appear to be 6 quantum related papers.
WHERE IS MY VOTEJune 20, 2009A week ago, Friday June 12, Ahmadinejad was declared the winner of the Iranian presidential election. Immediately after, all other candidates, Moussavi, Karroubi, and even the conservative Rezaei, disputed the official results. So did some people who started several demonstrations to express their anger. More news fueled the suspicion of fraud at an unprecendented scale. On Monday June 15, and to the amazement of the world, millions of people – of all ages, classes, and backgrounds – were in the streets of Tehran demanding another election in what was the biggest demonstration since the revolution in 1979. A week later, despite the threats and beatings issued and ordered by the government, millions of people are still demonstrating, and the movement is growing and spreading to other cities. Observers might find the situation confusing, since Iran has long been an isolated country and the everyday Iranian is unknown to the outside world. One cannot even prove that there was a fraud. There remains the fact that millions of people are protesting in the streets of Iran.
These are traditional, religious, modern, young, old, rich and poor, academics – some of them our colleagues – going out in the streets and risking their lives with a form of innocence in their aims and tactics. Some of them may stand on their roofs at night shouting “God is great” to keep the movement alive. They are braving the power because they insist that the Islamic republic is a republic.
The government is imposing a ban on the foreign press, shutting down all means of communication within their reach, arresting hundreds of prominent activists, politicians and religious figures opposing the results, and terrorising demonstrators. Every day fewer videos and reports escape from Iran. The state media is depicting the protests as incited by the West, accusing the movement of being a party of hooligans and traitors. After a week of uncertainty, the head of the state, Khamenei, just issued yesterday strong and explicit threats against participants in the protests and rallies.
This text is an urgent request to academics to fight the misrepresentation of this movement. This is not only about showing support to the courage and determination of people on the streets of Iran. It also means reaching for the many people in Iran who would like to participate but are frightened or know of the movement only through the state media. It means informing these people of the scale and nature of the movement, and thus widen its support within Iran. To all academics, please sign this appeal to support this movement in its call for a new election and oppose any violent intervention on protesters.
Dr. S. Aaronson (MIT) – Prof. S. Abramsky (University of Oxford) – Dr. R. Alleaume (Telecom ParisTech) – Prof. W. Arendt (University of Ulm) – Dr. E. Barker (University of Oxford) – Prof. S. M. Barnett (University of Strathclyde) – Dr. D. Browne (University College London) – Prof. P. Buneman (University of Edinburgh) – Prof. A. Cabello (Universidad de Sevilla) – Prof. T. Calarco (University of Ulm) – Prof. B. Chandrasekaran (Ohio State University) – Dr. B. Coecke (University of Oxford) – Prof. S. B. Cooper (University of Leeds) – Prof. D. W. Corne (Heriot-Watt University) – Dr. N. Datta (University of Cambridge) – Prof. V. Danos (University of Edinburgh) – Dr. J. Degorre (CNRS) – Dr. J. Desharnais (Universite Laval) – Prof. M. Dezani-Ciancaglini (Universita di Torino) – Prof. E. E. Doberkat (Technische Universitt Dortmund) – Dr. P. Dumais (Universite de Montreal) – Dr. K. Etessami (University of Edinburgh) – Dr. A. Feito (Imperial College London) – Prof. F. Ferreira (University of Edinburgh) – Prof. W. Fontana (Harvard University) – Prof. B. Foroughi (St. Francis Xavier University) – Dr. B. Farzad (Brock University) – Dr. J. Feret (INRIA) – Dr. J. Fitzsimons (University of Oxford) – Dr. D. Green (The City University of New York) – Dr. R. Harmer (CNRS) – Prof. J. M. Henderson (University of Edinburgh) – Prof. L. Hendren (McGill University) – Dr. M. Huth (Imperial College London) – Prof. H. J. Jensen (Imperial College London) – Dr. E. Kashefi (University of Edinburgh) – Dr. H. Koeppl (EPFL) – Dr. J. Krivine (IHES) – Prof. R. Laflamme (University of Waterloo) – Prof. B. Leimkuhler (University of Edinburgh) – Prof. N. Lutkenhaus (University of Waterloo) – Dr. D. Markham (CNRS) – Prof. H. Mairson (Brandeis University) – Prof. M. Mislove (Tulane University) – Prof. E. Mjolsness (University of California) – Prof. C. Moore (University of New Mexico) – Dr. M. Owari (Imperial College London) – Prof. C. Palamidessi (INRIA) – Prof. P. Panangaden (McGill University) – Prof. M. B. Plenio (Imperial College London) – Dr. O. Radulescu (University of Rennes 1) – Prof. Y. A. Ryan (University of Luxembourg) – Dr. A. Serafini (University College London) – Dr. P. Series (University of Edinburgh) – Dr. S. Severini (University of Waterloo) – Dr. M. P. da Silva (U. de Sherbrooke) – Prof. L. Smolin (Perimeter Institute) – Prof. F. Taddei (Universite Paris Descartes) – Prof. A. Tapp (Universite de Montreal) – Dr. L. Tortora de Falco (Universit Roma Tre) – Dr. D. Varacca (Universite Paris Diderot) – Dr. S. Virmani (University of Strathclyde) – Prof. P. Wadler (University of Edinburgh)
Tonight my heart hangs heavy. There can be little doubt now that the Iranian elections were rigged and that the population is being suppressed by a brutal dictatorship. It truly breaks my heart to see the violence dealt out on a people who want nothing more than for their voice to be heard. I don't know who the woman in this photo is, but I am truly touched by her courage and her defiance. I wish I had half her courage.
There have been huge street protests and riots. Men with iron bars riding motorcycles are attacking protesters in the street, and attacking students in their dormitories. This cannot be aloud to stand. But there is hope. The Iranian people have not taken this matted lying down. At this point there seem only two possible outcomes: a massacre or the overthrow of a dictator. Tonight it seems the latter may be possible.
While I have never been to Iran, have only ever flown over it, while my personal beliefs are far different from many Iranians, and while I know little of the other candidates, I am human and I understand the drive for freedom from tyranny. I stand in solidarity with the people of Iran, for tonight everyone is Iranian.
So I guess I have blown any chance of ever getting security clearance for anything, and probably can't go to Iran if the protesters fail, but that is meaningless. It is the people on the streets and in the universities that will suffer should the protests fail, which is why they must not fail. My heart is truely with the students in Tehran university tonight and throughout Iran.
The story seems to have been de-emphasised by many of the larger media organisations, so I will write this post in the hope that it reaches at least a few people.
The two best sources of information on this are liveblogs by Andrew Sullivan and at the Huffington Post. Also, tweets from those inside the protests: persiankiwi and Change_for_Iran, and hashtag #iranelections.
It seems that the government has been cutting off communication lines, and that twitter is one of the few ways for people to organize and get word out of the country. Access is being cut off, so the demonstrators are heavily reliant on outsiders setting up open proxies and relaying the details over twitter. I know many who read this will be tech savy, so I leave it to their judgement what they wish to do.
Let me close by saying that the people have spoken, and they have spoken for change:
I've just seen the future and it is wavy.
I've already applied for sandbox access, since it seems a much more natural solution for my Social Notebook project that the current cludge of Elgg and flash. I've been working on a tablet interface (in Silverlight of all things), but rather than adding it to the existing site, I think it is probably worth trying to turn the whole idea into a set of Wave extensions via robots and gadgets.
I've just received an email from Martin Plenio to tell me about a new initiative to exploit YouTube to promote science on the internet. Martin writes:
I am writing to you to bring to your attention some new tool that we (Daniel Burgarth and myself) have developed that has the aim of making science papers just a little more accessible. Its called Videoabstracts and consists of 'homemade' videos in which an author of the paper explains the key point of the paper in front of a whiteboard. The videos should not be longer than 5 minutes to force people to get to the point efficiently. We feel that these 5 minutes clarify the content and relevance of a paper much better than any abstract can do.
We have produced several examples that you may see on http://www.quantiki.org/video_abstracts. We did not strive for perfection as we feel that anybody should just be able to do these with a webcam and then upload them on QUANTIKI. The videos will then be stored on YouTube and at the same time a link will be created on the arXiv.
Viewers can leave comments on the content of the video and in that way stimulate discussions.
I've just won $5 dollars form Scott Aaronson and Seth Lloyd, and I'm feeling pretty pleased about it. I'm splitting $15 dollars with Anne Broadbent and Elham Kashefi for a partial solution to the Aaronson $25 Challenge: Does BQP = IPBQP. Dorit Aharonov, Michael Ben-Or and Elad Eban share $12 dollars for their independent work on interactive proofs. We don't have a full solution to the problem yet, but we do know that an almost classical verifier can participate in an interactive proof of any problem in BQP. I'll try to write a post on the problem soon.
The QIS workshop in D.C. should be over by now. Can anyone tell me how it went? I really wish I could have gone, but I have very limited travel funds and it was arranged very short notice. I know a few quantum bloggers went. Can anyone be persuaded to post a summary?
Let me explicitly warn you now, I am obviously not an economist and so the speculation contained in this post may be completely naive.
In the current climate, this is a question I find myself asking more and more often. Initially, prior to the recent global economic downturn I had been playing with the idea of whether it would be possible to apply fault-tolerance ideas to investments, but I never really reached any firm conclusions. Applying such ideas to an entire economy might be much easier, since you could consider substantial changes to the regulatory apparatus which would be impossible for a single investor.
So what do I mean by this? Well, basically one way to look at the economy is as a computation. Every trade, every bailout, every lay-off or expansion constitutes a step in the computation, essentially a logic gate. So what are we computing? Well, the unemployment level is clearly a function of birthrate, emigration, hires and fires/redundancies. The Dow-Jones is a function of the stock price of 30 blue chip companies, which are themselves dependant on recent trades.
It seems to me that bail-outs and interest rate adjustments can be viewed as a rather crude attempt at error correction. So we translate the processes which constitute the economy (financial, employment, policy, external events, etc.) into gates within a computation, we can start to bring computer science results to bare on the problem. One question we can ask is whether error-correction is sufficient to stop the computation going off-track. The resounding answer to this question appears to be "no", given that the cause of the recent economic crisis traces back to sub-prime mortgages. Indeed this is what we would expect viewing the process as a computation. Trades in mortgage derivatives spread throughout the system, and so when people started defaulting on their mortgages, the impact was felt throughout the economy. This is exactly the situation fault-tolerance is designed to avoid.
In a fault-tolerant computation the computation is performed in such a way that an error in one area does not propogate throughout the system. We can certainly data mine past transactions to determine a noise model for the computation (coming from external factors and our inability to predict exactly what anyone is going to do in any given circumstance), and so should be able to determine what noise factors are correlated, and which are independant. As an example, the stock price of companies within the same sector will likely be correlated in their reaction to external events. This noise model is fundamentally important to designing fault-tolerant operations.
So how could we apply fault-tolerance to the economy? Well, first we need to identify the subspace we wish the computation to remain within. Now, our initial state must be within the stabilized subspace. This means we can't really use fault-tolerance to maintain low unemployment and high stock prices, since that is not the regime we are currently in, but we can certainly design the system so that noise will not significantly raise or lower certain economic indicators we have decided to protect, allowing only intentional actions to manipulate these indicators. Faortunately, almost any indicator we can choose will depent on a range of factors, essentially acting as an error correction code. Now, unfortunately we don't get to choose our encoding, but it is fortunate that a fairly decent one already exists due to the complexity of the economy.
So if we have an error correction encoding (we essentially want a form of self correction), what else do we need? Well, one thing we need to do is to formulate a set of fundamental operations which does not lead to correlation in noise. One way to do this is to impose strict rules on how investment can be made in such a way that not only do we require investment be spread across many sectors, but also that individual investors be required to invest in a sense independently. I know that this requires a huge regulatory aparatus, but if it could free us from the fear o economic downturn, it would surely be worth while. Now I suspect that my libertarian friends are going to find this a horrifying prospect, if we can identify a universal set of operations for computation of the factors individual investors care about, then we haven't asked anyone to give up any freedom in their goals, we would only have required them to go about them in a much more responsible way. The end results should not actually be much different. The way things are at the moment, we are actively propogating risk within the economy and the financial markets, and it seems that this can be halted relatively easily.
So what would we need to do if we wanted to take a more rigorous look at this problem? Well, a few things we would need to determine:
I was just watching some of the @Google talks, when I came across one given by Sean Carroll who is one of the bloggers at Cosmic Variance. The video seems to be new, but I can see no mention of it on CV. The talk basically is an overview of dark matter and dark energy. Anyway, I really enjoyed it, and the chances are that if you read this blog you may too.
Since I'm on the program committee for this workshop, I should probably give it a plug on my blog. It's an interesting mixture of disciplines, so it won't just be quantum loonies.
Event Title: Workshop on Logical Aspects of Fault Tolerance (LAFT)
co-located with LICS 2009.
Date: 08/15/2009
Location: University of California, Los Angeles
URL: www.aero.org/support/laft
Description:
We are soliciting papers on logical aspects of fault tolerance. The concept of "fault" underlies essentially all computational systems that have any goal. Loosely speaking, a fault is an unintended event that can have an unintended effect on the attainment of that goal. "Fault tolerance" is the term given to a system's ability to cope in some way with a fault, either inherently or through design. Fault tolerance has been studied for its application to circuits, and then branching out to distributed systems and more recently to quantum computers, where the concern with fault tolerance is almost the paramount issue. The relevance to biological computation is also obvious. Papers must be concerned with the logic of fault tolerance, not simply fault tolerance.
IMPORTANT DATES:
Papers due: April 17, 2009
Notification: May 22, 2009
Final papers: July 10, 2009
Workshop: August 15, 2009
Please send all workshop correspondence, including submissions, to marcus [at] aero [dot] org
