Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am reading a paper on quantum automata, and within the proof of theorem $6$, there is the following statement (I have added a definition for completeness of the statement).

Let $U$ be a unitary matrix of rank $n$. Then, in its diagonal basis, $U$ rotates $n$ complex numbers on the unit circle by $n$ different angles $\omega_i$, $1 \leq i \leq n$. We can think of this as a rotation of an $n$-dimensional torus. If $V = (c\epsilon)^n$ is the volume of a $n$-dimensional ball of radius $\epsilon$, then $U^k$ is within a distance $\epsilon$ of the identity matrix for some number of iterations $k \leq \frac{1}{V}$.

Could anyone help me to understand the reasoning or give any hint to study and try to understand this?

share|cite|improve this question

I think it means this: As $U$ is unitary, it can be unitarily diagonalized as $U=Q^\ast DQ$, where $Q$ is a unitary matrix and $D$ is a diagonal matrix, say, $D=\operatorname{diag}(e^{i\omega_1},\ldots,e^{i\omega_n})$ with $\omega_j\in[0,2\pi)$ for each $j$. Therefore, $U^k=Q^\ast D^kQ$, where $D^k=\operatorname{diag}(e^{ik\omega_1},\ldots,e^{ik\omega_n})$. Now the paper claims that if $V=(c\epsilon)^n$ is the volumn of an $n$-ball with radius $\epsilon$ (so that $c^n\equiv\pi^{n/2}/\Gamma\left(\frac n2+1\right)$, if that matters), then for some natural integer $k\le\frac1V$, we have $|e^{ik\omega_j}-1|<\epsilon$ for every $j$. (Presumably $\epsilon$ is sufficiently small. Otherwise it is easy to find a counterexample.)

As to the torus bit, each $j$-th diagonal entry of $D^k$ represents a rotation on the Argand plane by the angle $k\omega_j$, and the locus of the rotations of the ball $B=\{(z_1,\ldots,z_n)\in\mathbb{C}^n: |z_j-1|<\epsilon\}$ by $D, D^2, D^3, \ldots$ lies on a torus. So, if the above statement on $k$ is true, then the ball will return to within a distance $\epsilon$ from its initial position after $k$ rotations. Yet I don't see how the statement on $k$ is proved in the paper.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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