# Can you take infinitely many square roots of Pauli-X?

I am trying to find the cost for a n-bit Toffoli gate based on the recurrent circuit presented on Barenco's Work in Lemma 7.5 (Elementary gates for quantum computation)

The construction requires that we iteratively take the square root of Pauli X. I was wondering if there is some proof that we can always take the square root of Pauli X as many times as possible?

In the case of the Pauli X matrix, the eigenvectors are $$|+\rangle\langle +|$$ and $$|-\rangle\langle -|$$ so you can find roots like this:
$$X^s = \frac{1}{2}\begin{bmatrix} 1 & 1 \\ 1 &1\end{bmatrix} + \frac{e^{i \pi s}}{2}\begin{bmatrix} 1 & -1 \\ -1 & 1\end{bmatrix}$$
Once that's done the actual challenge is realizing $$X^s$$ gates using the gate set you have available on your computer. For example, if you're using the Clifford+T gate set then you could approximate the rotation using a series of H and T gates.
• I found that website, It seems it yours by the icon :) Thank you so much for the info! I'll take a look. I found that using the recursive lemma on Barenco's we would need $O(3^{n-2})$ gates where n is the number of control qubits on the cnot. Aug 17 '20 at 6:23