How to select the embedded matrix in a unitary encoding?

Question

I embed a matrix M in a U unitary, where $M$ is $2^n \times 2^n$, and $$U = \begin{bmatrix}M & *\\ * &*\end{bmatrix}$$ with twice as many rows and columns..

I prepare a state vector with the first qubit being $|0\rangle$, that is

$$ |0\rangle \otimes \underbrace{|v\rangle}_{n \text{ qubits}} = \begin{bmatrix} 1\\0\end{bmatrix}\otimes|v\rangle = \begin{bmatrix}v \\ 0\end{bmatrix} \,.$$

The action of $U$ results in $$ U \begin{bmatrix}v \\ 0\end{bmatrix} = \begin{bmatrix}M & *\\ * &*\end{bmatrix}\begin{bmatrix}v \\ 0\end{bmatrix} = \begin{bmatrix}Mv \\ *\end{bmatrix}\,.$$

Now, I want to discard the $*$ part; in other words, I want to set the first qubit back to $|0\rangle$, so I have $$\begin{bmatrix}Mv \\ 0\end{bmatrix} = \begin{bmatrix}1 \\ 0\end{bmatrix} \otimes M|v\rangle = |0\rangle \otimes M|v\rangle\,.$$(Scaling is omitted for brevity.)

The only way I can imagine doing this is to measure the first qubit and hope for $0$. So there must be another way to go about this, right?

Answer 1

You say "scaling is omitted for brevity" but in fact this scaling is absolutely essential.

From a high-level perspective, you are asking to implement the map $$|v\rangle \mapsto \frac{M|v\rangle}{\|M|v\rangle\|}.$$ If $M$ is not unitary, this map necessarily involves some $<1$ probability of preparation. This is achieved by the techniques of block encodings, qubitization, quantum signal processing, or the quantum singular value transformation more generally.

Let's write your block encoding with some appropriate normalization $\alpha \geq \|M\|$: $$U = \begin{bmatrix}M/\alpha & *\\ * &*\end{bmatrix}.$$ Then the state you prepare is $$|\psi\rangle = U|0\rangle |v\rangle = |0\rangle \frac{M}{\alpha}|v\rangle + |1\rangle |*\rangle.$$ Measuring the first qubit and observing $|0\rangle$ heralds the successful preparation of $\frac{M|v\rangle}{\|M|v\rangle\|}$ in the remaining register. This corresponds to measuring the POVM $\{E_i = |i\rangle\!\langle i| \otimes I : i = 0, 1\}$ and occurs with success probability $$\Pr(E_0) = \mathrm{tr}(E_0 |\psi\rangle\!\langle \psi|) = \frac{\|M|v\rangle\|^2}{\alpha^2}.$$

The choice of $\alpha$ depends on the particular method used for constructing block encoding. If it is particularly large, this success probability will be small and so one would have to repeat many times to get a single success. One way to circumvent this is (oblivious) fixed-point amplitude amplification. The idea is to use Grover-like iterates to boost the amplitude of the $|0\rangle$ branch so that the probability of success is close to $1$. "Fixed-point" refers to a version of AA where, unlike Grover's classic algorithm which requires an exact # of iterates to get the maximum amplitude otherwise we "overcook" the quantum state, we can keep applying iterates and continue to improve our amplification. "Oblivious" refers to the fact that we don't need to know what $|v\rangle$ was in order to do this procedure. Note that this requires you to have access to both $U$ and $U^\dagger$. Roughly speaking, by querying $U$ and its inverse $O(\log(2/\delta)/\sqrt{\Pr(E_0)})$ times, the FPAA circuit produces a state such that measuring the first qubit now prepares $\frac{M|v\rangle}{\|M|v\rangle\|}$ with probability no less than $1 -\delta^2$. Compared to just repeating until success, which needs ${\sim} 1/\Pr(E_0)$ repetitions (hence queries to $U$), this achieves the famous Grover quadratic speedup.

See the original paper here and a relevant follow-up here. Also see this useful tutorial and the seminal QSVT paper, which provides another strategy to boost the probability by "uniform singular value amplification" - essentially, uniformly boosting the norm of the block-encoded matrix from $M/\alpha$ to $M'/\alpha'$, where $M'$ is close to $M$ (with controllable error) and ideally $\alpha' \approx \|M\|$. The choice of FPAA vs. USVA will depend on your application and prior knowledge about $M$ and/or $|v\rangle$.