Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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 ?
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).
