Tuesday, March 07, 2006

Computation and Geometry

Michael Nielsen returns to blogging after seven months since his last real post. He talks about his new Science paper Quantum Computation as Geometry with Dowling, Gu and Doherty. Last year Nielsen had an arXiv paper A Geometric Approach to Quantum Circuit Lower Bounds where he showed one can bound the minimal-size quantum circuit to implement a unitary operation U by the length of the minimal geodesic between the identity and U. The new Science paper shows the other direction, given a short path one can find an efficient quantum circuit.

While others are also trying geometric approaches to separate complexity classes, by having a tight result, the minimal geodesic gives us the right bound. Nielsen also shows that finding the minimal geodesic is as hard as solving a lattice closest vector problem, which means this approach might not have the constructivity requirement of Razborov-Rudich Natural Proofs. Since quantum circuits can simulate classical circuits, one can possibly prove classical lower bounds as well, maybe even an attack on P versus NP?

Well, I can dream, can't I?

1. Thanks for the comment, Lance.

One point of clarification is about the connection to the closest vector problem (CVP). Unfortunately, the first paper doesn't show that finding the length of the minimal geodesic is necessarily equivalent to solving a closest vector problem. All it shows is an equivalence between the closest vector problem and finding the minimal geodesic amongst a certain special class of geodesics, which I call Pauli geodesics.

To make this connection to CVP really useful, we'd need a guarantee that the minimal geodesic is, in fact, a Pauli geodesic. In my paper I prove that this will be the case if the minimal geodesic is unique, but there's no guarantee I know of that this will be the case for problems of interest. So the connection to CVP is, at best, incomplete.

The question of to what extent Razborov-Rudich applies to the geometric approach to quantum computing is a really interesting one, and it's not yet clear to me what the answer is.

Michael Nielsen

2. Lance,
Sorry for offtopic. There seems to be some P/NP-related activity in group-theory community, for example this workshop - http://math.berkeley.edu/index.php?module=announce&ANN_user_op=view&ANN_id=56
Participants are very well-known mathematicians. I wonder if you are aware and maybe able to provide us with some additional info?