Our objective now is to use block encoding to apply operators $B$ of the form $$ B = \sum_{i=0}^{K-1} \beta_i U_{i}, $$ that is, a **linear combination of unitaries,** or **LCU.** We assume that the $\beta_{i}$ are **positive and real.** If they aren't, we can always absorb any complex phases into the unitaries. For notational convenience, we will index the operators using binary strings $\mathbf{x}.$ $$ B = \sum_{\mathbf{x}\in \{0,1\}^k} \beta_\mathbf{x} U_\mathbf{x}, $$ For example, for $\mathbf{x} = 101,$ $U_{\mathbf{x}}=U_5$ and $\beta_{\mathbf{x}} = \beta_{5}$, since $101$ is 5 in binary. Note that this would require the number $K$ of unitaries to be a power of $2.$ If this isn't the case, we use the next highest power of $2$ and pad the remaining $\beta_{\mathbf{x}}$ with zeros. To warm up, let's start with a linear combination of two unitaries: $$ B = \kappa U + V. $$ Since we have two unitaries, we only need one auxiliary qubit. It turns out that the circuit

with $$ V_\kappa = \frac{1}{\sqrt{\kappa+1}}\begin{bmatrix} \sqrt{\kappa} & -1 \\ 1 & \sqrt{\kappa} \end{bmatrix} $$ does exactly what we need. You can check that this gives the right answers! --- ***Exercise HS.2.2.*** **(a)** Show that if we measure $0$ on the auxiliary wire, the state on the main register is $(\kappa U + V)\vert \psi\rangle$ up to normalization.

Solution.

We start in state $\vert 0\rangle \otimes\vert \psi\rangle$, and applying $V_\kappa$ gives $$ \frac{1}{\sqrt{\kappa + 1}} (\sqrt{\kappa}\vert 0 \rangle + \vert 1\rangle)\otimes \vert \psi\rangle. $$ Passing through the controlled $U$ and $V$ yields $$ \frac{1}{\sqrt{\kappa + 1}} (\sqrt{\kappa}\vert 0 \rangle \otimes U\vert \psi\rangle + \vert 1\rangle \otimes V\vert \psi\rangle). $$ Finally, applying $V_\kappa^\dagger$ (and doing a little algebra) produces a state $$ \frac{1}{\kappa + 1} \vert 0\rangle \otimes \left(\kappa U + V\right) \vert\psi\rangle + \frac{\sqrt{\kappa}}{\kappa + 1} \vert 1\rangle \otimes \left(V - U\right)\vert \psi\rangle. $$ If we measure $0$ on the auxiliary, we therefore obtain $\left(\kappa U + V\right) \vert\psi\rangle$ on the main register, up to normalization. ▢

**(b)** Observe that the output state has the form we expect from a block encoding $$ U \ket{0}\ket{\psi} \mapsto \ket{0}\frac{B}{\lambda}\ket{\psi} + \alpha \ket{\psi^{\perp}}. $$ Identify $\ket{\psi^{\perp}}$ and the normalization constants $\lambda$ and $\alpha.$

Solution

In part (a) we calculated the output state: $$ \frac{1}{\kappa + 1} \vert 0\rangle B \vert\psi\rangle + \frac{\sqrt{\kappa}}{\kappa + 1} \vert 1\rangle \otimes \left(V - U\right)\vert \psi\rangle. $$ The state $\ket{\psi^{\perp}}$ is $$ \ket{\psi^{\perp}} = \vert 1\rangle \otimes \left(V - U\right)\vert \psi\rangle, $$ which clearly satisifies $_A\langle 0 \ket{\psi^{\perp}} = 0.$ The normalization constants are $\lambda = \kappa + 1$ and $\alpha = \frac{\sqrt{\kappa}}{\kappa + 1}.$

--- Now we are ready to generalize this algorithm to obtain a linear combination $B$ of more than two unitaries $$ B = \sum_{\mathbf{x}\in \{0,1\}^k} \beta_\mathbf{x} U_\mathbf{x}. $$ Drawing inspiration from our implementation of the linear combination of two unitaries, we expect that a circuit of the form

The purple gate is known as the PREPARE routine, which we will now denote as $\text{PREP}$. The blue subcircuit is the SELECT routine, denoted by $\text{SEL}$ and is shown below.

