10
$\begingroup$

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 ?

Improve this question
$\endgroup$
4
  • $\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, 2011 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, 2011 at 4:07
  • $\begingroup$ crossposted on theoretical physics (theoreticalphysics.stackexchange.com/questions/651/…) $\endgroup$
    – Suresh Venkat
    Dec 10, 2011 at 23:07
  • 1
    $\begingroup$ possible duplicate of Reading up on $BQP = BPP^{BQNC}$ $\endgroup$
    – Greg Kuperberg
    May 17, 2015 at 15:23

1 Answer 1

Reset to default
3
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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