# Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices

Daan Camps
Applied Mathematics and Computational Research Division
Lawrence Berkeley National Laboratory
Berkeley, CA 94720
<EMAIL_ADDRESS>
& Lin Lin
Department of Mathematics and Challenge Institute of Quantum Computation
University of California at Berkeley
Applied Mathematics and Computational Research Division
Lawrence Berkeley National Laboratory
Berkeley, CA 94720
<EMAIL_ADDRESS>
Roel Van Beeumen
Applied Mathematics and Computational Research Division
Lawrence Berkeley National Laboratory
Berkeley, CA 94720
<EMAIL_ADDRESS>
Chao Yang
Applied Mathematics and Computational Research Division
Lawrence Berkeley National Laboratory
Berkeley, CA 94720
<EMAIL_ADDRESS>

###### Abstract

Many standard linear algebra problems can be solved on a quantum computer by
using recently developed quantum linear algebra algorithms that make use of
block encodings and quantum eigenvalue / singular value transformations. A
block encoding embeds a properly scaled matrix of interest $A$ in a larger
unitary transformation $U$ that can be decomposed into a product of simpler
unitaries and implemented efficiently on a quantum computer. Although quantum
algorithms can potentially achieve exponential speedup in solving linear
algebra problems compared to the best classical algorithm, such gain in
efficiency ultimately hinges on our ability to construct an efficient quantum
circuit for the block encoding of $A$, which is difficult in general, and not
trivial even for well structured sparse matrices. In this paper, we give a few
examples on how efficient quantum circuits can be explicitly constructed for
some well structured sparse matrices, and discuss a few strategies used in
these constructions. We also provide implementations of these quantum circuits
in MATLAB.

_Keywords_ quantum linear algebra, block encoding, quantum circuit, quantum
eigenvalue transformation, quantum singular value transformation, random walk,
quantum walk

##  1 Introduction

In recent years, a new class of quantum algorithms have been developed to
solve standard linear algebra problems on quantum computers. These algorithms
use the technique of block encoding Low and Chuang (2017, 2019); Gilyén et al.
(2019) to embed a properly scaled matrix $A$ of interest in a larger unitary
matrix $U_{A}$ so that the multiplication of $A$ with a vector $x$ can be
implemented by applying the unitary matrix $U_{A}$ to a carefully prepared
initial state and performing measurements on a subset of qubits. Furthermore,
if $A$ is Hermitian, by using the technique of the quantum eigenvalue
transformation, one can block encode a certain matrix polynomial $p(A)$ by
another unitary $U_{p(A)}$ efficiently using $U_{A}$ as the building block Low
and Chuang (2017). This procedure can be generalized to non-Hermitian matrices
$A$ using a technique called the quantum singular value transformation Gilyén
et al. (2019). The larger unitary $U_{p(A)}$ can be decomposed into a product
of simpler unitaries consisting of $2\times 2$ single qubit unitaries, multi-
qubit controlled-NOTs, $U_{A}$ and its Hermitian conjugate. Because
approximate solutions to many large-scale linear algebra problems such as
linear systems of equations, least squares problems and eigenvalue problems
(produced by iterative methods) can often be expressed as $p(A)v_{0}$ for some
initial vector $v_{0}$, the possibility to block encode $p(A)$ will enable us
to solve these problems on a quantum computer that performs unitary
transformations only Gilyén et al. (2019); Lin and Tong (2020a, b); Martyn et
al. (2021). In this paper, we use the term “quantum linear algebra algorithms”
to refer to such block encoding based algorithms for solving linear algebra
problems on a quantum computer.

In order to implement these quantum linear algebra algorithms, we need to
further express the block encoding matrix $U_{A}$ as a product of simpler
unitaries, i.e., we need to express $U_{A}$ as an efficient quantum circuit.
Although it is suggested in Berry et al. (2015); Childs et al. (2017); Low and
Chuang (2017); Gilyén et al. (2019) that such a quantum circuit can be
constructed in theory for certain sparse matrices, the proposed construction
relies on the availability of “oracles" that can efficiently encode both the
nonzero structure of $A$ and numerical values of the nonzero matrix elements.
However, for a general sparse matrix $A$, finding these “oracles" is entirely
non-trivial. Even for sparse matrices that have a well defined non-zero
structure and a small set of nonzero matrix elements, encoding the structure
and matrix elements by an efficient quantum circuit is not an easy task.

In this paper, we provide a few accessible examples on how to explicitly
construct efficient quantum circuits for some well structured sparse matrices.
In particular, we will present some general strategies for writing down the
oracles for the non-zero structure and non-zero matrix elements of these
matrices. In addition to explaining the general strategies and providing
circuit diagrams, we also show how these circuits can be easily constructed
using a MATLAB Toolbox called QCLAB Camps and Van Beeumen (2021). To the best
of our knowledge, our work is the first to demonstrate how explicit quantum
circuits can be constructed in practice to block encode structured sparse
matrices. All QCLAB circuit implementation can be downloaded from
https://github.com/QuantumComputingLab/explicit-block-encodings. The block
encoding of $A$ is not unique. We will show a few different encoding schemes
and the corresponding quantum circuits. For a sparse matrix $A$ that has at
most $s$ nonzero elements per column, which we refer to as an $s$-sparse
matrix, the general strategies we use to construct a quantum circuit actually
block encodes $A/s$. For many applications, the extra scaling factor $1/s$
does not introduce significant issues. However, for some applications such as
a quantum walk on a graph Szegedy (2004); Childs (2010), the presence of the
$1/s$ factor makes the quantum algorithm less efficient, as we will show later
in this paper. For these applications, we need to use a different strategy to
block encode $A$ directly. We will show how this can be done for a quantum
walk in which the matrix $A$ is a symmetric stochastic matrix or a
discriminant matrix, and the corresponding quantum walk can be viewed as a
block encoding of a Chebyshev polynomial of the discriminant matrix associated
with the stochastic matrix $A$ used to describe the corresponding random walk.

This paper is organized as follows. In section 3, we give a formal definition
of a block encoding of a matrix $A$ and the possibility of using the quantum
eigenvalue transformation to block encode $p(A)$ for some polynomial $p(t)$.
In section 4, we discuss how to construct a block encoding circuit for a
scaled $s$-sparse matrix $A/s$, and give two specific examples. We discuss the
possibility to use the techniques presented in section 4 to construct a
circuit for the block encoding of $P/s$ in section 5, where $P$ is a symmetric
stochastic a matrix associated with a random walk. We show this circuit can be
used as a building block to construct a circuit for performing a quantum walk
associated with such a random walk. We explain why such a construction leads
to a loss of quantum efficiency due to the $1/s$ scaling factor produced in
the block encoding schemes used in section 4. An alternative approach that
takes advantage of the stochastic property of a random walk and block encodes
$P$ directly instead of $P/s$ is presented. As a result, we can construct an
efficient block encoding for a Chebyshev polynomial of $P$. The block encoding
view of a quantum walk introduced in this section differs from how quantum
walks (in particular the Szegedy quantum walks Szegedy (2004)) are
traditionally introduced. We make a clear connection between these two views
in section 5 and show in the supplementary materials how the block encoding
view can be used to explain the efficiency of a quantum walk compared a
classical random walk.

##  2 Notations and Conventions

Following standard conventions used in the quantum computing literature, we
use the Dirac $\bra{\cdot}$ and $\ket{\cdot}$ notation to denote respectively
row and column vectors. In particular $\ket{0}$ and $\ket{1}$ are used to
represent the unit vectors $e_{{0}}=[1\ 0]^{T}$ and $e_{{1}}=[0\ 1]^{T}$,
respectively. The tensor product of $m$ $\ket{0}$’s is denoted by
$\ket{0^{m}}$. We use $\ket{x,y}$ to represent the Kronecker product of
$\ket{x}$ and $\ket{y}$, which is also sometimes written as $\ket{x}\ket{y}$
or $\ket{xy}$. The $N\times N$ identity matrix is denoted by $I_{N}$ and we
sometimes drop the subscript $N$ when the dimension is clear from the context.
The $j$th column of $I_{N}$ is denoted by $\ket{j}$ for $j=0,1,2...,N-1$. For
the binary representation of $j\in\mathbb{N}:0\leq j\leq 2^{n}-1$, we use the
_little-endian_ convention as given by

$j=[\mathtt{j}_{n-1}\cdots\mathtt{j}_{1}\mathtt{j}_{0}]=\mathtt{j}_{n-1}\cdot
2^{n-1}+\cdots+\mathtt{j}_{1}\cdot 2^{1}+\mathtt{j}_{0}\cdot 2^{0},$

where $\mathtt{j}_{i}\in\\{0,1\\}$ for $i=0,\ldots,n-1$.

We use the letters $H$, $X$, $Y$, and $Z$ to represent the Hadamard,
Pauli-$X$, Pauli-$Y$, and Pauli-$Z$ matrices, respectively, defined below

$\displaystyle H$
$\displaystyle=\frac{1}{\sqrt{2}}\begin{bmatrix}1&\phantom{-}1\\\
1&-1\end{bmatrix},$ $\displaystyle X$ $\displaystyle=\begin{bmatrix}0&1\\\
1&0\end{bmatrix},$ $\displaystyle Y$ $\displaystyle=\begin{bmatrix}0&-i\\\
i&\phantom{-}0\end{bmatrix},$ $\displaystyle Z$
$\displaystyle=\begin{bmatrix}1&\phantom{-}0\\\ 0&-1\end{bmatrix}.$ (2.1)

Further, rotation matrices along the Pauli-$Y$ axis will play a key role in
the construction of block encoding circuits and are defined as follows

${R_{y}(\theta):=\begin{bmatrix}\cos\left(\frac{\theta}{2}\right)&-\sin\left(\frac{\theta}{2}\right)\\\\[3.0pt]
\sin\left(\frac{\theta}{2}\right)&\phantom{-}\cos\left(\frac{\theta}{2}\right)\end{bmatrix}=e^{-i\theta
Y/2},}$ (2.2)

where $\theta$ is the rotation angle and the unitary $Y$ defined in (2.1). The
matrices in eqs. 2.1 and 2.2 are $2\times 2$ unitaries and serve as basic
single qubit quantum gates.

We follow the standard convention for drawing quantum circuits with multiple
parallel lines covered by several layers of rectangular boxes. Each line
corresponds to either a single qubit or multiple qubits depending on how it is
labelled and each box corresponds to a single qubit or multi-qubit gate
depending on the number of qubit lines passing through it. We use the
convention that the qubits in a circuit diagram are numbered increasingly from
the top to the bottom as illustrated by the 3 qubit circuit $U$ in fig. 1a. An
integer $j=[\mathtt{j}_{n-1}\cdots\mathtt{j}_{1}\mathtt{j}_{0}]$ input to a
circuit is prepared as a set of quantum states
$\ket{\mathtt{j}_{n-1}}$,…,$\ket{\mathtt{j}_{0}}$ with $\ket{\mathtt{j}_{0}}$
mapped to the highest numbered qubit $q_{n-1}$ and $\ket{\mathtt{j}_{n-1}}$
mapped to the lowest numbered qubit $q_{0}$, see e.g., fig. 1b.

$q_{0}$$q_{1}$$q_{2}$$U$ (a)

