A (single) qubit corresponds to a state space \( \mathcal{H}\cong\mathbb{C}^2\) . We also define

Since the state space of the spin-\( \frac12\) system is also isomorphic to \( \mathbb{C}^2\) , this is also called the single spin system, where \( \ket{0},\ket{1}\) are referred to as the spin-up and spin-down state, respectively. A general state vector in \( \mathcal{H}\) takes the form

and the normalization condition implies \( \left\lvert a\right\rvert ^2+\left\lvert b\right\rvert ^2=1\) . So we may rewrite \( \ket{\psi}\) as

If we ignore the irrelevant global phase \( \gamma\) , the state is effectively

So we may identify each single qubit quantum state with a unique point on the unit three-dimensional sphere (called the Bloch sphere) as

For a single qubit, the Pauli matrices are

Together with the two-dimensional identity matrix, they form a basis of all linear operators on \( \mathbb{C}^2\) .

Let the Hamiltonian \( H\) be the Pauli-X gate. Then

Starting from an initial state \( \ket{\psi(0)}=\ket{0}\) , after time \( t=\pi/2\) , the state evolves into \( \ket{\psi(\pi/2)}=-\mathrm{i} \ket{1}\) , i.e., the \( \ket{1}\) state (up to a global phase factor).

Again let \( M=X\) . From the spectral decomposition of \( X\) :

where \( \ket{\pm}:=\frac{1}{\sqrt{2}}(\ket{0}\pm\ket{1}),   \lambda_{\pm}=\pm 1\) , we obtain the eigendecomposition

Consider a quantum state \( \ket{\psi}=\ket{0}=\frac{1}{\sqrt{2}}(\ket{+}+\ket{-})\) , then

Therefore the expectation value of the measurement is \( \braket{\psi|M|\psi}=0.\)

The state space is \( \mathcal{H}=(\mathbb{C}^2)^{\otimes 2}\cong \mathbb{C}^{4}\) . The standard basis is (row-major order, i.e., last index is the fastest changing one)

The Bell state (also called the EPR pair) is defined to be

which cannot be written as any product state \( \ket{a}\otimes\ket{b}\) ( 4).

There are many important quantum operators on the two-qubit quantum system. One of them is the CNOT gate, with matrix representation

In other words, when acting on the standard basis, we have

This can be compactly written as

Here \( a\oplus b=(a+b)\mod 2\) is the “exclusive or” (XOR) operation.

For a \( n\) -qubit quantum system, the Pauli operator acting on the \( i\) -th qubit is denoted by \( P_i\) (\( P=X,Y,Z\) ). For instance

If \( \rho_{AB}=\rho_1\otimes \rho_2\) , then

Let us verify that the CNOT gate does not violate the no-cloning theorem, i.e., it cannot be used to copy a superposition of classical bits \( \ket{x}=a\ket{0}+b\ket{1}\) . Direct calculation shows

In particular, if \( \ket{x}=\ket{+}\) , then CNOT creates a Bell state.

Consider the circuit

Here the double line denotes the classical control operation. The outcome is that qubit \( 0\) has probability \( 1/2\) of outputting \( 0\) , and the qubit \( 1\) is at state \( \ket{0}\) . Qubit \( 0\) also has probability \( 1/2\) of outputting \( 1\) , and the qubit \( 1\) is at state \( \ket{1}\) .

However, we may replace the classical control operation after the measurement by a quantum controlled \( X\) (which is CNOT), and measure the qubit \( 0\) afterwards:

It can be verified that the result is the same. Note that CNOT acts as the classical copying operation. So qubit \( 1\) really stores the classical information (i.e., in the computational basis) of qubit \( 0\) .

The procedure of deferring quantum measurements using CNOTs is general, and important. Consider the following circuit:

The probability of obtaining \( 0,1\) is \( 1/2\) , respectively. However, if we simply “defer” the measurement to the end by removing the intermediate measurement, we obtain

The result of the measurement is deterministically \( 0\) ! The correct way of deferring the intermediate quantum measurement is to introduce another qubit

Measuring the qubit \( 0\) , we obtain \( 0\) or \( 1\) w.p. \( 1/2\) , respectively. Hence when deferring quantum measurements, it is necessary to store the intermediate information in extra (ancilla) qubits, even if such information is not used afterwards.

Let \( A\) be the single qubit to be measured in the computational basis, and we are interested in the accuracy in estimating the success probability of obtaining \( 1\) , i.e., \( p\) . This can be realized as an expectation value with \( M_A=\ket{1}\bra{1}\) , and \( p=\operatorname{Tr}\) . Note that \( M_A^2=M_A\) , then

Hence to estimate \( p\) to additive error \( \epsilon\) , the number of samples needed satisfies

Note that if \( p\) is close to \( 0\) or \( 1\) , the number of samples needed is also very small: indeed, the outcome of the measurement becomes increasing deterministic in this case!

If we are interested in estimating \( p\) to multiplicative accuracy \( \epsilon\) , then the number of samples is

and the task becomes increasingly more difficult when \( p\) approaches \( 0\) .

Let \( f:\{0,1\}^n\to\{0,1\}\) be a boolean function, which can be queried via the following unitary

This is called a phase kickback, i.e., the value of \( f(x)\) is returned as a phase factor. The phase kickback is an important tool in many quantum algorithms, e.g. Grover’s algorithm. Note that 1) \( U_f\) can be applied to a superposition of states in the computational basis, and 2) Having query access to \( f(x)\) does not mean that we know everything about \( f(x)\) , e.g. finding the set \( \set{x|f(x)=0}\) can still be a difficult task.

When designing quantum algorithms, it is common that we are not interested in the behavior of the entire unitary matrix \( U_f\) , but only \( U_f\) applied to certain vectors. For instance, for a \( (n+1)\) -qubit state space, we are only interested in

This means that we have only defined the first block-column of \( U_f\) as (remember that the row-major order is used)

Here \( A,B\) are \( N\times N\) matrices, and \( *\) stands for an arbitrary \( N\times N\) matrix so that \( U_f\) is unitary. Of course in order to implement \( U_f\) into quantum gates, we still need to specify the content of \( *\) . However, at the conceptual level, the partially specified unitary (88) simplifies the design process of quantum oracles.

Prove that any unitary matrix \( U\in \mathbb{C}^{N\times N}\) can be written as \( U=e^{\mathrm{i} H}\) , where \( H\) is an Hermitian matrix.

Prove 26.

Write down the matrix representation of the SWAP gate, as well as the \( \sqrt{ \operatorname{SWAP} }\) and \( \sqrt{ \operatorname{iSWAP} }\) gates.

Prove that the Bell state 32 cannot be written as any product state \( \ket{a}\otimes\ket{b}\) .

Prove 39 holds for a general mixed state \( \rho\) .

Prove that an ensemble of admissible density operators is also a density operator.

Prove the no-deleting theorem in 55.

Work out the circuit for implementing 76 and 78.

Prove that if \( f:\{0,1\}^n\to\{0,1\}^n\) is a bijection, and we have access to the inverse mapping \( f^{-1}\) , then the mapping \( U_f:\ket{x}\mapsto \ket{f(x)}\) can be implemented on a quantum computer.

Prove 56 and 57.

For \( f(0)=f(1)=1\) (constant case), we can use \( U_f=I\otimes X\) . For \( f(0)=0,f(1)=1\) (balanced case), we can use \( U_f= \operatorname{CNOT} \) .

https://qiskit.org/textbook/ch-algorithms/grover.html

One common scenario is that the implementation of \( U_{\psi_0}\) requires \( m\) ancilla qubits (also called signal qubits), i.e.,

where \( \ket{\perp}\) is some orthogonal state satisfying

Therefore

This setting is special since the “good” state can be verified by measuring the ancilla qubits after applying \( U_{\psi_0}\) in 119, and post-select the outcome \( 0^m\) . In particular, the expected number of measurements needed to obtain \( \ket{\psi_{\mathrm{good}}}\) is \( 1/p_0\) .

In order to employ the AA procedure, we first note that the reflection operator can be simplified as

This is because \( \ket{\psi_{\mathrm{good}}}\) can be entirely identified by measuring the ancilla qubits. Meanwhile

Let \( G=R_{\psi_0}R_{\mathrm{good}}\) , and applying \( G^k\) to \( \ket{\psi_0}\) for some \( k=\mathcal{O}(1/\sqrt{p_0})\) times, we obtain a state that has \( \Omega(1)\) overlap with \( \ket{\psi_{\mathrm{good}}}\) . This achieves the desired quadratic speedup.

Assuming access to an oracle in 119, where \( p_0\) is large, we can easily dampen the amplitude to any number \( \alpha\le \sqrt{p_0}\) .

We introduce an additional signal qubit. Then 119 becomes

Define a single qubit rotation operation as

and we have

Here \( (\ket{0^{m+1}}\bra{0^{m+1}}\otimes I_n)\ket{\perp'}=0\) . We only need to choose \( \sqrt{p_0}\cos \theta=\alpha\) .

In Deutsch’s algorithm, demonstrate why not assuming access to an oracle \( V_f:\ket{x}\mapsto\ket{f(x)}\) .

For all possible mappings \( f:\{0,1\}\to\{0,1\}\) , draw the corresponding quantum circuit to implement \( U_f:\ket{x,0}\mapsto\ket{x,f(x)}\) .

Prove 109.

Draw the quantum circuit for 117.

Prove that when ancilla qubits are used, the complexity of the unstructured search problem is still \( \Omega(\sqrt{N})\) .

An application of the Hadamard test is called the swap test, which is used to estimate the overlap of two quantum states \( \left\lvert \braket{\varphi|\psi}\right\rvert \) . The quantum circuit for the swap test is

Note that this is exactly the Hadamard test with \( U\) being the \( n\) -qubit swap gate. Direct calculation shows that the probability of measuring the qubit \( 0\) to be in state \( \ket{0}\) is

In the swap test, the quantum states \( \ket{\varphi},\ket{\psi}\) can be black-box states, and in such a scenario obtaining an estimate to \( \left\lvert \braket{\varphi|\psi}\right\rvert \) is the best one can do. In order to retrieve the relative phase information and to obtain \( \braket{\varphi|\psi}\) , we need to have access to the unitary circuit preparing \( \ket{\varphi},\ket{\psi}\) , i.e.,

Then we have \( \braket{\varphi|\psi}=\braket{0^n|U_{\varphi}^{†}U_{\psi}|0^n}\) .

The Hadamard test can also be used to derive the simplest version of the phase estimate based on success probabilities. Apply the Hadamard test in 6 with \( U,\psi\) satisfying 144. Then the probability of measuring the qubit \( 0\) to be in state \( \ket{1}\) is

Therefore

In order to quantify the efficiency of the procedure, recall from 11 that if \( p(1)\) is far away from \( 0\) or \( 1\) , i.e., \( (2\varphi \mod 1)\) is far away from \( 0\) , in order to approximate \( p(1)\) (and hence \( \varphi\) ) to additive precision \( \epsilon\) , the number of samples needed is \( \mathcal{O}(1/\epsilon^2)\) .

Now assume \( \varphi\) is very close to \( 0\) and we would like to estimate \( \varphi\) to additive precision \( \epsilon\) . Note that

Then \( p(1)\) needs to be estimated to precision \( \mathcal{O}(\epsilon^2)\) , and again the number of samples needed is \( \mathcal{O}(1/\epsilon^2)\) . The case when \( \varphi\) is close to \( 1/2\) or \( 1\) is similar.

Note that the circuit in 6 cannot distinguish the sign of \( \varphi\) (or whether \( \varphi\ge 1/2\) when restricted to the interval \( [0,1)\) ). To this end we need 7, but replace \( \mathrm{S}^{†}\) by \( \mathrm{S}\) , so that the success probability of measuring \( 1\) in the computational basis is

This gives

Unlike the previous estimate, in order to correctly estimate the sign, we only require \( \mathcal{O}(1)\) accuracy, and run 7 for a constant number of times (unless \( \varphi\) is very close to \( 0\) or \( \pi\) ).

Here is a qiskit example of the simple phase estimation for

with \( \varphi=0.5+\frac{1}{2^d}\equiv 0.{10… 01}\) (d bits in total). In this example, \( d=4\) and the exact value is \( \varphi=0.5625\) .

Consider \( \varphi=0.\varphi_4\varphi_3\varphi_2\varphi_1\varphi_0=0.11111\) and \( d=5\) . Running Kitaev’s algorithm with \( j=0,1,2\) gives the following possible choices of \( \beta_j\) :

Start with \( j=2\) . We have only one choice of \( \beta_j\) , and can recover \( 0.\varphi_2\varphi_1\varphi_0=0.111\) . Then for \( j=1\) , we need to use 161 to decide \( \varphi_3\) . If we choose \( \beta_j=0.111\) , we have \( \varphi_3=1\) . But if we choose \( \beta_j=0.000\) , we still need to choose \( \varphi_3=1\) , since \( \left\lvert .011-0.000\right\rvert _{\bmod 1}=0.100=1/2>1/4\) , and \( \left\lvert .111-0.000\right\rvert _{\bmod 1}=0.001=1/8<1/4\) . Similar analysis shows that for \( j=0\) we have \( \varphi_4=1\) . This recovers \( \varphi\) exactly.

Let us modify Kitaev’s algorithm as follows: for each \( 2^j \varphi\) is determined to precision \( 1/8\) , and round the result to \( \beta_j\in\set{0.00,0.01,0.10,0.11}\) . Start from \( j=d-2\) , we estimate \( .\varphi_1\varphi_0\) exactly. Then for \( j=d-3,…,0\) , we assign

Now that the inequality \( <1/2\) above can be equivalently written as \( \le 1/4\) .

Let us run the algorithm above for \( \varphi=0.\varphi_4\varphi_3\varphi_2\varphi_1\varphi_0=0.1111\) and \( d=4\) . This gives:

Start with \( j=2\) . We have only one choice of \( \beta_j\) , and can recover \( 0.\varphi_1\varphi_0=0.11\) . Then for \( j=1\) , if we choose \( \beta_j=0.11\) , we have \( \varphi_2=1\) . But if we choose \( \beta_j=0.00\) , then \( \left\lvert .01-0.00\right\rvert _{\bmod 1}=0.0.01=1/4\) , and \( \left\lvert .11-0.000\right\rvert _{\bmod 1}=0.01=1/4\) . So the algorithm cannot distinguish the two possibilities and fails.

Consider the implementation of

Let

and \( R_j=R_z(\pi/2^{j-1})\) . In particular, \( R_1=Z\) . The quantum circuit is

https://qiskit.org/textbook/ch-algorithms/quantum-fourier-transform.html

When \( d=1\) , note that \( U^{†}=U^{†}_{\mathrm{FT}}=H\) , the QFT based QPE in 12 is exactly the Hadamard test in 6. Note that \( \varphi\) does not need to be exactly represented by a one bit number!

https://qiskit.org/textbook/ch-algorithms/quantum-phase-estimation.html

Write down the quantum circuit for the overlap estimate in 19.

For \( \varphi=0.111111\) , we run Kitaev’s algorithm to estimate its first \( 4\) bits. Check that the outcome satisfies 162. Note that \( 0.0000\) and \( 0.1111\) are both acceptable answers. Prove the validity of Kitaev’s algorithm in general in the sense of 162.

For a \( 3\) qubit system, explicitly construct the circuit for \( U_{\mathrm{FT}}\) and its inverse.

For a \( n\) -qubit system, write down the quantum circuit for the swap operation used in QFT.

Similar to the Hadamard test in 26, develop an algorithm to perform QPE using the circuit in 12 with only \( d=2\) , while the phase \( \varphi\) can be any number in \( [0,1/2)\) .

The Hamiltonian for the one dimensional transverse field Ising model (TFIM) with nearest neighbor interaction of length \( n\) is

The dimension of the Hamiltonian matrix \( H\) is \( 2^n\) .

For a fermionic system (such as electrons), the Hamiltonian can be expressed in terms of the creation and annihilation operators as

The creation and annihilation operators \( \hat{a}^{†}_i,\hat{a}_i\) can be converted into Pauli operators via e.g. the Jordan-Wigner transform as

Here \( X,Y,Z,I\) are single-qubit Pauli-matrices. The dimension of the Hamiltonian matrix \( \hat{H}\) is thus \( 2^n\) .

The number operator takes the form

For a given state \( \ket{\Psi}\) , the total number of particles is

The Hamiltonian \( H\) preserves the total number of particles \( N_e\) .

Consider the circuit for the Hadamard test in 6 to estimate \( \operatorname{Re}\braket{\psi|U|\psi}\) . Let the initial state \( \ket{\psi}\) be prepared by a unitary \( U_{\psi}\) , then the following combined circuit

maps \( \ket{0}\ket{0^n}\) to

and the goal is to estimate \( p_0\) . This also gives the implementation of the reflector \( R_{\psi_0}\) .

Note that \( R_{\mathrm{good}}\) can be implemented by simply reflecting against the signal qubit, i.e.,

Then we can run QPE to the Grover unitary \( G=R_{\psi_0}R_{\mathrm{good}}\) to estimate \( p(0)\) , and the circuit depth is \( \mathcal{O}(\epsilon^{-1})\) .

The Gershgorin circle theorem does not provide a meaningful bound of the condition number when \( \operatorname{Re} a>0\) and \( 1<\left\lvert \xi\right\rvert <2\) . This is a correct behavior. To see this, just consider \( a=1,b=0\) , and the solution should grow exponentially as \( x(T)=e^{T}\) . If \( \kappa(\mathcal{A})=\mathcal{O}\left((\Delta t) ^{-1}\right)\) holds and in particular is independent of the final \( T\) , then the norm of the solution can only grow polynomially in \( T\) , which is a contradiction. See 16 for an illustration. Note that when \( a=-1.0\) , \( \Delta t=0.1\) , the condition number is less than \( 20\) , which is smaller than the upper bound above, i.e., \( 3\times\frac{2}{\Delta t (-a)}=60\) .

Given query access to a function \( f:\{0,1\}^N \rightarrow \{0,1\}\) design a quantum algorithm that computes the size of its kernel, i.e.,, total number of \( x\) ’s that satisfy \( f(x)=1\) .

Consider the initial value problem of the linear differential equation  267.

1. Construct the linear system of equations

   \[ \mathbf{\mathcal{A}} \mathbf{x} = \mathbf{b} \]

   like 271 using the backward Euler method.
2. In the scalar case when \( A(t) \equiv a \in \mathbb{C}\) is a constant satisfying \( \operatorname{Re}(a) \leq 0\) , estimate the query complexity of the HHL algorithm applying to the linear system constructed in (1).

For the one dimensional transverse field Ising model (TFIM) with nearest neighbor interaction in 195, wince all Pauli-\( Z_i\) operators commute, we have

Each \( e^{\mathrm{i} t Z_i Z_{i+1}}\) is a rotation involving only the qubits \( i,j\) , and the splitting has no error. Similarly

and each \( e^{\mathrm{i} t g X_i}\) can be implemented independently without error.

Let \( H=-\Delta_ř+V(\mathbf{r})=H_1+H_2\) be the Hamiltonian of a particle in a potential field \( V(\mathbf{r})\) , where \( \mathbf{r}\in \Omega=[0,1]^d\) with periodic boundary conditions. After discretization using Fourier modes, \( e^{\mathrm{i} H_1t}\) can be efficiently performed by diagonalizing \( H_1\) in the Fourier space, and \( e^{\mathrm{i} H_2t}\) can be efficiently performed since \( V(\mathbf{r})\) is diagonal in the real space.

Consider the Hamiltonian simulation problem for \( H = H_1 + H_2 + H_3\) . Show that the first order Trotter formula

has a commutator type error bound.

Consider the time-dependent Hamiltonian simulation problem for the following controlled Hamiltonian

where \( a(t)\) and \( b(t)\) are smooth functions bounded together with all derivatives. We focus on the following Trotter type splitting, defined as

where the intervals \( [t_j, t_{j+1}]\) are equidistant and of length \( \Delta t\) on the interval \( [0, t]\) with \( t_n = t\) . Show that this method has first-order accuracy, but does not exhibit a commutator type error bound in general.

For any \( n\) -qubit matrix \( A\) with \( \left\lVert A\right\rVert _2\le 1\) , the singular value decomposition (SVD) of \( A\) is denoted by \( W\Sigma V^{†}\) , where all singular values in the diagonal matrix \( \Sigma\) belong to \( [0,1]\) . Then we may construct an \( (n+1)\) -qubit unitary matrix

which is a \( (1,1)\) -block-encoding of \( A\) .

In some scenarios, we may want to construct a pseudo-random non-unitary matrix on quantum computers. Note that it would be highly inefficient if we first generate a dense pseudo-random matrix \( A\) classically and then feed it into the quantum computer using e.g. quantum random-access memory (QRAM). Instead we would like to work with matrices that are inherently easy to generate on quantum computers. This inspires the random circuit based block encoding matrix (RACBEM) model [6]. Instead of first identifying \( A\) and then finding its block encoding \( U_A\) , we reverse this thought process: we first identify a unitary \( U_A\) that is easy to implement on a quantum computer, and then ask which matrix can be block encoded by \( U_A\) .

34 shows that in principle, any matrix \( A\) with \( \left\lVert A\right\rVert _2\le 1\) can be accessed via a \( (1,1,0)\) -block-encoding. In other words, \( A\) can be block encoded by an \( (n+1)\) -qubit random unitary \( U_A\) , and \( U_A\) can be constructed using only basic one-qubit unitaries and CNOT gates. The layout of the two-qubit operations can be designed to be compatible with the coupling map of the hardware. A cartoon is shown in 19, and an example is given in 20.

As a special case, let us consider the block encoding of a diagonal matrix. Since the row and column indices are the same, we may simplify the oracle 333 into

In the case when the oracle \( \widetilde{O}_A\) is used, we may assume accordingly

Let \( U_A=O_A\) . Direct calculation shows that for any \( i,j\in [N]\) ,

This proves that \( U_A\in\operatorname{BE}_{1,1}(A)\) , i.e., \( U_A\) is a \( (1,1)\) -block-encoding of the diagonal matrix \( A\) .

Construct a query oracle \( O_A\) similar to that in 336, when \( A_{ij}\in\mathbb{C}\) with \( \left\lvert A_{ij}\right\rvert < 1\) .

Let \( A\in\mathbb{C}^{N\times N}\) be a \( s\) -sparse matrix. Prove that \( \left\lVert A\right\rVert \le s \left\lVert A\right\rVert _{\max}\) . For every \( 1\le s \le N\) , provide an example that the equality can reached.

Construct an \( s\) -sparse matrix so that the oracle in 356 does not exist.

Let \( A\in\mathbb{C}^{N\times N}\) (\( N=2^n\) ) be a Hermitian matrix with entries on the complex unit circle \( A_{ij}=z_{ij}\) , \( |z_{ij}|=1\) .

1. Construct a \( 2n\) qubit block-diagonal unitary \( V\in\mathbb C^{N^2\times N^2}\) such that

   \[ V\ket{0}\ket{j}=\frac1{\sqrt N}\sum_{i\in[N]}\sqrt{\bar z_{ij}}\ket{i}\ket{j}, ~ j\in [N]. \]

   Here, block-diagonal means \( (\bra{x}\otimes I)V(\ket{y}\otimes I)=0^{N\times N}\) for \( x\ne y\) .
2. Draw a circuit which uses \( V\) to implement a block encoding \( U\) of \( A\) with \( n\) ancilla qubits . What is the prefactor \( \alpha\) for the block encoding?
3. Give an explicit expression for the entries of the block encoding \( U\) .

Let \( G=(V,E)\) be a complete, graph of \( N=2^n\) vertices. We would like to distinguish the following two scenarios:

1. All vertices are the same, and the random walk is given by the transition matrix

   \[ \begin{equation} P=\frac{1}{N} e e^{\top}, ~ e=(1,\ldots,1)^{\top}. \end{equation} \]

   (411)

2. There is one marked vertex. Without loss of generality we may assume this is the \( 0\) -th vertex (of course we do not have access to this information). In this case, the transition matrix is

   \[ \begin{equation} \widetilde{P}_{ij}=\left\{ \begin{array}{ll} \delta_{ij}, & i=0,\\ P_{ij}, & i>0. \end{array}\right. \end{equation} \]

   (412)

In other words, in the case (2), the random walk will stop at the marked index. The transition matrix can also be written in the block partitioned form as

Here \( \widetilde{e}\) is an all \( 1\) vector of length \( N-1\) .

For the random walk defined by \( P\) , the stationary state is \( \pi=\frac{1}{N}e\) , and the spectral gap is \( 1\) . For the random walk defined by \( \widetilde{P}\) , the stationary state is \( \widetilde{\pi}=(1,0,…,0)^{\top}\) , and the spectral gap of is \( \delta=N^{-1}\) . Starting from the uniform state \( \pi\) , the probability distribution after \( k\) steps of random walk is \( \pi^{\top}\widetilde{P}^{k}\) . This converges to the stationary state of \( \widetilde{P}\) , and hence reach the marked vertex after \( \mathcal{O}(N)\) steps of walks (exercise).

These properties are also inherited by the discriminant matrices, with \( D=P\) and

To distinguish the two cases, we are given a Szegedy quantum walk operator called \( O\) , which can be either \( O_Z\) or \( \widetilde{O}_Z\) , which is associated with \( D,\widetilde{D}\) , respectively. The initial state is

Our strategy is to measure the expectation

which can be obtained via Hadamard’s test.

Before determining the value of \( k\) , first notice that if \( O=O_Z\) , then \( O_{Z}\ket{\psi_0}=\ket{\psi_0}\) . Hence \( m_k=1\) for all values of \( k\) .

On the other hand, if \( O=\widetilde{O}_Z\) , we use the fact that \( \widetilde{D}\) only has two nonzero eigenvalues \( 1\) and \( (N-1)/N=1-\delta\) , with associated eigenvectors denoted by \( \ket{\widetilde{\pi}}\) and \( \ket{\widetilde{v}}=\frac{1}{\sqrt{N-1}}(0,1,1…,1)^{\top}\) , respectively. Furthermore,

Due to qubitization, we have

where \( \ket{\perp}\) is an unnormalized state satisfying \( (\ket{0^n}\bra{0^n})\otimes I_n \ket{\perp}=0\) . Then using \( T_k(1)=1\) for all \( k\) , we have

Use the fact that \( T_k(1-\delta)=\cos(k\arccos(1-\delta))\) , in order to have \( T_k(1-\delta)\approx 0\) , the smallest \( k\) satisfies

Therefore taking \( k=\lceil\frac{\pi\sqrt{N}}{2\sqrt{2}} \rceil\) , we have \( m_k\approx 1/N\) . Running Hadamard’s test to constant accuracy allows us to distinguish the two scenarios.

Let \( U_A,U_B\) be two \( n\) -qubit unitaries, and we would like to construct a block encoding of \( T=U_A+U_B\) .

There are two terms in total, so one ancilla qubit is needed. The prepare oracle needs to implement

so this is the Hadamard gate. The circuit is given by 27, which constructs \( W\in \operatorname{BE}_{\sqrt{2},1}(T)\) .

A special case is the linear combination of two block encoded matrices. Given two \( n\) -qubit matrices \( A,B\) , for simplicity let \( U_A\in\operatorname{BE}_{1,m}(A),U_B\in\operatorname{BE}_{1,m}(B)\) . We would like to construct a block encoding of \( T=A+B\) . The circuit is given by 28, which constructs \( W\in \operatorname{BE}_{\sqrt{2},1+m}(T)\) . This is also an example of a linear combination of non-unitary matrices.

Consider the following TFIM model with periodic boundary conditions (\( Z_{n}=Z_0\) ), and \( n=2^\mathfrak{n}\) ,

In order to use LCU, we need \( (\mathfrak{n}+1)\) ancilla qubits. The prepare oracle can be simply constructed from the Hadamard gate

and the select oracle implements

The corresponding \( W\in\operatorname{BE}_{\sqrt{2n},\mathfrak{n}+1}(\hat{H})\) .

Let us use the LCU lemma to construct the block encoding for an arbitrary matrix polynomial for a Hermitian matrix \( A\) in 8.1.

with \( \left\lVert \alpha\right\rVert _1=\sum_{k\in[K]} |\alpha_k|\) and we set \( K=2^{a}\) . For simplicity assume \( \alpha_k\ge 0\) .

We have constructed \( U_k:=(U_A Z_{\Pi})^k\) as the \( (1,m)\) -block-encoding of \( T_k(A)\) . From each \( U_k\) we can implement the select oracle

via multi-qubit controls. Also given the availability of the prepare oracle

we obtain a \( (\left\lVert \alpha\right\rVert _1,m+a)\) -block-encoding of \( f(A)\) .

The need of using \( a\) ancilla qubits, and even more importantly the need to implement the prepare and select oracles is undesirable. We will see later that the quantum signal processing (QSP) and quantum singular value transformation (QSVT) can drastically reduce both sources of difficulties.

Instead of block encoding, LCU can also utilize a different query model based on Hamiltonian simulation. Let \( A\) be an \( n\) -qubit Hermitian matrix. Consider \( f(x)\in\mathbb{R}\) given by its Fourier expansion (up to a normalization factor)

and we are interested in computing the matrix function via numerical quadrature

Here \( \mathcal{K}\) is a uniform grid discretizing the interval \( [-L,L]\) using \( \left\lvert \mathcal{K}\right\rvert =2^{\mathfrak{k}}\) grid points, and the grid spacing is \( \Delta k = 2L/\left\lvert \mathcal{K}\right\rvert \) . The prepare oracle is given by the coefficients \( c_k=\Delta k \hat{f}(k)\) , and the corresponding subnormalization factor is

The select oracle is

This can be efficiently implemented using the controlled matrix powers as in 11, where the basic unit is the short time Hamiltonian simulation \( e^{\mathrm{i} \Delta k A}\) . This can be used to block encode a large class of matrix functions.

In order to block encode the Chebyshev polynomial, we have \( \phi_j=0,j=0,…,d\) . This gives \( \widetilde{\phi}_0=0\) , \( \widetilde{\phi}_j=\pi/2,j=1,…,d\) , and

According to 496, an equivalent symmetric choice for block encoding \( T_d(x)\) is

Let \( A,B\) be two \( n\) -qubit matrices. Construct a circuit to block encode \( C=A+B\) with \( U_A\in\operatorname{BE}_{\alpha_A,m}(A),U_B\in\operatorname{BE}_{\alpha_B,m}(B)\) .

Use LCU to construct a block encoding of the TFIM model with periodic boundary conditions in 195, with \( g\ne 1\) .

Prove 10.

Let \( A\) be an \( n\) -qubit Hermitian matrix. Write down the circuit for \( U_{P_{\operatorname{Re}}(A)}\in\operatorname{BE}_{1,m+1}(P_{\operatorname{Re}}(A))\) with a block encoding \( U_A\in\operatorname{BE}_{1,m}(A)\) , where \( P\) is characterized by the phase sequence \( \widetilde{\Phi}\) specified in 3.

Write down the circuit for LCU of Hamiltonian simulation.

Using QET to prepare the Gibbs state.

Consider a quantum circuit consisting of two registers denoted by \( a\) and \( s\) . Suppose we have a block encoding \( V\) of \( A\) : \( A=(\bra{0}_a\otimes I_s)V(\ket{0}_a\otimes I_s)\) . Let \( W=-V(\mathrm{REF}\otimes I_s)V^{\dagger}(\mathrm{REF}\otimes I_s)V\) , where \( \mathrm{REF}=I_a-2\ket{0}_a\bra{0}_a\) . (1) Within the framework of QSVT, what is the polynomial associated with the singular value transformation implemented by \( W\) ? (2) Suppose \( A=U/2\) for some unitary \( U\) . What is \( (\bra{0}_a\otimes I_s)W(\ket{0}_a\otimes I_s)\) ? (3) Explain the construction of \( W\) in terms of a singular value transformation \( f^{\diamond}(A)\) with \( f(x)=3x-4x^3\) . Draw the picture of \( f(x)\) and mark its values at \( x=0,\frac12,1\) .

Given access to a unitary \( U=e^{\mathrm{i} H}\) where \( \left\lVert H\right\rVert \le \pi/2\) . Use QSVT to design a quantum algorithm to approximately implement a block encoding of \( H\) , using controlled \( U\) and its inverses, as well as elementary quantum gates.