# 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).

• Mark, would it be possible for you to elaborate a bit about the application of this?
– Lior
Commented Feb 27, 2022 at 6:46