I am considering the unitary operation manifold for quantum computation. In order to examine the computational complexity of an algorithm using n qubits, we need to define the complexity of a certain unitary operation $U\in SU(2^n)$, where $U$ carries the initial state to the final state of the computation. Usually this is done by define it as the minimal number of simple gates (working on less than 2 qubits) to approximate $U$. Nielsen shows a Riemannian geometrical description of it where a certain Riemannian metric is defined on $U\in SU(2^n)$ to only count the 'number' of simple gates but put a high penalty on complex gates. Then the complexity problem is understood as finding the shortest geodesic connecting $I$ and $U$ with the given Riemannian metric on $SU(2^n)$. He also indicated that the curvature of this manifold is almost negative everywhere.

My question is: How can I judge the diameter of this manifold? I know usually there are upper bound of the diameter for a manifold with a positive lower curvature bound. But I can not find results on negative curvature manifold. Can I assume that this manifold does not have a finite diameter?

This is very important to understand the complexity of quantum computation and also the complexity of quantum states. We know that every unitary operation $U$ can be APPROXIMATED with an arbitrary accuracy with $e^{n}$ simple gates. For a quantum state, we can also define the complexity of the state as the minimal number of simple operations to achieve it from a simple initial state, for example a product state 000...0000. So this complexity should not be 'approximated' as in quantum computation since the word 'approximation' itself involves the definition of distance. My idea is that if the diameter of the above mentioned manifold is not finite, then we have states with an infinite complexity. If this is the case, and if also this is true for typical states of the state space, then this will change our understanding of quantum system since currently we think the maximal state complexity is $e^n$.

  • 1
    $\begingroup$ @x-dong Regarding the infinite complexity problem, perhaps it is worth looking at the problem backwards: Given any two arbitrary states (appropriately normalized), there do exist unitary operations $U(1 \rightarrow 2)$ that take state 1 into state 2. Because each such unitary op can be obtained from at most $e^N$ simple gates, the complexity of state 2 relative to state 1 cannot exceed $e^N$. Given that states 1 and 2 are otherwise arbitrary, according to your definition the diameter of the manifold cannot be larger than $e^N$. $\endgroup$ – udrv Aug 21 '15 at 19:01
  • $\begingroup$ Thanks for the answer. One question, do you mean a perfect implementation of the unitary operation by 'such unitary op can be obtained from at most eN simple gates'? Or just an approximation of it with a complexity of $e^n$? $\endgroup$ – XXDD Aug 22 '15 at 3:06
  • $\begingroup$ Sorry for using $N$, meant $n$. Had in mind that the approximation by $e^n$ gates can get arbitrarily close to the original unitary. The answer to your other question on the topic indicates a higher no. of gates is sufficient to give a perfect implementation, but I don't think it is actually necessary by virtue of the existence of arbitrarily accurate $e^n$ approximations. Unfortunately I don't know of any proof to this extent, but I am not up to date with the latest developments in the field. $\endgroup$ – udrv Aug 22 '15 at 3:45
  • $\begingroup$ Thanks. In fact what I am interested is the 'state complexity' of a quantum state, i.e., how it can be achieved perfectly from a simple product state by simple operators, but not to approximate it. So it's true you can always approximate the state with an arbitrary accuracy, but the state complexity of the state should not be defined by how you can approximate it. Instead it should be a 'precise' concept. For me, since 'complexity' means 'time', so the state complexity does matter if we consider the dynamic evolution of a system. Different complexity may set 'milestones' differently. Thanks. $\endgroup$ – XXDD Aug 22 '15 at 4:21

Your Answer

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

Browse other questions tagged or ask your own question.