Over the past few years there have been quite a few results where methods of quantum computing have been used to prove or reprove results about classical objects. Among these are lower bounds on locally decodable codes (de Wolf, Kerenidis, Wehner), limitations on classical algorithms for local search problems (Aaronson), a proof that PP is closed under intersection (Aaronson), and ways to use quantum communication complexity to prove lower bounds on classical circuit depths (Kerenidis). Now we have more to add to this mix, with quant-ph/0505188, “Lower Bounds on Matrix Rigidity via a Quantum Argument” by Ronald de Wolf (CWI Amsterdam). The rigidity of a matrix is the number of entries in a matrix which need to be changed in order to bring the rank of the matrix down to a certain value. What Ronald does in this paper is show how to use a quantum argument to prove some lower bounds on the rigidity of the Hadamard matrix. Very nice!
Whenever I see one of these quantum proofs of classical problems, I think, well: why are these quantum proofs significantly or slightly easier? But perhaps this thinking is backwards. Because the universe is quantum mechanical, should we really be surprised that the language of this theory is so powerful? One often hears the statement that it is amazing that mathematics is so useful for describing the physical world. But really this disregards the fact that different parts of mathematics are and are not useful for describing the physical world. So in a realm like computer science, where you are explicitly reasoning about physical systems, should it really be a surprise that the mathematics of these physical systems (quantum theory) is the best way to attack the problems?
Saros Type 130
Today is my birthday. And if there has ever been a doubt that I am a lunatic, my birthday should set to rest that debate because I was born on a lunar eclipse. (“All work and no play make Homer something somthing.” “Go crazy?” “Don’t mind if I do!”) My mother describes being in the hospital and looking up at the moon and thinking “that’s a strange looking moon.” I guess if I was religious or superstitious, I might take this as some sort of an omen and maybe even develop a nice messianic complex. Bah! I can develop such a complex perfectly fine without the aid of superstition.
LaTeX
This is a test of the render LaTeX plugin.
My first physics TA was an astrophysicist named David Hogg. He told me the following story. He said a friend of his was walking down the street, and, well this friend was really geeky looking so when a truck full of macho guys passed by they yelled out “Hey Geek! [tex]$E=mc^2$[/tex]”. The friend thought for a second, and then shouted back: “Only in the rest frame!”
Because of course everyone knows [tex]$E=gamma mc^2$[/tex]. But of course, having to explain [tex]$gamma$[/tex] is a lot harder than explaining [tex]$E$[/tex], [tex]$m$[/tex] and [tex]$c$[/tex].
Why So Many Songs?
My apartment in Seattle has a very nice view from the skyline of Seattle, all the way up Lake Union, and then to the outskirts of Fremont (which is the self-proclaimed center of the universe, and well, if you have a statue of Lenin, a thirty foot rocket, and a troll under a bridge, well, I guess you do get to do a little braging.) On clear days, you can see the cascade in the distance as well as Mt. Rainier to the left of the skyline. And the sea planes take off and land right in the middle of the view. What is kind of nice is that every room has a nice view. The master bedroom a view of Lake Union, the main living room with nearly solid windows and deck nearly the entire view, and the guest bedroom a view of downtown.
But to the point. Here is a picture of a rainbow over Lake Union as seen from my porch which I took with my cell phone:
Spore
Part of me thinks this game sounds like a lot of fun, and part of me thinks that it will create a bunch of intelligent design worshiping children (oh…wait)
Next year, Electronic Arts will release Wright’s next attempted masterpiece, Spore, a game some are calling “Sim Everything.”
Spore will give players the chance to control life — from the ground up.
Starting with single-cell organisms, players work on designing life with ever more complexity. As the game progresses, players must figure out how to take creatures from individual animals to small tribes and then to cities, whole planets, solar systems and galaxies.
A Supporter
It’s always good to see the “quantum computing friendly” gain entry to high places:
Tony Hey to join Microsoft as Corporate Vice President
Professor Tony Hey is to join Microsoft Corporation as a corporate vice president to co-ordinate their Technical Computing Initiative. He will work across the company to co-ordinate Microsoft’s efforts to collaborate with the scientific community worldwide.
Currently Director of the UK’s e-Science Programme, Tony Hey has been a member of staff of the School of Electronics and Computer Science (ECS) since 1986, and was Head of School from 1994 to 1999.
He played a critical role in building the School into one of the UK’s leading academic departments, and has retained his Chair in the School throughout his period of secondment to UK e-Science.
‘This is wonderful news,’ said Professor Wendy Hall, Head of ECS, ‘and I am delighted to send our warmest congratulations to Tony on behalf of the School. His energy, vision, and sheer ability to make things happen will be of huge benefit to Microsoft and to future collaboration with researchers worldwide. At Southampton we are very glad that Tony will be retaining his Chair in the School of Electronics and Computer Science, and his strong links with the School and the University.’
Professor Hey is a Fellow of the Royal Academy of Engineering, the British Computer Society, the Institution of Electrical Engineers and a member of the Institution of Electrical and Electronic Engineers. In the New Year Honours List (2005) he received the CBE (Commander of the British Empire) for his services to science.
‘Today computation plays a critical role in advancing research across almost every field of science, yet far too often scientists must build all their own programming infrastructures and research their own algorithms to help advance their research effort,’ said Professor Hey. ‘By collaborating with the scientific community, I am confident that some of Microsoft’s advanced technologies can be used to accelerate their rate of discover.’
He has worked in the field of parallel and distributed computing since the early 1980s and was instrumental in the development of the MPI message-passing standard and in the Genesis Distributed Memory Parallel Benchmark suite. In 1991, he founded the Southampton Parallel Applications Centre (now the IT Innovation Centre), which has played a leading technology transfer role in Europe and the UK in collaborative industrial projects. His personal research interests are concerned with performance engineering for Grid applications but he also retains an interest in experimental explorations of quantum computing and quantum information theory.
For those who don’t remember, Tony Hey was the editor for “Feynman Lectures on Computation” and the companion volume entitled “Feynman and Computation.”
Quantum Documentary?
One question I’ve had for a long time is why there hasn’t been a good documentary produced about the field of quantum information science. There is certainly a feeling that quantum computing has leaked into the mainstream of geeks through various sci-fi stories, articles in Scientific American, and postings on Slashdot, and yet there hasn’t been a NOVA style documentary produced on the field in spite of the (I think) fascinating results which have emerged from the field in the last few decades (we’ve got to count quantum cryptography!)
Journal of Well Written Scientific Papers
Via Michael Nielsen I’ve found that Ben Schumacher, inventor of the word “qubit” and quantum information theorist extraordinaire, has a blog. Michael points to the following from quote from Ben:
But you know, so much of academic writing is bad. It is banal, orotund, unmusical, and stuffed with wads of unnecessary jargon. It is the sort of writing that does more to obscure meaning than to convey it. I see this stuff almost every day. I swim in it. OK, maybe I do exaggerate, a little. After all, I teach at a liberal arts college that is moderately well-known for teaching people how to write. Our faculty is full of novelists and poets and whatnot. But let me tell you, it’s here, too. It’s everywhere. It is like a fungus growing over all things, blurring their shapes — the verbal equivalent, maybe, of the ivy on academic buildings. And like the ivy, I guess, its main purpose is to conceal the shabby edifices beneath
Which made me think that it would be fun to create a scientific journal in which good writing was a requirment. No silly page limits either. You either write a killer article, which is comprehensible and well written, or your articled doesn’t get accepted. Even if you result is correct and even if your result is groundbreaking. Sure, not all journals could be this way, but it would if such a journal existed, I would certainly be a regular reader. I certainly know that there are people who are up to the task: every once in a while you stumble upon a piece of scientific writing which is so well written it just makes you cry the next time you look through Physical Review Letters.
Homeless Life in a Loop
Yesterday, while waiting for the bus, I was acosted by a homeless man who was missing his front teeth. I asked him how he was doing and he said he was high. I told him I was a theoretical physicist and he said “Amazing! Because I don’t live in reality, so it’s strange that we should meet.” (Indeed!) Then he asked me if the manhole cover in front of us turned into a portal which would take me to an alternate reality whether I would jump into the hole. Of course I said I would. Then somehow our conversation turned to time travel (doesn’t it always) and he said he thought that he was in a situation where things kept repeating themselves. I told him that physicists call this a “closed timelike curve.” He asked me how he could get off the closed timelike curve. Which made me sad.
Filibuster Logic
I find it very difficult to agree with the majority of what any one political pundit has to say. It’s a rare case where I read an article that I don’t have at least some problem with the language and logic used in the article. Normally this is just in the back of my head and doesn’t really get to me. But the current “debate” over changing the filibuster rules has sent me over the edge.
Take, for example, this from Ronald D. Rotunda, a law professor at George Mason,
The filibuster has a long history, but its pedigree should not make us proud. It prevented civil rights legislation from being adopted for nearly a century. Now a minority of senators is using it to prevent the Senate from voting on judicial nominees even though a majority of the senators from both parties would vote to confirm if they only could vote.
Aaaaaah! The logic in this paragraph is (1) filibuster blocked civil rights legislation, (2) that was bad, (3) the filibuster is being used to block judicial nominations, (4) ergo blocking those judges (“even though”) must be bad. What kind of logic is that?
In the last paragraph of the article we further find
Now, a minority of senators once again claims that the Senate cannot change it rules to prevent this filibuster unless a super-majority agree. That is wrong. To paraphrase Senator Henry Cabot Lodge, to vote without debate is unwise, but to debate without even being able to vote is ridiculous.
Ack. Not being able to vote is ridiculous, but the filibuster IS a vote. It’s a vote by 41 Senators not to proceed. Just because a vote is not a majority vote does not invalidate that it is a vote. By a similar logic, votes to amend the constitution do not constitute a proper vote because they require supermajorities.
OK, sorry, I don’t usually make to many political posts, but this lack of logic in the debate is making me bonkers.