
An algorithm of a n-qubit quantum computation system is a unitary operation \(U \in U(2^{n})\) , which can evolve the n-qubit initial state \(|\psi _{ini}\rangle =|00...0\rangle \)  to the final state \(|\psi _{fin}\rangle =U|\psi \rangle _{ini}\) . \(U(2^n)\)  is the space of the unitary operations of n-qubits, which is both a manifold and a Lie group.

Any physical realization of the algorithm \(U\)  is a curve \(U(t)\in U(2^n),t\in [0,1]\)  with \(U(0)=I,U(1)=U\) , where \(I\)  is the identity operator. A smooth curve \(U(t)\)  can be achieved by a Hamiltonian \(H(t)\)  so that \(\dot{U}(t)=-iH(t)U(t)\) , where \(H(t)\)  is in the tangent space of \(U(2^n)\)  at \(U(t)\)  and also an element of the Lie algebra \(u(2^n)\) .

A Riemannian metric \(\langle \cdot ,\cdot \rangle _U\)  can be introduced to the manifold \(U(2^n)\)  so that a Riemannian structure can be built on \(U(2^n)\) . The metric is defined as
\(\langle H,J\rangle _U=[tr(H\mathcal {P}(J))+q tr(H\mathcal {Q}(J))]/2^n\) 
where \(J,P\)  are tangent vectors in the tangent space at \(U\) , and \(\mathcal {P}(J)\)  is the projection of \(J\)  to a simple local Hamiltonian space \(P\) , \(\mathcal {Q}=1-\mathcal {P}\)  and \(q>>1\) . With this metric any finite length curve \(U(t)\)  connecting the identity \(I\)  and \(U\)  will only contain local Hamiltonian when \(q\rightarrow \infty \) . Usually the geodesic \(U_{geo}(t)\)  connecting \(I\)  and \(U\)  has the minimal length, which is defined as the complexity of the algorithm \(U\) . We also know the geodesic is given by the EPDiff equation, which is obtained by solving the optimization problem \(\min _{H(t)} \int \langle H(t),H(t)\rangle _{U}^{1/2}dt\) .

The quantum circuit model of quantum computations tells us that any \(U\)  can be approximated with any accuracy with a small universal gate set, which contains only simple local operators, for example only a finite number of 1 and 2 qubit operators. The quantum circuit model can then be understood as approximating \(U(t)\)  with a piecewise smooth curve, where each segment corresponds to a universal gate. It's proven in [1]}[2]} that the number of universal gates to approximate \(U\)  within some constant error is given by \(O(n^{t}d(I,U)^{3})\) , where \(d(I,U)\)  is the geodesic distance between \(I\)  and \(U\) . So an algorithm \(U\)  can be efficiently realized by the quantum circuit model only when its geodesic distance to the identity operator \(I\)  is polynomial with respect to \(n\) .

The set of operators that can be reached by a geodesic with a length that is polynomial with the qubit number n is only a small subset of \(U(2^n)\) . Equivalently, starting from a simple initial state \(|\psi \rangle _{ini}=|000...0\rangle \) , the quantum state that can be obtained efficiently by local quantum operations is a small subset of the quantum state space. This defines the complexity of a quantum state.

Finding the geodesic \(U^{geo}(t)\)  can be achieved by either the lifted Jacobi field or standard geodesic shooting algorithm. The performance of the optimization procedure to find \(U_{geo}(t)\)  highly depends on the curvature of the Riemannian manifold. For the metric given in (REF ), the sectional curvature is almost negative everywhere when \(q\)  is large enough. This means the geodesic is unstable and it's general difficult to find a geodesic.

<FIGURE>