Quantum Signal Processing and Quantum Singular Value Transformation¶

Copyright (c) 2022 Institute for Quantum Computing, Baidu Inc. All Rights Reserved.

Overview¶

Quantum signal processing (QSP), originally purposed by Guang Hao Low and Issac L. Chuang [1], is an algorithm for simulation of polynomial transformation of scalars using reflection (RX$R_X$) and rotation (RZ$R_Z$) operators. QSP states that, for a specific group of polynomials like the Chebyshev polynomials of the first kind, such simulation can be done by a single qubit. Moreover, using a technique called "linear combination of unitaries", we can use two more ancilla qubit to simulate all complex polynomials and hence approximate any functions that can be expanded by Taylor series.

The idea of QSP is further generalized by paper [2], so that it can simulate polynomial transformation of matrices using high-dimensional rotation operators. Since the polynomial transformation of a diagonalizable matrix is intrinsically the polynomial transformation of its singular values, this algorithm is called the quantum singular value transformation (QSVT).

Moreover, a technique called qubitization is further employed to substantially reduce the complexity of high-dimensional rotation operators, so that one (ancilla) qubit suffices to perform the rotation in larger space.

Based on paper [2], this tutorial will illustrate quantum signal processing, quantum singular value transformation and qubitization, and how to implement these algorithms in PaddleQuantum. But first of all, we need to present the idea of block encoding.

Here are some necessary libraries and packages.

Block Encoding¶

Block encoding is a method to encode matrices of data. In quantum computing, for a matrix A∈C2n×2n$A\in C^{2^n\times 2^n}$, a unitary U∈C2m×2m$U\in C^{2^m\times 2^m}$ is said to be a block encoding of A$A$ if there exists two orthogonal projectors W,V∈C2m×2m$W,V\in C^{2^m\times 2^m}$ such that

This could appear more familiar when W=V=|0⟩⊗(m−n)⟨0|⊗(m−n)⊗I⊗n$W=V=|0{⟩}^{\otimes (m-n)}⟨0{|}^{\otimes (m-n)}\otimes I^{\otimes n}$, where above equation implies

That is, A$A$ is the left-upper block of matrix U$U$.

Encoding and Decoding of Matrices¶

There are numerous ways to find a block encoding unitary U$U$ of a matrix A$A$. For example, when A$A$ is diagonalizable, U$U$ can be constructed as

when A$A$ is a unitary, we can simply select U=A⊕I⊗(m−n)$U=A\oplus I^{\otimes (m-n)}$ i.e. U$U$ is a controlled A$A$. Despite the fact that we do not hold a mature method for doing this in a quantum system, several studies [3] [4] have been conducted on the quantum implementation of block encodings. In this tutorial, we will assume that there exists an efficient algorithm to block encode a matrix (or at least a Hermitian matrix) in a quantum circuit.

Realization in PaddleQuantum.¶

As for the decoding part, the information of matrix A∈C2n×2n$A\in C^{2^n\times 2^n}$ can be extracted by applying its block encoding unitary U∈C2m×2m$U\in C^{2^m\times 2^m}$ on |0⟩⊗(m−n)⟨0|⊗(m−n)⊗ρ$|0{⟩}^{\otimes (m-n)}⟨0{|}^{\otimes (m-n)}\otimes \rho$, where ρ$\rho$ is an n$n$-qubit quantum state. Then the output state is

Measuring the first quantum register with outcome 0⊗(m−n)$0^{\otimes (m-n)}$ gives the desired information.

The success probability of decoding is the probability of measuring 0⊗(m−n)$0^{\otimes (m-n)}$, which can be exponentially small as m−n$m-n$ increases. However, this would no longer be a problem if we can control the size of first register. In this tutorial we will assume m=n+1$m=n+1$.

We can verify that the output_rho is the same as AρA†Tr(AρA†)$\frac{A\rho A^{†}}{\text{Tr}\left(A\rho A^{†}\right)}$.

When m=1$m=1$ (and hence n=0$n=0$), A$A$ is a scalar. In this case we can calculate the expectance of U$U$ in terms of state |0⟩$|0⟩$ to receive A$A$.

Quantum Signal Processing¶

Theorem 3-4 in paper [2] state that, for a polynomial P∈C[x]$P\in C\left[x\right]$ with deg(P)=k$\mathrm{deg}\left(P\right)=k$ that satisfies

