3
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ So when block encoding, is the only way to "remove" the garbage qubits to perform the post-select measurement? Can you use an uncomputation to remove the garbage qubits? $\endgroup$ Dec 11, 2023 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.