# Existence of unitary matrix that produces quantum coin with given frequencies via iteration

I'm curious about for which $$n$$ there exists a $$2\times 2$$ unitary matrix $$U(n)$$ such that for $$1 \le k \le n$$ $$|U^k_{1,0}(n)|^2 = \frac kn,$$ where $$U^k_{1,0}(n)$$ is the lower left element of the $$k$$th power of $$U(n)$$.

The idea is that if such a matrix exists, then applying it $$k$$ times to the quantum state $$|0\rangle$$ will produce the quantum state $$\sqrt{1-k/n}|0\rangle + \sqrt{k/n}|1\rangle$$ modulo some phases, a "quantum coin" with probability $$k/n$$ of giving outcome 1.

It's easy to see that it exists for $$n=2$$, with an example being $$U(2) = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & -1 \\ 1 & 1 \end{pmatrix},$$ but I couldn't find an example for any other $$n$$. A bit of brute force shows that no such matrices exist for $$n=3$$, and suggests that indeed no other $$n$$ works. Perhaps there's an elegant way to prove this? Or maybe there is a construction that I missed?

I originally posted this question on Mathematics Stack Exchange, but nobody was interested about it there.

## 2 Answers

Let's try a general construction. We know that, to satisfy the $$k=1$$ instance, we need $$U_{1,0}=1/\sqrt{n}$$, up to a possible phase. But we can always take one of the elements of $$U$$ to be real by removing a global phase.

We also know that the sum mod-square of the rows and columns for a unitary is 1, and that the rows must be mutually orthogonal. This gives us a lot of structure for $$U$$. $$U=\frac{1}{\sqrt{n}}\left(\begin{array}{cc} \sqrt{n-1}e^{i\theta_1} & -e^{i(\theta_4+\theta_1)} \\ 1 & \sqrt{n-1}e^{i\theta_4} \end{array}\right).$$ Now we just start multiplying it together. We find that $$|U_{1,0}^2(n)|^2=\frac{4(n-1)}{n^2}\cos^2((\theta_1-\theta_4)/2).$$ So, for all $$n\geq 2$$, there's a solution for $$\theta_1-\theta_4$$ that gives a working $$k=2$$. Next, $$k=3$$: $$|U_{1,0}^3(n)|^2=\frac{(2 (n-1) \cos (\theta_1-\theta_4)+n-2)^2}{n^3}$$ Since we already know the value of $$\cos^2((\theta_1-\theta_4)/2)=n/(2(n-1))$$, we can use the double angle formula to find $$\cos (\theta_1-\theta_4)=1/(n-1)$$. Hence $$|U_{1,0}^3(n)|^2=\frac{1}{n}\neq\frac{3}{n}.$$ Hence, this only works for $$n=1,2$$ where we do not require that the $$k=3$$ condition is satisfied.

For a more elegant version, note that if the relation holds for $$k=n$$, it must be that $$U^n=e^{i\phi}\left(\begin{array}{cc} 0 & e^{-i\theta} \\ e^{i\theta} & 0 \end{array}\right)=e^{i\phi}(\cos\theta X+\sin\theta Y).$$ $$U$$ must be an $$n^{th}$$ root of this, so $$U^k=e^{ik\phi/n}\left(I\cos(k\pi/(2n))+i\sin(k\pi/(2n))(\cos\theta X+\sin\theta Y)\right).$$ In other words, $$|U^k_{1,0}|^2=\sin^2(k\pi/(2n))\neq \frac{k}{n},$$ with the exception of $$k=1,n=2$$ which, as we already know, does work. (There are a few phase freedoms floating around here, but they don't make a difference to the final answer. I don't want to worry about them because it detracts from the simple concept of this answer.)

• Your "more elegant" version is not correct. It excludes the case $k=1,n=2$, for which the construction does work. A possible solution for $|U^k_{1,0}|^2$ is $\sin^2(k\pi/(2n))$, but this is not the most general possible, as for $k=1,n=3$ it does not allow for $X^3 = X$. – Mateus Araújo Dec 7 '20 at 13:38
• @MateusAraújo I was being lazy about the one case that we do know does work. As for your second comment, this was what I meant by "there are a few phase freedoms" One of those is that the rotation angle of $U$ can be any $\alpha$ such that $n\alpha\text{ mod }2\pi=\pi$. – DaftWullie Dec 7 '20 at 13:49
• But it seems I did miss a factor of 1/2 in the angle of rotation. – DaftWullie Dec 7 '20 at 13:54
• But the missing phases do matter. In general you have $|U^k_{1,0}|^2 = \sin^2(\frac{k\pi}{n}(\frac12 + l))$ for any integer $l$. – Mateus Araújo Dec 7 '20 at 14:05
• I agree they give different numbers. I don't believe they give a different conclusion. – DaftWullie Dec 7 '20 at 14:13

This is a correct version of the "elegant" version of DaftWullie's answer.

If the relation holds for $$k=n$$, then $$U^n = \begin{pmatrix} 0 & e^{-i\theta} \\ e^{i\theta} & 0 \end{pmatrix},$$ modulo a global phase. Since the eigenvalues of $$U^n$$ are $$\pm 1$$, we have that $$(I+U)/2$$ and $$(I-U)/2$$ are orthogonal projectors, and thus $$U = e^{i \frac{2\pi a}{n}}(I+U^n)/2 + e^{i(\frac\pi n+\frac{2\pi b}{n})}(I-U^n)/2$$ for some integers $$a,b$$. The $$k$$th power is then just $$U^k = e^{i \frac{2\pi k a}{n}}(I+U^n)/2 + e^{i(\frac{\pi k} n+\frac{2\pi k b}{n})}(I-U^n)/2$$ Modulo a global phase, $$U^k$$ is then equal to $${U'}^k = I(1+e^{i(\frac{\pi k} n+\frac{2\pi k l}{n})})/2 + U^n(1-e^{i(\frac{\pi k} n+\frac{2\pi k l}{n})})/2,$$ for some integer $$l$$, which implies that $$|U^k_{1,0}|^2 = \sin^2\left(\frac{k\pi}{n}\left(\frac12+l\right)\right).$$ This will be equal to $$k/n$$ for $$l=0$$ and $$n=2k$$, for example. In general it doesn't work, though, because for $$k=1$$ we need that $$\frac{\pi}{n}\left(\frac12+l\right) = \pm\arcsin\frac{1}{\sqrt{n}},$$ but $$\arcsin\frac{1}{\sqrt{n}}$$ is only a rational multiple of $$\pi$$ for $$n=1,2,$$ and $$4$$.

The cases $$n=1,2$$ do work, but for $$n=4$$ we would need $$\frac{\pi}{4}\left(\frac12+l\right) = \pm\frac{\pi}{6},$$ which is not possible for integer $$l$$.