# 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
Feb 27, 2022 at 6:46

What is a good circuit for [...]

Here's a circuit that does it.

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:

• Thanks, how did you go from my 13-gate circuit to your six-gate circuit so quickly? Was it intuitive, or did you have it in your back-pocket? Or did you auto-synthesize it somehow? Feb 26, 2022 at 21:27
• @MarkS I opened Quirk and made a manual version that matched. Then I mirrored it so I had it then its inverse, so the overall operation was identity. Then I iteratively manually optimized one half while preserving the fact that the whole thing was an identity. I was verifying its identity-ness by applying it to entangled qubits and making sure they were in the same state at the end. Then the optimized half was the result. An alternative automated method that would have worked was using Cirq's KAK decomposition functionality, which can give min-CZ versions of any two qubit unitary. Feb 26, 2022 at 21:30
• @MarkS Ah, I made have made a mistake when copying the unitary matrix. I tried it again and got a different circuit. I started from the circuit link you gave this time, instead of trying to resynthesize the matrix, so it should be correct. I updated the answer. Feb 26, 2022 at 21:39
• @MarkS Specific things I used were: S commutes with CZ, CP conjugated by a Clifford U can be rewritten into C(UPU^dagger), etc. Feb 26, 2022 at 21:40