If $A^4=B^4=AB=I$, what is a good circuit for $\sqrt A\sqrt B$?

Question

TL/DR

What is a good circuit for: $$\frac{1}{2}\begin{pmatrix} -i & i & 1 & 1 \\ 1 & 1 & -i & i \\ i & -i & 1 & 1 \\ 1 & 1 & i & -i\end{pmatrix},$$

as this may be a useful matrix for taking square roots of other unitaries?

EDIT - there are some significant errors in my question, and I retract the setup. For example the initial circuit below is improper in at least three ways, as I didn't phase the ancillae, I got the IQFT wrong, and I didn't uncompute properly.

But I don't want to delete the question as @CraigGidney's answer is still valid to the original question, and his pointers to his posts are instructive, and deserves the check!

---

Separate Square Roots

In more detail, given two unitary operators $A,B$ acting on an $n$-qubit state $|\psi\rangle$, where $A$ and $B$ are inverses of each other, e.g., $AB=BA=I$, and both $A$ and $B$ are of order $4$, e.g., $A^4=B^4=I$, we wish to find a good circuit for $\sqrt A\sqrt B$, as this might be part of a product formula for Hamiltonian simulation.

Initially we can construct the square roots for each of $A$ and $B$ separately, noting that because the eigenvalues of $A$ and $B$ are the fourth roots of unity, e.g., $\pm i, \pm 1$, we can use two ancillae for phase estimation with $S$ gates that rotate the ancillae and take the roots:

The last Hadamard gates are included to emphasize that the ancillae all revert back to $|0\rangle$.

---

Parallel Circuit

Because $[\sqrt A, \sqrt B]=0$, i.e. the above circuits commute, we can execute them in parallel with four ancillae (two at the top and two at the bottom):

With the above parallel circuit, we have six controlled applications each of $A$ and $B$, sixteen Hadamard gates, and eight $S$/$CS$ gates.

---

Initial Serial Circuit

But in the first circuits the ancillae revert back to $|0\rangle$, and we can also execute them in series:

This only uses two ancillae, with the same number of gates as, but double the depth of, the parallel circuit.

---

Simplified Serial Circuit

However, recall that $H^2=I$, and we also were given that $AB=A^2 B^2=I$. Thus much of the above cancels out, leaving:

This simplified serial circuit uses two ancillae and six $S$ and one $CZ$ gate, but with ten $H$ gates and significantly only three controlled applications each of $A$ and $B$.

---

Question

Quirk tells us that the remaining highlighted circuit in the middle of the last figure is equal to the matrix mentioned in the intro:

$$\frac{1}{2}\begin{pmatrix} -i & i & 1 & 1 \\ 1 & 1 & -i & i \\ i & -i & 1 & 1 \\ 1 & 1 & i & -i\end{pmatrix}.$$

I suspect the highlighted circuit could be simplified further still. Can the above circuit/matrix be simplified any more, using, say, Clifford+$T$ gates?

Indeed, the $S$ gates, the $CZ$ gate, etc. are all Clifford gates anyways (although cube roots/fourth roots/etc. would use non-Clifford gates).

Answer 1

What is a good circuit for [...]

Here's a circuit that does it.

[rest of your question]

Congrats, you've rediscovered that phase kickback can be used to implement powers of operations! But it's not just limited to cases where the eigenvalues are multiples of i, such as the fractional fourier transform. It works for anything (but only efficiently if you can implement big powers of the operation). For example, you can use it to turn incrementing into a continuous operation: