Product of block-encoded matrices

Question

I am trying to understand just the first step of the proof fo Lemma 53 of this paper, with scarce success.

Before starting, let me state this definition:

Definition: Block encoding of operator A. Let $A$ be a $s$-qubit operator, and $\alpha, \epsilon \in \mathbb{R}_+$ and $a \in \mathbb{N}$. Then, we say that a $(s+a)$-qubit unitary $U$ is a $(\alpha, a, \epsilon)$ block encoding of $A$ if: $$\|A - \alpha(\langle0|^{\otimes a} \otimes I) U (|0\rangle^{\otimes a} \otimes I) \| \leq \epsilon $$

This is the statement I would like to prove:

Lemma 53: (Product of block-encoded matrices) If $U$ is an $(\alpha, a, \delta)$-block encoding of an $s$-qubit operator $A$, and $V$ is an $(\beta,b,\epsilon)$-block encoding of a s-qubit operator $B$, then $(I_b \otimes U)(I_a \otimes V)$ is an ($\alpha\beta, a+b, \alpha\epsilon + \beta\delta)$-block encoding of $AB$.

The first step of the proof is writing the definition of block encoding, which for this case s: $$\| AB - \alpha\beta(\langle 0| ^{\otimes a+b} \otimes I )(I_b \otimes U)(I_a \otimes V)(|0\rangle^{\otimes a+b} \otimes I) \| =$$

I understand all the steps of the proof, but I don't understand the first passage. Why the previous equation should be equal to:

$$=\|AB - \alpha(\langle 0| ^{\otimes a} \otimes I )U(|0\rangle ^{\otimes a} \otimes I )\beta(\langle 0|^{b} \otimes I)V(|0\rangle^{\otimes b} \otimes I) \| $$

This looks similar to the cases where I can apply the property that: $$(A \otimes B)(|x\rangle \otimes |y\rangle) = (A|x\rangle \otimes B|y\rangle) $$

But I really don't see how in this case. I suppose there is some abuse of notation hidden somewhere. Probably, knowing the dimension of the various $I$ identity matrices would help the understanding..

Remark: in the statement of the Theorem there is a small footnote where they claim "The identity operators act on each others ancilla qubits, which is hard to express properly using simple tensornotation, but the reader should read this tensor product this way."

Answer 1

The remark that you state is absolutely critical. Let's try and introduce a notation that takes the spaces into account better. So, we're going to have a set of $a$ qubits denoted $C$, a set of $b$ qubits denoted $D$ and a set of $s$ qubits denoted $S$. Now I can use $U_{CS}$ to mean apply $U$ on qubits in sets $C$ (the ancillas) and $S$, and act as identity on the qubits in set $D$.

The calculation that they are doing is $$ \left\|AB-\alpha\beta(\langle 0|^{\otimes(a+b)}_{C,D}\otimes I_S) U_{CS}\cdot V_{DS}(|0\rangle^{\otimes(a+b)}_{C,D}\otimes I_S)\right\|. $$ Now, because you know that $U$ acts as $I$ on qubits $D$, the $\langle 0|^{\otimes b}_D$ just moves past that operator. $$ =\left\|AB-\alpha\beta(\langle 0|^{\otimes a}_{C}\otimes I_S) U)\cdot(\langle 0|^{\otimes b}_D\otimes I_{C,S}))\cdot V_{DS}(|0\rangle^{\otimes(a+b)}_{C,D}\otimes I_S)\right\|. $$ You'll note that now $U$ is only acting on qubits from sets $C$ and $S$ so I don't need the subscripts any more. We can do a similar thing with the $|0\rangle^{\otimes a}_C$ as $V_{DS}$ only acts as $I$ on the $C$ qubits. Thus, $$ =\left\|AB-\alpha\beta(\langle 0|^{\otimes a}_{C}\otimes I_S) U\cdot(\langle 0|^{\otimes b}_D\otimes I_{C,S}))\cdot(|0\rangle^{\otimes a}_C\otimes I_{D,S}) V(|0\rangle^{\otimes b}_{D}\otimes I_S)\right\|. $$ This rearranges to give the result that you want, \begin{align*} &=\left\|AB-\alpha\beta(\langle 0|^{\otimes a}_{C}\otimes I_S) U\cdot(|0\rangle^{\otimes a}_C\otimes I_{S})\cdot(\langle 0|^{\otimes b}_D\otimes I_{S}))\cdot V(|0\rangle^{\otimes b}_{D}\otimes I_S)\right\|. \\ &=\left\|AB-\alpha\beta(\langle 0|^{\otimes a}\otimes I) U(|0\rangle^{\otimes a}\otimes I)\cdot(\langle 0|^{\otimes b}\otimes I)) V(|0\rangle^{\otimes b}\otimes I)\right\|. \end{align*}