[Computational Complexity] 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?
Posted by Lance to Computational Complexity at 3/07/2006 04:31:00 PM