Observe that each $U_{\mathbf{x}}$ is controlled by the wires in the auxiliary register $A.$ The control values follow a binary counting pattern: for $U_0$ the values are $0,\ldots,0$; for $U_1$ they are $0,\ldots,0,1$, and so on. In general, the control values for $U_{\mathbf{x}}$ are identical to the $0s$ and $1s$ in the binary number $\mathbf{x}.$ The SELECT routine will *always* look like this. The only step we need to piece together is the choice of $\text{PREP}$ gate that will give us the encoding. Let's start from the right answer and check that it works! Choose the $\text{PREP}$ operator such that it satisfies $$ \text{PREP}\vert \mathbf{0}\rangle \ket{\psi}= \sum_{\mathbf{x}} \sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}} \vert \mathbf{x}\rangle \ket{\psi}, $$ where $\lambda = \sum_{\mathbf{x}}\beta_{\mathbf{x}}.$ From the figure, we see that the $\text{SEL}$ operator's defining property is $$ \text{SEL}\vert \mathbf{x}\rangle \vert \psi\rangle = \vert \mathbf{x}\rangle U_\mathbf{x} \vert \psi\rangle. $$ In a sense, it "Selects" and applies the operator $U_{\mathbf{x}}$ as instructed by the state $\ket{\mathbf{x}}$ in the auxiliary register. Note that $\text{SEL}$ is completely determined, but $\text{PREP}$ is not uniquely defined. We will show in the following exercise that $$ \text{PREP}^{\dagger}\text{ SEL PREP}\ket{0}\ket{\psi} = \ket{0}\frac{B}{\lambda}\ket{\psi} +\alpha\ket{\psi^{\perp}} $$ where $\ket{\psi^{\perp}}$ is a state orthogonal to all the states of the form $\ket{0}\ket{\phi}.$ Therefore, it is a **block encoding** of the linear combination of unitaries $B.$ Recall that this means that, when $\ket{0}$ is measured in the auxiliary register, the state in the main register must be $\frac{B}{\lambda}\ket{\psi}.$ Due to its structure, this block encoding routine is known as **PrepSelPrep.** --- ***Exercise HS.2.3.*** **(a)** The $\text{PREP}$ and $\text{SEL}$ operators are defined via the following action on quantum states $$ \text{PREP}\vert \mathbf{0}_A\rangle \ket{\psi}_M= \sum_{\mathbf{x}} \sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}} \vert \mathbf{x}\rangle_A \ket{\psi}_M, $$ $$ \text{SEL}\vert \mathbf{x}\rangle_A \vert \psi\rangle_M = \vert \mathbf{x}\rangle_A U_\mathbf{x} \vert \psi\rangle_M. $$ with $\lambda = \sum_{\mathbf{x}}\beta_{\mathbf{x}}.$ Show that the output of the PrepSelPrep routine

is indeed a block encoding for $B,$ that is, $$ \text{PREP}^{\dagger}\text{ SEL PREP}\ket{0}_A\ket{\psi}_M = \ket{0}_A\frac{B}{\lambda}\ket{\psi}_M +\alpha\ket{\psi^{\perp}}_{AM}, $$ where $\ket{\psi^{\perp}}_{AM}$ is a state perpendicular to $\ket{0}_A.$

Solution.

