Subscribe
The Quantum Pontiffs
Pontifex Praeteritorum
Quantum Annoucements

Recent Posts
Category Archives: Computer Science
A Breakthrough Donation for Computer Science
Lance Fortnow has a post summarizing some of the news affecting the CS community over the past month, including updates on various prizes as well as the significant media attention focusing on physics and mathrelated topics such as movies about Turing and … Continue reading
Posted in $$$, Computer Science, Prize
5 Comments
Error correcting aliens
Happy New Year! To celebrate let’s talk about error correcting codes and….aliens. The universe, as many have noted, is kind of like a computer. Or at least our best description of the universe is given by equations that prescribe how … Continue reading
Simple circuit "factors" arbitrarily large numbers
Last Thursday, at the QIP rump session in Beijing, John Smolin described recent work with Graeme Smith and Alex Vargo [SSV] showing that arbitrarily large numbers can be factored by using this constantsized quantum circuit to implement a compiled version … Continue reading
What increases when a selforganizing system organizes itself? Logical depth to the rescue.
(An earlier version of this post appeared in the latest newsletter of the American Physical Society’s special interest group on Quantum Information.) One of the most grandly pessimistic ideas from the 19th century is that of “heat death” according to … Continue reading
Posted in Computer Science, General, Mathematics, Physics, Science
6 Comments
Immanants
Recently computer scientist Leslie Valliant won the ACM’s Turing Award, considered one of the most prestigious prizes in computer science. Valliant is famous for many results, not the least of which are his results on the Permanent of a matrix. … Continue reading
Posted in Computer Science, Mathematics
5 Comments
BPP^(Wolfram Alpha)
Via @fortnow, Wolfram Alpha is now offering answers to classical complexity queries (see blog post at the WolframAlpha Blog).
Posted in Computer Science
2 Comments
US Quantum Computing Theory CS Hires?
I’m trying to put together a list of people who have been hired in the United States universities in CS departments who do theoretical quantum computing over the last decade. So the requirements I’m looking for are (a) hired into … Continue reading
TQC 2011 and a Bonus! Rant!
So most of my conference announcements are going out on qspeak now (and will be digested every week in a post here.) But since I’m helping out with this one it, I thought I’d post a separate note here. TQC … Continue reading
Posted in Computer Science, Conferences, Quantum Computing
6 Comments
Consequence of the Concept of the Universe as a Computer
The ACM’s Ubiquity has been running a symposium on the question What is Computation?. Amusingly they let a slacker like me take a shot at the question and my essay has now been posted: Computation and Fundamental Physics. As a … Continue reading
Does Not Compute
Okay, last one. But damn I could make these movies all night and it would make me laugh and all of you cry: