Chapter 2.4 Quantum Linear Algebra

We next introduce quantum linear algebra, a potent toolbox for designing various FTQC-based algorithms. For clarity, we start with the definition of block encoding, which is about how to implement a matrix on the quantum computer. Based on this, we introduce some basic arithmetic rules for block encodings, like the multiplication, linear combination, and the Hadamard product. Finally, we introduce the quantum singular value transformation method, which enables one to implement functions onto singular values of block-encoded matrices.

Block encoding

For many computational problems, such as solving linear equations, we need to deal with a non-unitary matrix $A$. However, remember that quantum gates are unitaries. Therefore, if we want to solve these problems on quantum computers, it is essential to consider how to encode the matrix $A$ into a unitary. This challenge can be addressed by the block encoding technique.

Definition. Suppose that $A$ is an $N$-qubit operator, $\alpha, \varepsilon\geq 0$ and $a\in \mathbb{N}$. Then we say that the $(a+ N)$-qubit unitary $U$ is an $(\alpha,a,\varepsilon)$-block-encoding of $A$ if

$$|A-\alpha(\bra{0}^{\otimes a} \otimes \mathbb{I})U(\ket{0}^{\otimes a}\otimes \mathbb{I})|\leq \varepsilon. $$

Here, $|\cdot|$ represents the spectral norm, i.e., the largest singular value of the matrix.

Fact. (Block encoding via the linear combination of unitaries (LCU) method, [@gilyenquantum2019]). Suppose that $A$ can be written in the form $$\begin{aligned} A=\sum_{k} \alpha_k U_k, \end{aligned}$$ where $\{\alpha_k\}$ are real numbers and $U_k$ are some easily prepared unitaries such as Pauli strings. Then, the LCU method allows us to have the access to two unitaries, i.e.,

$$U_{\text{SEL}}=\sum_{k} \ket{k} \bra{k}\otimes U_k,$$

$$U_{\text{PREP}}:\ket{0}\rightarrow \frac{1}{\sqrt{|\vec{\alpha}|_1}}\sum_k \sqrt{\alpha_k}\ket{k},$$

where $\vec{\alpha}=(\alpha_1,\alpha_2,\dots)$.

After simple mathematical analysis, one can obtain $$U=(U^\dagger_{\text{PREP}}\otimes \mathbb{I})U_{\text{SEL}}(U_{\text{PREP}}\otimes \mathbb{I})$$

which is a $(|\vec{\alpha}|_1,m,0)$-block-encoding of $A$. Here, $\mathbb{I}$ is the identity operator of $N$-qubit size.

Similar to the definition of block encoding, we can also define the state preparation encoding.

Definition. We say a unitary $U_{\psi}$ is an $(\alpha,a,\epsilon)$-state-encoding of an $N$-qubit quantum state $\ket{\psi}$ if $$\begin{aligned} \left|\ket{\psi}-\alpha (\bra{0^{a}}\otimes I)U_{\psi}\ket{0^{a+N}}\right|_{\infty} \leq \epsilon. \end{aligned}$$ :::

More straightforwardly, the $(\alpha,a,\epsilon)$-state-encoding $U_\psi$ prepares the state $$\begin{aligned} U_{\psi}\ket{0}\ket{0}= \frac{1}{\alpha}\ket{0}\ket{\psi’}+\sqrt{1-\alpha^2}\ket{1}\ket{\mathrm{bad}},\notag \end{aligned}$$ where $\left|\ket{\psi’}-\ket{\psi}\right|_{\infty}\leq \epsilon$ and $\ket{\mathrm{bad}}$ is an arbitrary quantum state. One can further prepare the state $\ket{\psi’}$ by using $\mathcal{O}(\alpha)$ times of amplitude amplification [@brassard2002quantum]. The state preparation encoding can be understood as a specific case of the block encoding, i.e., it is the block encoding of a $\mathbb{C}^{2^N \times 1}$ matrix.

Basic arithmetics for block encodings

Now we introduce some arithmetic rules for block encoding unitaries. The following two facts describe the product and linear combination rules of block encoding unitaries, respectively.

Fact. If $U$ is an $(\alpha,a,\delta)$-block encoding of an $N$-qubit operator $A$, and $V$ is a $(\beta,b,\varepsilon)$-block encoding of an $N$-qubit operator $B$, then $(\mathbb{I}\otimes U)(\mathbb{I}\otimes V)$ is an $(\alpha\beta,a+b,\alpha\varepsilon+\beta\delta)$-block-encoding of $AB$. Here, $\mathbb{I}$ is the identity operator of $a(b)$-qubit size.

Fact. Let $A=\sum_k \alpha_k A_k$ be an $s$-qubit operator with $\beta\geq |\vec{x}|_1$ and $\varepsilon_1>0$. Suppose we have access to

$$P_L\ket{0}=\sum_k c_k\ket{k},$$

$$P_R\ket{0}=\sum_k d_k\ket{k},$$

$$ W=\sum_k \ket{k}\bra{k}\otimes U_k+\left(\bigl(\mathcal{I}_s-\sum_k \ket{k}\bra{k}\bigl)\otimes \mathcal{I}_a\otimes \mathcal{I}_b\right),$$

