In block encoding, how to determine the dimension of the elements from $\alpha(⟨0|^{\otimes a}\otimes I)U(|0〉^{\otimes a}\otimes|\psi〉)=A|\psi〉$?

Question

The block-encoding framework shows the following statement in general, as discussed in the paper https://arxiv.org/abs/1804.01973.

A block-encoding of a matrix $A \in \mathbb{C}^{N \times N}$ is a unitary $U$ such that the top left block of $U$ is equal to $A / \alpha$ for some normalizing constant $\alpha \geq\|A\|$: $$ U=\left(\begin{array}{cc} A / \alpha & \\ \cdot & \cdot \end{array}\right) $$ In other words, for some $a$, for any state $|\psi\rangle$ of appropriate dimension, $$\alpha\left(\left\langle\left. 0\right|^{\otimes a} \otimes I\right) U\left(|0\rangle^{\otimes a} \otimes\right.\right |\psi\rangle)=A|\psi\rangle.$$

My question is to find out the dimension of the elements from $$\alpha\left(\left\langle\left. 0\right|^{\otimes a} \otimes I\right) U\left(|0\rangle^{\otimes a} \otimes\right.\right.|\psi\rangle)=A|\psi\rangle.$$ I am not sure where $a$ came from in $|0\rangle^{\otimes a}$, and not sure what the dimension of $I$ is in this expression.

Any help could be highly appreciatedted!

Answer 1

$U$ can be written as: $$U=\begin{pmatrix}\frac{1}{\alpha}A&B\\C&D\end{pmatrix}$$ while $|0\rangle^{\otimes a}\otimes|\psi\rangle$ can be written as: $$|0\rangle^{\otimes a}\otimes|\psi\rangle=\begin{pmatrix}|\psi\rangle\\0\end{pmatrix}$$ We thus have: $$U\left(|0\rangle^{\otimes a}\otimes|\psi\rangle\right)=\begin{pmatrix}\frac{1}{\alpha}A&B\\C&D\end{pmatrix}\begin{pmatrix}|\psi\rangle\\0\end{pmatrix}=\begin{pmatrix}\frac{1}{\alpha}A|\psi\rangle\\C|\psi\rangle\end{pmatrix}$$ and then: $$\alpha\left(\langle0|^{\otimes a}\otimes I\right)U\left(|0\rangle^{\otimes a}\otimes|\psi\rangle\right)=\alpha\begin{pmatrix}I & 0\end{pmatrix}\begin{pmatrix}\frac{1}{\alpha}A|\psi\rangle\\C|\psi\rangle\end{pmatrix}=A|\psi\rangle$$

Is is now easy to see that $I$ must have the same size as $A$, which is the $N\times N$ identity matrix, while $a$ is equal to $\frac{n}{N}$, where $n$ is the dimension of $U$. You can also see in the last equation that the $\alpha$ at the beginning of the product cancels out with the $\frac{1}{\alpha}$ factor applied to $A$ in $U$.