Controlled unitaries in quantum singular value transformation

Question

tldr -- Building general polynomials with QSVT requires implementing controlled versions of vanilla QSVT circuits. Is this a trivial task? Does it change the complexity? How is it done in practice?

Quantum singular value transformation (QSVT) allows applying polynomial transformations to singular values of some matrix $A$ block-encoded into a unitary matrix $U$. A typical QSVT circuit looks something like (ignoring some details) $$U_{\phi}=\prod_i \Pi(\phi_{2i})U^\dagger \Pi(\phi_{2i+1})U$$ and consists of applications of $U$ and $U^\dagger$ interleaved with projector-based rotations.

The result is that $U_{\phi}$ block-encodes some polynomial function of $A$. However, the range of polynomials obtained in this way is limited and not always practical. E.g. they need to have definite parities and could not directly implement $e^{-ixt}$.

A workaround for this is to build two block-embeddings $U^{even}_\phi$ and $U^{odd}_\phi$ and combine them via the linear combination of unitaries. To do this, we need to be able to implement controlled versions of $U^{even/odd}_\phi$ and in particular controlled versions of $U,U^\dagger$ as well as $\Pi(\phi)$.

Is it in general easy to implement controlled $U/\Pi(\phi)$ or is this an independent assumption? Does implementing $C(U_\phi)$ change the complexity of the QSVT?

Answer 1

tldr

I found the answer in Lemma 19 of https://arxiv.org/abs/1806.01838. Controlled versions of projector rotations are easy to implement. Controlled version of the whole QSVT sequence can be obtained by controlling only the projectors (for even polynomials) or only projectors and a single $U$ (for odd polynomials).

Controlled projectors

Rotations $\Pi(\phi)$ are typically implemented assuming access to $C_\Pi NOT$ gates, use one ancilla qubit, and take the following form

To implement a controlled version of $\Pi(\phi)$ simply control the intermediate rotation, as follows

Choose $\phi^{0}=0, \phi^{1}=\phi$ to get the standard controlled $\Pi(\phi)$.

Controlled QSVT sequence

First consider a QSVT sequence featuring an even number of signal operators $$U_\phi=\prod_{i}\Pi_{\phi_{2i}}U^\dagger \Pi_{\phi_{2i+1}} U$$

To perform controlled version of this operation $C(U_\phi)$ we simply need to control the projectors

$$ C(U_\phi)=\prod_{i}C(\Pi_{\phi_{2i}})U^\dagger C(\Pi_{\phi_{2i+1}}) U$$

Indeed, if the control qubit is in $|1\rangle$ the $C(U_\phi)=U(\phi)$, else all projectors are replaced by identity operators and the whole sequence collapses to the identity $C(U_\phi)=\prod_i U^\dagger U=1$.

For an odd-degree polynomial QSVT sequence takes the form

$$U_{\phi}=\Pi_{\phi_0}U \prod_{i}\Pi_{\phi_{2i}}U^\dagger \Pi_{\phi_{2i+1}}U$$

and to implement $C(U_\phi)$ is suffices to additionally implement a single unbalanced controlled $U$

$$C(U_{\phi})=C(\Pi_{\phi_0})C(U) \prod_{i}C(\Pi_{\phi_{2i}})U^\dagger C(\Pi_{\phi_{2i+1}})U.$$