• if k$k$ is even/odd, then P$P$ is a even/odd polynomial;
• |P(x)|≤1,∀x∈[−1,1]$|P\left(x\right)|\le 1,\forall x\in [-1,1]$;
• |P(x)|≥1,∀x∈(−∞,−1]∪[1,∞)$|P\left(x\right)|\ge 1,\forall x\in (-\infty ,-1]\cup [1,\infty )$;
• if k$k$ is even, then P(ix)P∗(ix)≥1$P\left(ix\right)P^{\ast }\left(ix\right)\ge 1$,

there exists a polynomial Q∈C[x]$Q\in C\left[x\right]$ and a vector of angles Φ=(ϕ0,...,ϕk)∈Rk+1$\Phi =({\varphi }_0,...,{\varphi }_k)\in R^{k+1}$ such that ∀x∈[−1,1]$\forall x\in [-1,1]$,

That is, we can use k+1$k+1$ rotation (RZ$R_Z$) gates and k$k$ reflection (RX$R_X$) gates to receive a block encoding unitary WΦ(x)$W_{\Phi }\left(x\right)$ of P(x)$P\left(x\right)$. After block decoding we have completed the simulation of P(x)$P\left(x\right)$.

Here are some polynomials that satisfy above requirements.

Note that such structure of WΦ$W_{\Phi }$ naturally fits the family of Chebyshev polynomials. Indeed, for a Chebyshev polynomials of first kind with order k$k$, its corresponding Φ$\Phi$ is (0,π,...,π)$(0,\pi ,...,\pi )$ (if k$k$ is even) or (π,...,π)$(\pi ,...,\pi )$ (if k$k$ is odd).

PaddleQuantum has a built-in class ScalarQSP for quantum signal processing and a function Phi_verification to verify whether WΦ$W_{\Phi }$ is a block encoding of P$P$.

We can also verify the correctness of Φ$\Phi$ from the corresponding circuit.

Variant of QSP¶

Moreover, the number of parameters can be further simplified to k$k$ by finding a vector of angles Φ∈Rk$\Phi \in R^k$ such that

where

In PaddleQuantum, we can compute such Φ$\Phi$ by function reflection_based_quantum_signal_processing.

Note: R−Φ(x)$R_{-\Phi }\left(x\right)$ is a block encoding of P∗(x)$P^{\ast }\left(x\right)$.

Quantum Singular Value Transformation¶

To start with, we need to define the singular value transformation.

Let X∈C2m×2m$X\in C^{2^m\times 2^m}$ be a matrix. Suppose there exists a unitary U$U$ and two orthogonal projectors W$W$ and V$V$ such that X=WUV$X=WUV$. Then there exists two orthonormal basis {|ωj⟩}2mj=1$\{|{\omega }_j⟩{\}}_{j=1}^{2^m}$ and {|νj⟩}2mj=1$\{|{\nu }_j⟩{\}}_{j=1}^{2^m}$ extended by eigenstates of W$W$ and V$V$ respectively, such that

where

is a singular value of X$X$. The singular value transformation (SVT) of X$X$ for a function f$f$ is defined to be

Decomposition and QSP¶

Paper [2] proves that under appropriate choices of basis, U,V$U,V$ and W$W$ can be decomposed by subspaces of λj${\lambda }_j$ such that

We can decompose f(SV)$f^{\left(SV\right)}$ in a similar manner.

Let's connect above decomposition with quantum signal processing. Suppose function f$f$ is a polynomial P∈C[x]$P\in C\left[x\right]$ with degree k$k$ that satisfies the requirements in the last section. Then there exists Φ∈Rk$\Phi \in R^k$ such that RΦ$R_{\Phi }$ is a block encoding of P$P$. Moreover, P$P$ satisfies P(1)=ei∑kj=1ϕj$P\left(1\right)=e^{i{\sum }_{j=1}^k{\varphi }_j}$ and P(0)=ei∑kj=1(−1)j+1ϕj$P\left(0\right)=e^{i{\sum }_{j=1}^k(-1{)}^{j+1}{\varphi }_j}$. Now Define UΦ$U_{\Phi }$ as

Then

and hence

If we can realize VUΦV$V{U}_{\Phi }V$ or WUΦV$W{U}_{\Phi }V$ by a quantum algorithm, then such transformation is the quantum singular value transformation of X$X$.

