# How to find a circuit for the roots of QFT?

After reading about using quantum gates instead of ancillas, it asserts that every quantum circuit has a square root. Theoretically, they do, but is there a practical method to generate the quantum circuit of the square root of arbitrary gates? Specifically, I'm interested in knowing if $$\sqrt[2^k]{QFT}$$ Has a concise, practical representation as a quantum circuit. Besides from diagonalizing the matrix by hand and then using the sledgehammer of quantum circuits for arbitrary isometries, i see no other possible method.

Wikipedia says: "Squared root-gates can be constructed for all other gates by finding a unitary matrix that, multiplied by itself, yields the gate one wishes to construct the squared root gate of. All rational exponents of all gates can be found similarly" but provides no proof or associated reference to that claim.

Help and insights are greatly appreciated.

Existence (as mentioned on Wikipedia, for example), is easy, although not necessarily unique. Any unitary can be written as $$U=\sum_ie^{i\theta_i}P_i$$ where $$P_i$$ are projectors such that $$\sum_iP_i=1$$, and $$\theta_i$$ is in the range 0 to $$2\pi$$. Then we have that $$\sqrt{U}=\sum_ie^{i\theta_i/2}P_i.$$

Giving a circuit construction of the gate is an entirely non-trivial matter. There is no simply conversion that you can run on a circuit for a given $$U$$ to create a circuit for $$\sqrt{U}$$.

One method (even if you don't know anything about the $$U$$) is that if you can implement $$U$$ then you can implement controlled-$$U$$ (just replace all gates with their controlled versions. It's probably overkill, but is guaranteed to work). Then you can use those as part of a phase estimation. Apply a phase on the ancilla system corresponding to half the phase of the original unitary, and then apply the inverse of phase estimation. The details can be found here.

One simplification that you can make is that if $$U=VWV^\dagger,$$ then $$\sqrt{U}=V\sqrt{W}V^\dagger,$$ so if you have your circuit and can find a big section corresponding to $$V$$, you can remove it and just worry about implementing the square root of the remaining component $$W$$.

You'll notice that I'm not giving a proof that square roots are hard to come up with. It'll vary on a case by case basis. But think about the opposite task of creating integer powers of a unitary. Usually, we cannot do any better than repeated application of the original unitary. Just look at what you get in one of the very few special cases where you can compute higher powers more efficiently: you get Shor's factoring algorithm! (The point being that phase estimation becomes vastly more efficient.) If you could generically do better, you could apply phase estimation to Grover's search and you'd have a faster search algorithm.

There is a known circuit construction https://arxiv.org/abs/quant-ph/0208130

Also check this post https://algassert.com/post/1710
It uses phase estimation ideas to derive the resulting circuit