Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
I'm reading the lecture notes from Ronald de Wolf and got confused at the part where it introduces Block encoding, specifically by this notation at page 76:
More generally we can define an $a$-qubit block-encoding of $A$, which is an $(a + n)$-qubit unitary $U$ with the property that $(\langle 0^a|\otimes I)U(|0^a\rangle \otimes I)=A$.
How do I interpret $(\langle 0^a|\otimes I)U(|0^a\rangle \otimes I)$? Like having a tensor product between a ket vector and a $2^n\times 2^n$ matrix?
I will try to answer this question for myself. We know that an $a$-qubit quantum state $|\psi\rangle$ lives in a $2^a$-dimensional Hilbert space $\mathcal{H}$. The operator $\mathbb{1}$ acting on $|\psi\rangle$ is a map $\mathcal{H}\rightarrow\mathcal{H}$, but also a vector in $\mathcal{B}(\mathcal{H})$, the vector space of bounded linear operators over $\mathcal{H}$. We can define elements in the tensor product space $\mathcal{H}\otimes \mathcal{B}(\mathcal{H})$. If $\mathcal{H}$ and $\mathcal{B}(\mathcal{H})$ are both finite dimensional, then $\dim(\mathcal{H}\otimes \mathcal{B}(\mathcal{H})) = \dim(\mathcal{H})\times\dim(\mathcal{B}(\mathcal{H}))$. In our case, $\dim(\mathcal{H}) = 2^a$ and $\dim(\mathcal{B}(\mathcal{H}))=2^a\times2^a$, so $\dim(\mathcal{H}\otimes \mathcal{B}(\mathcal{H}))=2^a\times2^a\times2^a$.
Generally, if $A\in \mathbb{C}^{m\times n}$ and $B\in \mathbb{C}^{k\times l}$ are two matrices, we can define $A\otimes B$ as $$ A\otimes B =\begin{bmatrix}a_{11} B & \cdots & a_{1n}B \\ \vdots & & \vdots \\ a_{m1}B & \cdots & a_{mn}B\end{bmatrix}. $$ In the case of block-encoding (let's assume $a=1$ and $A\in\mathbb{C}^{2\times 2}$for simplicity), $$ \begin{align} \langle 0 | &= \begin{bmatrix}1 & 0\end{bmatrix}, \\ |0\rangle &= \begin{bmatrix}1 \\ 0\end{bmatrix} \\ \mathbb{1} &= \begin{bmatrix}1 & 0\\0 & 1 \end{bmatrix} \end{align} $$ hence $$ \begin{align} \langle 0 | \otimes \mathbb{1} &= \begin{bmatrix}1&0&0&0\\0&1&0&0\end{bmatrix} = \begin{bmatrix}\mathbb{1} & 0\end{bmatrix},\\ |0\rangle \otimes \mathbb{1} &= \begin{bmatrix} 1 & 0 \\ 0&1\\0&0\\0&0\end{bmatrix} = \begin{bmatrix}\mathbb{1} \\ 0\end{bmatrix}. \end{align} $$ Therefore, $$ (\langle 0 | \otimes \mathbb{1}) U (| 0 \rangle \otimes \mathbb{1}) = \begin{bmatrix}\mathbb{1} & 0\end{bmatrix} \begin{bmatrix}A&B\\C&D\end{bmatrix}\begin{bmatrix}\mathbb{1} \\ 0\end{bmatrix} = \begin{bmatrix}\mathbb{1} & 0\end{bmatrix} \begin{bmatrix}A \\ C\end{bmatrix} = A. $$ The case when $A\in \mathbb{C}^{2^n\times 2^n}$ and $a>1$ is similar to the above.
