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 ?

  • $\begingroup$ 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? $\endgroup$ – Mahdi Cheraghchi Dec 6 '11 at 3:21
  • $\begingroup$ 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) $\endgroup$ – Suresh Venkat Dec 6 '11 at 4:07
  • $\begingroup$ crossposted on theoretical physics (theoreticalphysics.stackexchange.com/questions/651/…) $\endgroup$ – Suresh Venkat Dec 10 '11 at 23:07
  • 1
    $\begingroup$ possible duplicate of Reading up on $BQP = BPP^{BQNC}$ $\endgroup$ – Greg Kuperberg May 17 '15 at 15:23

Not exactly what you are looking for, I know, but geodesics have been used to prove optimal state transfer rates in Ising spin chains (see arXiv:0705.0378). I'm not sure how related this is to Nielsen's approach, as I haven't read that particular paper, but I remember thinking this was quite a neat result when it first came out. Basically this is the minimum time to transfer a quantum state from one end of a linear array of qubits to the other. It is a very simple problem, but in the above paper they show that the transfer can be achieved significantly faster than was previously believed (although of course there is still a linear scaling, with the speed-up in the constant).

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.