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?
Thanks for the comment, Lance.
ReplyDeleteOne 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
Lance,
ReplyDeleteSorry 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?