Avoiding garbage amplitudes in block-encoding

Question

Block-encoding is a technique to embed non-unitary operations in quantum circuits. Let's restrict it to just Hermitian operations.

Suppose $H$ is some operation. To encode it into a quantum gate $U$, the following method is used:

$$ U = \begin{bmatrix} H & \sqrt{I - H} \\ \sqrt{I - H} & -H \end{bmatrix} $$

But I don't quite understand how $U$ actually works as a quantum circuit; there will be an extra garbage qubit.

For example, if $H$ is

$$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} $$

Which "deletes" the $01$ and $11$ states

The block encoding would be:

$$ \begin{bmatrix} \begin{bmatrix} +1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & +1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} & \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 \end{bmatrix} \\ \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 \end{bmatrix} & \begin{bmatrix} -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} \end{bmatrix} $$

If we act $|0\rangle \otimes \frac{1}{2} \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix}^T$, the result is:

$$ \frac{1}{2} \begin{bmatrix} 1 & 0 & 1 & 0 & 0 & -1 & 0 & -1 \end{bmatrix}^T $$

Measuring the last two qubits of this state has no change on the expected measurement.

So what is the use of block-encoding? It seems that there will always be garbage qubits that mess up the final measurement.

Answer 1

If I understand your question correctly, you're right, there always will be 'garbage' after you act with a block-encoded matrix. Equivalently, block encoding only performs the transformation you need if you post-select on the state of the ancilla qubit. In particular, non-hermitian operations can not be implemented on a quantum computer deterministically (with probability 1).

Suppose you have the following single-ancilla block encoding

$$U=\begin{pmatrix} H & *\\ *&*\end{pmatrix}=|0\rangle\langle0|\otimes H+\dots$$

and you want to compute $H|\psi\rangle$. You can act with $U$ on the state $|0\rangle\otimes |\psi\rangle$ to get

$$U |0\rangle\otimes|\psi\rangle=\begin{pmatrix} H & *\\ *&*\end{pmatrix}\begin{pmatrix}|\psi\rangle\\0\end{pmatrix}=\begin{pmatrix}H|\psi\rangle\\*\end{pmatrix}=|0\rangle\otimes H|\psi\rangle+|1\rangle\otimes |*\rangle$$

At this point you can measure the ancilla qubit and if you find it in state $|0\rangle$, the state of the remaining qubits encodes the result you want $$\frac{H|\psi\rangle}{\sqrt{p_0}}$$

where $p_0=\langle \psi|H^\dagger H\psi\rangle$ is the probability of this event.