# Lower bounds for quantum circuits using the geodesic framework

Some of us have been reading Michael Nielsen's paper on a geometric approach to using quantum lower bounds (in brief, the construction of a Finsler metric on $SU(2^n)$ such that the geodesic distance from $I$ to an element $U$ is a lower bound on the number of gates in a quantum circuit that computes $U$).

I was wondering if there were concrete examples of problems where this program led to a lower bound that came close to, matched or beat prior lower bounds obtained by other means ?

• Also, how does this program compare to Ketan Mulmuley's on "Geometric Complexity Theory"? Mulmuley's program turns the problem of finding a lower bound to an upper bounding problem. But here we are looking for a lower bound on the geodesic as I understand from your question, right? – Mahdi Cheraghchi Dec 6 '11 at 3:21
• It's a different program: in some ways more concrete, and useful for specific lower bounds (or maybe - that's what the question is about) – Suresh Venkat Dec 6 '11 at 4:07
• crossposted on theoretical physics (theoreticalphysics.stackexchange.com/questions/651/…) – Suresh Venkat Dec 10 '11 at 23:07
• possible duplicate of Reading up on $BQP = BPP^{BQNC}$ – Greg Kuperberg May 17 '15 at 15:23