where $\sum_k |\beta c_k^*d_k-\alpha_k|\leq \varepsilon_1$ and $U_k$ is an $(\alpha,a,\varepsilon_2)$-block-encoding of $A_k$. Then we can implement an $(\alpha\beta, a+b,\alpha\varepsilon_1+\beta\varepsilon_2)$-block-encoding of $A$ by using one time of $W,P_R$, and $P_L$.

These results can be verified via direct computation. Another arithmetic rule broadly employed in quantum machine learning is the Hadamard product, a.k.a, the element-wise product. The following lemma exhibits how to achieve this operation via the block encoding framework.

Lemma. With $N \in \mathbb{N}$, consider two matrices $A, B\in \mathbb{C}^{2^N\times 2^N}$, and assume that we have an $(\alpha,a,\delta)$-encoding $U_{A}$ of matrix $A$ and $(\beta,b,\epsilon)$-encoding $U_{B}$ of matrix $B$, then we can construct an $(\alpha\beta,a+b+N,\alpha\epsilon+\beta\delta)$-encoding of matrix $A \circ B$.

Quantum singular value transformation

Now we understand how to implement matrices on the quantum computer and some arithmetic methods among these matrices, here we further introduce how one can implement matrix functions on the quantum computer. The method is called the quantum singular value transformation (QSVT), which is a powerful framework that can unify most known quantum algorithms.

For machine learning applications, we mostly deal with the real matrices. The computational cost of QSVT for the real matrix case is summarized in the following theorem. For a matrix $A$, consider its singular value decompostision $A=\sum_{i}\sigma_i |\psi_i\rangle\langle \phi_i|$. Given a function $P(x)$, we use $P^{(SV)}(A)$ to represent $P^{(SV)}(A)=\sum_{i} P(\sigma_i) |\psi_i\rangle\langle \phi_i|$.

Fact. Suppose that $U_A$ is an $(\alpha, a, \varepsilon)$-block-encoding of a real matrix $A$. If $\delta \geq 0$ and $P:\mathbb{R}\rightarrow \mathbb{C}$ is a d-degree polynomial satisfying that $$ \mathrm{for\ all}\ x \in[-1,1]:\left|P(x)\right| \leq \frac{1}{4}, $$ then there is a quantum circuit $\tilde{U}$, which is an $(1, a+3, 4d \sqrt{\varepsilon / \alpha}+\delta)$-block-encoding of $P^{(SV)}(A / \alpha)$, and consists of d applications of $U_A$ and $U^{\dagger}_A$ gates. Further, the description of such a circuit can be computed classically in time $\mathcal{O}(\operatorname{poly}(d, \log (1 / \delta)))$.

Notice that if the block-encoded matrix $A$ is Hermitian, the singular value transformation is equivalent to the eigenvalue transformation. In this case, we can directly implement the matrix function via QSVT.

In the following, we introduce some applications of QSVT method. There are several important applications, however, in this tutorial, we focus on introducing some applications that can be applied in the machine learning related tasks. The first is matrix inversion, which has been widely used in traditional machine learning methods such as principal component analysis. Note that for a general matrix, we actually mean to implement the Moore-Penrose pseudoinverse, i.e., the inverse of all singular values.

Lemma. Let $U_A$ be a $(1,a,0)$-block encoding of matrix $A$. Further, for simplicity, assume the nonzero singular values of $A$ are lower bounded by $\delta>0$. Let $0\leq \epsilon\leq \delta \leq \frac{1}{2}$. One can construct a $(1/\delta,a+2,\epsilon)$-block encoding of $A^{-1}$ by using $\mathcal{\tilde{O}}(\frac{1}{\delta}\log(\frac{1}{\epsilon}))$ times of $U_A$ and $U_A^\dagger$.

Proof sketch of this Lemma. This can be achieved by finding a good polynomial approximation for the function $1/x$. One can not find such a polynomial on the whole interval $[-1,1]$, however, such a polynomial exists on the interval $[-1,-\delta]\cup [\delta,1]$ for some $\delta>0$.

The second application of QSVT is the nonlinear amplitude transformation. To deal with classical data, there are several ways to encode them into quantum. Here, we focus on the amplitude encoding case, especially for the real amplitudes. The nonlinear transformation is achieved by combining the diagonal block encoding and QSVT.

::: fact Given a state preparation unitary $U_{\psi}$ of an $N$-qubit state $\ket{\psi}=\sum_{j=1}^{2^N} \psi_j \ket{j}$, where $\{\psi_j\}$ are real, $\left|\psi\right|_2=1$, one can construct an $(1,N+2,\epsilon)$-encoding of the diagonal matrix $A=\text{diag}(\psi_1,…,\psi_d)$ with $\mathcal{O}(N)$ circuit depth and $\mathcal{O}(1)$ times of controlled-$U$ and controlled-$U^\dagger$.

As a straightforward generalization, one can replace the state preparation unitary with the general state preparation encoding. By constructing the block encoding of amplitudes, one can implement many functions onto these amplitudes via QSVT. A direct application is performing the neural network on the quantum computer.