FXPAL Blog

Frequently, particularly when searching for work related to possibly novel research ideas I or others at FXPAL have had, it is not easy to determine when to stop searching. This dilemma comes up any time anyone is searching for something we are not sure exists.  After doing N searches, and finding nothing, how certain can we be that it isn’t there?

An unusual example of an existence search came up as I was doing background research for my review of N. David Mermin’s book Quantum Computer Science that was recently published in ACM SIGACT News. As part of the review, I wanted to give a sense for the extent that Mermin’s thoughts and writings have influenced scholarly and popular thought on quantum mechanics. I thought I remembered that he was the originator of the “Shut up and calculate” interpretation of quantum mechanics, but I wanted to fact check before putting it in my review. Would this search be a hard or easy one?
(more…)

Dave Bacon, who wrote the elegant overview of the research discussed in my New Year’s Day post, just published his review, joint with Wim van Dam, of Recent Progress in Quantum Algorithms. Bacon writes beautifully, and this piece is no exception.

Most people have heard of no more than two quantum algorithms: Shor’s factoring algorithm and Grover’s search algorithm. For five years after Grover’s algorithm, no one discovered a significantly novel quantum algorithm, only variations on Shor’s and Grover’s algorithms were found. The first truly new quantum algorithms were discovered starting in 2001. Now there are many quantum algorithms found using a variety of approaches, though the applications remain restricted.  My recent overview of quantum computing mentions many of these algorithms. Bacon and van Dam provide a more detailed, but still high level, view of these algorithms. They group the algorithms into four categories corresponding to different approaches: quantum random walks, wave packet scattering, finding hidden symmetries, and simulating quantum physics. I hope many of you will enjoy learning more about, in their words, “the benefits of … studying the notion of an algorithm through the perspective of the physical laws of the universe.”

Which research result excited you the most in the past year? We’re not asking for the one you thought most important, or the one that would be most exciting to everyone, but which one got you, personally, most excited.

I’ll start things off with a result that delighted me so much I went around smiling all day, only feeling sad that more people couldn’t appreciate it! The result, that appeared in two papers almost simultaneously, is that some quantum states are too entangled to be able to compute one way. The result enchants me because it is surprising, fundamental, and related to topics close to my heart. Prior to these papers, the conventional wisdom held that more entanglement could only help quantum computation. It came as a complete surprise that it could hurt!  Dave Bacon writes beautifully and succinctly about these startling results in his viewpoint, published in Physics, about the two papers published together in Physics Review Letters 102 last May. Here I give an briefer account in order to explain why these result delighted me so much.

(more…)

In yesterday’s post, I mentioned that one of my favorite topics is classical results informed by the quantum information processing viewpoint. There are now sufficiently many such results that Drucker and deWolf have written a survey, “Quantum Proofs for Classical Theorems.” I was surprised last month, when another such  example popped up in one of the biggest cryptographic results of 2009, Craig Gentry’s discovery of a fully homomorphic encryption scheme.

(more…)

Wiley’s Handbook of Technology Management, which includes my entry on Quantum Computing, just appeared. I received my tome in the mail today. It is definitely the biggest, weightiest, and most expensive publication I’ve contributed to yet! I was only willing to write the entry if I could also post it on the ArXiv. Wiley agreed, so you can find my entry on the ArXiv as “An Overview of Quantum Computing for Technology Managers.”

I hope the entry conveys the excitement of the field while eliminating some of the hype.  It is focused on what is known about what quantum computers can and cannot do. It does not try to explain how they do what they do. (For that, my tutorial with Wolfgang Polak remains a good starting place.) While the entry discusses well known aspects of quantum computation, such as Shor’s algorithm, quantum key distribution, and quantum teleportation,  it also discusses many lesser known results including more recent algorithmic results and established limitations on quantum computation. I had the pleasure of writing about some of my favorite topics in quantum computing, including purely classical results inspired by the quantum information processing point of view, the elegant cluster state model of quantum computation, and Aaronson’s suggestion that limits on computational power be considered a fundamental guiding principle for physical theories, much like the laws of thermodynamics.

Comments and questions welcome!