To do this, let's apply PrepSelPrep to states of the form $\ket{0}_A \ket{\mathbf{y}}_M$, where $\ket{\mathbf{y}}_M$ are computational basis states for the main register $M.$ The first PREP gives $$ \text{PREP}\ket{0}_A\ket{\mathbf{y}}_M = \sum_{\mathbf{x}}\sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}}\ket{\mathbf{x}}_A\ket{\mathbf{y}}_M $$ Applying SELECT we get $$ \text{SEL}\left(\sum_{\mathbf{x}}\sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}}\ket{\mathbf{x}}_A\ket{\mathbf{y}}_M\right) = \sum_{\mathbf{x}}\sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}}\ket{\mathbf{x}}_A U_{\mathbf{x}}\ket{\mathbf{y}}_M. $$ At a first glance, we're stuck, since we don't have a rule for applying $\text{PREP}^{\dagger}$ on this state. We can get around this by inserting a resolution of the identity $I_A =\sum_{\mathbf{x}'}\ket{\mathbf{x'}}\bra{\mathbf{x'}}_A$ on the left. $$ \begin{align*} &\sum_{\mathbf{x}'}\ket{\mathbf{x'}}\bra{\mathbf{x'}}_A \text{PREP}^{\dagger}\left(\sum_{\mathbf{x}}\sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}}\ket{\mathbf{x}}_A U_{\mathbf{x}}\ket{\mathbf{y}}_M\right)=\\ &\ket{\mathbf{0}}\bra{0}_A \text{PREP}^{\dagger}\left(\sum_{\mathbf{x}}\sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}}\ket{\mathbf{x}}_A U_{\mathbf{x}}\ket{\mathbf{y}}_M\right)+\\ &\sum_{\substack{\mathbf{x}\\ \mathbf{x'}\neq 0}}\sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}}\bra{\mathbf{x'}}_A \text{PREP}^{\dagger} \ket{\mathbf{x}}_A \ket{\mathbf{x'}}_A U_{\mathbf{x}}\ket{\mathbf{y}}_M. \end{align*} $$ We then identify $$ \alpha \vert \psi^{\perp}\rangle_{AM} = \sum_{\substack{\mathbf{x}\\ \mathbf{x'}\neq 0}}\sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}}\bra{\mathbf{x'}}_A \text{PREP}^{\dagger} \ket{\mathbf{x}}_A \ket{\mathbf{x'}}_A U_{\mathbf{x}}\ket{\mathbf{y}}_M, $$ where $\alpha$ is the a normalization constant that ensures that $\vert \psi^{\perp}\rangle_{AM} $ has unit norm. We split the sum so that there are no states containing $\ket{0}_A$ in $\vert \psi^{\perp}\rangle_{AM}$, therefore me must have $_A\bra{0}\psi^{\perp}\rangle_{AM} = 0.$ The point in splitting the sum is that we know how $\text{PREP}^{\dagger}$ acts on $_A \bra{0}.$ Then we can evaluate the first term in the sum $$ \begin{align*} &\ket{\mathbf{0}}\bra{0}_A \text{PREP}^{\dagger}\left(\sum_{\mathbf{x}}\sqrt{\frac{\beta_{\mathbf{x}}}{\lambda}}\ket{\mathbf{x}}_A U_{\mathbf{x}}\ket{\mathbf{y}}_M\right)= \\ & \sum_{\mathbf{x, \ x'}}\sqrt{\frac{\beta_{\mathbf{x}}\beta_{\mathbf{x'}}}{\lambda^2}}\bra{\mathbf{x'}}\mathbf{x}\rangle_A \ket{0}_A U_\mathbf{x}\ket{\mathbf{y}}_M = \\ & \sum_{\mathbf{x}}\ket{0}_A \frac{\beta_{\mathbf{x}}}{\lambda} U_{\mathbf{x}}\ket{\mathbf{y}}_M = \ket{0}_A\frac{B}{\lambda}\ket{\mathbf{y}}_M. \end{align*} $$ Putting it all together, we have derived $$ \text{PREP}^{\dagger}\text{ SEL PREP}\ket{0}_A\ket{\psi}_M = \ket{0}_A\frac{B}{\lambda}\ket{\psi}_M +\alpha\ket{\psi^{\perp}}_{AM}. $$

**(b)** There's one step missing though! Justify that $\lambda = \sum_{\mathbf{x}}\beta_{\mathbf{x}}$ is the correct normalization factor.

Solution.

We need $\text{PREP}\ket{0}\ket{\psi}$ to have unit norm. Then we must have $$ 1= \bra{\psi}\bra{0}\text{PREP}^{\dagger}\text{PREP}\ket{0}\ket{\psi} = \sum_{\mathbf{x}, \ \mathbf{y}}\sqrt\frac{{\beta_{\mathbf{x}}\beta_{\mathbf{y}}}}{\lambda^2}\bra{\mathbf{y}}\mathbf{x}\rangle = \frac{1}{\lambda}\sum_{\mathbf{x}}\beta_{\mathbf{x}}. $$ so $\lambda = \sum_{\mathbf{x}}\beta_{\mathbf{x}}.$

--- We have learned how to use the PrepSelPrep routine to block-encode linear combinations of unitaries. This means that we can apply such linear combinations to quantum states in a non-deterministic way! Solve the Codercises on the left to get some hands-on practice on how to do this and to explore PennyLane functions that make it easy for you.

Codercise HS.2.1 - Linear combination of two unitaries

Codercise HS.2.2a - The SELECT routine

Codercise HS.2.2b - PrepSelPrep

Codercise HS.2.3a - Block encoding in PennyLane

Codercise HS.2.3b - PennyLane PrepSelPrep

Block encodings

Encoding LCUs