QSVT and Block Encoding¶

Suppose U$U$ is a block encoding unitary of A$A$ with respect to orthogonal projectors W$W$ and V$V$. Then X=A⊕0I⊗(m−n)$X=A\oplus 0I^{\otimes (m-n)}$ and P(SV)(X)=P(SV)(A)⊕0I⊗(m−n)$P^{\left(SV\right)}\left(X\right)=P^{\left(SV\right)}\left(A\right)\oplus 0I^{\otimes (m-n)}$. Therefore, UΦ$U_{\Phi }$ is a block encoding of P(SV)(A)$P^{\left(SV\right)}\left(A\right)$.

When W=V$W=V$, {|ωj⟩}2mj=1={|νj⟩}2mj=1$\{|{\omega }_j⟩{\}}_{j=1}^{2^m}=\{|{\nu }_j⟩{\}}_{j=1}^{2^m}$. Denote P(x):=∑ki=0cixi$P\left(x\right):={\sum }_{i=0}^k{c}_i{x}^i$. We can find that

That is, when W=V$W=V$, QSVT maps a block encoding of A$A$ to a block encoding of P(A)$P\left(A\right)$.

PaddleQuantum has a built-in class QSVT for quantum singular value transformation when W=V=|0⟩⊗(m−n)⟨0|⊗(m−n)⊗I⊗n$W=V=|0{⟩}^{\otimes (m-n)}⟨0{|}^{\otimes (m-n)}\otimes I^{\otimes n}$. We can call its member function QSVT.block_encoding_matrix() to verify the correctness of above theories, from entries to entries and from eigenvalues to eigenvalues.

Qubitization: Quantum Realization of UΦ$U_{\Phi }$¶

One question is, how to realize UΦ$U_{\Phi }$ by a quantum circuit? Note that we assume U$U$ is implementable. Then the remaining problem is the realization of unitaries eiϕ(2W−I)$e^{i\varphi (2W-I)}$ and eiϕ(2V−I)$e^{i\varphi (2V-I)}$, which are essentially RZ(−2ϕ)$R_Z(-2\varphi )$ operators performed in projection spaces of W$W$ and V$V$ respectively.

To achieve this, Lemma 10 in paper [1] projects the image space of projector into an ancilla qubit and perform the rotation operation on that qubit. Then by entanglement such rotation is simultaneously applied to the main register.

The results are summarized to the following circuit:

When W=V=|0⟩⊗(m−n)⟨0|⊗(m−n)⊗I⊗n$W=V=|0{⟩}^{\otimes (m-n)}⟨0{|}^{\otimes (m-n)}\otimes I^{\otimes n}$, PaddleQuantum can create a circuit in Figure 2 by member function QSVT.block_encoding_circuit. We can show that the constructed quantum circuit can simulate UΦ$U_{\Phi }$, by comparison of the output state and (UΦ⊗I)|ψ⟩|0⟩$(U_{\Phi }\otimes I)|\psi ⟩|0⟩$ for |ψ⟩∈C2m$|\psi ⟩\in C^{2^m}$.

Note: if we add Hadamard gates at the beginning and the end of the ancilla register in Figure 2, then the quantum circuit turns to simulate the real part of the polynomial. Combined with the technique of linear combination of unitaries, theocratically we can simulate all complex polynomials with norm smaller than 1 using quantum circuit.

Application: Amplitude Amplification¶

Let |ψ⟩$|\psi ⟩$ be a m$m$-qubit quantum state such that |ψ⟩=sin(θ)|ψgood⟩+cos(θ)|ψbad⟩$|\psi ⟩=\sin \left(\theta \right)|{\psi }_{\text{good}}⟩+\cos \left(\theta \right)|{\psi }_{\text{bad}}⟩$. Amplitude amplification is a quantum algorithm that can increase the amplitude of |ψgood⟩ to approximately 1. This algorithm can be viewed in a different prospective. Let U be the unitary and W,V be two orthogonal projectors such that |ψ⟩=UV|0⟩⊗m and sin(θ)|ψgood⟩=W|ψ⟩, implying sin(θ)|ψgood⟩=WUV|0⟩⊗m. Therefore, amplitude amplification is essentially a singular value transformation of X=WUV. In this section we will show how to use QSVT to do fixed-point (i.e. θ=π2k for some k∈Z) amplitude amplification from Theorem 28 of paper [2].