Is Controlled$(R_z(\theta))$ more expensive than Controlled$(Z^t)$ on the surface code?

Question

There are (at least) two conventions for single-qubit, arbitrary-angle Z rotations in quantum computing, which I will call Rz(theta) and Z^t.

$$ R_Z(\theta) = \exp(-i \theta Z/2) = \mathrm{diag}(e^{-i \theta/2}, e^{i \theta/2}) \\ Z^t = \mathrm{diag}(1, (-1)^t) = \mathrm{diag}(1, e^{i \pi t}). $$

In Cirq, these are Rz and ZPowGate. In OpenQASM3 these are rz and p "phase". They are related by a global phase

$$ R_Z(\theta) = e^{-i \theta/2} Z^{\theta / \pi}. $$

Global phase doesn't matter until you start controlling operations, so Controlled(Z^t) is not the same as Controlled(Rz(t/pi)).

When doing lattice surgery on the surface code, arbitrary-angle rotations are very expensive; so I'd like to find compilations of C(Z^t) and C(Rz(t/pi)) that minimize the number of uncontrolled, arbitrary-angle rotations.

A circuit for C(Z^t) using one arbitrary-angle rotation is given in https://arxiv.org/abs/1204.0567, figure 8. Is there an earlier reference that contains this circuit identity?

You can do C(Rz(t/pi)) with two arbitrary-angle rotations, e.g. https://docs.pennylane.ai/en/stable/code/api/pennylane.CRZ.html#pennylane.CRZ.compute_decomposition. Is there a reference for this circuit identity I can cite?

Is there a way to do C(Rz) with only one arbitrary-angle rotation?

or alternatively...

Is it possible to prove that you need two arbitrary-angle rotations to implement C(Rz)?

Answer 1

TL;DR: We need at least two arbitrary-angle rotations to implement $CR_z(\theta):=\mathrm{diag}(1,1,e^{-i\theta/2},e^{i\theta/2})$ using unitary gates and auxiliary qubits. This follows from the observation that every circuit realizing $CR_z$ using a single $R_z$ gives rise to a matrix similarity between $CR_z$ and $R_z\otimes I$. But $CR_z$ has three distinct eigenvalues while $R_z\otimes I$ only has two.

Assumption

First we formalize the assumption that $CR_z$ can be implemented using a single arbitrary-angle rotation and then derive a contradiction.

Consider a register of $n+2$ qubits $q_0,q_1,a_1,\dots,a_n$ where $q_0$ and $q_1$ are input/output qubits and $a_1,\dots,a_n$ are auxiliary qubits that are initialized and returned to the $|0^n\rangle$ state. Suppose that there exist unitaries $U$ and $V$ and a non-constant function $f:[0,2\pi)\to[0,2\pi)$ such that applying a unitary $U$ to all $n+2$ qubits, followed by $R_z(\alpha)$ on$^1$ $q_0$, followed by $V$ on all $n+2$ qubits sends $|\psi\rangle\otimes|0^n\rangle$ to $(CR_z(f(\alpha))|\psi\rangle)\otimes|0^n\rangle$. In other words, we assume that \begin{align} CR_z(f(\alpha))=\langle 0^n|V\circ (R_z(\alpha)\otimes I)\circ U|0^n\rangle\tag1 \end{align} where $\circ$ denotes serial composition, $\otimes$ denotes parallel composition, i.e. tensor product, and $I$ denotes the identity operator on $n+1$ qubits $q_1,a_1,\dots,a_n$. Crucially, $U$ and $V$ are independent of $\alpha$.

Contradiction

Let $f_0:=f(0)$ and hit $(1)$ with $CR_z(-f_0)$ on the left to get \begin{align} CR_z(g(\alpha)) = \langle 0^n|V'\circ (R_z(\alpha)\otimes I)\circ U|0^n\rangle\tag2 \end{align} where we defined $g(\alpha):=f(\alpha)-f_0$ and absorbed $CR_z(-f_0)$ into $V'$. But $g(0)=0$, so $\langle 0^n|V'\circ U|0^n\rangle$ is the identity on $q_0$ and $q_1$. Therefore, we can choose$^2$ $V'$ to be the inverse of $U$. But then $U^\dagger\circ (R_z(\alpha)\otimes I)\circ U$ is similar to $R_z(\alpha)\otimes I$ and thus has the same eigenvalues. Moreover, by unitarity, the spectrum of $\langle 0^n|U^\dagger\circ (R_z(\alpha)\otimes I)\circ U|0^n\rangle$ is a subset of the spectrum of $U^\dagger\circ (R_z(\alpha)\otimes I)\circ U$. In particular, $\langle 0^n|U^\dagger\circ (R_z(\alpha)\otimes I)\circ U|0^n\rangle$ has at most two distinct eigenvalues. On the other hand, $CR_z(g(\alpha))$ has three distinct eigenvalues unless $g(\alpha)=0$. Therefore, $f$ is constant. The contradiction means that $CR_z$ cannot be implemented using a single $R_z$.

---

^{$^1$ The choice of qubit does not sacrifice generality.
$^2$ By appropriately choosing the irrelevant action of $V'$ on the subspace orthogonal to $\mathbb{C}^4\otimes|0^n\rangle$.}