$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$U$$\ket{j}\left\\{\phantom{\begin{matrix}~{}\\\\[3.0pt]
~{}\\\\[3.0pt] ~{}\end{matrix}}\right.$ (b)

Figure 1: (a) Qubits of a quantum circuit $U$ are numbered increasingly from
the top to the bottom. (b) How the binary representation of an integer ($j$)
input is mapped to the qubits of the quantum circuit $U$.

An important class of quantum gates are the controlled gates, i.e., one or
more qubits act as a control for some operation. Graphically, the control
operation is represented by a vertical line connecting the control qubit(s),
marked by either a solid or open circle, to the so called target gate, see
e.g., the controlled NOT (CNOT) in fig. 2. The target can also be multiple
gates grouped in a subcircuit block used to perform certain operations. A
solid circle indicates that the controlled operation is performed on the
connected qubit, when the input to the controlling qubit is a $\ket{1}$ state.
Similarly, an open circle indicates that the controlled operation is performed
when the input to the controlling qubit is a $\ket{0}$ state.

$q_{0}$$q_{1}$$=\ \begin{bmatrix}0&1&0&0\\\ 1&0&0&0\\\ 0&0&1&0\\\
0&0&0&1\end{bmatrix}$ (a) $\ket{0}$ controlled

$q_{0}$$q_{1}$$=\ \begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&0&1\\\
0&0&1&0\end{bmatrix}$ (b) $\ket{1}$ controlled

Figure 2: Controlled-NOT gates.

Mathematically, the controlled gates from fig. 2 translate into

${E_{0}\otimes X+(I-E_{0})\otimes I},\qquad\mbox{and}\qquad{E_{1}\otimes
X+(I-E_{1})\otimes I},$ (2.3)

respectively, where the orthogonal projection operators

$\displaystyle E_{{0}}$ $\displaystyle=e_{{0}}e_{{0}}^{T}=\ket{0}\bra{0},$
$\displaystyle E_{{1}}$ $\displaystyle=e_{{1}}e_{{1}}^{T}=\ket{1}\bra{1},$
(2.4)

serve as the controls. Note that the NOT ($X$) operation is applied to the
input of qubit $q_{1}$ in fig. 2a only if the input to qubit $q_{0}$ is
$\ket{0}$. Likewise, the NOT operation is applied to the input of qubit
$q_{1}$ in fig. 2b if the input to qubit $q_{0}$ is $\ket{1}$. A similar
expression can be use to denote multi-qubit controlled NOT gates.

Throughout this paper, we use the QCLAB Toolbox111QCLAB Toolbox:
https://github.com/QuantumComputingLab/qclab to construct and draw quantum
circuits for block encodings of matrices in MATLAB. Hence, it will be
convenient to verify that a presented quantum circuit performs the correct
unitary transformation. As a simple example, the following listing constructs
a simple quantum circuit with $n=2$ qubits that prepares a so-called Bell
state when the input of the circuit is $\ket{00}$. The circuit consists of a
Hadamard gate on the first qubit, followed by a CNOT gate with control on the
first and target on the second qubit.

⬇

circuit = qclab.QCircuit(2);

circuit.push_back(qclab.qgates.Hadamard(0));

circuit.push_back(qclab.qgates.CNOT(0,1));

$q_{0}$$q_{1}$$H$

QCLAB uses MATLAB’s object oriented programming capabilities to keep track of
all gates used in the circuit and to which qubits these gates are applied to
and in what order. The first line of the listing defines a QCLAB circuit
object circuit consisting of 2 qubits. The circuit is constructed by using the
push_back function to place quantum gates (qgates) one layer at a time into
the circuit object according to the circuit diagram shown to the right of the
listing. The unitary matrix defined by the circuit is not explicitly formed
unless the circuit.matrix function is called. One can also draw a circuit by
using the circuit.draw function. We refer readers to the User’s manual of
QCLAB Camps and Van Beeumen (2021) for the syntax of its usage.

##  3 Block encoding and quantum eigenvalue transformation

Block encoding is a technique for embedding a properly scaled nonunitary
matrix $A\in\mathbb{C}^{N\times N}$ into a unitary matrix $U_{A}$ of the form

$U_{A}=\begin{bmatrix}A&\ast\\\ \ast&\ast\end{bmatrix},$ (3.1)

where $\ast$ denotes a matrix block yet to be determined. Applying $U_{A}$ to
a vector of the form

$v=\begin{bmatrix}x\\\ 0\end{bmatrix}=\ket{0}\ket{x},$ (3.2)

where $\|x\|_{2}=1$, yields

$w=U_{A}v=\begin{bmatrix}Ax\\\
*\end{bmatrix}=\ket{0}(A\ket{x})+\ket{1}\ket{\ast},$

where $\ast$ here denotes a vector that we do not care about. If we measure
the first qubit and obtain the $\ket{0}$ state, the second qubit register then
contains $A\ket{x}$. The probability of such a successful measurement is
$\|Ax\|^{2}$.

Note that by “a properly scaled $A$", we mean that $A$ is scaled to satisfy
$\|A\|_{2}\leq 1$. Without such a scaling, a block encoding of $A$ may not
exist because the singular values of any submatrix blocks of a unitary matrix
must be bounded by $1$. Furthermore, if there are some constraints on the type
of unitary we can construct, e.g., the type of quantum gates available on a
quantum computer, we may not be able to find a $U_{A}$ that block encodes $A$
exactly. However, in this paper, we assume that $A$ has already been properly
scaled, and there is no constraints on the quantum gates we can use to
construct a quantum circuit representation of the unitary matrix $U_{A}$.

To give an example of a block encoding, let us consider a $1\times 1$ matrix
$A=\alpha$, where $0<\alpha<1$. In this extremely simple case, a block
encoding of $A$ can be constructed as

$U_{A}=\begin{bmatrix}\alpha&\sqrt{1-\alpha^{2}}\\\
\sqrt{1-\alpha^{2}}&-\alpha\end{bmatrix},\qquad\mbox{or}\qquad
U_{A}=\begin{bmatrix}\alpha&-\sqrt{1-\alpha^{2}}\\\
\sqrt{1-\alpha^{2}}&\alpha\end{bmatrix}.$ (3.3)

Although this type of block encoding can be extended to a properly scaled
matrix $A$ of a larger dimension to yield

$U_{A}=\begin{bmatrix}A&(I-A^{\dagger}A)^{1/2}\\\
(I-A^{\dagger}A)^{1/2}&-A\end{bmatrix},\ \ \mbox{or}\ \
\begin{bmatrix}A&-(I-A^{\dagger}A)^{1/2}\\\
(I-A^{\dagger}A)^{1/2}&A\end{bmatrix},$ (3.4)

this approach is not practical because it requires computing the square root
of $A^{\dagger}A$, which requires computing and diagonalizing $A^{\dagger}A$.
In general, there is no efficient algorithm to perform these operations on a
quantum computer using $\mathcal{O}(\mathrm{poly}(n))$ quantum gates.

A more practical scheme that does not require computing the square root of $A$
can be illustrated by the following real symmetric $2\times 2$ example. Let

$A=\begin{bmatrix}\alpha_{1}&\alpha_{2}\\\
\alpha_{2}&\alpha_{1}\end{bmatrix},$ (3.5)

where $|\alpha_{1}|,|\alpha_{2}|\leq 1$. It can be verified that the matrix

$U_{A}=\frac{1}{2}\begin{bmatrix}U_{\alpha}&-U_{\beta}\\\
U_{\beta}&U_{\alpha}\end{bmatrix}$ (3.6)

is a block encoding of $A/2$, where

$\displaystyle U_{\alpha}$
$\displaystyle=\begin{bmatrix}\alpha_{1}&\alpha_{2}&\alpha_{1}&-\alpha_{2}\\\
\alpha_{2}&\alpha_{1}&-\alpha_{2}&\alpha_{1}\\\
\alpha_{1}&-\alpha_{2}&\alpha_{1}&\alpha_{2}\\\
-\alpha_{2}&\alpha_{1}&\alpha_{2}&\alpha_{1}\end{bmatrix},$ $\displaystyle
U_{\beta}$
$\displaystyle=\begin{bmatrix}\beta_{1}&\beta_{2}&\beta_{1}&-\beta_{2}\\\
\beta_{2}&\beta_{1}&-\beta_{2}&\beta_{1}\\\
\beta_{1}&-\beta_{2}&\beta_{1}&\beta_{2}\\\
-\beta_{2}&\beta_{1}&\beta_{2}&\beta_{1}\end{bmatrix},$ (3.7)

with $\beta_{1}=\sqrt{1-\alpha_{1}^{2}}$ and
$\beta_{2}=\sqrt{1-\alpha_{2}^{2}}$. To implement this unitary on a quantum
computer, we must further decompose $U_{A}$ as a product of simpler unitaries
and construct a quantum circuit with a limited number of quantum gates. We
will discuss how to construct such a quantum circuit in the next section. The
method for constructing the block encoding shown in (3.6)–(3.7) cannot be
easily generalized to matrices of larger dimensions. However, for matrices
with special structures, e.g., sparse matrices, it is possible to develop some
general block encoding strategies which we will discuss in the next section.
The general definition of a block encoding is as follows.

######  Definition 3.1 (Block encoding).

Given an $n$-qubit matrix $A$ ($N=2^{n}$), if we can find
$\alpha,\epsilon\in\mathbb{R}_{+}$, and an $(m+n)$-qubit unitary matrix
$U_{A}$ so that

$\|A-\alpha\left(\langle 0^{m}|\otimes
I_{N}\right)U_{A}\left(|0^{m}\rangle\otimes I_{N}\right)\|_{2}\leq\epsilon,$
(3.8)

then $U_{A}$ is called an $(\alpha,m,\epsilon)$-block-encoding of $A$. In
particular, when the block encoding is exact with $\epsilon=0$, $U_{A}$ is
called an $(\alpha,m)$-block-encoding of $A$.

Here $m$ is the number of ancilla qubits used to block encode $A$, and the
expression $\left(\langle 0^{m}|\otimes
I_{N}\right)U_{A}\left(|0^{m}\rangle\otimes I_{N}\right)$ should be
interpreted as taking the upper-left $2^{n}\times 2^{n}$ matrix block of
$U_{A}$. For example, the block encoding in (3.6)–(3.7) is a $(1,2)$-block-
encoding of $A$ in eq. 3.5.

When solving a large and sparse linear algebra problem on a classical
computer, we often use an iterative solver to seek an approximate solution
$\hat{x}$. For simplicity we assume $A$ is Hermitian. In many cases, such as
when a Krylov subspace method is used, the approximate solution can be written
as $\hat{x}=p(A)v_{0}$, where $p(t)$ is a polynomial that approximates a
desired function and $v_{0}$ is an initial guess or simply a random vector.
For example, to solve a linear system of equations $Ax=b$, we choose $p(t)$ to
be a polynomial approximation to $1/t$ on the spectrum of $A$ and $v_{0}=b$.

To solve this problem on a quantum computer using the technique of block
encoding, we need to block encode the matrix function $p(A)$. If we are
provided a $(1,m)$-block-encoding of the Hermitian matrix $A$ denoted by
$U_{A}$, this task can be achieved by a quantum eigenvalue transformation
(QET) Low and Chuang (2017); Gilyén et al. (2019). Specifically, for any real
polynomial $p(t)$ of degree $d$ satisfying (i) the parity of $p$ is $(d\bmod
2)$, and (ii) $|p(t)|\leq 1,\forall t\in[-1,1]$, there exists a set of
parameters $\\{\phi_{i}\\}_{i=0}^{d}\in\mathbb{R}^{d+1}$ so that the quantum
circuit in fig. 3 provides a $(1,m+1)$-block-encoding of $p(A)$ (Gilyén et
al., 2019, Corollary 11) denoted by $U_{p(A)}$.

$\ket{0}$$\ket{0^{m}}$$\ket{\psi}$$H$$e^{-i\phi_{d}Z}$$U_{A}$$e^{-i\phi_{d-1}Z}$$U_{A}^{\dagger}$$\cdots$$\cdots$$\cdots$$e^{-i\phi_{0}Z}$$H$
Figure 3: A quantum circuit for the block encoding of $p(A)$.

The QET theory and the corresponding quantum circuit for block encoding a
polynomial of $A$ in terms of the block encoding of $A$ is a consequence of
quantum signal processing (QSP) Low and Chuang (2017); Gilyén et al. (2019),
which represents a scalar polynomial of degree $d$ using a product of unitary
matrices of size $2\times 2$, parameterized by $(d+1)$ real numbers called the
phase factors. We state the result of QSP below for completeness, which is a
slight variation of (Gilyén et al., 2019, Theorem 4).

######  Theorem 3.2 (Quantum signal processing).

Let

$U(t)=\begin{bmatrix}t&\sqrt{1-t^{2}}\\\ \sqrt{1-t^{2}}&-t\end{bmatrix}.$
(3.9)

There exists a set of phase angles
$\Phi_{d}\equiv\\{\phi_{0},,...,\phi_{d}\\}\in\mathbb{R}^{d+1}$so that

$U_{\Phi_{d}}(t)\equiv
e^{i\phi_{0}Z}\Pi_{j=1}^{d}\left[U(t)e^{i\phi_{j}Z}\right]=\begin{bmatrix}p(t)&-q(t)\sqrt{1-t^{2}}\\\
q^{\ast}(t)\sqrt{1-t^{2}}&p^{\ast}(t)\end{bmatrix},$ (3.10)

if and only if $p(t)$ and $q(t)$ are complex valued polynomials in $t$ and
satisfy

  1. 1.

$\mathrm{deg}(p)\leq d$, $\mathrm{deg}(q)\leq d-1$;

  2. 2.

$p$ has parity $d$ mod $2$ and $q$ has parity $d-1$ mod $2$;

  3. 3.

$|p(t)|^{2}+(1-t^{2})|q(t)|^{2}=1$, $\forall t\in[-1,1]$.

When $d=0$, $\deg(q)\leq-1$ should be interpreted as $q=0$.

We may verify that if $\Phi_{d}\equiv(\phi_{0},\phi_{1},...,\phi_{d})$ is
chosen as

$\phi_{j}=\left\\{\begin{array}[]{ll}\pi/4,&j=0\>\mathrm{or}\>d\\\
\pi/2,&j=1,...,d-1,\end{array}\right.$

then $p(t)$ is the $d$th degree Chebyshev polynomial of the first kind (up to
a constant global factor $i^{d}$). However, for a properly normalized
arbitrary $d$th degree (real valued) polynomial $p(t)$, finding the phase
angles in $\Phi_{d}\equiv(\phi_{0},\phi_{1},...,\phi_{d})$ to make (3.10) hold
is not trivial. In the past few years, there has been significant progress in
developing new algorithms to improve the efficiency and robustness to find
phase factors Gilyén et al. (2019); Haah (2019); Chao et al. (2020); Dong et
al. (2021); Ying (2022); Dong et al. (2022).

The approach adopted in this paper is the optimization based method Dong et
al. (2021), which computes the phase angles $\phi_{0}$, $\phi_{1}$, …,
$\phi_{d}$ by solving the nonlinear least squares problem

$\min_{\Phi_{d}}\sum_{k=1}^{\widetilde{d}}|\Re[e_{1}^{T}U_{\Phi_{d}}(t_{k})e_{1}]-p_{d}(t_{k})|^{2},$

where $t_{k}$ are chosen to be roots of a Chebyshev polynomial, and
$\widetilde{d}=\lceil(d+1)/2\rceil$. This approach is particularly useful when
we are targeting a real polynomial $p(t)$. With a proper choice of the initial
guess, and despite the complex global optimization landscape Wang et al.
(2022), this approach can robustly find phase factors for high degree
polynomials ($d\sim 10^{4}$).

Once we have an efficient quantum circuit to construct the block encoding
$U_{A}$, we can easily construct an efficient quantum circuit for $U_{p(A)}$.
For a general matrix $A$, the quantum circuit in fig. 3 no longer corresponds
to a QET, but a quantum singular value transformation (QSVT) of $A$ (see
Gilyén et al. (2019) for more detailed discussion of QSVT).

In the next section, we will focus on techniques for constructing an efficient
quantum circuit for $U_{A}$ associated with a well structured sparse $A$.

##  4 Efficient quantum circuits for block encodings of $s$-sparse matrices

In this section, we introduce strategies to directly construct quantum
circuits for block encodings of structured and sparse matrices. Before diving
into all the details, we first return to real symmetric $2\times 2$ example of
(3.5). If we define $\phi_{1}=\arccos(\alpha_{1})+\arccos(\alpha_{2})$ and
$\phi_{2}=\arccos(\alpha_{1})-\arccos(\alpha_{2})$, then we can verify that
the block encoding (3.6)–(3.7) for the $2\times 2$ matrix (3.5) can be
factored as a product of simpler unitaries, i.e.,

$U_{A}=U_{6}U_{5}U_{4}U_{3}U_{2}U_{1}U_{0},$ (4.1)

where $U_{0}=U_{6}=I_{2}\otimes H\otimes I_{2}$, $U_{1}=R_{1}\otimes
I_{2}\otimes I_{2}$, $U_{2}=U_{4}=(I_{2}\otimes E_{0}+X\otimes E_{1})\otimes
I_{2}$, $U_{3}=R_{2}\otimes I_{2}\otimes I_{2}$, and
$U_{5}=I_{2}\otimes(E_{0}\otimes I_{2}+E_{1}\otimes X)$. Here, $H$, $X$ are
the Hadamard and Pauli-$X$ gates defined in (2.1), $R_{1}=R_{y}(\phi_{1})$,
$R_{2}=R_{y}(\phi_{2})$ are the rotation matrices defined in (2.2), and
$E_{0}$, $E_{1}$ are projectors defined in (2.4). The quantum circuit
associated with the factorization given in (4.1) is shown in fig. 4.

$\ket{0}$$\ket{0}$$\ket{j}$$H$$R_{1}$$R_{2}$$H$AA

⬇

C = qclab.QCircuit(3);

C.push_back(qclab.qgates.Hadamard(1));

C.push_back(qclab.qgates.RotationY(0,phi1));

C.push_back(qclab.qgates.CNOT(1,0));

C.push_back(qclab.qgates.RotationY(0,phi2));

C.push_back(qclab.qgates.CNOT(1,0));

C.push_back(qclab.qgates.CNOT(1,2));

C.push_back(qclab.qgates.Hadamard(1));

Figure 4: A quantum circuit for the block encoding of a $2\times 2$ symmetric
matrix $A$.

Note that in this case, the quantum circuit requires 2 ancilla qubits in
addition to the $n=1$ system qubit required to match the dimension of $A$,
which is $N=2^{n}$. As a result, the unitary that block encodes the $2\times
2$ matrix $A$ is of dimension $2^{3}$, which is twice the dimension of the
block encoding given by (3.4).

Although it may not be immediately clear how (4.1) and the corresponding
quantum circuit shown in fig. 4 are obtained from the block encoding matrix
(3.6)–(3.7), it is possible, as we will show below, to develop a general
scheme to construct a block encoding and the corresponding quantum circuit for
well-structured matrices. In particular, when the matrix $A$ is sparse with a
structured sparsity pattern and the nonzero matrix elements can also be well
characterized, an efficient block encoding circuit for $A$ can be constructed,
as we will show in the next section.

In the following, we will focus on an $s$-sparse matrix, which is defined to
be an sparse matrix with at most $s$ nonzeros in each column and row. For
simplicity, let us assume $s=2^{m}\ll N$ for some integer $m\ll n$. When $s$
is not a power of 2, we can always increase $s$ to a power of 2 by treating
some zeros as nonzeros. The following theorem, which is a variant of (Gilyén
et al., 2019, Lemma 48 (in the full version)), asserts that such a sparse
matrix can be block encoded if we can construct unitaries that can encode both
the nonzero structure and the nonzero matrix elements of $A$.

######  Theorem 4.1.

Let $c(j,\ell)$ be a function that gives the index of the $\ell$th non-zero
element in the $j$th column of an $s$-sparse matrix $A\in\mathbb{C}^{N\times
N}$ with $N=2^{n}$, where $s=2^{m}$. If there exists a unitary $O_{c}$ such
that

$O_{c}\ket{\ell}\ket{j}=\ket{\ell}\ket{c(j,\ell)},$ (4.2)

and a unitary $O_{A}$ such that

$O_{A}\ket{0}\ket{\ell}\ket{j}=\left(A_{c(j,\ell),j}\ket{0}+\sqrt{1-|A_{c(j,\ell),j}|^{2}}\ket{1}\right)\ket{\ell}\ket{j},$
(4.3)

then

$U_{A}=\left(I_{2}\otimes D_{s}\otimes I_{N}\right)\left(I_{2}\otimes
O_{c}\right)O_{A}\left(I_{2}\otimes D_{s}\otimes I_{N}\right),$ (4.4)

block encodes $A/s$. Here $D_{s}$ is called a diffusion operator and is
defined as

$D_{s}\equiv\underbrace{H\otimes H\otimes\cdots\otimes H}_{m},$ (4.5)

###### Proof.

Note that applying $D_{s}$ to $\ket{0^{m}}$ yields

$D_{s}\ket{0^{m}}=\frac{1}{\sqrt{s}}\sum_{\ell=0}^{s-1}\ket{\ell},$

where {$\ket{\ell}\\}$ forms the computational basis in the Hilbert space
defined by $m$ qubits. Our goal is to show that
$\bra{0}\bra{0^{m}}\bra{i}U_{A}\ket{0}\ket{0^{m}}\ket{j}=A_{ij}/s$. In order
to compute the inner product
$\bra{0}\bra{0^{m}}\bra{i}U_{A}\ket{0}\ket{0^{m}}\ket{j}$, we apply
$D_{s},O_{A},O_{c}$ to $\ket{0}\ket{0^{m}}\ket{j}$ successively as illustrated
below

$\begin{split}\ket{0}\ket{0^{m}}\ket{j}\xrightarrow{D_{s}}&\frac{1}{\sqrt{s}}\sum_{\ell\in[s]}\ket{0}\ket{\ell}\ket{j}\\\
\xrightarrow{O_{A}}&\frac{1}{\sqrt{s}}\sum_{\ell\in[s]}\left(A_{c(j,\ell),j}\ket{0}+\sqrt{1-\lvert
A_{c(j,\ell),j}\rvert^{2}}\ket{1}\right)\ket{\ell}\ket{j}\\\
\xrightarrow{O_{c}}&\frac{1}{\sqrt{s}}\sum_{\ell\in[s]}\left(A_{c(j,\ell),j}\ket{0}+\sqrt{1-\lvert
A_{c(j,\ell),j}\rvert^{2}}\ket{1}\right)\ket{\ell}\ket{c(j,\ell)},\end{split}$
(4.6)

where $[s]$ denotes the set of integers $\\{0,1,...,s-1\\}$. Instead of
multiplying the leftmost factor $I_{2}\otimes D_{s}\otimes I_{N}$ in (4.4) to
last line of (4.6), we apply it to $\ket{0}\ket{0^{m}}\ket{i}$ first to obtain

$\ket{0}\ket{0^{m}}\ket{i}\xrightarrow{D_{s}}\frac{1}{\sqrt{s}}\sum_{\ell^{\prime}\in[s]}\ket{0}\ket{\ell^{\prime}}\ket{i}.$
(4.7)

Finally, taking the inner product between (4.6) and (4.7) yields

$\bra{0}\bra{0^{m}}\bra{i}U_{A}\ket{0}\ket{0^{m}}\ket{j}=\frac{1}{s}\sum_{\ell}A_{c(j,\ell),j}\delta_{i,c(j,\ell)}=\frac{1}{s}A_{ij}.$
(4.8)

∎

The quantum circuit associated with the block encoding defined in theorem 4.1
is shown in fig. 5. Note that the implementation of this block encoding
requires $m+1$ ancilla qubits in addition to $n$ system qubits. In order to
turn this into an efficient quantum circuit, we need to further decompose the
$O_{c}$ and $O_{A}$ unitaries into a sequence of quantum gates, which may not
be straightforward. In the circuit shown in fig. 4 which corresponds to the
decomposition given in (4.1), $O_{A}$ is decomposed as
$O_{A}=U_{4}U_{3}U_{2}U_{1}$ and $O_{C}$ is simply $U_{5}$. We will show how
these decompositions are constructed systematically in the next section.

Although it may be possible to construct a set of controlled quantum gates to
achieve (4.2) and (4.3) for a specific pair of $j$ and $\ell$. This approach
will not yield an efficient quantum circuit because the total number of
quantum gates in the circuit will be on the order of $\mathcal{O}(N)$, which
is exponential with respect to $n$. Other brute-force approaches such as the
one proposed in Camps and Van Beeumen (2022) may also require $\mathcal{O}(N)$
gates. Our goal is to construct a circuit that has a gate complexity of
$\mathrm{poly}(n)$, i.e., a polynomial in $n$, at least for certain sparse
and/or structured matrices with well defined sparsity patterns.

$\ket{0}$$\ket{0^{m}}$$\ket{j}$$D_{s}$$\,O_{A}\,$$\,O_{C}\,$$D_{s}^{\dagger}$AA
Figure 5: A general schematic circuit drawing for the block encoding of an
$s$-sparse matrix $A$.

Note that $O_{C}$ is unitary. According to eq. 4.2, we must have
$O_{C}^{{\dagger}}\ket{\ell}\ket{c(j,\ell)}=\ket{\ell}\ket{j}$. This means
that for each row index $i=c(j,\ell)$, we can recover the column index $j$
given the value of $\ell$. This assumption is of course somewhat restrictive,
but it covers important cases such as banded matrices. For more general query
models we refer readers to Gilyén et al. (2019). We remark that it can
generally be more difficult to explicitly construct quantum circuits for
$O_{C}$’s in these more general query models.

In the following, we give some specific examples to illustrate how efficient
quantum circuits for $O_{C}$ and $O_{A}$ can be constructed for some well
structured sparse matrices.

###  4.1 Real symmetric $2\times 2$ matrix

We revisit the matrix (3.5) once more and view it as an $s$-sparse matrix with
$s=2$ even though it is dense. Therefore, we can still use the recipe given in
theorem 4.1 to construct a block encoding of $A/2$. We will show below how
explicit circuits for $O_{C}$ and $O_{A}$ can be constructed.

####  4.1.1 The $O_{C}$ circuit

Since the second column of (3.5) is a down or up shift of the first one, the
function $c(j,\ell)$, which defines the (0-based) row index of the $\ell$th
nonzero element in the $j$th column, can be defined by

$c(j,\ell)=\mathrm{mod}(j+\ell,2),$ (4.9)

for $j,\ell=\\{0,1\\}$. After enumerating of all possible combinations of
$(\ell,j)$ input pairs and their corresponding $(\ell,c(j,\ell)$ output pairs
shown in (4.10) (on the right), we see that $O_{C}$ can be simply implemented
as a CNOT gate shown on the left of (4.10).

$\ket{\ell}$$\ket{j}$$\,O_{C}\,$$=$ $\ell$ | $j$
---|---
0 | 0
0 | 1
1 | 0
1 | 1
$\quad\to\quad$ $\ell$ $c(j,\ell)$ 0 0 0 1 1 1 1 0 (4.10)

using the following two lines QCLAB code

⬇

OC = qclab.QCircuit(2,1);

OC.push_back(qclab.qgates.CNOT(0,1));

####  4.1.2 The $O_{A}$ circuit

The basic strategy to construct a circuit for $O_{A}$ defined by (4.3) is to
use controlled rotations to place numerical values at proper locations in
$U_{A}$. Because the matrix $A$ in (3.5) has at most two unique matrix
elements. We need two controlled rotations. In general, we need to condition
the application of these rotations on the values of $j$ and $\ell$. However,
since the values of $\alpha_{1}$ and $\alpha_{2}$ in (3.5) depend solely on
$\ell$, control is only required on the qubit that takes $\ket{\ell}$ as the
input. We apply the rotation $R_{y}(\theta_{1})$ with
$\theta_{1}=2\arccos(\alpha_{1})$ when $\ell=0$, and $R_{y}(\theta_{2})$ with
$\theta_{2}=2\arccos(\alpha_{2})$ when $\ell=1$. These controlled rotations
are combined to yield the following $O_{A}$ circuit.

$\ket{0}$$\ket{\ell}$$\ket{j}$$\,O_{A}\,$$\,R_{y}(\theta_{1})\,$$\,R_{y}(\theta_{2})\,$$=$$\begin{aligned}
\theta_{1}&=2\arccos(\alpha_{1})\\\ \theta_{2}&=2\arccos(\alpha_{2})\\\
\end{aligned}$ (4.11)

Note that the last qubit is not used in this $O_{A}$ circuit. The
corresponding QCLAB code is given by

⬇

OA = qclab.QCircuit(3);

OA.push_back(qclab.qgates.CRotationY(1,0,theta1,0));

OA.push_back(qclab.qgates.CRotationY(1,0,theta2,1));

On some quantum hardware, it is preferable to use single qubit rotation and
CNOT gates in place of controlled rotation gates. These are sometimes referred
to as _uniformly controlled rotations_ Möttönen et al. (2004). In (4.12), we
show how the controlled rotations used in the $Q_{A}$ circuit (4.11) can be
replaced by an equivalent set of uniformly controlled rotation gates.

$\,R_{y}(\theta_{1})\,$$\,R_{y}(\theta_{2})\,$$\,R_{y}(\phi_{1})\,$$\,R_{y}(\phi_{2})\,$$=$$\begin{aligned}
\theta_{1}&=\phi_{1}+\phi_{2}\\\ \theta_{2}&=\phi_{1}-\phi_{2}\\\
\end{aligned}$ (4.12)

The desired uniformly controlled rotations can be constructed in QCLAB by

⬇

OA = qclab.QCircuit(3);

OA.push_back(ucry([theta1,theta2]));

To see that the right hand side of (4.12) is identical to the left hand, we
observe first that, if the second qubit is in the $\ket{0}$ state, the circuit
on the left applies $R_{y}(\theta_{1})$ to the first qubit. In the circuit on
the right, $R_{y}(\phi_{2})R_{y}(\phi_{1})$ is applied to the first qubit in
this case. These two operations are identical when
$\theta_{1}=\phi_{1}+\phi_{2}$. Secondly, if the second qubit is in the
$\ket{1}$ state, the left circuit applies $R_{y}(\theta_{2})$ to the first
qubit, while the right circuit applies the gate sequence
$XR_{y}(\phi_{2})XR_{y}(\phi_{1})$. It follows from the identity
$XR_{y}(\theta)X=R_{y}(-\theta)$ that these operations are equivalent if
$\theta_{2}=\phi_{1}-\phi_{2}$.

####  4.1.3 The complete circuit

Finally, we substitute circuits eqs. 4.12 and 4.10, together with $D_{s}=H$
into fig. 5 and obtain the complete block-encoding quantum circuit for the
matrix (3.5). Note that this circuit is identical to the one we have already
introduced in fig. 4.

###  4.2 Banded circulant matrix

A sparse matrix $A$ can be viewed as an adjacency matrix for a directed graph
defined in terms a vertex set $V$, which consists of column indices $\\{j\\}$
of $A$, and an edge set $E$, which consists of pairs of indices $\\{(i,j)\\}$.
The $(i,j)$th element of $A$ is nonzero if $(i,j)\in E$. The numerical value
of the $(i,j)$th element of $A$, denoted by $A_{i,j}$, represents the weight
of the edge emanating from the vertex $j$ and incident to the vertex $i$ for a
directed graph. For an undirected graph, the corresponding adjacency matrix is
symmetric, i.e., $A_{i,j}=A_{j,i}$.

In this subsection, we will focus on the sparse matrix associated with a
directed cyclic graph. To illustrate this, we consider the following cyclic
graph with $N=8$ vertices and associated banded circulant adjacency matrix

$\displaystyle A$
$\displaystyle=\begin{bmatrix}\alpha&\gamma&0&\cdots&\beta\\\
\beta&\alpha&\ddots&\ddots&0\\\ 0&\beta&\ddots&\gamma&\vdots\\\
\vdots&\ddots&\ddots&\alpha&\gamma\\\ \gamma&0&\cdots&\beta&\alpha\\\
\end{bmatrix}.$ (4.13)

Although not shown explicitly in (4.13), two directed edges emanate from each
vertex $j$, $0\leq j\leq N-1$, i.e., $(\mathrm{mod}(j+1,N),j)\in E$ and
$(j,\mathrm{mod}(j-1,N))\in E$. The weights associated with these edges are
$\beta$ and $\gamma$. We also assign a weight $\alpha$ to each vertex. This
weight can also be viewed as the weight associated with a self-loop edge from
a vertex $j$ to itself. The matrix is nearly tridiagonal with the value
$\alpha$ on its diagonal, $\gamma$ on its superdiagonal and $\beta$ on the
subdiagonal. The non-zero elements $A_{N-1,0}=\gamma$ and $A_{0,N-1}=\beta$
reflect the cyclic feature of the graph. Each column of the matrix has 3
nonzeros. We use $m=\lceil\log_{2}3\rceil=2$ ancilla qubits to encode the row
indices of the nonzero matrix elements in each column. An additional ancilla
qubit is needed to encode the numerical values of the nonzero matrix elements.
When using theorem 4.1 to construct the block encoding circuit, we take
$s=2^{m}=4$ here, i.e., we view (4.13) as a $4$-sparse matrix even though each
column of the matrix has only 3 nonzero matrix elements.

####  4.2.1 The $O_{C}$ circuit

For the sparse adjacency matrix induced by the cyclic graph, the function
$c(j,\ell)$, which defines the row index of the $\ell$th nonzero element in
the $j$th column, can be written as

$c(j,\ell)=\mathrm{mod}(j+\ell-1,N)={\begin{cases}\mathrm{mod}(j-1,N)&\text{if
$\ell=0$ (superdiagonal),}\\\ j&\text{if $\ell=1$ (diagonal) or 3,}\\\
\mathrm{mod}(j+1,N)&\text{if $\ell=2$ (subdiagonal).}\end{cases}}$ (4.14)

Therefore, to implement the $O_{C}$ unitary defined in (4.2), we need to
construct a circuit to map $\ket{j}$ to $\ket{\mathrm{mod}(j-1,N)}$,
$\ket{j}$, or $\ket{\mathrm{mod}(j+1,N)}$ depending on the value of
$\ell=\\{0,1,2\\}$. These cyclic subtraction and addition mappings are simply
left and right shift permutation operators defined as

$\displaystyle L$ $\displaystyle=\begin{bmatrix}0&0&\ldots&\ldots&1\\\
1&0&0&\ddots&0\\\ \vdots&1&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&\vdots\\\ 0&0&\ldots&1&0\\\ \end{bmatrix},$
$\displaystyle R$ $\displaystyle=\begin{bmatrix}0&1&\ldots&\ldots&0\\\
0&0&1&\ddots&0\\\ \vdots&\ddots&\ddots&\ddots&\vdots\\\
\vdots&\ddots&\ddots&\ddots&1\\\ 1&0&\ldots&\ddots&0\\\ \end{bmatrix}.$ (4.15)

Note that the $L$ and $R$ operators correspond to the addition and subtraction
arithmetic operations, i.e., $+1$ and $-1$, respectively. They can be
implemented by a quantum circuit consisting of multi-qubit controlled-NOT
gates shown in figs. 6b and 6a. The multi-qubit controlled gates perform the
carry operation in the binary format (see e.g. (Rieffel and Polak, 2011,
Chapter 6)).

$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$L$$X$$=$ (a) $L$-shift circuit

$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$R$$X$$=$ (b) $R$-shift circuit

Figure 6: The shift circuits.

To use these shift components in the quantum circuit implementation of
$O_{C}$, we need to control the applications of the $L$ and $R$ shift
operators from the qubits that take $\ket{\ell}$ as the input. For $\ell=0$,
we need to apply the $R$-shift to account for the $-1$ term in (4.14) and
encode the row indices of the superdiagonal elements. For $\ell=1$, nothing
needs to be done. For $\ell=2$, we need to apply the $L$-shift to account for
the $+1$ term and encode the row indeces of the subdiagonal elements. Note
that the use of $D_{s}$ requires us to also consider $\ell=3$ even though the
matrix $A$ only has 3 nonzero elements per column. In this case, we do not
need to do anything. All of these conditions can be implemented by the
following $O_{C}$ circuit

${\ket{\ell_{1}}}$${\ket{\ell_{0}}}$$\ket{j}$$\,O_{C}\,$$R$$L$$=$ (4.16)

with the corresponding QCLAB code

⬇

OC = qclab.QCircuit(n+2,1);

OC.push_back(rightshift(n+2,2:n+1,[0,1],[0,0]));

OC.push_back( leftshift(n+2,2:n+1,[0,1],[1,0]));

We should note that the construction of $O_{C}$ depends on how $c(j,\ell)$ is
defined, which is not unique. For example, instead of defining $c(j,\ell)$ by
(4.14), we can use the following definition

$c(j,\ell)=\begin{cases}j&\text{if $\ell=0$ (diagonal) or 3,}\\\
{\mathrm{mod}(j+1,N)}&\text{if $\ell=1$ (subdiagonal),}\\\
{\mathrm{mod}(j-1,N)}&\text{if $\ell=2$ (superdiagonal),}\end{cases}$ (4.17)

resulting in the $O_{C}$ circuit

${\ket{\ell_{1}}}$${\ket{\ell_{0}}}$$\ket{j}$$\,O_{C}\,$$L$$R$$=$$L$$R$$=$
(4.18)

that can further be simplified because the $L$-shift and $R$-shift cancel each
other for $\ell=0$ and $\ell=3$. The corresponding QCLAB code is given by

⬇

OC = qclab.QCircuit(n+2,1);

OC.push_back( leftshift(n+2,2:n+1,1));

OC.push_back(rightshift(n+2,2:n+1,0));

####  4.2.2 The $O_{A}$ circuit

For circulant matrices, the matrix elements of $A$ depend exclusively on
$\ell$. Therefore, when we use controlled rotations to encode the nonzero
matrix elements, we place controls only on qubits that take $\ket{\ell}$ as
the input. If $c(j,\ell)$ is defined by (4.17), the follow $O_{A}$ circuit can
be constructed to use the rotation $R_{y}(\theta_{0})$ to encode the diagonal
entry $\alpha$. The rotation is applied when $\ell=0$. The rotations
$R_{y}(\theta_{1})$ and $R_{y}(\theta_{2})$ are used to encode the sub- and
sup-diagonal matrix elements $\beta$ and $\gamma$ respectively. They are
applied when $\ell=1$ and $\ell=2$ respectively.

$\ket{0}$${\ket{\ell_{1}}}$${\ket{\ell_{0}}}$$\ket{j}$$\,O_{A}\,$$\,R_{y}(\theta_{0})\,$$\,R_{y}(\theta_{1})\,$$\,R_{y}(\theta_{2})\,$$=$
(4.19)

The unitary matrix implemented by the circuit can be written as

$O_{A}=:O_{A}^{(2)}O_{A}^{(1)}O_{A}^{(0)},$ (4.20)

where

$\displaystyle O_{A}^{(0)}$
$\displaystyle=R_{y}(\theta_{0})\otimes(E_{0}\otimes E_{0})\otimes
I_{n}+I_{2}\otimes(I_{4}-E_{0}\otimes E_{0})\otimes I_{n},$ (4.21)
$\displaystyle O_{A}^{(1)}$
$\displaystyle=R_{y}(\theta_{1})\otimes(E_{0}\otimes E_{1})\otimes
I_{n}+I_{2}\otimes(I_{4}-E_{0}\otimes E_{1})\otimes I_{n},$ (4.22)
$\displaystyle O_{A}^{(2)}$
$\displaystyle=R_{y}(\theta_{2})\otimes(E_{1}\otimes E_{0})\otimes
I_{n}+I_{2}\otimes(I_{4}-E_{1}\otimes E_{0})\otimes I_{n}.$ (4.23)

To determine the value of the rotation angle $\theta_{0}$ from $\alpha$, we
first compute the quantum state after applying the diffusion operator
$D_{s}=H\otimes H$, the $O_{A}^{(0)}$ circuit, and the $O_{C}$ circuit to the
initial state $\ket{0}\ket{00}\ket{j}$, i.e.,

$\displaystyle\Big{(}I_{2}\otimes O_{C}\Big{)}$ $\displaystyle
O_{A}^{(0)}\Big{(}I_{2}\otimes D_{s}\otimes
I_{n}\Big{)}\ket{0}\ket{00}\ket{j}$
$\displaystyle={\frac{1}{2}}\Big{(}I_{2}\otimes
O_{C}\Big{)}O_{A}^{(0)}\ket{0}\Big{(}\ket{00}+\ket{01}+\ket{10}+\ket{11}\Big{)}\ket{j},$
$\displaystyle={\frac{1}{2}\Big{(}I_{2}\otimes
O_{C}\Big{)}\Big{(}R_{y}(\theta_{0})\ket{0}\ket{00}+\ket{0}\ket{01}+\ket{0}\ket{10}+\ket{0}\ket{11}\Big{)}\ket{j},}$
$\displaystyle={\frac{1}{2}\Big{(}R_{y}(\theta_{0})\ket{0}\ket{00}\ket{j}+\ket{0}\ket{01}\ket{j+1}+\ket{0}\ket{10}\ket{j-1}+\ket{0}\ket{11}\ket{j}\Big{)}.}$
(4.24)

Next, taking the inner product of (4.24) with $(I_{2}\otimes D_{s}\otimes
I_{n})\ket{0}\ket{00}\ket{j}$ results in

$\frac{1}{4}\bra{j}\bra{00}\braket{0}{R_{y}(\theta_{0})}{0}\ket{00}\ket{j}+\frac{1}{4}\bra{j}\bra{11}\braket{0}{0}\ket{11}\ket{j}=\frac{1}{4}\left[\cos\left(\tfrac{\theta_{0}}{2}\right)+1\right],$
(4.25)

where we use the fact that
$\braket{0}{R_{y}(\theta_{0})}{0}=\cos\left(\frac{\theta_{0}}{2}\right)$.
Finally, to satisfy the equality
$\frac{1}{4}\left[\cos\left(\tfrac{\theta_{0}}{2}\right)+1\right]=\frac{\alpha}{4}$,
we obtain $\theta_{0}=2\arccos(\alpha-1)$. Without loss of generality, we have
assumed $\alpha$ is real and positive. The case for $\alpha<0$ can be handled
by first multiplying $A$ by $-1$.

To calculate the rotation angle $\theta_{1}$ from the subdiagonal element
$\beta$, we start again from the quantum state after applying $D_{s}$,
$O_{A}^{(1)}$, and $O_{C}$ to $(I_{2}\otimes D_{s}\otimes
I_{n})\ket{0}\ket{00}\ket{j}$, i.e.,

$\displaystyle\Big{(}I_{2}\otimes O_{C}\Big{)}$ $\displaystyle
O_{A}^{(1)}\Big{(}I_{2}\otimes D_{s}\otimes
I_{n}\Big{)}\ket{0}\ket{00}\ket{j}$
$\displaystyle={\frac{1}{2}}\Big{(}I_{2}\otimes
O_{C}\Big{)}O_{A}^{(1)}\ket{0}\Big{(}\ket{00}+\ket{01}+\ket{10}+\ket{11}\Big{)}\ket{j},$
$\displaystyle={\frac{1}{2}\Big{(}I_{2}\otimes
O_{C}\Big{)}\Big{(}\ket{0}\ket{00}+R_{y}(\theta_{1})\ket{0}\ket{01}+\ket{0}\ket{10}+\ket{0}\ket{11}\Big{)}\ket{j},}$
$\displaystyle={\frac{1}{2}\Big{(}\ket{0}\ket{00}\ket{j}+R_{y}(\theta_{1})\ket{0}\ket{01}\ket{j+1}+\ket{0}\ket{10}\ket{j-1}+\ket{0}\ket{11}\ket{j}\Big{)}.}$
(4.26)

Next, taking the inner product of (4.26) with $(I_{2}\otimes D_{s}\otimes
I_{n})\ket{0}\ket{00}\ket{j+1}$ results in

$\frac{1}{4}\bra{j+1}\bra{01}\braket{0}{R_{y}(\theta_{1})}{0}\ket{01}\ket{j+1}=\frac{1}{4}\cos\left(\tfrac{\theta_{1}}{2}\right),$
(4.27)

where we use the fact that
$\braket{0}{R_{y}(\theta_{1})}{0}=\cos\left(\frac{\theta_{1}}{2}\right)$.
Finally, to satisfy the equality
$\frac{1}{4}\cos\left(\tfrac{\theta_{1}}{2}\right)=\frac{\beta}{4}$, we obtain
$\theta_{1}=2\arccos(\beta)$.

In a similar way, we can show that $\theta_{2}=2\arccos(\gamma)$. The $O_{A}$
circuit (4.19) corresponding to the $O_{C}$ circuit (4.18) can be implemented
in QCLAB as

⬇

theta0 = 2*acos(alpha - 1);

theta1 = 2*acos(beta);

theta2 = 2*acos(gamma);

OA = qclab.QCircuit(n+3);

OA.push_back(qclab.qgates.MCRotationY([1,2],0,[0,0],theta0));

OA.push_back(qclab.qgates.MCRotationY([1,2],0,[0,1],theta1));

OA.push_back(qclab.qgates.MCRotationY([1,2],0,[1,0],theta2));

If we choose to use (4.14) to define $c(j,\ell)$, we can use controlled
rotations by $R_{y}(\theta_{0})$, $R_{y}(\theta_{1})$ and $R_{y}(\theta_{2})$
to encode $\gamma$, $\alpha$ and $\beta$ respectively. It can be shown that
corresponding rotations angles are $\theta_{0}=2\arccos(\gamma)$,
$\theta_{1}=2\arccos(\alpha-1)$, and $\theta_{2}=2\arccos(\beta)$. The $Q_{A}$
circuit can be implemented in QCLAB as

⬇

theta0 = 2*acos(gamma);

theta1 = 2*acos(alpha - 1);

theta2 = 2*acos(beta);

OA = qclab.QCircuit(n+3);

OA.push_back(qclab.qgates.MCRotationY([1,2],0,[0,0],theta0));

OA.push_back(qclab.qgates.MCRotationY([1,2],0,[0,1],theta1));

OA.push_back(qclab.qgates.MCRotationY([1,2],0,[1,0],theta2));

In both cases, we can again replace multi-qubit controlled $R_{y}$ rotations
in (4.19) with a uniformly controlled rotation. This approach leads to an
$O_{A}$ circuit that has the following structure

$\ket{0}$${\ket{\ell_{1}}}$${\ket{\ell_{0}}}$$\ket{j}$$\,O_{A}\,$$\,R_{y}(\phi_{0})\,$$\,R_{y}(\phi_{1})\,$$\,R_{y}(\phi_{2})\,$$\,R_{y}(\phi_{3})\,$$=$
(4.28)

which we implement in QCLAB as follows

⬇

OA = qclab.QCircuit(n+3);

OA.push_back(ucry([theta_0,theta_1,theta_2]));

The angles $\phi_{i}$ are computed from $\theta_{i}$ through a Walsh-Hadamard
transformation Möttönen et al. (2004).

####  4.2.3 The complete circuit

The complete circuit for a block encoding of $A/{4}$ for a $8\times 8$
circulant matrix of the form (4.13) is given in fig. 7. The total number of
Hadamard gates and controlled rotations are proportional to $\log(s)$ which is
generally very small for a sparse matrix. The number of controlled $R$ and $L$
shifts is also on the order of $O(\log s)$. Each controlled-$R$ and
controlled-$L$ circuit is a general multi-qubit controlled (Toffoli) gate that
can be further decomposed into $\mathrm{poly}(n)$ two-qubit gates. Therefore,
the overall gate complexity of the $U_{A}$ circuit is $\mathrm{poly}(n)$,
which is considered efficient.

$\ket{0}$$\ket{0}$$\ket{0}$$\ket{j}$$H$$H$$\,R_{y}(\phi_{0})\,$$\,R_{y}(\phi_{1})\,$$\,R_{y}(\phi_{2})\,$$\,R_{y}(\phi_{3})\,$$L$$R$$H$$H$AAA
Figure 7: A complete quantum circuit for the block encoding of a $8\times 8$
banded circulant matrix.

We should also note that the circuit shown in fig. 7 can be easily modified to
block encode a tridiagonal matrix with $\alpha$ on the diagonal, $\beta$ on
the subdiagonal and $\gamma$ on the superdiagonal. All we need to do is to add
the following two multi-qubit control gates to the sequence of gates in the
$O_{A}$ block of the circuit. These gates perform controlled rotations
$R_{y}(\pi-\theta_{1})$ and $R_{y}(\pi-\theta_{2})$ to zero out $\beta$ in the
$(0,N-1)$th entry of $U_{A}$ and $\gamma$ in the $(N-1,0)$th entry of $U_{A}$,
respectively, as shown in Figure 8.

$\ket{\ell_{1}}$$\ket{\ell_{0}}$$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$\,R_{y}(\pi-\theta_{1})$
$\,R_{y}(\pi-\theta_{2})$ Figure 8: Multi-qubit controlled rotations that can
be added to the quantum circuit shown in fig. 7 between $O_{A}$ and $O_{C}$ to
block encode a tri-diagonal matrix.

###  4.3 Extended binary tree

The banded circulant matrix is special in the sense that the $c(j,\ell)$
function is relatively simple, and the values of nonzero matrix elements are
independent of $j$. Next we consider another special case that has a slightly
more complicated $c(j,\ell)$ function. In this case, the matrix $A$ is the
adjacency matrix for an undirected and balanced binary tree. A standard
balanced binary tree has $2^{n}-1$ vertices. To simplify our discussion, we
add one additional vertex and connect it to the root of the binary tree so
that the total number of vertices is $2^{n}$. The additional vertex is the new
root of the tree and labeled by $0$. We call this binary tree an extended
binary tree and consider the following extended binary tree with $8$ vertices
and associated $8\times 8$ adjacency matrix

baseline,for tree= grow=south, circle, draw, minimum size=3ex, inner sep=1pt,
s sep=5mm [0 [1 [2 [4] [5] ] [3 [6] [7] ] ] ] $\displaystyle A$
$\displaystyle=\begin{bmatrix}\gamma&\beta&&&&&&\\\
\beta&\alpha&\beta&\beta&&&&\\\ &\beta&\alpha&&\beta&\beta&&\\\
&\beta&&\alpha&&&\beta&\beta\\\ &&\beta&&\gamma&&&\\\ &&\beta&&&\gamma&&\\\
&&&\beta&&&\gamma&\\\ &&&\beta&&&&\gamma\end{bmatrix}.$ (4.29)

We assign the weight $0<\alpha<1$ to each vertex (or self loop from a vertex
to itself) with the exception of the root and leaves of the tree. For those
vertices, we assign the weight $0<\gamma<1$ instead. We assign the weight
$0<\beta<1$ to each edge between a parent and its child.

####  4.3.1 The $O_{C}$ circuit

The function $c(j,\ell)$ associated with the nonzero pattern of the adjacency
matrix (4.29) can be defined as

$c(j,\ell)={\begin{cases}2j&\text{if $\ell=0$ (left child),}\\\ 2j+1&\text{if
$\ell=1$ (right child),}\\\ j/2&\text{if $\ell=2$ and $j$ even (parent),}\\\
(j-1)/2&\text{if $\ell=3$ and $j$ odd (parent),}\\\ j&\text{if $\ell=4$
(diagonal).}\end{cases}}$ (4.30)

Because this function involves multiplying a column index $j$ by 2 and
dividing $j$ by 2, the $O_{C}$ circuit will contain controlled subcircuits
that perform these operations in addition to the controlled $L$-shift and
$R$-shift circuits used to perform the addition and subtraction by 1 for
$\ell=1$ and $\ell=3$, respectively.

The mapping from $\ket{j}$ to $\ket{2j}$ can be defined by a unitary operator
$M_{2}$ which consists of a sequence of swap operations between adjacency
qubits as shown in fig. 9a. Note that the bottom 3 qubits are used to encode
the column index with $\ket{j_{0}}$ being the label for the least significant
and $\ket{j_{2}}$ being the label for the most significant bits. The top qubit
labelled by $\ket{0}$ is an ancilla qubit that serves as a carry for $j\geq
4$.

$\ket{0}$$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$\ket{0}$
(a) multiply by 2

$\ket{0}$$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$\ket{j_{0}}$$\ket{0}$$\ket{j_{2}}$$\ket{j_{1}}$
(b) divide by 2

Figure 9: The quantum circuits for (a) multiplying $\ket{j}$ by 2 and (b)
dividing $\ket{j}$ by 2.

The mapping from $\ket{j}$ to $\ket{j/2}$, which we denote by $D_{2}$, is the
inverse operation of $M_{2}$. Thus, we can simply reverse the sequence of SWAP
gates in fig. 9a to obtain a circuit for $D_{2}$ in fig. 9b. Note that in this
case, the least significant $\ket{j_{0}}$ ends up at the top qubit after
$D_{2}$ is applied. This is problematic because taking the inner product of
$D_{2}(\ket{0}\ket{j})$ with $\ket{0}\ket{i}$, which appears in the evaluation
of the $(i,j)$th element of $U_{A}$, will always result in 0, which means that
we cannot properly encode the non-zero element $A_{i,j}$ when $i$ is the
parent of $j$ and $j$ is odd. However, this problem can be resolved by
subtracting 1 from $\ket{j}$, if $j$ is odd, before applying $D_{2}$ to ensure
that a $\ket{0}$ state is always present on the ancilla qubit after $O_{C}$ is
applied.

With properly constructed $M_{2}$ and $D_{2}$ circuits, we can implement the
$O_{C}$ circuit as follows

$\ket{\ell_{2}}$$\ket{\ell_{1}}$$\ket{\ell_{0}}$$\ket{0}$$\ket{j}$$\,O_{C}\,$$\,M_{2}\,$$\,M_{2}\,$$L$$\,D_{2}\,$$R$$\,D_{2}\,$$=$
(4.31)

with the corresponding QCLAB code

⬇

OC = qclab.QCircuit(n+4,1);

OC.push_back( mul2(n+4,3:n+3,[0,1,2],[0,0,0]));

OC.push_back( mul2(n+4,3:n+3,[0,1,2],[0,0,1]));

OC.push_back( leftshift(n+4,4:n+3,[0,1,2],[0,0,1]));

OC.push_back( div2(n+4,3:n+3,[0,1,2],[0,1,0]));

OC.push_back(rightshift(n+4,4:n+3,[0,1,2],[0,1,1]));

OC.push_back( div2(n+4,3:n+3,[0,1,2],[0,1,1]));

####  4.3.2 The $O_{A}$ circuit

As we indicated earlier, the construction of the $O_{A}$ quantum circuit
depends closely on how $O_{C}$ is contructed. For the adjacency matrix
associated with the extended binary tree, the $O_{A}$ circuit corresponding to
the $O_{C}$ circuit shown in eq. 4.31 can be constructed as follows:

  1. 1.

First, we use a rotation angle $\theta_{0}=2\arccos(\beta)$ controlled by
$\ell_{2}=0$ to place $\beta$ on the off-diagonals of the principal leading
block of $U_{A}$.

  2. 2.

Second, we use a rotation angle $\theta_{1}=2\arccos(\frac{\alpha}{4})$
controlled by $(\ell_{2},j_{2})=(1,0)$ to place $\alpha$ at the diagonal
elements not corresponding to the root or leaves.

  3. 3.

Third, we use a rotation angle $\theta_{2}=2\arccos(\frac{\gamma}{4})$
controlled by $(\ell_{2},j_{2})=(1,1)$ to place $\gamma$ at the diagonal
elements corresponding to the leaves.

  4. 4.

Finally, we use a rotation angle
$\theta_{3}=2\arccos(\frac{\gamma}{4}-\frac{\beta}{2})-\theta_{1}$ controlled
by $(\ell_{2},j)=(1,0)$ to fix the leading element of $U_{A}$.

The complete $O_{A}$ circuit resulting from the above procedure can be
implemented by the following circuit

$\ket{0}$$\ket{\ell_{2}}$$\ket{\ell_{1}}$$\ket{\ell_{0}}$$\ket{0}$$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$\,O_{A}\,$$\,R_{y}(\theta_{0})\,$$\,R_{y}(\theta_{1})\,$$\,R_{y}(\theta_{2})\,$$\,R_{y}(\theta_{3})\,$$=$
(4.32)

with the corresponding QCLAB code

⬇

theta0 = 2*acos(beta);

theta1 = 2*acos(alpha/4);

theta2 = 2*acos(gamma/4);

theta3 = 2*acos(gamma/4 - beta/2) - theta1;

OA = qclab.QCircuit(n+5);

OA.push_back(qclab.qgates.CRotationY(1,0,theta0,0));

OA.push_back(qclab.qgates.MCRotationY([1,5],0,[1,0],theta1));

OA.push_back(qclab.qgates.MCRotationY([1,5],0,[1,1],theta2));

OA.push_back(qclab.qgates.MCRotationY([1,5:n+4],0,...

[1,zeros(1,n)],theta3));

####  4.3.3 The complete circuit

Combining the $O_{C}$ and $O_{A}$ circuits, we obtain the complete circuit for
the block encoding of the $8\times 8$ adjacency matrix associated with the
8-vertex extended binary tree as shown in fig. 10.

$\ket{0}$$\ket{0}$$\ket{0}$$\ket{0}$$\ket{0}$$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$H$$H$$H$$R_{0}$$R_{1}$$R_{2}$$R_{3}$$\,M_{2}\,$$\,M_{2}\,$$\,L\,$$\,D_{2}\,$$\,R\,$$\,D_{2}\,$$H$$H$$H$AAAAA
Figure 10: The full block-encoding quantum circuit for the adjacency matrix
associated with the extended binary tree shown in eq. 4.29.

This circuit can be easily generalized for larger adjacency matrices
associated with an extended binary tree with a larger number ($N=2^{n}$) of
vertices. However, because the number of unique cases defined by the function
$c(j,\ell)$ in (4.30) is a constant $4$ due to the relatively small number of
additional vertices each vertex is connected to, the number of the controlled
multiplication, division and additional gates in $O_{C}$ is fixed.
Furthermore, because the number of distinct values of matrix elements in $A$
is fixed at 3, the number of controlled rotations required in $O_{A}$ is also
fixed. Each of these controlled rotations can be further decomposed into a
subcircuit with $\mathcal{O}(\mathrm{poly}(n))$ two-qubit gates. The overall
gate complexity of the quantum circuit is $\mathcal{O}(\mathrm{poly}(n))$,
which is considered efficient.

##  5 Efficient circuits for the block encoding of a symmetric stochastic
matrix and quantum walks

In the previous section, we presented a general technique for constructing an
efficient quantum circuit to block encode $A/s$ for a properly scaled
$s$-sparse matrix $A$. For many applications such as solving a linear system,
the $1/s$ factor does not fundamentally change the solution besides a simple
rescaling (though a large scaling factor can reduce the final success
probability). However, for other applications, introducing the $1/s$ factor is
problematic. One such an application is the construction of a quantum walk
from the block encoding of an $s$-sparse symmetric stochastic matrix $P$. For
such a matrix, we need a different strategy to construct an efficient quantum
circuit that block encodes $P$ directly instead of $P/s$.

In this section, we will give a brief introduction of the construction of a
quantum walk from the block encoding of a symmetric $s$-sparse stochatic
matrix $P$ associated with a classical random walk. We will explain why it is
important to block encode $P$ instead of $P/s$, and present a strategy for
constructing an efficient quantum circuit for block encoding $P$. We will also
show how such a circuit can be used to construct a quantum circuit for a
quantum walk.

A stochastic matrix $P$, also called a Markov chain matrix, describes the
transition probabilities of traversing from one vertex to another in a random
walk on a graph $G=(V,E)$. Since the matrix element $P_{ij}$ represents the
probability of walking from vertex $i$ to vertex $j$, it satisfies

$P_{ij}\geq 0,\quad\sum_{j}P_{ij}=1.$ (5.1)

A stochastic matrix has many interesting properties, which are briefly
summarized in the supplementary materials. In particular, it can be used to
model a classical random walk, which can be characterized by the equation
$w=P^{k}v$, where the $i$th element of the initial state $v$ specifies the
probability of a walker being at vertex $i$ initially, and the $i$th element
of the final state $w$ gives the probability of the walker being at vertex $i$
after $k$ steps of random walks have been taken using $P$ as the transition
probability. The efficiency of the walk is often measured in terms of the
number of steps it takes to reach a certain vertex (hitting time).

For a symmetric $P$, which becomes a doubly stochastic Markov chain matrix,
and is what we consider later in this section, a more efficient type of walk,
called quantum walk Mackay et al. (2002); Venegas-Andraca (2012) can be
constructed by block encoding $T_{k}(P)$, where $T_{k}(t)=\cos(k\arccos(t))$
is the $k$th degree Chebyshev polynomial of the first kind. When such a block
encoding is applied to an initial state prepared as $\ket{v}\ket{0}$, it
yields

$w=\left(T_{k}(P)\ket{v}\right)\ket{0}+\ket{\ast}\ket{1},$ (5.2)

where $\ast$ denotes a vector that we do not care about. After measuring the
second register and obtaining $\ket{0}$, the first register contains
$T_{k}(P)\ket{v}$. This suggests that performing $k$ steps of a quantum walk
yields $T_{k}(P)\ket{v}$ instead of $P^{k}\ket{v}$. The consequence of such a
transformation will be discussed in the supplementary materials through a
specific application of a quantum walk.

Quantum walks have found many other applications in quantum algorithms Shenvi
et al. (2003); Paparo and M. (2012). In this section, we will present the
block encoding view of a quantum walk and examine quantum circuits for the
block encoding of $T_{k}(P)$, which is in turn expressed in terms of the block
encoding of $P$.

###  5.1 Direct block encoding of $P$ and $T_{k}(P)$

For an $s$-sparse $P$, we can use the techniques discussed in section 4 to
construct an efficient quantum circuit that block encodes $P/s$.

Once we have the block encoding for $P/s$, we can use the QET discussed in
section 3 to construct a quantum circuit for a block encoding of $T_{k}(P/s)$.
However, our ultimate goal for implementing a quantum walk is not to have a
block encoding of $T_{k}(P/s)$ but for $T_{k}(P)$ because $P/s$ is not a
stochastic matrix. To overcome this difficulty, we may express the $k$th
degree Chebyshev polynomial $T_{k}(t)$ in terms of $T_{j}(t/s)$ for
$j=0,1,...,k$, i.e.,

$T_{k}(t)=\tilde{T}_{k}(t^{\prime})=\sum_{j=0}^{k}\alpha_{j}T_{j}(t^{\prime}),$
(5.3)

where $t^{\prime}=t/s$ and $\alpha_{j}=0$ for odd (even) $j$ if $k$ is even
(odd).

For example, when $s=4$,

$T_{2}(t)=\tilde{T}_{2}(t^{\prime})=15+16T_{2}(t^{\prime}),\ \ \mbox{where}\ \
t^{\prime}=t/4.$ (5.4)

We then try to use the QET to construct a block encoding of
$\tilde{T}_{k}(t^{\prime})$. However, to use the QET, the magnitude of the
polynomial $\tilde{T}_{k}(t^{\prime})$ must be bounded by 1 within the
interval $[-1,1]$. Since the magnitude of $\tilde{T}_{k}(t^{\prime})$ can be
much larger than 1 at $t^{\prime}=\pm 1$, we need to scale
$\tilde{T}_{k}(t^{\prime})$ by $1/|\tilde{T}_{k}(1)|$ before using the QET.
For example, for $s=4$, $\tilde{T}_{2}(1)=31$. As a result, we need to divide
$\tilde{T}_{2}(t^{\prime})$ in (5.4) by 31 before applying the QET.
Consequently, we effectively construct a block encoding for $T_{k}(P)/\alpha$,
where $\alpha=\tilde{T}_{k}(1)$, instead of $T_{k}(P)$. This has the effect of
lowering the probability of successful measurement of $\ket{0}$ in (5.2) (when
$T_{k}(P)$ is replaced with $T_{k}(P)/\alpha$.)

Nonetheless, we can construct a quantum circuit for such a block encoding. For
$k=2$, it follows from the discussion in section 3 and fig. 3 that such a
circuit can be drawn as the one shown in fig. 11, where the phase angles

$\phi_{0}=1.17,\>\phi_{1}=0.8\>,\>\phi_{2}=1.17$

can be found numerically by using QSPPACK Dong et al. (2021) and $U_{P/s}$
denotes the block encoding of $P/s$.

$\ket{0}$$\ket{0^{m}}$$\ket{\psi}$$H$$e^{-i\phi_{0}Z}$$U_{P/4}$$e^{-i\phi_{1}Z}$$U^{\dagger}_{P/4}$$e^{-i\phi_{0}Z}$$H$AA
Figure 11: A quantum circuit for $T_{2}(P)/31$ for a sparse symmetric
stochastic matrix $P$ with at most $4$ nonzero matrix elements per column
using $U_{P/4}$ which is the block encoding for $P/4$.

###  5.2 An alternative block encoding scheme and its connection to a
Szegedy’s quantum walk

There is a way to block encode $P$ instead of $P/s$. Such a block encoding
scheme relies on using a different unitary oracle $O_{P}$ that carries out the
following mapping

$O_{P}\ket{0^{n}}\ket{j}=\sum_{k}\sqrt{P_{jk}}\ket{k}\ket{j}.$ (5.5)

Thanks to the stochasticity of $P$, the right hand side is already a
normalized vector, and no additional ancilla qubit is needed.

The following theorem describes the structure of the blocking encoding
constructed from a combination of $O_{P}$ and an $n$-qubit swap operator that
performs the following operation

$\operatorname{SWAP}\ket{i}\ket{j}=\ket{j}\ket{i},$ (5.6)

which swaps the value of the two registers in the computational basis, and can
be directly implemented using $n$ two-qubit SWAP gates.

######  Theorem 5.1.

If $P$ is a symmetric stochastic Markov chain matrix, and if there exists a
unitary operator $O_{P}$ that can be used to carry out the mapping defined in
Eq. (5.5), then

$U_{P}=O_{P}^{\dagger}\operatorname{SWAP}O_{P}$ (5.7)

is a Hermitian block encoding of $P$, where the swap operator
$\operatorname{SWAP}$ is defined by Eq. (5.7).

###### Proof.

Clearly $U_{P}$ is unitary and Hermitian. Now we compute as before

$\ket{0^{n}}\ket{j}\xrightarrow{O_{P}}\sum_{k}\sqrt{P_{jk}}\ket{k}\ket{j}\xrightarrow{\operatorname{SWAP}}\sum_{k}\sqrt{P_{jk}}\ket{j}\ket{k}.$
(5.8)

Meanwhile

$\ket{0^{n}}\ket{i}\xrightarrow{O_{P}}\sum_{k^{\prime}}\sqrt{P_{ik^{\prime}}}\ket{k^{\prime}}\ket{i}.$
(5.9)

The inner product of (5.8) and (5.9) yields (using $P_{ij}=P_{ji}$)

$\bra{0^{n}}\bra{i}U_{P}\ket{0^{n}}\ket{j}=\sum_{k,k^{\prime}}\sqrt{P_{ik^{\prime}}P_{jk}}\delta_{j,k^{\prime}}\delta_{i,k}=\sqrt{P_{ij}P_{ji}}=P_{ij}.$
(5.10)

∎

Note the symmetry requirement for $P$ in the above theorem is not essential.
When $P\neq P^{T}$, we can work with the discriminant matrix defined in the
supplementary materials. To simplify notation, we assume $P$ is symmetric
below. We should also note that in general the block encoding of a Hermitian
matrix $A$ is not necessarily Hermitian. theorem 5.1 gives a Hermitian block
encoding of a Hermitian $P$, which is important for performing an efficient
quantum walk. A more general approach of constructing a Hermitian block
encoding of a Hermitian matrix $A$ is discussed in the supplementary
materials. However, the computational advantage of the Hermitian block
encoding over a general block encoding of the same Hermitian matrix is still
unclear at this stage.

We now discuss how to construct an efficient circuit for $O_{P}$ using the
banded circulant matrix (4.13) as an example, where we assume
$\alpha+\beta+\gamma=1$ for the matrix to be stochastic and $\beta=\gamma$.
The construction of a block-encoding circuit can be done in two steps. In the
first step, we construct a unitary $K$ that performs the following mapping

$K\ket{0^{n}}=(\sqrt{\alpha}\>\sqrt{\beta}\>0\>\cdots\>0\>\sqrt{\gamma})^{T}.$
(5.11)

The first column of $K$ has to encode the square root of the first column of
the circulant matrix. It is generally possible to construct a circuit for
performing such a unitary transformation using fully-controlled quantum Givens
rotations that zero out elements in the vector in Gray code ordering
Vartiainen et al. (2004). Our approach is similar, but exploits the sparsity
of (5.11) to further reduce the gate complexity to $\mathcal{O}(n)$ for this
special case. The circuit for $K$, shown in fig. 12, is best explained in
reverse order by considering the action of $K^{\dagger}$. The inverse
operation for $K^{\dagger}$ starts with a sequence of multi-controlled NOT
gates that permute the non-zero element in the $N-1$st (last) row to row 3. We
can now zero out $\sqrt{\gamma}$ in row 3 by applying the rotation
$R_{y}(\theta_{2})$ with $\theta_{2}=-\arctan{\sqrt{\frac{\gamma}{\beta}}}$ to
rows 1 and 3 of resulting state. Finally, we can zero out the element
$\sqrt{\beta+\gamma}$ in row 1 of the resulting state against $\sqrt{\alpha}$
in row 0 with the rotation $R_{y}(\theta_{1})$ where
$\theta_{1}=-\arctan{\sqrt{\frac{\beta+\gamma}{\alpha}}}$. To obtain a circuit
for $K$, we reverse the order of operations listed above and negate the signs
on the rotation angles as shown in Figure 12.

$\ket{0}$$\ket{0}$⋮$\ket{0}$$\ket{0}$$\ket{0}$$R_{y}(-\theta_{1})$$R_{y}(-\theta_{2})$
Figure 12: A quantum circuit for the state preparation unitary $K$ given in
(5.11).

In the second step, we use the fact that $Pe_{j}=L_{n}^{j-1}Pe_{0}$, where
$e_{j}$ is the $j$th column of the identity matrix, to construct a controlled
shift (adder) circuit to map $\ket{Pe_{0}}\ket{j}$ to $\ket{Pe_{j}}\ket{j}$.
We show in the supplementary materials how such a controlled $L$-shift circuit
is derived. Combining these two steps as well as the SWAP operator, we can
represent the quantum circuit for the Hermitian block encoding of $P$ by the
diagram shown in fig. 13.

$\ket{0}$$\ket{0}$$\ket{0}$$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$K$$L$$L$$R$$R$$K^{\dagger}$AAA
Figure 13: The complete quantum circuit for a Hermitian block encoding of the
$8\times 8$ Hermitian banded circulant matrix $P$ defined by (4.13) with
$\alpha>0$, $\gamma=\beta>0$ and $\alpha+2\beta=1.0$.

Once a quantum circuit for a symmetric block encoding of $P$ is available, we
can then use QET to construct a circuit that block encodes $T_{k}(P)$ for a
$k$th degree of Chebyshev polynomial. It can be easily shown that the phase
angles required in the QET circuit are

$\varphi_{0}=\pi/2,\>\varphi_{1}=\cdots=\varphi_{k-1}=\pi/2\>\mbox{and}\>\varphi_{k}=0.$
(5.12)

It follows from the discussion in section 3 that the circuit for the block
encoding of $T_{k}(P)$ has a structure shown in fig. 14.

$\ket{0}$$\ket{0^{n}}$$\ket{0^{n}}$$e^{i\frac{\pi}{2}Z}$$U_{P}$$e^{i\frac{\pi}{2}Z}$$U_{P}$AA
Figure 14: The overall structure of a quantum circuit for the block encoding
of $T_{2}(P)$.

It the following, we draw the connection between the block encoding view of a
quantum walk with early studies of quantum walks that are often written as the
product of a swap operator and a reflector. Such a quantum walk are sometimes
referred to as the Szegedy quantum walk Szegedy (2004). We should note that
there are alternative formulations of quantum walks and efficient methods for
constructing quantum circuits for these formulations Lemieux et al. (2020).

We begin by noticing that the first two multi-qubit controlled NOT gates and
the single qubit phase gate labelled by $e^{i\frac{\pi}{2}Z}$ can be viewed as
a way to implement the $e^{i\frac{\pi}{2}Z_{\Pi}}$ operator, where $Z_{\Pi}$
is a reflector defined as

$Z_{\Pi}\equiv 2\Pi-I,$ (5.13)

with $\Pi\equiv\ket{0^{n}}\bra{0^{n}}\otimes I_{N}$. In general, such a
circuit block is used to implement $e^{i\phi Z_{\Pi}}$, which appears in the
block encoding of a matrix polynomial, for an arbitrary angle $\phi$. However,
when $\phi=\pi/2$, we can use the identity
$e^{i\frac{\pi}{2}Z_{\Pi}}=-iZ_{\Pi}$ to simplify the block encoding circuit.
This simplification allows us to rewrite the block encoding of $T_{k}(P)$ as
(up to an irrelevant global phase factor $(-i)^{k}$)

$U_{T_{k}(P)}=\left(U_{P}Z_{\Pi}\right)^{k}.$ (5.14)

Substituting the symmetric block encoding $U_{P}$ defined in (5.7) into (5.14)
and grouping $O_{P}^{\dagger}$, $Z_{\Pi}\otimes I$, $O_{P}$ and
$\operatorname{SWAP}$ together allows us to express $U_{T_{k}(P)}$ in terms of
repeated applications of

$\operatorname{SWAP}\cdot U_{R},$ (5.15)

where $U_{R}\equiv O_{P}\left(Z_{\Pi}\otimes I\right)O_{P}^{\dagger}$ is a
reflector. This indicates that the block encoding of $T_{k}(P)$ is equivalent
to performing $k$ steps of a Szegedy quantum walk, which is typically defined
as the product of a reflection and a swap operator. We will show this
equivalence more precisely in the supplementary materials.

It follows that constructing an efficient circuit for the Szegedy quantum walk
is equivalent to constructing an efficient circuit for the symmetric block
encoding of $P$ defined in (5.7). We should note that a method for
constructing efficient quantum circuits for a Szegedy quantum walk on
structured graphs was previously presented in Loke and Wang (2017). We now
show that this method is equivalent to the construction of the block encoding
circuit for $P$.

The method presented in Loke and Wang (2017) seeks a unitary transformation
$V$ in the form of $\sum_{i=0}^{N-1}V_{i}\otimes\ket{i}\bra{i}$ to diagonalize
$U_{R}$. If $V_{i}$’s can be found to satisfy $V_{i}\ket{\phi_{i}}=\ket{b}$
for a computational basis $\ket{b}$, then one can verify that

$V^{\dagger}U_{R}V=2\sum_{i=0}^{N-1}\Big{(}V_{i}^{\dagger}\ket{\phi_{i}}\bra{\phi_{i}}V_{i}\Big{)}\otimes\ket{i}\bra{i}=2(\ket{b}\bra{b}-I).$
(5.16)

If $\ket{b}$ is chosen to be $\ket{0^{n}}$, the right hand side of (5.16)
becomes the $Z_{\Pi}$ matrix appeared in (5.14).

The transformation $V$ defined in (5.16) is equivalent to the $O_{P}$
transformation defined by (5.5). Hence, constructing a circuit for $O_{P}$ is
equivalent to constructing a circuit for $V$. When this circuit is combined
with the circuit implementation of $Z_{\Pi}$, we obtain a quantum circuit for
the Szegedy quantum walk that is equivalent to the circuit presented in Loke
and Wang (2017).

##  6 Concluding remarks

Block encodings and quantum eigenvalue/singular value transformations provide
a powerful framework for solving large sparse linear algebra problems on
quantum computers. However, to make this approach practical, we need to
construct block encoding unitaries that can be easily decomposed into
efficient quantum circuits. Although the general strategies for constructing
such block encoding unitaries have been proposed in terms of oracles in the
past, not much effort has been developed to the explicit construction of
quantum circuits for realizing these block encodings.

Our work in this paper is focused on addressing this practical issue. In
particular, we discussed techniques for constructing an efficient quantum
circuit for the block encoding of an $s$-sparse matrix $A/s$ and gave some
specific examples. In general, the block encoding circuit consists of an
$O_{c}$ circuit block that encodes the nonzero structure of the matrix and an
$O_{A}$ circuit that encodes the numerical values of the nonzero matrix
elements. Without an efficient implementation of these oracles with
$\mathrm{poly}(n)$ gate complexity, it can be very difficult to achieve
exponential quantum advantage over classical algorithms Tang (2021); Gharibian
and Gall (2021). Through explicit examples, we show what is required to
construct these circuit blocks and that the construction of these circuit
blocks may not be completely independent of each other. In particular, the
$O_{A}$ circuit may be constructed to zero out certain matrix element to
maintain the desired sparsity structure.

For a general sparse matrix $A$, constructing an efficient block encoding of
$A/s$ can be non-trivial. In particular, it may be difficult to find an
efficient $O_{c}$ if the sparsity pattern of $A$ is somewhat arbitrary. In
some cases, a more general block encoding scheme that includes an additional
$O_{r}$ unitary that encodes the row sparsity separately from the column
sparsity may be needed.

The general construction procedure is not suitable for block encoding a sparse
symmetric stochastic matrix $P$ associated with a random walk on a graph when
such a block encoding is used to implement a quantum walk on the same graph.
For this type of matrices, an alternative construction procedure that yields a
symmetric block encoding circuit for $P$ instead of $P/s$ is desired. Such a
block encoding allows us to construct an efficient block encoding of a
Chebyshev polynomial of $P$, which is the unitary used in a quantum walk. We
showed that constructing a circuit for a block encoding of $T_{k}(P)$ is
equivalent to a previously developed technique for constructing an efficient
quantum circuit for Szegedy quantum walks on special graphs.

Throughout this paper, we assume that single qubit gates are available for an
arbitrary rotation matrix, and that multi-qubit controls are available to
carry out the required encoding schemes. No constraint has been placed on the
topology of qubits and their connections. These assumptions certainly do not
hold for existing quantum devices, and they are not expected to be valid for
at least early fault-tolerant quantum computers. When the quantum gates
available on these devices are restricted to a few elementary gates (such as
Hadamard and Pauli gates), additional decompositions and transformations are
required to express some of the gates (especially, the multi-qubit control
gates) used in the block encoding circuits described above in terms of
elementary gates. The circuit construction will also need to take the topology
and connection of qubits into consideration. We will pursue efficient ways to
construct this type of circuits in future works.

##  7 Appendix

###  7.1 Efficient circuits for powers of a shift operator

In section 4.2, we indicated that powers of a shift operator can be
implemented efficiently without repeating the circuit associated with the
shift operator. We will elaborate on this point a bit more in this section.

If we use $L_{n}$ to denote an $n$-qubit $L$-shift operator of dimension
$2^{n}\times 2^{n}$, then it can be shown that

$L_{n}^{2}=L_{n-1}\otimes I_{2},$ (7.1)

for $n>1$. As a result, the circuit for the $L_{n}^{2}$-shift operator can be
drawn, for example, as in fig. 15 for $n=3$. A similar decomposition holds for
$R_{n}^{2}$.

$0$$1$$2$$L_{3}^{2}$$0$$1$$2$$L_{2}$$=$ Figure 15: $L^{2}$-shift circuit

Using the binary representation of an integer

$j=[\mathtt{j}_{n-1}\cdots\mathtt{j}_{1}\mathtt{j}_{0}]=\mathtt{j}_{n-1}\cdot
2^{n-1}+\cdots+\mathtt{j}_{1}\cdot 2^{1}+\mathtt{j}_{0}\cdot 2^{0},$

for $j\in\mathbb{N}:0\leq j\leq 2^{n}-1$, where $\mathtt{j}_{k}\in\\{0,1\\}$
for $0\leq k\leq n-1$, we can rewrite $L^{j}$ as

$L_{n}^{j}=\left(L_{n}^{2^{n-1}}\right)^{\mathtt{j}_{n-1}}\cdot\left(L_{n}^{2^{n-2}}\right)^{\mathtt{j}_{n-2}}\cdots\left(L_{n}^{2^{0}}\right)^{\mathtt{j}_{0}}.$
(7.2)

Applying (7.1) recursively to $L_{n}^{2^{n-k}}$ yields

$L_{n}^{2^{n-k}}=L_{k}\otimes\underbrace{I_{2}\otimes\cdots\otimes
I_{2}}_{n-k}.$

Therefore, to apply $L_{n}^{j}$ to an input $\ket{\ell}$, we just need to
apply a sequence of controlled $L_{k}$ operations for $k=n,n-1,...,1$
successively to the leading $k$ qubits using $\ket{\mathtt{j}_{k}}$ as the
control for $L_{k}$ as shown, for example, in fig. 16 for $n=3$.

$\ket{\ell_{2}}$$\ket{\ell_{1}}$$\ket{\ell_{0}}$$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$L_{3}$$L_{2}$
Figure 16: A quantum circuit for $L_{3}^{j}$.

###  7.2 Hermitian block encoding of Hermitian sparse matrices

In general, the block encoding unitary of a real symmetric or complex
Hermitian matrix is not necessarily symmetric or Hermitian. This is clearly
the case for the block encodings constructed in sections 4.2 and 4.3. It is
also possible to obtain a Hermitian block encoding of a Hermitian matrix,
which can simplify certain theoretical treatments (e.g. quantum walks). We
will show how an efficient quantum circuit can be constructed for such a block
encoding. The following theorem lays out the basic structure of such a
circuit.

######  Theorem 7.1.

Suppose $A$ is a sparse Hermitian matrix of dimension $2^{n}$ with at most
$s=2^{m}$ non-zeros per column, with $m\leq n$. If a unitary $O_{C}$ satisfies

$O_{C}\ket{\ell}\ket{j}=\ket{c(j,\ell)}\ket{j},$ (7.3)

where $c(j,\ell)$ is the row index of the $\ell$th non-zero elements in the
$j$th column, and if there exists a unitary $O_{A}$ such that

$\left(I\otimes
O_{A}\right)\ket{0}\ket{0}\ket{i}\ket{j}=\ket{0}\left(\sqrt{A_{ij}}\ket{0}+\sqrt{1-|A_{ij}|}\ket{1}\right)\ket{i}\ket{j}.$
(7.4)

For $A_{ij}=\lvert A_{ij}\rvert e^{\imath\theta_{ij}},\theta_{ij}\in[0,2\pi)$,
the square root is uniquely defined as $\sqrt{A_{ij}}=\sqrt{\lvert
A_{ij}\rvert}e^{\imath\theta_{ij}/2}$. Then the unitary $U_{A}$ represented by
the circuit shown in fig. 17 is a Hermitian block encoding of $A$, where
$D_{s}$ is a diffusion operator defined as

${D_{s}\equiv I_{2}\otimes\cdots\otimes\underbrace{H\otimes H\otimes\cdots
H}_{m},}$

and $\operatorname{SWAP}$ is a swap operator that swaps the last two $n$-qubit
registers in fig. 17 respectively.

$\ket{0}$$\ket{0}$$\ket{0^{n}}$$\ket{j}$$D_{s}$$O_{A}$$O_{C}$$\mathrm{SWAP}$$O_{C}^{\dagger}$$O_{A}^{\dagger}$$D_{s}^{\dagger}$AAA
Figure 17: The general structure of a quantum circuit for a Hermitian block
encoding of an $s$-sparse Hermitian matrix $A$. The $S$ block represents a
SWAP operator that swaps the the last two $n$-qubit registers qubit-by-qubit.

###### Proof.

Our goal is to show that
$\bra{0}\bra{0}\bra{0^{n}}\bra{i}U_{A}\ket{0}\ket{0}\ket{0^{n}}\ket{j}=A_{ij}/s$.
In order to compute this inner product, we apply $D_{s},O_{A},O_{c}$ to
$\ket{0}\ket{0}\ket{0^{n}}\ket{j}$ successively as below

$\begin{split}\ket{0}\ket{0}\ket{0^{n}}\ket{j}\xrightarrow{D_{s}}&\frac{1}{\sqrt{s}}\sum_{\ell\in[s]}\ket{0}\ket{0}\ket{\ell}\ket{j}\\\
\xrightarrow{O_{A}}&\frac{1}{\sqrt{s}}\sum_{\ell\in[s]}\ket{0}\left(\sqrt{A_{c(j,\ell),j}}\ket{0}+\sqrt{1-\lvert
A_{c(j,\ell),j}\rvert}\ket{1}\right)\ket{\ell}\ket{j}\\\
\xrightarrow{O_{c}}&\frac{1}{\sqrt{s}}\sum_{\ell\in[s]}\ket{0}\left(\sqrt{A_{c(j,\ell),j}}\ket{0}+\sqrt{1-\lvert
A_{c(j,\ell),j}\rvert}\ket{1}\right)\ket{c(j,\ell)}\ket{j}.\end{split}$ (7.5)

After passing the SWAP gates, the state becomes

$\frac{1}{\sqrt{s}}\sum_{\ell\in[s]}\left(\sqrt{A_{c(j,\ell),j}}\ket{0}+\sqrt{1-\lvert
A_{c(j,\ell),j}\rvert}\ket{1}\right)\ket{0}\ket{j}\ket{c(j,\ell)}.$ (7.6)

We may similarly compute

$\begin{split}&\ket{0}\ket{0}\ket{0^{n}}\ket{0}\ket{i}\xrightarrow{D_{s}}\xrightarrow{O_{A}}\xrightarrow{O_{c}}\\\
&\frac{1}{\sqrt{s}}\sum_{\ell^{\prime}\in[s]}\ket{0}\left(\sqrt{A_{c(i,\ell^{\prime}),i}}\ket{0}+\sqrt{1-\lvert
A_{c(i,\ell^{\prime}),i}\rvert}\ket{1}\right)\ket{c(i,\ell^{\prime})}\ket{i}.\end{split}$
(7.7)

Finally, taking the inner product between (7.6) and (7.7) yields

$\begin{split}&\bra{0}\bra{0}\bra{0^{n}}\bra{i}U_{A}\ket{0}\ket{0}\ket{0^{n}}\ket{j}\\\
=&\frac{1}{s}\sum_{\ell,\ell^{\prime}\in[s]}\sqrt{A_{c(j,\ell),j}}\sqrt{A^{*}_{c(i,\ell^{\prime}),i}}\delta_{i,c(j,\ell)}\delta_{c(i,\ell^{\prime}),j}\\\
=&\frac{1}{s}\sqrt{A_{ij}A_{ji}^{*}}\sum_{\ell,\ell^{\prime}}\delta_{i,c(j,\ell)}\delta_{c(i,\ell^{\prime}),j}=\frac{1}{s}A_{ij}.\end{split}$
(7.8)

In this equality, we have used the fact that $A$ is Hermitian:
$A_{ij}=A_{ji}^{*}$, and there exists a unique $\ell$ such that $i=c(j,\ell)$,
as well as a unique $\ell^{\prime}$ such that $j=c(i,\ell^{\prime})$. ∎

We use the $8\times 8$ banded circulant matrix defined by (4.13) with
$0<\alpha,\beta<1$, $\beta=\gamma$ as an example to illustrate how to
construct an efficient quantum circuit for a Hermitian block encoding of a
Hermitian sparse matrix.

For this example, we define $c(j,\ell)$ to be used in the construction of the
$O_{C}$ circuit as

${c(j,\ell)=\mathrm{mod}(\ell+j-1,N),}$ (7.9)

to represent the row index of the $\ell$th non-zero matrix elements in the
$j$th column. It is important to note that the definition of $O_{C}$ in (7.3)
is different from the definition given in (4.2). In (4.2), the qubit register
that takes $\ket{j}$ as the input is changed and the register used to hold
$\ket{\ell}$ is simply used as a control and is not altered after the unitary
transformation. In (7.3), the register that holds $\ket{\ell}$ is changed
while $\ket{j}$ is unchanged. Therefore, we need to construct a circuit that
adds $j-1$ to $\ell$ using $\ket{j}$ as the control. The addition of $j$ to a
quantum state can be carried by applying $L^{j}$ to that state using the
efficient circuit presented in the previous section.

The construction of the $O_{A}$ circuit in this example is similar to the way
$O_{A}$ is constructed in section 4.2. We use rotations controlled by $\ell$
to place non-zero $\sqrt{A_{ij}}$ at appropriate locations in the principal
leading block of $U_{A}$. To be specific, we use the rotation $R(\theta_{1})$
with the angle $\theta_{1}=\arccos(\sqrt{\beta}-1)$ conditioned on $\ell=0$ to
place $\beta$ on the supdiagonal. We use the rotation $R(\theta_{2})$ with
$\theta_{2}=\arccos(\sqrt{\alpha})+\pi$ conditioned on $\ell=1$ to place
$\alpha$ on the diagonal, and the rotation $R(\theta_{3})$ with
$\theta_{3}=\arccos(\beta)+\pi$ to place $\beta$ on the subdiagonal.

The complete circuit for the Hermitian block encoding of $A$ is shown in fig.
18.

$\ket{0}$$\ket{0}$$\ket{0}$$\ket{0}$$\ket{0}$$\ket{j_{2}}$$\ket{j_{1}}$$\ket{j_{0}}$$H$$H$$R_{1}$$R_{2}$$R_{3}$$R$$L$$L$$\mathrm{SWAP}$$R$$R$$L$$R_{1}^{\dagger}$$R_{2}^{\dagger}$$R_{3}^{\dagger}$$H$$H$AAAAA
Figure 18: The complete quantum circuit for a Hermitian block encoding of the
$8\times 8$ Hermitian banded circulant matrix $A$ defined by (4.13). The SWAP
operator swaps the last two $n$-qubit registers qubit-by-qubit.

###  7.3 Additional results on quantum walks

In the following section, we provide additional materials that describe
properties of a random walk as well as an application that demonstrates the
higher (query) efficiency of a quantum walk compared to that of a classical
random walk from a block encoding point of view.

####  7.3.1 Properties a Markov chain matrix

Because the sum of all probabilities of transitions from the vertex $i$ to
other vertices must be 1 for all $i$, the vector $\left(1\>1\>\cdots
1\right)^{T}$ is a right eigenvector of the Markov chain stochastic matrix $P$
associated with the eigenvalue $1$. The corresponding left eigenvector $\pi$
is called a stationary state and satisifies

$\pi^{T}P=\pi,\quad\pi_{i}\geq 0,\quad\sum_{i}\pi_{i}=1.$ (7.10)

A Markov chain matrix $P$ is _irreducible_ if any state can be reached from
any other state in a finite number of steps of a random walk, i.e., the $j$th
element of $w=P^{k}e_{i}$ is nonzero for any $j$ and some finite $k$ where
$e_{i}$ is the $i$th column of the identity matrix. An irreducible Markov
chain is _aperiodic_ if there exists no integer greater than one that divides
the length of every directed cycle of the graph. A Markov chain is _ergodic_
if it is both irreducible and aperiodic. By the Perron–Frobenius Theorem, any
ergodic Markov chain $P$ has a unique stationary state $\pi$ in (7.10). A
Markov chain is _reversible_ if the following detailed balance condition is
satisfied

$\pi_{i}P_{ij}=\pi_{j}P_{ji}.$ (7.11)

For a nonsymmetric but reversible $P$, we can construct a quantum walk by
block encoding the _discriminant matrix_ $D$ associated with $P$. Such a
matrix is defined componentwise as

$D_{ij}=\sqrt{P_{ij}P_{ji}},$ (7.12)

which is real symmetric.

When $P$ is reversible, it can be shown that

$\ket{\pi}=\sum_{i}\sqrt{\pi_{i}}\ket{i}$ (7.13)

is a normalized eigenvector of the discrimant matrix $D$ defined by (7.12),
i.e., $\ket{\pi}$ satisfies

$D\ket{\pi}=\ket{\pi}.$ (7.14)

Furthermore, because $\pi_{i}>0$ for all $i$, we have

$D=\operatorname{diag}(\sqrt{\pi})P\operatorname{diag}(\sqrt{\pi})^{-1}.$
(7.15)

Therefore, for a reversible $P$, $P$ and $D$ share the same set of
eigenvalues, and the spectral properties of a nonsymmetric $P$ can be analyzed
by working with the symmetric $D$ matrix.

####  7.3.2 The equivalence of Szegedy quantum walk and block encoding of
$T_{k}(D)$

The Szegedy quantum walk is traditionally introduced as follows. Using the
following $O_{P}$ oracle and the multi-qubit $\operatorname{SWAP}$ gate, we
can define two set of quantum states

$\begin{split}\ket{\psi_{j}^{1}}&=O_{P}\ket{0^{n}}\ket{j}=\sum_{k}\sqrt{P_{jk}}\ket{k}\ket{j},\\\
\ket{\psi_{j}^{2}}&=\operatorname{SWAP}(O_{P}\ket{0^{n}}\ket{j})=\sum_{k}\sqrt{P_{jk}}\ket{j}\ket{k}.\end{split}$
(7.16)

These quantum states yield two projection operators

$\Pi_{l}=\sum_{j\in[N]}\ket{\psi_{j}^{l}}\bra{\psi_{j}^{l}},\quad l=1,2,$
(7.17)

from which we can define two $2n$-qubit reflection operators
$R_{\Pi_{l}}=2\Pi_{l}-I_{2n}$. Let us write down the reflection operators more
explicitly. Using the resolution of identity, we obtain

$R_{\Pi_{1}}=O_{P}((2\ket{0^{n}}\bra{0^{n}}-I)\otimes
I_{n})O_{P}^{{\dagger}}=O_{P}(Z_{\Pi}\otimes I_{n})O_{P}^{{\dagger}},$ (7.18)

where $Z_{\Pi}$ is as defined in (5.13). Similarly, we have

$R_{\Pi_{2}}=\operatorname{SWAP}O_{P}(Z_{\Pi}\otimes
I_{n})O_{P}^{{\dagger}}\operatorname{SWAP}.$ (7.19)

Then Szegedy’s quantum walk operator takes the form

$\mathcal{U}_{Z}=R_{\Pi_{2}}R_{\Pi_{1}},$ (7.20)

which is a rotation operator that resembles the one that appears in the
Grover’s algorithm. Note that

$\mathcal{U}_{Z}=\operatorname{SWAP}O_{P}(Z_{\Pi}\otimes
I_{n})O_{P}^{{\dagger}}\operatorname{SWAP}O_{P}(Z_{\Pi}\otimes
I_{n})O_{P}^{{\dagger}},$ (7.21)

so $O^{{\dagger}}_{P}\mathcal{U}_{Z}(O^{{\dagger}}_{P})^{-1}$ is the same as a
block encoding of $T_{2}(D)$ using qubitization up to a matrix similarity
transformation. More generally, $k$-steps of Szegedy’s quantum walk given by
$\mathcal{U}_{Z}^{k}$ is equivalent to a block encoding of $T_{2k}(D)$.

####  7.3.3 Quantum walk efficiency in detecting a marked vertex

In this section, we provide a brief explanation of the advantage of a quantum
walk over a classical random walk from a block encoding point of view, i.e.,
why it is of interest to block encode $T_{k}(D)$ and perform the corresponding
unitary transformation (5.2) on a quantum computer rather than simply applying
$P^{k}$ to an initial vector of probability distributions on a classical
computer.

The direct consequence of applying $T_{k}(P)$ in a quantum walk (instead of
$P^{k}$ in a classical random walk) to $v$ can be analyzed as follows. Since
an eigenvalue $\lambda$ of $P$ is between $-1$ and $1$, we can reparameterize
it as $\lambda=\cos\theta$. Clearly, the corresponding eigenvalue of $P^{k}$
is $\cos^{k}\theta$, and the corresponding eigenvalue of $T_{k}(P)$ is
$\cos(k\theta)$. For small $\theta$, it follows from the Taylor expansion of
$\cos^{k}\theta$ and $\cos\hat{k}\theta$ that

$\displaystyle\cos^{k}\theta$ $\displaystyle=$ $\displaystyle
1-\frac{k\theta^{2}}{2}+O(k^{2}\theta^{4}),$ (7.22)
$\displaystyle\cos\hat{k}\theta$ $\displaystyle=$ $\displaystyle
1-\frac{\hat{k}^{2}\theta^{2}}{2}+O(\hat{k}^{4}\theta^{4}),$ (7.23)

for integers $k$ and $\hat{k}$.

We can readily see that the Taylor expansions of these functions agree up to
the second order term when $\hat{k}=\sqrt{k}$. This observation suggests that,
for a reversible random walk, the second largest eigenvalue of
$T_{\hat{k}}(P)$ can reach that of $P^{k}$ when $\hat{k}=O(\sqrt{k})$. Since
properties of a random walk is often determined by the gap between the largest
eigenvalue and the second largest eigenvalue, this observation highlights the
fundamental reason why a quantum walk can be asymptotically much faster than a
classical random walk.

To demonstrate how a quantum walk can be used to solve a practical problem,
let us examine the following example. Our goal is to detect the presence of a
marked vertex in a graph $G=(V,E)$. Our assumption is that we do not know a
priori whether such a marked vertex exists. Nor do we know the location of
this vertex if it indeed exists. What we are given are some tools we can use
to find out the presence of the marked vertex and its position if it is
present.

In the classical setting, the tool we are given is a random walk transition
probability matrix $P$ (constructed by someone who knows the answer). We are
allowed to apply $P$ to a vector and check the result (but not allowed to look
at $P$ itself). The vector we will apply $P$ to is prepared as $v=e/N$, where
$e=(1,\ldots,1)^{T}$. It describes an initial uniform probability of being at
any vertex. We examine the probability of being at each vertex after
performing several steps of the random walk, i.e., we examine elements of the
vector $w=P^{k}v$. If $G$ contains a marked vertex, the element of $w$
associated with such vertex will have a much higher magnitude. The position of
this element informs us the position of the marked vertex.

To clearly demonstrate the advantage of performing a quantum walk, we choose
$G$ to be a complete graph, even though the efficiency of a quantum walk holds
for a general graph. If no marked vertex is present in $G$, the matrix $P$ we
are given is

$P=\frac{1}{N}ee^{T},\quad e=(1,\ldots,1)^{T}.$ (7.24)

Otherwise, if a marked vertex is present, and if, without loss of generality,
the marked vertex is the $0$-th vertex (which we do not know in advance), the
matrix $P$ we are given is

$P=\begin{pmatrix}1&0\\\
\frac{1}{N}\widetilde{e}&\frac{1}{N}\widetilde{e}\widetilde{e}^{T}\end{pmatrix},$
(7.25)

where $\widetilde{e}$ is a vector of all ones of length $N-1$.

Clearly, applying the $P$ matrix defined by (7.24) to $v$ does not change $v$.
The output from such a random walk remains the same, i.e., the probability of
being at each vertex remains at $1/N$.

However, if we are given the $P$ matrix defined by (7.25), one can show that
$w=P^{k}v$ converges to the eigenvector $\widetilde{\pi}=(1,0,\ldots,0)^{T}$
associated with the largest eigenvalue 1 of $P$ when $k=\mathcal{O}(N)$.
Hence, after performing $\mathcal{O}(N)$ steps of the random walk using this
$P$, we can conclude, with high confidence, that there is a marked vertex and
it is the $0$th vertex since the 0th element of $w$ is nearly 1.

In the quantum setting, the tool we are given is different. Instead of the $P$
matrix, we are given the block encoding of the discriminant matrix $D$
associated with $P$ denoted by $U_{D}$. Again, we are allowed to apply
$U_{D}^{k}$ to a carefully prepared quantum state $\ket{\psi_{0}}$ to perform
a quantum walk (but not allowed to look at $U_{D}$ itself). The prepared
initial quantum state is

$\ket{\psi_{0}}=\ket{0^{n}}(H^{\otimes n}\ket{0^{n}}).$ (7.26)

To detect the presence of a marked vertex, which is equivalent to determining
whether the quantum walk operator is the block encoding of the discriminant
matrix associated with the $P$ matrix defined in (7.24) or (7.25), we measure
the first $n$ qubits, and evaluate the success probability of measuring the
$\ket{0^{n}}$ state. This probability should be

$p(\ket{0^{n}})=\lVert(\ket{0^{n}}\bra{0^{n}}\otimes
I_{n})U_{D}^{k}\ket{\psi_{0}}\rVert^{2}.$ (7.27)

Then, if $U_{D}$ were the block encoding of $P$ (which is the same as the
corresponding discriminant matrix $D$ when $P=P^{T}$),
$U_{D}\ket{\psi_{0}}=\ket{\psi_{0}}$. As a result, the probability of
measuring $\ket{0^{n}}$ is $p(\ket{0^{n}})=1$, regardless how many steps of
the quantum walk are taken.

On the other hand, if $U_{D}$ results from the block encoding of the
discriminant matrix $D$ associated with the $P$ matrix defined in (7.25),
which has the form

$D=\begin{pmatrix}1&0\\\
0&\frac{1}{N}\widetilde{e}\widetilde{e}^{T}\end{pmatrix},$ (7.28)

the success probability of measuring $\ket{0^{n}}$ can be much less than 1.

To see this, we recognize that the matrix $D$ defined in (7.28) has two
nonzero eigenvalues $1$ and $(N-1)/N=1-\delta$, with the corresponding
eigenvectors $\ket{\widetilde{\pi}}=(1,0,...,0)^{T}$ and
$\ket{\widetilde{v}}=\frac{1}{\sqrt{N-1}}(0,1,1\ldots,1)^{T}$, respectively.
Because

$\ket{\psi_{0}}=\frac{1}{\sqrt{N}}\ket{0^{n}}\ket{\widetilde{\pi}}+\sqrt{\frac{N-1}{N}}\ket{0^{n}}\ket{\widetilde{v}},$
(7.29)

it follows from the fact that $U_{D}^{k}$ block encodes $T_{k}(D)$ that

$U_{D}^{k}\ket{\psi_{0}}=\frac{1}{\sqrt{N}}\ket{0^{n}}T_{k}(1)\ket{\widetilde{\pi}}+\sqrt{\frac{N-1}{N}}\ket{0^{n}}T_{k}(1-\delta)\ket{\widetilde{v}}+\ket{\perp},$
(7.30)

where $\ket{\perp}$ is an unnormalized state satisfying
$(\ket{0^{n}}\bra{0^{n}})\otimes I_{n}\ket{\perp}=0$. Since $T_{k}(1)=1$ for
all $k$, we have

$p(0^{n})=\frac{1}{N}+\left(1-\frac{1}{N}\right)T^{2}_{k}(1-\delta).$ (7.31)

Using the fact that $T_{k}(1-\delta)=\cos(k\arccos(1-\delta))$, we can show
that $T_{k}(1-\delta)\approx 0$ when $k$ satisfies

$k\approx\frac{\pi}{2\arccos(1-\delta)}\approx\frac{\pi}{2\sqrt{2\delta}}=\frac{\pi\sqrt{N}}{2\sqrt{2}}.$
(7.32)

Therefore, after taking $k=\lceil\frac{\pi\sqrt{N}}{2\sqrt{2}}\rceil$ steps of
the quantum walk, the probability of successfully measuring $\ket{0^{n}}$
drops down to $1/N$, which is significantly lower than $1$. This will allow us
to declare, with high confidence, the presence of a marked vertex in the graph
in $\mathcal{O}(\sqrt{N})$ steps of a quantum walk, which is a significant
(quadratic) speed up compared to $\mathcal{O}(N)$ steps of a random walk
required in the classical setting for large $N$.

We simulate this experiment for $n=6$ qubits in QCLAB. The script to reproduce
this simulation is made available on
https://github.com/QuantumComputingLab/qclab. We first generate quantum
circuits that block encode the discriminant matrix for (7.24) and (7.25).
These circuits are given in Figure 19.

(a) $U_{D}$ for (7.24) (b) $U_{D}$ for (7.25)

Figure 19: Quantum circuits for block encoding of (7.24) and (7.25).

Starting from the state (7.26), we repeat both circuits for $k$ steps and
measure the success probability (7.27). The results of this simulation are
shown in Figure 20. We observe that it is sufficient to use a very small $k$
to distinguish the two states, and the two states are maximally
distinguishable for $k_{opt}$ given by (7.32) as indicated by the dotted line.

$0$$5$$10$$15$$20$$25$$30$$0$$0.2$$0.4$$0.6$$0.8$$1$$k$Success
probability$p(\ket{0^{n}})$Detecting a marked vertex
($n=6$)DDt$\text{k}_{\text{opt}}$ Figure 20: Simulation results for detecting
the marked vertex.

## References

  * Low and Chuang [2017] Guang Hao Low and Isaac L. Chuang.  Optimal hamiltonian simulation by quantum signal processing.  _Phys. Rev. Lett._ , 118:010501, 2017.
  * Low and Chuang [2019] Guang Hao Low and Isaac L Chuang.  Hamiltonian simulation by qubitization.  _Quantum_ , 3:163, 2019.
  * Gilyén et al. [2019] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics.  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , pages 193–204, 2019.
  * Lin and Tong [2020a] Lin Lin and Yu Tong.  Optimal quantum eigenstate filtering with application to solving quantum linear systems.  _Quantum_ , 4:361, 2020a.
  * Lin and Tong [2020b] Lin Lin and Yu Tong.  Near-optimal ground state preparation.  _Quantum_ , 4:372, 2020b.
  * Martyn et al. [2021] John M Martyn, Zane M Rossi, Andrew K Tan, and Isaac L Chuang.  Grand unification of quantum algorithms.  _PRX Quantum_ , 2(4):040203, 2021.
  * Berry et al. [2015] Dominic W. Berry, Andrew M. Childs, and Robin Kothari.  Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters.  _Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS_ , 2015-Decem:792–809, 2015.  doi:10.1109/FOCS.2015.54.
  * Childs et al. [2017] Andrew M. Childs, Robin Kothari, and Rolando D. Somma.  Quantum algorithm for systems of linear equations with exponentially improved dependence on precision.  _SIAM J. Comput._ , 46(6):1920–1950, 2017.  doi:10.1137/16M1087072.
  * Camps and Van Beeumen [2021] D. Camps and R. Van Beeumen.  QCLAB, 2021.  URL https://github.com/QuantumComputingLab/qclab.  Version 0.1.3.
  * Szegedy [2004] Mario Szegedy.  Quantum Speed-Up of Markov Chain Based Algorithms.  In _45th Annual IEEE Symposium on Foundations of Computer Science_ , pages 32–41, 2004.  doi:10.1109/FOCS.2004.53.
  * Childs [2010] Andrew M. Childs.  On the relationship between continuous- and discrete-time quantum walk.  _Comm. Math. Phys._ , 294(2):581–603, 2010.  doi:10.1007/s00220-009-0930-1.
  * Haah [2019] J. Haah.  Product decomposition of periodic functions in quantum signal processing.  _Quantum_ , 3:190, 2019.
  * Chao et al. [2020] Rui Chao, Dawei Ding, András Gilyén, Cupjin Huang, and Mario Szegedy.  Finding Angles for Quantum Signal Processing with Machine Precision.  2020\.
  * Dong et al. [2021] Yulong Dong, Xiang Meng, K Birgitta Whaley, and Lin Lin.  Efficient phase factor evaluation in quantum signal processing.  _Phys. Rev. A_ , 103:042419, 2021.
  * Ying [2022] Lexing Ying.  Stable factorization for phase factors of quantum signal processing.  _arXiv preprint arXiv:2202.02671_ , 2022.
  * Dong et al. [2022] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang.  Infinite quantum signal processing.  _arXiv:2209.10162_ , 2022.
  * Wang et al. [2022] Jiasu Wang, Yulong Dong, and Lin Lin.  On the energy landscape of symmetric quantum signal processing.  _Quantum_ , 6:850, 2022.
  * Camps and Van Beeumen [2022] Daan Camps and Roel Van Beeumen.  Fable: Fast approximate quantum circuits for block-encodings.  _arXiv preprint arXiv:2205.00081_ , 2022.
  * Möttönen et al. [2004] Mikko Möttönen, Juha J. Vartiainen, Ville Bergholm, and Martti M. Salomaa.  Quantum circuits for general multiqubit gates.  _Phys. Rev. Lett._ , 93:130502, Sep 2004.  doi:10.1103/PhysRevLett.93.130502.  URL https://link.aps.org/doi/10.1103/PhysRevLett.93.130502.
  * Rieffel and Polak [2011] Eleanor G Rieffel and Wolfgang H Polak.  _Quantum computing: A gentle introduction_.  MIT Press, 2011.
  * Mackay et al. [2002] T D Mackay, S D Bartlett, L T Stephenson, and B C Sanders.  Quantum walks in higher dimensions.  _Journal of Physics A: Mathematical and General_ , 35(12):2745–2753, 2002.  doi:10.1088/0305-4470/35/12/304.
  * Venegas-Andraca [2012] S.E. Venegas-Andraca.  Quantum walks: a comprehensive review.  _Quantum Inf Process_ , 11:1015–1106, 2012.
  * Shenvi et al. [2003] Neil Shenvi, Julia Kempe, and K. Birgitta Whaley.  Quantum random-walk search algorithm.  _Phys. Rev. A_ , 67:052307, 2003.  doi:10.1103/PhysRevA.67.052307.
  * Paparo and M. [2012] G. Paparo and Martin-Delgado M.  Google in a quantum network.  _Sci Rep_ , 2:444, 2012.
  * Vartiainen et al. [2004] Juha J Vartiainen, Mikko Mötiönen, and Martti M Salomaa.  Efficient decomposition of quantum gates.  _Phys. Rev. Lett._ , 92(17):1–4, 2004.  doi:10.1103/PhysRevLett.92.177902.
  * Lemieux et al. [2020] Jessica Lemieux, Bettina Heim, David Poulin, Krysta Svore, and Matthias Troyer.  Efficient Quantum Walk Circuits for Metropolis-Hastings Algorithm.  _Quantum_ , 4:287, June 2020.  ISSN 2521-327X.  doi:10.22331/q-2020-06-29-287.  URL https://doi.org/10.22331/q-2020-06-29-287.
  * Loke and Wang [2017] T Loke and J B Wang.  Efficient quantum circuits for Szegedy quantum walks.  _Ann. Physics_ , 382:64–84, 2017.  doi:10.1016/j.aop.2017.04.006.
  * Tang [2021] Ewin Tang.  Quantum principal component analysis only achieves an exponential speedup because of its state preparation assumptions.  _Phys. Rev. Lett._ , 127(6):060503, 2021.
  * Gharibian and Gall [2021] Sevag Gharibian and François Le Gall.  Dequantizing the quantum singular value transformation: Hardness and applications to quantum chemistry and the quantum pcp conjecture.  _arXiv preprint arXiv:2111.09079_ , 2021.