<p>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 <a href="http://arxiv.org/abs/0705.0378" rel="nofollow">arXiv:0705.0378</a>). 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).</p>

CC BY-SA 3.0
2011-12-07T11:38:38.150Z
2011-12-07T11:38:38.150Z
Joe Fitzsimons
<p>Some of us have been reading <a href="http://arxiv.org/abs/quant-ph/0502070">Michael Nielsen's paper</a> 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$). </p>

<p>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 ? </p>

CC BY-SA 3.0
2011-12-06T03:21:03.633Z
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
CC BY-SA 3.0
2011-12-06T04:07:04.633Z
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
CC BY-SA 3.0
2011-12-10T23:07:41.627Z
crossposted on theoretical physics (http://theoreticalphysics.stackexchange.com/questions/651/lower-bounds-for-quantum-circuits-using-the-geodesic-framework)
Suresh Venkat
CC BY-SA 3.0
2015-05-17T15:23:45.033Z
possible duplicate of [Reading up on $BQP = BPP^{BQNC}$](http://cstheory.stackexchange.com/questions/6912/reading-up-on-bqp-bppbqnc)
Greg Kuperberg
<quantum-computing>
Lower bounds for quantum circuits using the geodesic framework
Suresh Venkat
# Lower bounds for quantum circuits using the geodesic framework

(Asked by: username_0 on 2011-12-06)

Some of us have been reading [Michael Nielsen's paper](http://arxiv.org/abs/quant-ph/0502070) 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 ?

**Tags:** quantum-computing
> **Comments:**
> **username_1**: 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?  
> **username_0**: 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)  
> **username_0**: crossposted on theoretical physics (http://theoreticalphysics.stackexchange.com/questions/651/lower-bounds-for-quantum-circuits-using-the-geodesic-framework)  
> **username_2**: possible duplicate of [Reading up on $BQP = BPP^{BQNC}$](http://cstheory.stackexchange.com/questions/6912/reading-up-on-bqp-bppbqnc)  

---

## 1 answers

### Answer by username_3 on 2011-12-07. Score: 4

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](http://arxiv.org/abs/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).


---

