Quantum Phase Processing and its Applications in Estimating Phase and Entropies
Youle Wang
Institute for Quantum Computing, Baidu Research, Beijing 100193, China
Lei Zhang
Institute for Quantum Computing, Baidu Research, Beijing 100193, China
Thrust of Artificial Intelligence, Information Hub, Hong Kong University of Science and Technology (Guangzhou), Nansha, China
Zhan Yu
Institute for Quantum Computing, Baidu Research, Beijing 100193, China
Xin Wang
Institute for Quantum Computing, Baidu Research, Beijing 100193, China
Thrust of Artificial Intelligence, Information Hub, Hong Kong University of Science and Technology (Guangzhou), Nansha, China

Quantum computing can provide speedups in solving many problems as the evolution of a quantum system is described by a unitary operator in an exponentially large Hilbert space. Such unitary operators change the phase of their eigenstates and make quantum algorithms fundamentally different from their classical counterparts. Based on this unique principle of quantum computing, we develop a new algorithmic toolbox “quantum phase processing” that can directly apply arbitrary trigonometric transformations to eigenphases of a unitary operator. The quantum phase processing circuit is constructed simply, consisting of single-qubit rotations and controlled-unitaries, typically using only one ancilla qubit. Besides the capability of phase transformation, quantum phase processing in particular can extract the eigen-information of quantum systems by simply measuring the ancilla qubit, making it naturally compatible with indirect measurement. Quantum phase processing complements another powerful framework known as quantum singular value transformation and leads to more intuitive and efficient quantum algorithms for solving problems that are particularly phase-related. As a notable application, we propose a new quantum phase estimation algorithm without quantum Fourier transform, which requires the fewest ancilla qubits and matches the best performance so far. We further exploit the power of our method by investigating a plethora of applications in Hamiltonian simulation, entanglement spectroscopy and quantum entropies estimation, demonstrating improvements or optimality for almost all cases.

§ INTRODUCTION

Quantum computer provides a computational framework that can solve certain problems dramatically faster than classical machines. Quantum computing has been applied in many important tasks, including breaking encryption <cit.>, searching databases <cit.>, and simulating quantum evolution <cit.>.

Recent advances in quantum computing show that quantum singular value transformation (QSVT) introduced by <cit.> has led to a unified framework of the most known quantum algorithms <cit.>, including amplitude amplification <cit.>, quantum walks <cit.>, phase estimation <cit.>, and Hamiltonian simulations <cit.>. This framework can further be used to develop new quantum algorithms such as quantum entropies estimation <cit.>, fidelity estimation <cit.>, ground state preparation and ground energy estimation <cit.>.

The framework of QSVT was originated from a technique called quantum signal processing (QSP) <cit.>. By interleaving single-qubit signal unitaries and signal processing unitaries, QSP is able to implement a transformation of the signal in $\mathrm{SU}(2)$. There are several conventions of QSP varied by choosing different signal unitaries. In the construction of QSVT, <cit.> chose the signal unitary to be a reflection, then extended the signal unitary to a multi-qubit block encoding with the idea of qubitization <cit.>, which naturally leads to a polynomial transformation on the singular values of a block-encoded linear operator. The achievable polynomial transformations in QSVT are decided by reflection-based QSP, which has parity constraints or limitations, i.e., it can implement either an even polynomial or an odd one. Thus, to achieve a general transformation in QSVT, one might have to apply techniques such as linear-combination-of-unitaries <cit.> and amplitude amplification <cit.>, which take extra resources like ancilla qubits. Based on a convention of QSP using $z$-rotation as the signal unitary <cit.>, <cit.> developed an improved version of QSP that overcomes the parity limitation by adding an extra signal processing unitary, which could implement arbitrary complex trigonometric polynomials on one-qubit quantum systems.

For the signal unitary being a $z$-rotation, the corresponding trigonometric QSP naturally possesses the ability of processing phase, which indeed plays a central role in many quantum algorithms.  For example, the trick of phase kickback, where the phase of the target qubits is kicked back to the ancilla qubit, is intensively used almost everywhere in quantum computing. With the aid of controlled-unitary gates, many quantum algorithms utilize phase kickback to extract information of large unitary operations from phases of ancilla qubits, including the quantum phase estimation <cit.>, the swap test <cit.>, the Hadamard test <cit.>, and the one-clean-qubit model <cit.>.
Hence, it is of great interest and necessity to explore a generalized formalism that could interpret those phase-related quantum algorithms, which may further leads to new quantum algorithms and helps us better exploit the power of quantum signal processing. Consequently, it is natural to investigate and develop the multi-qubit extension of the improved trigonometric QSP in Ref. <cit.>.

In this work, we generalize the trigonometric QSP and propose a novel algorithmic toolbox called quantum phase processing (QPP). This toolbox has the ability to apply arbitrary trigonometric transformations to eigenphases of a unitary operator. Besides achieving the eigenphases transformation, QPP is also natively compatible with indirect measurements, enabling it to extract the eigen-information of quantum systems by measuring a single ancilla qubit. We further employ this toolbox to design efficient quantum algorithms for solving various problems. First, we use the idea of binary search to develop an efficient phase estimation algorithm without using quantum Fourier transform, requiring only one ancilla qubit. Such an algorithm can be applied to solve factoring problems and amplitude estimations.
Second, we show that QPP can be applied to simulate the time evolution under a Hamiltonian $H$ with access to a block encoding of $H$.
This method is in the same spirit as QSP-based Hamiltonian simulation <cit.>, which also matches the optimal query complexity.

Third, we propose a generic method to estimate quantum entropies, including the von Neumann entropy, the quantum relative entropy and the family of quantum Rényi entropies <cit.>. Despite the fact that QPP could be combined with amplitude estimation to achieve a quadratic speedup, we present algorithms that repeatedly measure the single ancilla qubit to estimate entropies rather than using amplitude estimation, demonstrating its compatibility with indirect measurements. Overall, QPP provides a powerful algorithmic toolbox to exploit quantum applications and delivers a new perspective on understanding and designing quantum algorithms.

The structure of this paper is presented as follows. Section <ref> introduces the structure and principal capability of quantum phase processing. In Section <ref>, we propose the novel quantum phase search algorithm, then we analyze the performance of the algorithm and make a brief comparison with previous works. Section <ref> interprets the method of Hamiltonian simulation in the QPP structure. In Section <ref>, we develop a generic approach for quantum entropies estimation and further showcase the methods of estimating von Neumann entropies, quantum relative entropies and quantum Rényi entropies, then we compare our algorithms with prior methods.  Proofs and further discussions of this work are left in the appendix.

§ QUANTUM PHASE PROCESSING

§.§ Quantum signal processing

We first review the concept of quantum signal processing (QSP). QSP was introduced by <cit.>, who showed how to transform a $2\times2$ signal unitary $R_x(x) = e^{ix\sigma_x}$ into a target unitary whose entries are some transformations of the signal $x$. The approach is to apply the signal unitary $R_x(x)$ interleaved with some signal processing unitaries $R_z(\phi)$, i.e.

\begin{equation}
R_z(\phi_0) R_x(x) R_z(\phi_1) R_x(x) \cdots R_x(x) R_z(\phi_k).
\end{equation}

<cit.> modified the signal unitary as a reflection and explicitly showed that the transformation corresponds to a Chebyshev polynomial of the signal $x$. Another common convention of QSP is to choose the signal unitary to be a $z$-rotation $R_z(x)$ with signal processing unitaries being $x$-rotations $R_x(\phi)$ <cit.>, which corresponds to a trigonometric polynomial of the signal $x$.
Different types of QSP and their relationships are summarized by <cit.>.
Observe that both of these two conventions of QSP have constraints on the achievable polynomials: for the Chebyshev QSP, each entry is a polynomial with either even or odd parity; for the trigonometric QSP, each entry is a trigonometric polynomial (in the exponential form) with either real or imaginary coefficients. As a result, the technique of linear-combination-of-unitaries <cit.> might be required for these conventions of QSP to implement a general polynomial transformation, which requires extra ancilla qubits. In a recent work, <cit.> overcame the constraints by adding an extra signal processing unitary in each iteration so that one could implement arbitrary complex trigonometric polynomial transformation in a single QSP. Our work is heavily based on this improved trigonometric QSP, which is defined as

\begin{equation}\label{eqn:QSP yzzyz decompose}
\UQSP^L(x) \coloneqq R_z(\omega)R_y(\theta_0)R_z(\phi_0) \prod_{l = 1}^L R_z(x) R_y(\theta_l)R_z(\phi_l),
\end{equation}

where $L\in \NN$ is the number of layers, $\omega \in \RR$, $\bm\theta = (\theta_0, \theta_1, \ldots, \theta_L)\in \RR^{L+1}$ and $\bm\phi = (\phi_0, \phi_1, \ldots, \phi_L)\in \RR^{L+1}$ are parameters. The quantum circuits of different QSP conventions and their realizable polynomials are presented in Table <ref>.

The following lemma characterizes the correspondence between trigonometric QSP and complex trigonometric polynomials. The initial version of Lemma <ref> first introduced in <cit.> is in the form of quantum neural networks. Here we restate the lemma in the formalism of QSP without changing the results.

There exist $\omega \in \RR$, $\bm\theta = (\theta_0, \theta_1, \ldots, \theta_L)\in \RR^{L+1}$ and $\bm\phi = (\phi_0, \phi_1, \ldots, \phi_L)\in \RR^{L+1}$ such that

\begin{equation}\label{eqn:trig form of QSP_}
\UQSP^L(x) = \begin{bmatrix}
P(x) & -Q(x)\\
Q^*(x) & P^*(x)
\end{bmatrix}
\end{equation}

if and only if Laurent polynomials $P, Q \in \CC[e^{ix/2}, e^{-ix/2}]$ satisfy

* $\deg(P)\leq L$ and $\deg(Q) \leq L$,

* $P$ and $Q$ have parity [For a Laurent polynomial $P\in\CC[z,z^{-1}]$, $P$ has parity $0$ if all coefficients corresponding to odd powers of $z$ are $0$, and similarly $P$ has parity $1$ if all coefficients corresponding to even powers of $z$ are $0$.] $L \bmod 2$,

* $\forall x\in \RR$, $\abs{P(x)}^2 + \abs{Q(x)}^2 = 1$.

Lemma <ref> demonstrates a decomposition of QSP $\UQSP^L(x)$ into complex Laurent polynomials, as well as a construction of QSP from complex Laurent polynomials. From the second condition of Lemma <ref>, it seems that $P$ and $Q$ still have parity constraints, i.e. either have parity $0$ or $1$, but in fact Laurent polynomials in $\CC[e^{ix/2}, e^{-ix/2}]$ with parity $0$ are essentially complex trigonometric polynomials in $\CC[e^{ix}, e^{-ix}]$ without parity constraints. The proof of this theorem also provides an algorithm that calculates angles $\omega, \bm \theta$ and $\bm \phi$ in $\mathcal{O}(\poly(L))$ operations, one can refer to Algorithm <ref> in Appendix <ref> for more details. There are also many other methods to compute the angles, see e.g., Refs. <cit.>. It can be inferred from Lemma <ref> that if $P(x)$ satisfies the parity constraint and $\abs{P(x)} \leq 1$ for all $x \in \RR$, then there exists a corresponding $Q(x)$ satisfying the three conditions. The detailed analysis can be found in Appendix <ref>.

Following the trigonometric QSP construction and decomposition in Ref. <cit.>, we are interested in how to represent the trigonometric polynomial transformation. One way is to project out $P(x)$ from $\UQSP$, i.e., the $\bra{0} \cdot \ket{0}$:

For any complex-valued trigonometric polynomial $F(x) = \sum_{j=-L}^L c_j e^{ijx}$ with $\norm{\bm c}_1 \leq 1$, there exist $\omega \in \RR$ and $\bm\theta,\bm\phi \in \RR^{2L+1}$ such that for all $x\in \RR$,

\begin{equation}\label{eqn:yzzyz_function_}
\bra{0} \UQSP^{2L}(x) \ket{0} = F(x)

Moreover, based on the fact that any non-negative real-valued trigonometric polynomial can be decomposed as a product between a Laurent polynomial in $\CC[e^{ix/2}, e^{-ix/2}]$ and its complex conjugate, as proved in Appendix <ref>, the trigonometric polynomial can be represented by the expectation value of measuring a Pauli-$Z$ observable with respect to the state $\UQSP^L \ket{0}$:

For any real-valued trigonometric polynomial $F(x) = \sum_{j=-L}^L c_j e^{ijx}$ with $\norm{\bm c}_1 \leq 1$, there exist $\omega \in \RR$ and $\bm\theta,\bm\phi \in \RR^{L+1}$ such that for all $x\in \RR$,

\begin{equation}\label{eqn:yzzyz_function_expectance}
f_W(x) \coloneqq \bra{0} \UQSP^L(x)^\dagger Z \UQSP^L(x)\ket{0} = F(x)

The concept of this corollary is that, for a real-valued trigonometric polynomial $F(x)$ with degree $L$ and satisfies $\norm{F(x)}\leq 1$, we could always find a complex Laurent polynomial $P\in\CC[e^{ix/2}, e^{-ix/2}]$ with degree $L$ such that $PP^* =(1 + F(x))/2$, then the expectation value of measuring $Z$ observable turns to be $F(x)$.

As a summary of this subsection, the construction and functions of the trigonometric QSP are briefly reviewed. Particularly, the trigonometric QSP is capable of implementing arbitrary complex trigonometric polynomials by projection or measuring the Pauli-$Z$ observable in a single-qubit system. These properties are the fundamental reasons why its generalized version can achieve improvements in aspects of phase estimation and entropy estimation, as will be demonstrated in later sections.

§.§ Processing phases of high-dimensional unitaries

Although the model of QSP provides a systematical method to make arbitrary polynomial transformations, it only works on a qubit-like quantum system.
<cit.> proposed a multi-qubit lifted version of the Chebyshev QSP, called quantum singular value transformation (QSVT), which could efficiently apply Chebyshev polynomial transformations to the singular values of a linear operator embedded in a larger unitary. In this work, we consider a similar extension of the trigonometric QSP and establish a quantum phase processing (QPP) algorithmic toolbox that could apply arbitrary trigonometric transformations to eigenphases of a unitary matrix $U$. The structure of QPP generalizes the trigonometric QSP by replacing the input signal $x$ with the phases of a higher-dimensional unitary matrix. For an even $L\in \NN$, angle parameters $\omega \in \RR$ and $\bm\theta, \bm\phi \in \RR^{L + 1}$, we define the quantum phase processor of the $n$-qubit unitary $U$ as

\begin{equation}
\UQPP^L(U) \coloneqq R_z^{(0)}(\omega)R_y^{(0)}(\theta_0) R_z^{(0)}(\phi_0) \left[
\prod_{l=1}^{L / 2}
\begin{bmatrix}
U^\dagger & 0 \\
0 & I^{\otimes n}
\end{bmatrix} R_y^{(0)}(\theta_{2l - 1})R_z^{(0)}(\phi_{2l - 1}) \begin{bmatrix}
I^{\otimes n} & 0 \\
0 & U
\end{bmatrix} R_y^{(0)}(\theta_{2l})R_z^{(0)}(\phi_{2l})
\right] \label{eqn:qnn_1}

where $R_y^{(0)}$ and $R_z^{(0)}$ are rotation gates applied on the first qubit. For an odd $L \in \NN$, we apply an extra layer

\[\begin{bmatrix}
U^\dagger & 0 \\
0 & I^{\otimes n}
\end{bmatrix} R_y^{(0)}(\theta_L)R_z^{(0)}(\phi_L)\]

to $\UQPP^{L-1}(U)$.
The quantum circuit of $\UQPP^L(U)$ is shown as in Fig. <ref>.

\[
\Qcircuit @C=0.5em @R=0.5em {
\lstick{\ket{0}} & \gate{R_z(\phi_L)} & \gate{R_y(\theta_L)} & \ctrl{1}  & \gate{R_z(\phi_{L-1})} & \gate{R_y(\theta_{L-1})} & \ctrlo{1} & \gate{R_z(\phi_{L-2})} & \gate{R_y(\theta_{L-2})} & \qw & &&\cdots&&& & \ctrlo{1} & \gate{R_z(\phi_{0})} & \gate{R_y(\theta_{0})} &\gate{R_z(\omega)} &\qw &\qw\\
\lstick{} &/^n\qw & \qw & \gate{U}  & \qw & \qw  & \gate{U^\dagger} & \qw & \qw & \qw & &&\cdots&&& & \gate{U^\dagger} & \qw & \qw & \qw &\qw
\]

General circuit for quantum phase processing $\UQPP^L(U)$, here the number of layers $L$ is an even integer.

One could find that QPP simply replaces the signal unitary $R_z(x)$ in QSP with interleaved unitaries controlled-$U$ and controlled-$U^\dagger$. We note that such a construction of using controlled-unitaries was first purposed by <cit.>, namely the “signal transduction”, which was frequently used in various works <cit.>. The intuition lying behind the extension is that controlled-$U$ and its inverse are naturally multi-qubit analogs of $R_z$ gates. To better understand how rotation gates in the first ancilla qubit process the phase of the target unitary $U$, we analyze the eigenspace decomposition of QPP:

Suppose $U$ is an $n$-qubit unitary with spectral decomposition

\begin{equation}
U = \sum_{j=0}^{2^n - 1} e^{i \tau_j} \ketbra{\chi_j}{\chi_j}

For all $L \in \NN$, $\omega \in \RR$ and $\bm\theta,\bm\phi \in \RR^{L+1}$, we have

\begin{equation}
\UQPP^L(U) = \bigoplus_{j=0}^{2^n - 1} (e^{-i \tau_j/2})^{L\bmod{2}} \cdot \UQSP^L(\tau_j)_{\mathbb{B}_j}
\end{equation}

where $\mathbb{B}_j \coloneqq \{\ket{0, \chi_j}, \ket{1, \chi_j}\}$.

The proof of this lemma is deferred to Appendix <ref>. Lemma <ref> shows that the eigenspace of QPP $\UQPP(U)$ coincides with that of the unitary $U$. Using this property, we generalize the single-qubit trigonometric QSP to the multi-qubit QPP that could perform a trigonometric polynomial transformation on the eigenphase of the unitary $U$. In the similar spirit of previous works <cit.>, we could measure the first ancilla qubit and achieve an evolution of the input state upon post-selection of the measurement result being $\ket{0}$, as shown in the follow theorem.

Given an $n$-qubit unitary $U = \sum_{j=0}^{2^n - 1} e^{i \tau_j} \ketbra{\chi_j}{\chi_j}$ and an $n$-qubit quantum state $\ket{\psi} = \sum_{j=0}^{2^n - 1} \alpha_j \ket{\chi_j}$, for any trigonometric polynomial $F(x) = \sum_{j=-L}^L c_j e^{ijx}$ with $\norm{\bm c}_1 \leq 1$, there exist $\omega \in \RR$ and $\bm\theta,\bm\phi \in \RR^{2L+1}$ such that

\begin{equation}
\left(\bra{0} \otimes I^{\otimes n}\right) \UQPP^{2L}(U) \ket{0,\psi} = \sum_{j=0}^{2^n - 1} \alpha_j F(\tau_j) \ket{\chi_j}.
\end{equation}

The proof of Theorem <ref> trivially follows from combining Lemma <ref> with Corollary <ref>, which we defer to Appendix <ref>. The other way is to evaluate trigonometric polynomial on the eigenphases and represent the result by the expectation value of measuring an observable on the first qubit:

Given an $n$-qubit unitary $U = \sum_{j=0}^{2^n - 1} e^{i \tau_j} \ketbra{\chi_j}{\chi_j}$ and an $n$-qubit quantum state $\rho$, for any real-valued trigonometric polynomial $F(x) = \sum_{j=-L}^L c_j e^{ijx}$ with $\norm{\bm c}_1 \leq 1$, there exist $\omega \in \RR$ and $\bm\theta,\bm\phi \in \RR^{L+1}$ such that $\widehat{\rho} = \UQPP(U) \left(\ketbra{0}{0} \otimes \rho\right)  \UQPP(U)^\dagger$ satisfies

\begin{equation}
f_V(U) \coloneqq \tr \left[ \left(Z^{(0)}\otimes I^{\otimes n}\right) \cdot \widehat{\rho} \right] = \sum_{j=0}^{2^n - 1} p_{j} F(\tau_j),
\end{equation}

where $p_j = \bra{\chi_j} \rho \ket{\chi_j}$ and $Z^{(0)}$ is a Pauli-$Z$ observable acting on the first qubit.

Theorem <ref> is proved by combining Lemma <ref> and Corollary <ref>, as shown in Appendix <ref>.
Theorem <ref> shows that QPP is natively compatible with indirect measurements, which could represent the target trigonometric polynomial by probabilities of measuring the ancilla qubit. Such a property does not emerge in QSVT, since QSVT typically represent the target polynomial transformation in amplitudes. Chebyshev's inequality dictates that an estimate of the expectation value within an additive error $\d$ can be obtained by measuring the ancilla qubit for $(1/^̣2)$ times. Alternatively, one could apply amplitude estimation~\cite{brassard2002quantum} to estimate the value by calling the QPP circuit for $(1/)̣$ times, which is quadratically more efficiently than classical sampling but with a larger circuit depth. In particular, since the ancilla qubit in QPP naturally works as a flag qubit, we could directly apply the iterative amplitude estimation~\cite{grinko2021iterative} on QPP without using extra qubits.

Theorem~\ref{thm:qpp evolution} and Theorem~\ref{thm:qpp evaluation} lie in the heart of QPP algorithmic toolbox, together demonstrating that QPP is a versatile and flexible toolbox for phase-related problems. First, QPP could act in a similar manner to QSVT but transforming eigenphases of a unitary rather than singular values of an embedded linear operator. Moreover, using block encoding and qubitization~\cite{low2019hamiltonian} enables QPP to process eigenvalues of an embedded operator as well, as presented in later applications. Second, QPP could extract the eigen-information after desired transformations by simply measuring the single ancilla qubit, generalizing many indirect measurement methods like the Hadamard test, which could not be natively achieved by QSVT to the best of our knowledge.

For the sake of notation simplicity, we omit the parameters $L,ω,θ$ and $ϕ$, writing QSP as $W(x)$ and QPP as $V(U)$ in the rest of this paper. The capabilities of QPP are summarized in Figure~\ref{fig:flow chart}. Next we will show that the structure of QPP is a powerful tool for designing efficient and intuitive quantum algorithms for solving various problems, including quantum phase estimation, Hamiltonian simulation, and quantum entropies estimation.

\begin{figure}[t]
\centering
\includegraphics[width=0.8\textwidth]{figs/flow_chart.png}
\caption{Illustration of the capabilities of quantum phase processing. A trigonometric transformation $F(x) = \frac{1}{2} \left(e^{\sin x} - e^{\cos x} \right)$ of eigenphases of an $n$-qubit unitary $U$ can be represented by a QPP circuit $V(U)$ in two different ways. \textbf{(a)} One approach is to directly simulate the target function. By post-selecting the ancilla qubit to be $\ket{0}$, the function transformations of phases are encoded into the amplitudes of eigenvectors,. \textbf{(b)} The other approach is to retrieve the target function by the expectation value of measuring a Pauli-$Z$ observable on the ancilla qubit. More intuitively, if the input state of circuit $V(U)$ is a maximally mixed state, then the sum of eigenphase transformations is approximately the square difference between two shaded areas in (b) multiplied by a constant. \textbf{(c-e)} Three examples for the QPP circuits to approximate functions near a discontinuity, which will be useful in applications of quantum phase estimation and quantum entropies estimation. In these three subfigures, the quantity ``deg'' refers to the degree of trigonometric polynomials, where every increase of such degree takes an extra layer in a QPP circuit.}
\label{fig:flow chart}
\end{figure}

\section{Quantum phase estimation} \label{sec:unitary}

Quantum phase estimation is one of the most important and useful subroutines in quantum computing. The problem of phase estimation is formally defined as follow: Given a unitary $U$ and an eigenstate $|χ⟩$ of $U$ with eigenvalue $e^iτ$, estimate the eigenphase $τ$ up to an additive error $$̣. In this section, we will develop an efficient algorithm for quantum phase estimation based on QPP. Before proceeding, let us do a little warming up to get familiar with the QPP toolbox. We start by considering a simple method of Hadamard test.

§.§ Warm-up example: the Generalized Hadamard test

A common method to estimate the phase of a unitary is the Hadamard test, which solves the following problem: Given a unitary $U$ and a state $\ket{\chi}$, estimate $\braket{\chi|U|\chi}$. The Hadamard test uses the measurement result of the ancillary qubit as a random variable whose expected value is the real part ${⟨χ|U|χ|}⟩$. It can also estimate the imaginary part ${⟨χ|U|χ|}⟩$ by adding a phase gate. We now show that QPP is a generalization of the Hadamard test.

Given a unitary $U$ and a quantum state $|χ⟩$ such that $U|χ⟩ = e^i τ |χ⟩$, let $F(x) = cos(x)$ be the target trigonometric polynomial for QPP. By Theorem~\ref{thm:qpp evaluation}, there exists a single-layer QPP $V(U)$ such that
\begin{equation}
f_V(U) = \tr\left[ \bra{0, \chi} V(U)^\dagger \left(Z^{(0)} \otimes I^{\otimes n}\right) V(U) \ket{0, \chi} \right] = \cos(\tau) = \Re \{\braket{\chi|U|\chi})\},
\end{equation}
Specifically, by computing the angles $ω, θ$ and $ϕ$, one can find that the two rotation gates in the first ancilla qubit are essentially Hadamard gates, which means that QPP implements the Hadamard test. Similarly, let the target trigonometric polynomial be $F(x) = sin(x)$, then QPP can estimate $sin(τ) = {⟨χ|U|χ|}⟩$. The phase $τ$ could be obtained from $cos(τ)$ and $sin(τ)$. Furthermore, one can select trigonometric polynomials other than $sin(x)$ and $cos(x)$, which yields a generalization of the Hadamard test. For example, QPP with a trigonometric polynomial $F(x)$ that approximates the function $f(x) = x/2π$ could directly estimates the phase $τ$.

Although QPP can implement a generalized Hadamard test to estimate the phase, the input state $|χ⟩$ is required to be an eigenstate of target unitary. However, quite often we are given a superposition of eigenstates instead of a pure eigenstate, such as in the factoring problem. In addition, measuring the ancilla qubit for $( 1/^̣2)$ times are necessary to estimate the expected value with an additive error $$̣, despite the fact that the complexity can be improved via amplitude estimation. Can we do better? As demonstrated in the following section, we can further employ QPP to construct a more efficient phase estimation algorithm that accepts a superposition of eigenstates, without using amplitude estimation.

§.§ Quantum phase searching

As introduced in Section <ref>, QPP can directly process the eigenphases of the target unitary, which allows us to classify the eigenphases. The main idea is to use a trigonometric polynomial to approximate a step function, so that we could utilize QPP to locate the eigenphases by a binary search procedure. We first show that QPP can classify the eigenphases of $U$.

Given a unitary $U = \sum_{j=0}^{2^n - 1} e^{i \tau_j} \ketbra{\chi_j}{\chi_j}$, then for any $\Delta \in (0, \pi)$ and $\eps \in (0, 1)$, there exists a QPP circuit $V(U)$ of $L = \cO \left(\frac{1}{\Delta}\log\frac{1}{\eps}\right)$ layers such that

\begin{equation}
V (U) \ket{0, \chi_k} = \begin{dcases}
\sqrt{1 - \eps_k} \ket{0, \chi_k} + \sqrt{\eps_k} \ket{1, \chi_k} & \text{if $\tau_k \in [\Delta, \pi-\Delta)$,}\\
\sqrt{\eps_k} \ket{0, \chi_k} + \sqrt{1 - \eps_k} \ket{1, \chi_k} & \text{if $\tau_k \in(-\pi + \Delta, -\Delta]$,}
\end{dcases}
\end{equation}

for $0 \leq k < 2^n$, where $\eps_k \in (0, \eps)$.

The proof of Lemma <ref> is deferred to Appendix <ref>. By phase kickback, measuring the ancilla qubit decides which subinterval the eigenphase $\tau$ belongs to with probability at least $1-\eps$. Next we apply a phase shift $e^{i\z}$ to $U$ to move to the middle point of the designated subinterval, so that $V(e^{i\z}U)$ determines the next subinterval. Using this fascinating property, repeating the binary search procedure shrinks the phase interval until QPP cannot decide next subintervals, i.e. $\tau \in [\z_l, \z_r]$ and $\abs{\z_r - \z_l} \approx 2\Delta$. See the phase interval search (PIS) procedure in Algorithm <ref> for details.

Phase Interval Search (PIS)

[1]
A unitary $U$, an eigenstate $\ket{\c}$ of $U$ with eigenvalue $e^{i\tau}$, an interval $[\z_l, \z_r]$, a $\Delta \in (0, \frac{1}{2})$, an $\eps \in (0,1)$, and an integer $\cQ$.
An updated interval $[\z_l, \z_r]$ such that $\tau \in [\z_l, \z_r]$ and $\z_r - \z_l = 2(\Delta + \frac{\pi}{2^{\cQ+1}})$.
$j=0\ldots \cQ-1$
Set the middle point $\z_m =\frac{\z_l+\z_r}{2}$.
Construct QPP circuit $\UQPP(e^{-i \z_m} U)$ in Lemma <ref> according to $\Delta$ and $\eps$.
Apply the circuit to the state $\ket{0, \c}$ and measure the ancilla qubit. If $\z_r - \z_l > 2\pi - 2\Delta$, update

\begin{equation}
[\z_l, \z_r] \leftarrow
\begin{dcases}
[\z_m - \Delta, \z_r + \Delta], & \text{if the outcome is 0} \\
[\z_l - \Delta, \z_m + \Delta], & \text{if the outcome is 1}
\end{dcases}

\begin{equation}
[\z_l, \z_r] \leftarrow
\begin{dcases}
[\z_m - \Delta, \z_r], & \text{if the outcome is 0} \\
[\z_l, \z_m + \Delta], & \text{if the outcome is 1}
\end{dcases}

Output the interval $[\z_l, \z_r]$.

The phase interval search procedure will shrink the phase interval to a length $2(\Delta + \frac{\pi}{2^{\cQ+1}})$ with probability at least $(1-\eps)^\cQ$, where $\cQ$ is the number of repetitions. Now the phase interval is too narrow for phase classification. We apply QPP on $(e^{i\z}U)^d$ for some appropriate integer $d$ so that the binary search procedure can continue to locate the amplified phase $d\tau \in [d\z_l, d\z_r]$. Repeating the entire procedure gives an estimation of phase $\tau$ up to required precision $\d$, as shown in Algorithm~\ref{alg:eigenphase search}.

\begin{figure}[htb]
\centering
\begin{algorithm}[H]
\caption{Quantum Phase Search Algorithm (QPS)}
\label{alg:eigenphase search}
\begin{algorithmic}[1]
\REQUIRE A unitary $U$, an eigenstate $\ket{\c}$ of $U$ with eigenvalue $e^{i\tau}$, a $\Delta \in (0, \frac{1}{2})$, an $\eps \in (0, 1)$ and a $\d \in (0, 1)$.
\ENSURE A phase $\bar\tau \in \RR$ such that $|\bar{\tau} - \tau| < \delta$.
\STATE Set $\cQ \leftarrow \lceil \log\frac{2\pi}{1 - 2\Delta} \rceil$, $\bar{\Delta} \leftarrow \Delta + \frac{\pi}{2^{\cQ+1}}$, $\cT \leftarrow \lceil \frac{\log\d}{\log\Delta} \rceil$ and $d \leftarrow \lfloor 1/\bar{\Delta} \rfloor$. Initialize the interval $[\z_l, \z_r] \leftarrow [-\pi, \pi]$.
\FOR{$t=0,\ldots, \cT-1$}
\STATE Update the interval by the phase interval search procedure,
\begin{equation}
[\z_l, \z_r] \leftarrow \PIS \left(U, \ket{\c}, [\z_l, \z_r], \Delta, \frac{\eps}{\cQ\cT}, \cQ\right).
\end{equation}
\STATE Store the middle point of interval $\z_m^{(t)} \leftarrow \frac{\z_l + \z_r}{2}$.
\STATE Update $U \leftarrow \left[e^{-i \z_m^{(t)}} U \right]^d$ and $[\z_l, \z_r] \leftarrow [d(\z_l - \z_m^{(t)}), d(\z_r - \z_m^{(t)})]$.
\ENDFOR
\STATE Output $\bar\tau \leftarrow \sum_{t=0}^{\cT - 1}\z_m^{(t)} d^{-t}$.
\end{algorithmic}
\end{algorithm}
\end{figure}

Note that Algorithm~\ref{alg:eigenphase search} could accept a superposition of eigenstates as the input, since eigenstates whose eigenvalues disagree with measurement results of the ancilla qubit will be filtered out, and finally the state in the main register converges to a single eigenstate of $U$ at the end of the quantum phase search algorithm. We conclude the above discussions in Theorem~\ref{thm:qps complexity}.

\begin{theorem} [Complexity of Quantum Phase Search] \label{thm:qps complexity}
Given an $n$-qubit unitary $U$ and an eigenstate $\ket{\c}$ of $U$ with eigenvalue $e^{i\tau}$,  Algorithm~\ref{alg:eigenphase search} can use one ancilla qubit and $\cO \left(\frac{1}{\delta} \log \left(\frac{1}{\eps} \log\frac{1}{\d} \right) \right)$ queries to controlled-$U$ and its inverse to obtain an estimation of $\tau$ up to $\d$ precision with probability at least $1 - \eps$.
\end{theorem}

We can see that the quantum phase search algorithm provides a nearly quadratic speedup compared to the Hadamard test method in Section~\ref{sec:Hadamard test}. More importantly, the phase search algorithm does not require the input state being an eigenstate of $U$, making it more versatile for solving specific problems like the factoring problem.

\subsection{Comparison to related works}

The quantum phase estimation method originally purposed to solve the Abelian Stabilizer Problem~\cite{kitaev1995quantum, kitaev2002classical} was found to work for general unitaries. The most well-known version of phase estimation method~\cite{kitaev1995quantum} queries the controlled-$U$ for $\cO(\frac{1}{\d})$ times and applies the inverse quantum Fourier transform (QFT)~\cite{Coppersmith1994} to estimate the eigenphase of a unitary $U$ with precision $\d$ and success probability at least $4/\pi^2$. The success probability can be boosted to $1-\eps$ by using additional $\cO(\log\frac{1}{\eps})$ ancilla qubits~\cite{cleve1998quantum}. Introducing classical feed-forward process~\cite{kitaev1995quantum, Griffiths1996} can further reduce the number of ancilla to one without increase of circuit depth. Recent studies~\cite{martyn2021grand, rall2021faster} utilize the structure of QSVT to reinterpret phase estimation methods, bringing potential trade-offs among precision, query complexity and number of ancilla qubits. The quantum phase search method proposed in this work is based on the intuitive idea of binary search, which is fundamentally different from the previous QFT-based algorithms. {\citet{dong2022ground} proposed a phase estimation algorithm, in a similar spirit of ours, to the case $U\ket{\psi}=e^{-i\lambda}\ket{\psi}$, where $\lambda\in[\eta, \pi-\eta]$ for some constant $\eta>0$. However, this prior condition on the eigenvalue is usually not satisfied for an arbitrary unitary and initial state.} Here we compare our phase search method to some previous phase estimation algorithms with respect to the query complexity and number of ancilla qubits under the same precision and success probability, which is shown in Table~\ref{table:QPE algs}. One can see that the quantum phase search method achieves the best query complexity while requiring the least ancilla qubits, turning out to be an efficient phase estimation algorithm.

\begin{table}[H]
\centering
\setlength{\tabcolsep}{1em}
\begin{tabular}{lccccc}
\toprule
Methods for QPE & Queries to controlled-$U$ & \# of ancilla qubits & Success probability & Precision \\
\midrule
QFT-based~\cite{kitaev1995quantum, cleve1998quantum, Nielsen2010} & $ \cO \left( \frac{1}{\d}\left(1 + \frac{1}{\eps}\right) \right)$ & $ \ceil*{\log{\frac{1}{\d}} + \log(2+\frac{1}{\eps})}$ & {} & {} \\
\addlinespace
Semi-classical QFT-based~\cite{kitaev1995quantum, Griffiths1996} & $\cO \left( \frac{1}{\d}\left(1 + \frac{1}{\eps}\right) \right)$ & $1$ & \multirow{3}{*}{$ 1-\eps$} & \multirow{3}{*}{$ \d$} \\
\addlinespace
QSVT-based~\cite{martyn2021grand, rall2021faster} & $ \widetilde\cO \left(\frac{1}{\d} \log\left(\frac{1}{\eps}\right) \right)$ & $ \ceil*{\log{\frac{1}{\d}}} + 3$ (or $3$) & {} & {} \\
\addlinespace
QPP-based (in Theorem~\ref{thm:qps complexity}) & \multicolumn{1}{c}{$ \widetilde\cO \left(\frac{1}{\d} \log\left(\frac{1}{\eps}\right) \right)$} & $1$ & {} & {}\\
\bottomrule
\end{tabular}
\caption{Comparison of QPE Algorithms. In the query complexity, the $\widetilde\cO$ notation omits $\log\log$ factors. The number of ancilla qubits is the total number of qubits used other for the system of $U$.}\label{table:QPE algs}
\end{table}

\section{Quantum entropy estimation} \label{sec:state}
Quantum entropy is used to characterize the randomness and disorder of a quantum system, which has various theoretical and experimental applications of relevance. Estimating the entropy of a quantum system is an important problem in quantum information science. Classical methods of estimating the quantum entropies require the density matrix of a quantum state, which is costly, especially when the size of system is large. Recent works proposed quantum algorithms that could efficiently estimate quantum entropies~\cite{gilyen2020distributional,subramanian2021quantum,gur2021sublinear}, showing potential quantum speedups over the classical methods. The motivating idea behind these quantum approaches is the purified quantum query model~\cite{low2019hamiltonian}, which prepares a purification of a mixed state $\rho$. {The purified query model can apply to cases where the states are generated by a quantum circuit and have applications in many tasks \cite{belovs2019quantum,gilyen2020distributional}.} Formally, the purified quantum query oracle of a mixed state $\rho$ is a unitary $U_\rho$ acting as
\begin{equation}\label{eqn:purified query}
U_\rho \ket{0}_A\ket{0}_B = \ket{\Psi_\rho}_{AB} = \sum_{j=0}^{2^n-1} \sqrt{p_j} \ket{\psi_j}_A\ket{\phi_j}_B
\end{equation}
such that $\tr_B(\ketbra{\Psi_\rho}{\Psi_\rho}) = \rho$, where $\{\ket{\psi_j}\}$ and $\{\ket{\phi_j}\}$ are sets of orthonormal states on the system $A$ and $B$ respectively. Using the qubitization method in~\cite{low2019hamiltonian}, such an oracle model can be used to build a qubitized block encoding $\widehat{U}_\rho$ of the target state $\rho$. We show the detailed construction of $\widehat{U}_\rho$ in Appendix~\ref{appendix:dm block enc}.

% \RV{\textbf{Reviewer C:} I hope the authors could better motivate the purified quantum query model. What is the complexity of realizing that purified state preparation for concrete entropy estimation problems people care about?}

Consequently, it is reasonable and compelling to investigate whether QPP, the structure designed for unitary phase processing, could contribute to the improvement of quantum algorithms for quantum entropy estimation. Note that quantum entropies of a quantum state $\rho$ can be interpreted as the corresponding classical entropies of the eigenvalues of $\rho$. If one could find \tps{} $F(x)$ that approximate the classical entropic functions,
% functions in classical entropies \YL{classic entropic functions},
then quantum entropies can be naturally estimated via phase evaluation of $\widehat{U}_\rho$ in Theorem~\ref{thm:qpp evaluation} by the spectral correspondence between $\rho$ and $\widehat{U}_\rho$. Specifically, the following theorem is the basic principle of the QPP-based quantum entropies estimation, and the proof of which is deferred to Appendix~\ref{appendix:state entropy estimation}.

\begin{theorem} \label{thm:state entropy estimation}
Let $\ket{\Psi_\rho}_{AB}$ be a purification of an $n$-qubit state $\rho$ and $\widehat{U}_\sigma$ be a qubitized block encoding of an $n$-qubit state $\sigma$ with $m$ ancilla qubits. For any real-valued polynomial $f(x) = \sum_{k=0}^L c_j x^k$ with $\norm{\bm c}_1 \leq 1$, there exists a QPP circuit $\UQPPs(\widehat{U}_\sigma)$ of $L$ layers such that
\begin{align}
\langle Z^{(0)} \rangle_{\ket{\Phi}} = \tr \left(\rho f(\sigma) \right)
where $\ket{\Phi} = \left(\UQPPs(\widehat{U}_\sigma) \otimes I_B\right)\ket{0^{\otimes (m + 1)}} \ket{\Psi_\rho}_{AB}$ and the polynomial on a quantum state is defined as $f(\sigma) = \sum_{k=0}^L c_j \sigma^k$.
\end{theorem}

Theorem~\ref{thm:state entropy estimation} shows that one could measure the value of $\tr(\rho f(\sigma))$ as the $Z$ expectation value of the ancilla qubit. An estimate of the expectation value within an additive error $\d$ can be obtained by measuring the ancilla qubit for $\cO(1/\d^2)$ times. Moreover, we could directly apply the iterative amplitude estimation~\cite{grinko2021iterative} on QPP to achieve a quadratic speedup without using extra qubits. For clarity, we present the QPP circuit of quantum entropy estimation in Figure~\ref{fig:circuit of QPP for state}. We also note that Theorem \ref{thm:state entropy estimation} can be applied to extract many information-theoretic properties of quantum states other than quantum entropies.

\begin{figure}[H]
\[
\Qcircuit @C=0.5em @R=1.5em {
\lstick{\ket{0}} & \qw & \gate{R_z} & \gate{R_y} & \ctrl{1}  & \gate{R_z} & \gate{R_y} & \ctrlo{1} & \gate{R_z} & \gate{R_y} & \qw & &&\cdots&&& & \ctrlo{1} & \gate{R_z} & \gate{R_y} &\gate{R_z} &\qw &\meter\\
\lstick{\ket{0^{\otimes m}}} & /\qw & \qw & \qw & \multigate{1}{\widehat{U}_\sigma}  & \qw & \qw  & \multigate{1}{\widehat{U}_\sigma^\dagger} & \qw & \qw & \qw & &&\cdots&&& & \multigate{1}{\widehat{U}_\sigma^\dagger} & \qw & \qw & \qw &\qw \\
\lstick{\ket{0^{\otimes n}}_A} & /\qw & \multigate{1}{U_\rho} & \qw & \ghost{\widehat{U}_\sigma}  & \qw & \qw  & \ghost{\widehat{U}_\sigma^\dagger} & \qw & \qw & \qw & &&\cdots&&& & \ghost{\widehat{U}_\sigma^\dagger} & \qw & \qw & \qw &\qw \\
\lstick{\ket{0}_B} & /\qw & \ghost{U_\rho} & \qw & \qw & \qw & \qw  & \qw & \qw & \qw & \qw & &&\cdots&&& & \qw & \qw & \qw & \qw &\qw
\]
\caption{The QPP circuit in Theorem~\ref{thm:state entropy estimation} for quantum entropies estimation.}
\label{fig:circuit of QPP for state}
\end{figure}

In this section, to demonstrate the power of QPP, we utilize the generic method in Theorem~\ref{thm:state entropy estimation} to estimate the most fundamental entropic functionals for quantum systems, including the von Neumann entropy, the quantum relative entropy, and the family of quantum R\'enyi entropies.

\subsection{von Neumann and quantum relative entropy estimation}

The von Neumann entropy~\cite{von1932mathematische} is a generalization of the Shannon entropy from the classical information theory to quantum information theory. For an $n$-qubit quantum state $\rho$, the von Neumann entropy is defined as follows
\begin{equation}
S(\rho) = - \tr(\rho \ln \rho).
\end{equation}
Let $\{p_j\}_j$ be the eigenvalues of $\rho$, then the von Neumann entropy is the same as the Shannon entropy of the probability distribution $\{p_j\}_j$,
\begin{equation}
S(\rho) = - \sum_{j=0}^{2^n - 1} p_j \ln p_j.
\end{equation}
Recall from the qubitization technique that {partial} eigenphases of the qubitized block encoding $\widehat{U}_\rho$ are {given by} $\pm \tau_j = \pm \arccos(p_j)$, then we have $p_j = \cos(\pm \tau_j) \in [0, 1]$. Here we assume the non-zero eigenvalues are lower bounded by some $\gamma > 0$. Then by Theorem~\ref{thm:state entropy estimation}, the main idea of using QPP to estimate the von Neumann entropy is to find a polynomial $f(x)$ that approximates the function $\ln(x)$ with some appropriate scale on the interval $[\gamma, 1]$, and $|f(x)| \leq 1$ for $x \in [-1, 1]$. Particularly, the polynomial $f(x)$ could be obtained from the Taylor series of $\ln(x)$. The overall result is stated in the following theorem.

\begin{theorem}[von Neumann entropy estimation] \label{thm:von Neumann complexity}
Given a purified quantum query oracle $U_\rho$ of a state $\rho$ whose non-zero eigenvalues are lower bounded by $\gamma > 0$, there exists an algorithm that estimates $S(\rho)$ up to precision $\eps$ with high probability by measuring a single qubit, querying $U_\rho$ and $U_\rho^\dagger$ for $\cO\left(\frac{1}{\gamma \eps^2}\log^2(\frac{1}{\gamma})\log(\frac{\log(1/\gamma)}{\eps})\right)$ times. Moreover, using amplitude estimation improves the query complexity to $\cO\left(\frac{1}{\gamma \eps}\log(\frac{1}{\gamma})\log(\frac{\log(1/\gamma)}{\eps})\right)$.
\end{theorem}

In particular, the dependence on $\gamma$ can be translated to the rank (or dimension) of the density matrix, from which we have the following corollary.
\begin{corollary} \label{coro:von Neumann complexity no gamma}
Given a purified quantum query oracle $U_\rho$ of a state $\rho$ whose rank is $\kappa \leq 2^n$, there exists an algorithm that estimates $S(\rho)$ up to precision $\eps$ with high probability by measuring a single qubit, querying $U_\rho$ and $U_\rho^\dagger$ for $\cO\left( \frac{\kappa}{\eps^3} \log^3 \left(\frac{\kappa}{\eps}\right)\log\left(\frac{1}{\eps}\right)\right)$ times. Moreover, using amplitude estimation improves the query complexity to $\cO\left( \frac{\kappa}{\eps^2} \log^2 \left(\frac{\kappa}{\eps}\right) \log\left(\frac{1}{\eps}\right)\right)$.
\end{corollary}

We defer the proofs to Appendix~\ref{appendix:guarantee for neumann and relative}. Note that the estimation of the quantum relative entropy between states $\rho$ and $\sigma$, i.e.\
\begin{equation}
\infdiv{\rho}{\sigma} = -\tr(\rho\ln\sigma) - S(\rho),
\end{equation}
immediately follows from the above analysis. In particular, we only need to apply QPP on a qubitized block encoding of $\sigma$ to estimate $\tr(\rho\ln\sigma)$ if the relative entropy is finite. The result of quantum relative entropy estimation is shown in Theorem~\ref{thm:relative complexity}.

\begin{theorem}[Quantum relative entropy estimation]
\label{thm:relative complexity}
Given purified quantum query oracles $U_\rho$ and $U_\sigma$ of states $\rho$ and $\sigma$, respectively, such that their non-zero eigenvalues are lower bounded by $\gamma > 0$ and the kernel of $\sigma$ has trivial intersection with the support of $\rho$, there exists an algorithm that estimates $\infdiv{\rho}{\sigma}$ up to precision $\eps$ with high probability, querying $U_\rho$, $U_\sigma$ and their inverses for $\cO\left(\frac{1}{\gamma \eps^2}\log^2(\frac{1}{\gamma})\log(\frac{\log(1/\gamma)}{\eps})\right)$ times. Moreover, using amplitude estimation improves the query complexity to $\cO\left(\frac{1}{\gamma \eps}\log(\frac{1}{\gamma})\log(\frac{\log(1/\gamma)}{\eps})\right)$.
% Suppose $\rho$ and $\sigma$ are $n$-qubit states with non-zero eigenvalues larger than $\gamma > 0$. We can use one ancilla qubit and $\cO(\frac{1}{\gamma \eps^2}\log^2(\frac{1}{\gamma})\log(\frac{\log(1/\gamma)}{\eps}))$ queries of $U_\rho$ and $U_\sigma$ and their inverses, to estimate $\infdiv{\rho}{\sigma}$ up to precision $\eps$. Moreover, using QAE can further improve this complexity to $\cO(\frac{1}{\gamma \eps}\log(\frac{1}{\gamma})\log(\frac{\log(1/\gamma)}{\eps}))$.
\end{theorem}

\subsection{Quantum R\'enyi entropy estimation}
The quantum R\'enyi entropy~\cite{Petz1986a} is a quantum version of the classical R\'enyi entropy that was first introduced in~\cite{renyi1961measures}. For $\alpha\in(0,1)\cup(1,\infty)$, the quantum $\a$-R\'enyi entropy of an $n$-qubit quantum state $\rho$ is defined as follows:
\begin{equation}
\end{equation}
Let $\{p_j\}_j$ be the eigenvalues of $\rho$, then the quantum $\a$-R\'enyi entropy reduces to the $\a$-R\'enyi entropy of the probability distribution $\{p_j\}_j$,
\begin{equation}
S_{\alpha}(\rho)=\frac{1}{1-\alpha}\log \left(\sum_{j=0}^{2^n - 1} p_j^\alpha \right).
\end{equation}
Similarly, we assume all non-zero eigenvalues are greater than some $\gamma > 0$. The method of R\'enyi entropy estimation, based on Theorem~\ref{thm:state entropy estimation}, is in the same spirit of estimating the von Neumann entropy; the only difference is that we now aim to find a polynomial $f(x)$ that approximates the function $x^{\a - 1}$ for any $\alpha>0$ and $\alpha\neq1$ on the interval $[\gamma, 1]$. The exponent is $\a - 1$ because we can write $\tr(\rho^\a)$ as $\tr(\rho \cdot \rho^{\a-1})$, and the isolated $\rho$ comes from the input state of QPP.

When $\alpha>0$ is a non-integer, the polynomial could be given by separately considering the integer part and decimal part of $\alpha - 1$.
% This is because the integer part can be precisely expressed as a polynomial, while the decimal part is not and hence needs to be approximated.
Thus we only need to find a polynomial that approximates $x^{\a-1}$ for $\alpha \in (0, 1)$ on the interval $x \in [\gamma, 1]$, which could be obtained from the Taylor series of $x^{\a-1}$. We present the results in the following theorem and more discussions in Appendix~\ref{appendix:guarantee for Renyi}.

\begin{theorem} [Quantum R\'enyi entropy estimation for real $\alpha$]
\label{thm:real Renyi complexity}
Given a purified quantum query oracle $U_\rho$ of a state $\rho$ whose non-zero eigenvalues are lower bounded by $\gamma > 0$, there exists an algorithm that estimates $S_\alpha(\rho)$ up to precision $\eps$ with high probability by measuring a single qubit, querying $U_\rho$ and $U_\rho^\dagger$ for a total number of times of
% Suppose $\a > 0$ is a real number and $\rho$ is an $n$-qubit state with non-zero eigenvalues larger than $\gamma > 0$. We can use one ancilla qubit and
\begin{equation}
\begin{dcases}
\widetilde\cO \left(\frac{1}{\gamma^{3 - 2\a} \eps^2} \cdot \eta^2 \right), & \textrm{if } \a \in (0, 1); \\[10pt]
\widetilde\cO \left(\frac{\a\gamma + 1}{\gamma \eps^2} \cdot \eta^2 \right), & \textrm{if } \a \in (1, \infty);
\end{dcases}
\end{equation}
where $\eta = \frac{\tr(\rho^\a)^{-1}}{\abs{1 - \a}}$.
Moreover, using quantum amplitude estimation improves the query complexity to
\begin{equation}
\begin{dcases}
\widetilde\cO \left(\frac{1}{\gamma^{2 - \a} \eps} \cdot \eta \right), & \textrm{if } \a \in (0, 1). \\[10pt]
\widetilde\cO \left(\frac{\a\gamma + 1}{\gamma \eps} \cdot \eta \right), & \textrm{if } \a \in (1, \infty).
\end{dcases}
\end{equation}
Here the $\widetilde\cO$ notation omits logarithmic factors.
\end{theorem}

Similarly, we provide a method to estimate $S_\a(\rho)$ without information of $\gamma$ in Appendix~\ref{appendix:guarantee for Renyi}.
% \begin{corollary} \label{coro:renyi complexity no gamma}
% Assume a rank $\kappa \leq 2^{n}$ for an $n$-qubit state $\rho$ and a purified quantum oracle $U_\rho$. There exists a QPP circuit that estimates $S_\alpha(\rho)$ within precision $\eps$ by measuring a single qubit, at an expense of querying $U_\rho$ and $U_\rho^\dagger$ for a number of
%     % Suppose $\a > 0$ is a real number and $\rho$ is an $n$-qubit state with non-zero eigenvalues larger than $\gamma > 0$. We can use one ancilla qubit and
% \begin{equation}
%     \begin{dcases}
%         \widetilde\cO\left( \frac{\kappa^{3/\a - 2}}{\eps^{3/\a}} \cdot \frac{2^{12/\a}}{\a}  \eta^{\frac{3}{\a}}  \right), & \textrm{if } \a \in (0, 1); \\[10pt]
%         \widetilde\cO\left(  \frac{\kappa/\eps + \alpha/(2\eta)}{\eps^2} \cdot \eta^3 \right), & \textrm{if } \a \in (1, \infty);
%     \end{dcases}
% .\end{equation}
% where $\eta = \frac{\tr(\rho^\a)^{-1}}{\abs{1 - \a}}$ and the $\widetilde\cO$ notation omits the $\log$ factors.
% Moreover, using QAE can improve query complexity to
% \begin{equation}
%     \begin{dcases}
%         \widetilde\cO\left( \frac{\kappa^{2/\a - 1}}{\eps^{2/\a}} \cdot \frac{2^{8/\a}}{\a}  \eta^{\frac{2}{\a}}  \right), & \textrm{if } \a \in (0, 1); \\[10pt]
%         \widetilde\cO\left(  \frac{\kappa/\eps + \alpha/(2\eta)}{\eps} \cdot \eta^2 \right), & \textrm{if } \a \in (1, \infty);
%     \end{dcases}
% .\end{equation}
% \end{corollary}
When $\alpha$ is an integer, the function $x^{\a - 1}$ naturally turns to be a normalized polynomial so that approximation error does not exist by Theorem~\ref{thm:state entropy estimation}. {In this case, the dependence on the threshold $\gamma$ can be further improved.}

\begin{theorem}[Quantum R\'enyi entropy estimation for integer $\alpha$]
\label{thm:integer Renyi complexity}
Suppose $\alpha>1$ is a positive integer, there exists an algorithm that estimates $S_\a(\rho)$ up to precision $\eps$ with high probability by measuring a single qubit, querying $U_\rho$ and $U_\rho^\dagger$ for $\cO\left(\frac{\alpha\tr(\rho^\a)^{-2}}{ \eps^2}\right)$ times.
% queries of $U_\rho$ and its inverse to compute $S_\a(\rho)$ up to precision $\eps$.
% Suppose $\a > 1$ Cis a positive integer and $\rho$ is an $n$-qubit state. We can use one ancilla qubit and $\cO(\frac{\tr(\rho^\a)^{-2}}{\a \eps^2})$ queries of $U_\rho$ and its inverse to compute $S_\a(\rho)$ up to precision $\eps$.
Moreover, using amplitude estimation improves the query complexity to $\cO\left(\frac{\alpha\tr(\rho^\a)^{-1}}{\eps}\right)$.
\end{theorem}

Note that this method of computing $S_\a(\rho)$ for $\alpha \in \NN_+$ naturally establishes an efficient algorithm for entanglement spectroscopy, a task of obtaining the entanglement of a quantum state. Consider a bipartite pure state $\ket{\Psi_\rho}_{AB}$ in Eq.~\eqref{eqn:purified query}, the entanglement between systems $A$ and $B$ can be characterized by the eigenvalues of the reduced density operator $\rho = \tr_B(\ketbra{\Psi_\rho}{\Psi_\rho})$. Specifically, one needs to compute the $\tr(\rho^k)$ for $k= 1, \ldots, k_{\max}$ to estimate $k_{\max}$ largest eigenvalues of $\rho$ by the Newton-Girard method~\cite{johri2017entanglementa, subasi2019entanglement, yirka2021qubitefficient}.

\subsection{Comparison to related works}
As introduced above, we utilize the structure of QPP to estimate quantum entropies based on the purified quantum query model. Here we briefly mention some closely related works on quantum entropy estimation under a similar setting.
For von Neumann entropy $S(\rho)$, \citet{gilyen2020distributional} proposed an efficient quantum algorithm based on QSVT and amplitude estimation that achieves a near-linear query complexity and an additive error $\eps$.  Another work by~\citet{gur2021sublinear} utilized the quantum singular value estimation \cite{kerenidis2016quantum} and amplitude estimation to implement an algorithm with a sublinear query complexity up to a multiplicative error bound.

By contrast, our algorithm could estimate the result by measuring the first ancilla qubit, which has a slightly worse query complexity in the worst case but a smaller circuit size. Nevertheless, by Corollary~\ref{coro:von Neumann complexity no gamma}, our complexity can depend on the rank of the density matrix, which will be further improved for low-rank cases. Note that one could apply amplitude estimation on QPP without using extra qubits, which might be required for previous QSVT-based algorithms. As a result, the QPP-based algorithms allow us to flexibly consider the trade-off between the query complexity and the circuit depth in practical applications.

\begin{table}[htbp]
\centering
\setlength{\tabcolsep}{1em}
\begin{tabular}{lccc}
\toprule
Methods for $S(\rho)$ estimation & Total queries to $U_\rho$ and $U_\rho^\dagger$ & Queries per use of circuit\\
\midrule
QSVT-based with QAE (\cite{gilyen2020distributional}) & $\widetilde\cO(\frac{d}{\eps^{1.5}})$ & $\widetilde\cO(\frac{d}{\eps^{1.5}})$ \\
% \addlinespace
% QSVT-based with rank and QAE (\cite{wang2022new}) & $\widetilde\cO(\frac{\kappa^2}{\eps^2})$ & $\widetilde\cO(\frac{\kappa^2}{\eps^2})$   \\
\addlinespace
QPP-based (assumes rank, in Corollary~\ref{coro:von Neumann complexity no gamma}) & $\widetilde\cO(\frac{\kappa}{\eps^3})$ & $\widetilde\cO(\frac{\kappa}{\eps})$  \\
\addlinespace
QPP-based with QAE (assumes rank, in Corollary~\ref{coro:von Neumann complexity no gamma})  & $\widetilde\cO(\frac{\kappa}{\eps^2})$ &  $\widetilde\cO(\frac{\kappa}{\eps^2})$  \\
\addlinespace
QPP-based (in Theorem~\ref{thm:von Neumann complexity})  & $\widetilde\cO(\frac{1}{\gamma \eps^2})$ & $\widetilde\cO(\frac{1}{\gamma})$  \\
\addlinespace
QPP-based with QAE (in Theorem~\ref{thm:von Neumann complexity}) & $\widetilde\cO(\frac{1}{\gamma \eps})$ &  $\widetilde\cO(\frac{1}{\gamma\eps})$  \\
\bottomrule
\end{tabular}
\caption{Comparison of algorithms on estimating von Neumann entropy within additive error. Here the $\widetilde\cO$ notation omits $\log$ factors, $\gamma > 0$ is the lower bound of eigenvalues, $\kappa > 0$ is the rank of the state $\rho \in \CC^{d \times d}$, and $\eps$ is the additive error of estimating $S(\rho)$. QAE is short for quantum amplitude estimation.}
\label{table:von Neumann algs}
\end{table}

With regard to the family of quantum $\a$-R\'enyi entropies $S_\a(\rho)$, when $\a$ is an integer, QPP establishes an efficient algorithm for entanglement spectroscopy. Compared to previous algorithms for entanglement spectroscopy~\cite{johri2017entanglementa, subasi2019entanglement}, the QPP-based algorithm significantly reduces the circuit width from $\Theta(n\a)$ to $4n+1$ without using qubit resets as in~\cite{yirka2021qubitefficient}. For a more general case that $\a$ is not an integer, \citet{subramanian2021quantum} introduced a quantum algorithm that combines the QSVT technique and the $\mathsf{DQC1}$ (Deterministic Quantum Computation with one clean qubit) method. Their algorithm estimates $S_\alpha(\rho)$ with an additive error by measuring a single qubit, using an expected total number $\widetilde\cO(\sfrac{d^2}{\gamma\eps^2})$ queries to the purified quantum oracle, where $d = 2^n$ is the dimension of $\rho$. Our QPP-based approaches improve the results in~\cite{subramanian2021quantum} in terms of the dependence on the dimension. For instance, for $\alpha>1$, our algorithms based on single-qubit measurement require a query complexity of $\widetilde\cO(\sfrac{\alpha}{\gamma\eps^2 })$. {The main reason there is a speedup factor of $d^2$ is that the $\mathsf{DQC1}$ method requires a maximally mixed state $\frac{1}{d}I$ as the input state, whereas the QPP-based method uses $\rho$ as the input state.} Moreover, as we mention before, QSVT is not natively compatible with indirect measurement, one needs to utilize an extra ancilla qubit to control the QSVT circuit in order to implement indirect measurement, as shown in~\cite{subramanian2021quantum}.
% The idea of employing QSVT to estimate $S_{\alpha}(\rho)$ has also been discussed by \citet{wang2022new}, where the state's information is extracted by applying QAE. However, their approaches have an awful query complexity when $\alpha$ approaches an integer. In this case, their query complexity would explode exponentially, which is not intuitive.
Similar to the earlier description, we could leverage quantum amplitude estimation to achieve a better query complexity. More detailed comparisons are shown in Table~\ref{table:Renyi algs}.

\begin{table}[htbp]
\centering
\setlength{\tabcolsep}{1em}
\begin{tabular}{lcccc}
\toprule
\multirow{2}{*}[-2pt]{Methods for $S_\a(\rho)$ estimation} & \multicolumn{3}{c}{Total queries to $U_\rho$ and $U_\rho^\dagger$}\\
\cmidrule{2-4}
& $\a \in (0, 1)$ & $\a \in (1, \infty)$ &  $\a \in \NN_+$\\
\midrule
QSVT-based with $\mathsf{DQC1}$ (\cite{subramanian2021quantum}) & $\widetilde\cO \left(\frac{d^2}{\gamma \eps^2} \cdot \eta^2\right)$ & $\widetilde\cO \left(\frac{d^2}{\gamma \eps^2} \cdot \eta^2\right)$ & $\cO \left(\frac{d^2}{\eps^2} \cdot \a^3 \eta^2\right)$  \\
% \addlinespace
% QSVT-based with rank and QAE (\cite{wang2022new}) & $\widetilde\cO \left(\frac{\kappa^{\frac{3 - \a^2}{2\a}}}{\eps^{\frac{3 + \a}{2\a}}}\right)$ & $\widetilde\cO \left(\frac{\kappa^{\a - 1 + \a/\{ \frac{\a - 1}{2} \}}}{\eps^{1 + 1/\{ \frac{\a - 1}{2} \}}}\right)$ & $\widetilde\cO \left(\frac{\kappa^{\a - 1}}{\eps}\right)$ \\
\addlinespace
QPP-based (in Theorem~\ref{thm:real Renyi complexity} and~\ref{thm:integer Renyi complexity}) & $\widetilde\cO \left(\frac{1}{\gamma^{3 - 2\a} \eps^2} \cdot \eta^2\right)$ & $\widetilde\cO \left(\frac{\a\gamma + 1}{\gamma \eps^2} \cdot \eta^2\right)$ & $\cO \left(\frac{1}{\eps^2} \cdot \a \eta^2\right)$ \\
% \addlinespace
% QPP-based with rank (in Corollary~\ref{coro:renyi complexity no gamma}) & $\widetilde\cO\left( \frac{\kappa^{3/\a - 2}}{\eps^{3/\a}} \cdot \frac{2^{12/\a}}{\a}  \eta^{\frac{3}{\a}} \right)$ & $\widetilde\cO\left(  \frac{\kappa/\eps + \alpha/(2\eta)}{\eps^2} \cdot \eta^3 \right)$ & \textrm{same as above} \\
\addlinespace
QPP-based with QAE (in Theorem~\ref{thm:real Renyi complexity} and~\ref{thm:integer Renyi complexity}) & $\widetilde\cO \left(\frac{1}{\gamma^{2 - \a} \eps} \cdot \eta\right)$ & $\widetilde\cO \left(\frac{\a\gamma + 1}{\gamma \eps} \cdot \eta\right)$ & $\cO \left(\frac{1}{\eps} \cdot \a \eta\right)$ \\
% \addlinespace
% QPP-based with rank and QAE (in Corollary~\ref{coro:renyi complexity no gamma}) & $\widetilde\cO\left( \frac{\kappa^{2/\a - 1}}{\eps^{2/\a}} \cdot \frac{2^{8/\a}}{\a}  \eta^{\frac{2}{\a}} \right)$ & $\widetilde\cO\left(  \frac{\kappa/\eps + \alpha/(2\eta)}{\eps} \cdot \eta^2 \right)$ & \textrm{same as above} \\
\bottomrule
\end{tabular}
\caption{Comparison of algorithms on estimating quantum $\a$-R\'enyi entropies within additive error for different $\a$. Here the $\widetilde\cO$ notation omits $\log$ factors, $\gamma > 0$ is the lower bound of eigenvalues of a mixed state $\rho \in \CC^{d \times d}$, $\eta \coloneqq \frac{\tr(\rho^\a)^{-1}}{|1-\a|}$ is the quantity depending on $\a$ and $\rho$, and $\eps$ is the additive error of estimating $S_\a(\rho)$. QAE is short for quantum amplitude estimation.}\label{table:Renyi algs}
\end{table}

The polynomial transformation implemented by QSVT lies in amplitudes of the outcome state, which could not be obtained by indirect measurements of the ancilla qubit in QSVT, thus most QSVT-based entropies estimation algorithms estimate the value either by applying amplitude estimation or combining with the $\mathsf{DQC1}$ model, and both of these methods increase the circuit size. Another approach is using a polynomial to estimate the square root of the function $\sqrt{f(x)}$, as shown by~\citet{wang2022new}. This approach makes QSVT compatible with indirect measurements, since the approximated function now can be represented by the probability of measuring, which is similar as in QPP. However, the problem is that sometimes $\sqrt{f(x)}$ could be more difficult to approximate than $f(x)$. For example, $f(x) = x$ is just a simple one-term polynomial, whereas $\sqrt{f(x)} = \sqrt{x}$ takes much more terms to precisely approximate. Thus such a method presented in~\cite{wang2022new} may lead to even worse complexity than previous ones in~\cite{gilyen2020distributional, subramanian2021quantum, gur2021sublinear}. We defer further discussion and comparison to Appendix~\ref{appendix:entropy table}.

\section{Hamiltonian simulation} \label{sec:hamiltonian}
{This section aims to investigate the application of our phase processing circuits in simulating the dynamics of a quantum system. Unsurprisingly, our algorithms can reproduce the optimal results introduced in \cite{low2017optimal}.} {Specifically, for Hamiltonian $H$}, given evolution time $t$ and simulation error $\eps$, the goal is to simulate the time evolution $e^{-iHt}$ with error $\eps$, i.e.,\ produce a unitary $U$ such that $\norm{U - e^{-iHt}}\leq \eps$. {Usually}, this is accomplished by designing a quantum circuit to simulate the operator $e^{-iHt}$ with high precision. {In the setup, we assume a block encoding of the Hamiltonian, which is a commonly used input model appearing in \cite{low2019hamiltonian, chakraborty2019power,gilyen2019quantum}. Before presenting the results, we recall the definition of block encoding.}

\subsection{Block Encoding} \label{sec:block enc intro}

A block encoding of a matrix $A\in \CC^{2^n \times 2^n}$ with spectral norm $\norm{A} \leq 1$ is a unitary matrix $U_A$ such that the upper-left block of the matrix is $A$, i.e.\
\begin{equation}
A  & \cdot\\
\cdot & \cdot
\end{bNiceMatrix}.
\end{equation}
Then we can write $A = \left(\bra{0^{\otimes m}} \otimes I^{\otimes n}\right) U_A \left(\ket{0^{\otimes m}} \otimes I^{\otimes n}\right)$, where $m$ denotes the number of ancilla qubits in the block encoding. In other words, for any state $\ket{\psi} \in \CC^N$, we have $\left(\bra{0^{\otimes m}} \otimes I^{\otimes n}\right) U_A \ket{0^{\otimes m}, \psi} = A\ket{\psi}$. In particular, let $\ket{\psi_\lambda}$ be an eigenvector of $A$ with an eigenvalue $\lambda$, then we will have a state
\begin{align}
U_A \ket{0^{\otimes m},\psi_\lambda}=\lambda \ket{0^{\otimes m}, \psi_\lambda}+\sqrt{1-\lambda^2}\ket{\bot_\lambda},
\label{eqn:psi}
\end{align}
where $\ket{\bot_\lambda}$ denotes a state orthogonal to $\ket{0^{\otimes m}, \psi_\lambda}$. In the above equation, we absorb the relative phase into states and ignore the global phase. To associate the spectrum of $A$ and its block encoding $U$, it has to be ensured that the subspace $\opspan\{\ket{0^{\otimes m}, \psi_\lambda}, U \ket{0^{\otimes m}, \psi_\lambda}\}$ is invariant under $U_A$. However, this is generally not true for an arbitrary block encoding. To resolve this issue, \citet{low2019hamiltonian} proposed a so-called ``qubitization'' technique that uses controlled-$U_A$ and controlled-$U^\dagger_A$ once to implement a qubitized block encoding $\widehat{U}_A$ preserving the subspace $\opspan\{\ket{0^{\otimes (m+1)}, \psi_\lambda}, \widehat{U}_A \ket{0^{\otimes (m+1)}, \psi_\lambda}\}$. Write
\begin{equation} \label{eqn:qubitization for block encoding}
\widehat{U}_A \ket{0^{\otimes (m + 1)},\psi_\lambda}=\lambda \ket{0^{\otimes (m + 1)}, \psi_\lambda}+\sqrt{1-\lambda^2}\ket{\widehat{\bot}_\lambda},
\end{equation}
where $\ket{\widehat{\bot}_\lambda}$ denotes a state orthogonal to $\ket{0^{\otimes (m + 1)}, \psi_\lambda}$. Then
\begin{equation}
\ket{\c_\lambda^\pm} = \frac{1}{\sqrt{2}}( \ket{0^{\otimes (m + 1)}, \psi_\lambda} \pm i\ket{\widehat{\bot}_\lambda})
\end{equation}
are eigenstates of $\widehat{U}_A$ with eigenphases $\pm \tau_\lambda = \pm\arccos\lambda$. Now the spectrum of $A$ and that of $\widehat{U}_A$ are associated, which allows us to process and extract the spectrum of an arbitrary matrix $A$ by applying QPP on $\widehat{U}_A$. More details of qubitization are discussed in Appendix~\ref{appendix:qubitization intro}. In the next section, we will show how to use QPP to solve the Hamiltonian simulation problem.

\subsection{Hamiltonian simulation}

Suppose we have a block encoding $U_H=[\begin{smallmatrix} H/\Lambda & \cdot \\ \cdot & \cdot \end{smallmatrix}]$. With out loss of generality, we may assume $\norm{H} \leq 1$ and $\L = 1$, since for $\norm{H} > 1$ the problem can be considered as simulating evolution under the rescaled Hamiltonian $H/\L$ for time $\L t$. Recall that the qubitization establishes the relation between the eigenvalues of the Hamiltonian $H$ and eigenphases of its qubitized block encoding $\widehat{U}_H$, i.e.\ $\tau_\lambda = \arccos(\lambda)$. Since the time-evolution operator $e^{-iHt}$ can be decomposed as $e^{-i\lambda t}$, the main idea is to transform eigenphases of $\widehat{U}_H$ by Theorem \ref{thm:qpp evolution} as $\tau_\lambda \mapsto e^{-i\lambda t}$. We select a trigonometric polynomial $F(x)$ that approximates the function $f(x)=e^{-i\cos(x) t}$ with desired precision. Then applying the \tp{} $F(x)$ on each eigenphase $\tau_\lambda$ approximates
\begin{equation}
f(\tau_\lambda) = e^{-i\cos(\tau_\lambda) t} = e^{-i\lambda t},
\end{equation}
which provides a precise approximation of the time-evolution operator $e^{-iHt}$. The query complexity of Hamiltonian simulation is analyzed in the following theorem, and the detailed proof is deferred to Appendix~\ref{appendix:hamiltonian simulation}.

\begin{theorem}\label{thm:ham simulation complexity}
Given a block encoding $U_H$ of $H/\Lambda$ for some $\Lambda \geq \norm{H}$, there exists an algorithm that simulates evolution under the Hamiltonian $H$ for time $t \in \mathbb{R}$ within precision $\delta>0$, using two ancilla qubits and querying controlled-$U_H$ and controlled-$U_H^\dagger$ for a total number of times in \[\Theta\left(\Lambda|t|+\frac{\log(2/\delta^2)}{\log\left(e+\frac{\log(2/\delta^2)}{\Lambda|t|}\right)}\right).\]
\end{theorem}

{For remark, one could measure the ancilla qubit after applying our circuit, and the residual state is highly approximate to the desired state.} In this case, we can relax the function approximation error. The final state approximates the target state with an error of $\delta$, succeeding with a probability at least $1-2\delta$. {As a result}, the circuit depth can be reduced.

From the result, we conclude that QPP solves Hamiltonian simulation problems with the access to block encoding, and the query complexity matches the optimal results as in~\cite{low2019hamiltonian}. We notice that QPP could also solve other Hamiltonian problems like spectrum estimation, ground state energy estimation, and ground state preparation. We defer the discussion of those applications to Appendix \ref{appendix:hamiltonian simulation}.

\section{Concluding remarks}

In this paper, we introduce a new quantum phase processing (QPP) algorithmic toolbox based on applying trigonometric transformations to eigenphases of a unitary operator. The toolbox allows us to implement a desired evolution to the input state and, more interestingly, to extract the eigen-information of quantum systems by simply measuring the ancilla qubit. We demonstrate the capability of this toolbox by developing QPP-based algorithms for solving a variety of problems. Owing to the capability of QPP to directly process eigenphases, we design an efficient and intuitive phase estimation algorithm purely based on the idea of binary search, which uses only one ancilla qubit and matches the best prior performance. Utilizing block encoding and qubitization, we show that QPP could reproduce and even improve previous quantum algorithms based on the framework of QSVT, such as Hamiltonian simulation and quantum entropies estimation.

QPP generalizes the trigonometric QSP by extending the $R_z$ rotation instead of the reflection in the Chebyshev-based QSP as QSVT did, providing a new interpretation for lifting QSP to multiple qubits. Due to the common underlying logic between these two QSP conventions, it is unavoidable to find similarities between QPP and QSVT. However, due to the distinctions between trigonometric and Chebyshev-based QSP, our results show that QPP is a powerful toolbox for developing quantum algorithms related to eigenphase transformation and processing, which essentially complements the existing QSVT framework. On one hand, QPP implements arbitrary complex trigonometric polynomial, which overcomes the parity constraints in QSVT and thus exempts the use of linear-combination-of-unitaries in certain cases. On the other hand, QPP is natively compatible with indirect measurements, which could extract eigen-information of the main system via measuring the single ancilla qubit. Notably, QPP could work without amplitude estimation, which requires shorter circuits and less coherence time than QSVT, and hence might be more friendly to near-term quantum hardware.
QPP natively inherits the trick of phase kickback, and thus it is particularly suitable to develop phase-related quantum algorithms. Other than applications mentioned in this paper, QPP can be potentially applied to other problems, including but not limited to R\'enyi divergence estimation, unitary trace estimation, and quantum Monte Carlo method. Moreover, considering the connections between quantum signal processing and single-qubit quantum neural networks~\cite{perez-salinas2020data, yu2022power}, our results may lead to  applications of QSVT and QPP in the area of quantum machine learning. Overall, we believe that the QPP algorithmic toolbox would deepen our understanding of quantum algorithm design and shed light on the search for quantum applications in quantum physics, quantum chemistry, machine learning, and beyond.

\section*{Acknowledgement}
Part of this work was done when Y. W.,  L. Z., Z. Y. and X. W. were at Baidu Research.
Y. W. acknowledges support from the Baidu-UTS AI Meets Quantum project.
% The authors would like to thank Yuan Su for helpful comments.

%merlin.mbs apsrev4-1.bst 2010-07-25 4.21a (PWD, AO, DPC) hacked
%Control: key (0)
%Control: author (0) dotless jnrlst
%Control: editor formatted (1) identically to author
%Control: production of article title (0) allowed
%Control: page (1) range
%Control: year (0) verbatim
%Control: production of eprint (0) enabled
\begin{thebibliography}{60}%
\makeatletter
\providecommand \@ifxundefined [1]{%
\@ifx{#1\undefined}
\providecommand \@ifnum [1]{%
\ifnum #1\expandafter \@firstoftwo
\else \expandafter \@secondoftwo
\fi
\providecommand \@ifx [1]{%
\ifx #1\expandafter \@firstoftwo
\else \expandafter \@secondoftwo
\fi
\providecommand \natexlab [1]{#1}%
\providecommand \enquote  [1]{``#1''}%
\providecommand \bibnamefont  [1]{#1}%
\providecommand \bibfnamefont [1]{#1}%
\providecommand \citenamefont [1]{#1}%
\providecommand \href@noop [0]{\@secondoftwo}%
\providecommand \href [0]{\begingroup \@sanitize@url \@href}%
\providecommand \@href[1]{\@@startlink{#1}\@@href}%
\providecommand \@@href[1]{\endgroup#1\@@endlink}%
\providecommand \@sanitize@url [0]{\catcode `\\12\catcode `\$12\catcode
`\&12\catcode `\#12\catcode `\^12\catcode `\_12\catcode `\%12\relax}%
\providecommand \@@startlink[1]{}%
\providecommand \@@endlink[0]{}%
\providecommand \url  [0]{\begingroup\@sanitize@url \@url }%
\providecommand \@url [1]{\endgroup\@href {#1}{\urlprefix }}%
\providecommand \urlprefix  [0]{URL }%
\providecommand \Eprint [0]{\href }%
\providecommand \doibase [0]{http://dx.doi.org/}%
\providecommand \selectlanguage [0]{\@gobble}%
\providecommand \bibinfo  [0]{\@secondoftwo}%
\providecommand \bibfield  [0]{\@secondoftwo}%
\providecommand \translation [1]{[#1]}%
\providecommand \BibitemOpen [0]{}%
\providecommand \bibitemStop [0]{}%
\providecommand \bibitemNoStop [0]{.\EOS\space}%
\providecommand \EOS [0]{\spacefactor3000\relax}%
\providecommand \BibitemShut  [1]{\csname bibitem#1\endcsname}%
\let\auto@bib@innerbib\@empty
\bibitem [{\citenamefont {Shor}(1997)}]{shor1997polynomialtime}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Peter~W.}\
\bibnamefont {Shor}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Polynomial-{{Time Algorithms}} for {{Prime Factorization}} and {{Discrete
Logarithms}} on a {{Quantum Computer}}},}\ }\href {\doibase
10.1137/S0097539795293172} {\bibfield  {journal} {\bibinfo  {journal} {SIAM
J. Comput.}\ }\textbf {\bibinfo {volume} {26}},\ \bibinfo {pages}
{1484--1509} (\bibinfo {year} {1997})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Grover}(1996)}]{grover1996fast}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Lov~K.}\ \bibnamefont
{Grover}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {A fast quantum
mechanical algorithm for database search},}\ }in\ \href {\doibase
10.1145/237814.237866} {\emph {\bibinfo {booktitle} {Proceedings of the
Twenty-Eighth Annual {{ACM}} Symposium on {{Theory}} of {{Computing}}}}},\
\bibinfo {series and number} {{{STOC}} '96}\ (\bibinfo  {publisher}
{{Association for Computing Machinery}},\ \bibinfo {address} {{New York, NY,
USA}},\ \bibinfo {year} {1996})\ pp.\ \bibinfo {pages} {212--219}\BibitemShut
\bibitem [{\citenamefont {Lloyd}(1996)}]{lloyd1996universal}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Seth}\ \bibnamefont
{Lloyd}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Universal
{{Quantum Simulators}}},}\ }\href {\doibase 10.1126/science.273.5278.1073}
{\bibfield  {journal} {\bibinfo  {journal} {Science}\ }\textbf {\bibinfo
{volume} {273}},\ \bibinfo {pages} {1073--1078} (\bibinfo {year}
{1996})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Gily{\'e}n}\ \emph {et~al.}(2019)\citenamefont
{Gily{\'e}n}, \citenamefont {Su}, \citenamefont {Low},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Andr{\'a}s}\
\bibnamefont {Gily{\'e}n}}, \bibinfo {author} {\bibfnamefont {Yuan}\
\bibnamefont {Su}}, \bibinfo {author} {\bibfnamefont {Guang~Hao}\
\bibnamefont {Low}}, \ and\ \bibinfo {author} {\bibfnamefont {Nathan}\
\bibnamefont {Wiebe}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Quantum singular value transformation and beyond: Exponential improvements
for quantum matrix arithmetics},}\ }in\ \href {\doibase
10.1145/3313276.3316366} {\emph {\bibinfo {booktitle} {Proceedings of the
51st {{Annual ACM SIGACT Symposium}} on {{Theory}} of {{Computing}}}}}\
(\bibinfo {year} {2019})\ pp.\ \bibinfo {pages} {193--204},\ \Eprint
{http://arxiv.org/abs/1806.01838} {arXiv:1806.01838 [quant-ph]} \BibitemShut
\bibitem [{\citenamefont {Martyn}\ \emph {et~al.}(2021)\citenamefont {Martyn},
\citenamefont {Rossi}, \citenamefont {Tan},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {John~M.}\ \bibnamefont
{Martyn}}, \bibinfo {author} {\bibfnamefont {Zane~M.}\ \bibnamefont {Rossi}},
\bibinfo {author} {\bibfnamefont {Andrew~K.}\ \bibnamefont {Tan}}, \ and\
\bibinfo {author} {\bibfnamefont {Isaac~L.}\ \bibnamefont {Chuang}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {A {{Grand Unification}} of
{{Quantum Algorithms}}},}\ }\href {\doibase 10.1103/PRXQuantum.2.040203}
{\bibfield  {journal} {\bibinfo  {journal} {PRX Quantum}\ }\textbf {\bibinfo
{volume} {2}},\ \bibinfo {pages} {040203} (\bibinfo {year} {2021})},\ \Eprint
{http://arxiv.org/abs/2105.02859} {arXiv:2105.02859} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Rall}(2021)}]{rall2021faster}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Patrick}\ \bibnamefont
{Rall}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Faster {{Coherent
Quantum Algorithms}} for {{Phase}}, {{Energy}}, and {{Amplitude
Estimation}}},}\ }\href {\doibase 10.22331/q-2021-10-19-566} {\bibfield
{journal} {\bibinfo  {journal} {Quantum}\ }\textbf {\bibinfo {volume} {5}},\
\bibinfo {pages} {566} (\bibinfo {year} {2021})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Low}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Guang~Hao}\
\bibnamefont {Low}}\ and\ \bibinfo {author} {\bibfnamefont {Isaac~L.}\
\bibnamefont {Chuang}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Hamiltonian {{Simulation}} by {{Qubitization}}},}\ }\href {\doibase
10.22331/q-2019-07-12-163} {\bibfield  {journal} {\bibinfo  {journal}
{Quantum}\ }\textbf {\bibinfo {volume} {3}},\ \bibinfo {pages} {163}
(\bibinfo {year} {2019})},\ \Eprint {http://arxiv.org/abs/1610.06546}
{arXiv:1610.06546 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Lloyd}\ \emph {et~al.}(2021)\citenamefont {Lloyd},
\citenamefont {Kiani}, \citenamefont {{Arvidsson-Shukur}}, \citenamefont
{Bosch}, \citenamefont {De~Palma}, \citenamefont {Kaminsky}, \citenamefont
{Liu},\ and\ \citenamefont {Marvian}}]{lloyd2021hamiltonian}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Seth}\ \bibnamefont
{Lloyd}}, \bibinfo {author} {\bibfnamefont {Bobak~T.}\ \bibnamefont {Kiani}},
\bibinfo {author} {\bibfnamefont {David R.~M.}\ \bibnamefont
{{Arvidsson-Shukur}}}, \bibinfo {author} {\bibfnamefont {Samuel}\
\bibnamefont {Bosch}}, \bibinfo {author} {\bibfnamefont {Giacomo}\
\bibnamefont {De~Palma}}, \bibinfo {author} {\bibfnamefont {William~M.}\
\bibnamefont {Kaminsky}}, \bibinfo {author} {\bibfnamefont {Zi-Wen}\
\bibnamefont {Liu}}, \ and\ \bibinfo {author} {\bibfnamefont {Milad}\
\bibnamefont {Marvian}},\ }\href@noop {} {\enquote {\bibinfo {title}
{Hamiltonian singular value transformation and inverse block encoding},}\ }
(\bibinfo {year} {2021}),\ \Eprint {http://arxiv.org/abs/2104.01410}
{arXiv:2104.01410 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Martyn}\ \emph {et~al.}(2022)\citenamefont {Martyn},
\citenamefont {Liu}, \citenamefont {Chin},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {John~M.}\ \bibnamefont
{Martyn}}, \bibinfo {author} {\bibfnamefont {Yuan}\ \bibnamefont {Liu}},
\bibinfo {author} {\bibfnamefont {Zachary~E.}\ \bibnamefont {Chin}}, \ and\
\bibinfo {author} {\bibfnamefont {Isaac~L.}\ \bibnamefont {Chuang}},\
}\href@noop {} {\enquote {\bibinfo {title} {Efficient {{Fully-Coherent
Quantum Signal Processing Algorithms}} for {{Real-Time Dynamics
Simulation}}},}\ } (\bibinfo {year} {2022}),\ \Eprint
{http://arxiv.org/abs/2110.11327} {arXiv:2110.11327 [quant-ph]} \BibitemShut
\bibitem [{\citenamefont {Childs}\ \emph {et~al.}(2018)\citenamefont {Childs},
\citenamefont {Maslov}, \citenamefont {Nam}, \citenamefont {Ross},\ and\
\citenamefont {Su}}]{childs2018toward}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Andrew~M}\
\bibnamefont {Childs}}, \bibinfo {author} {\bibfnamefont {Dmitri}\
\bibnamefont {Maslov}}, \bibinfo {author} {\bibfnamefont {Yunseong}\
\bibnamefont {Nam}}, \bibinfo {author} {\bibfnamefont {Neil~J}\ \bibnamefont
{Ross}}, \ and\ \bibinfo {author} {\bibfnamefont {Yuan}\ \bibnamefont {Su}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {Toward the first quantum
simulation with quantum speedup},}\ }\href
{https://www.pnas.org/doi/abs/10.1073/pnas.1801723115} {\bibfield  {journal}
{\bibinfo  {journal} {Proceedings of the National Academy of Sciences}\
}\textbf {\bibinfo {volume} {115}},\ \bibinfo {pages} {9456--9461} (\bibinfo
{year} {2018})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Gily{\'{e}}n}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Andr{\'{a}}s}\
\bibnamefont {Gily{\'{e}}n}}\ and\ \bibinfo {author} {\bibfnamefont
{Tongyang}\ \bibnamefont {Li}},\ }\bibfield  {title} {\enquote {\bibinfo
{title} {Distributional property testing in a quantum world},}\ }in\ \href
{\doibase 10.4230/LIPIcs.ITCS.2020.25} {\emph {\bibinfo {booktitle} {11th
Innovations in Theoretical Computer Science Conference, {ITCS} 2020, January
12-14, 2020, Seattle, Washington, {USA}}}}\ (\bibinfo {year} {2020})\ pp.\
\bibinfo {pages} {25:1--25:19}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Subramanian}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sathyawageeswar}\
\bibnamefont {Subramanian}}\ and\ \bibinfo {author} {\bibfnamefont
{Min-Hsiu}\ \bibnamefont {Hsieh}},\ }\bibfield  {title} {\enquote {\bibinfo
{title} {Quantum algorithm for estimating $\ensuremath{\alpha}$-{{Renyi}}
entropies of quantum states},}\ }\href {\doibase 10.1103/PhysRevA.104.022428}
{\bibfield  {journal} {\bibinfo  {journal} {Physical Review A}\ }\textbf
{\bibinfo {volume} {104}},\ \bibinfo {pages} {022428} (\bibinfo {year}
{2021})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Gur}\ \emph {et~al.}(2021)\citenamefont {Gur},
\citenamefont {Hsieh},\ and\ \citenamefont {Subramanian}}]{gur2021sublinear}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Tom}\ \bibnamefont
{Gur}}, \bibinfo {author} {\bibfnamefont {Min-Hsiu}\ \bibnamefont {Hsieh}}, \
and\ \bibinfo {author} {\bibfnamefont {Sathyawageeswar}\ \bibnamefont
{Subramanian}},\ }\href {\doibase 10.48550/arXiv.2111.11139} {\enquote
{\bibinfo {title} {Sublinear quantum algorithms for estimating von
{{Neumann}} entropy},}\ } (\bibinfo {year} {2021}),\ \Eprint
{http://arxiv.org/abs/2111.11139} {arXiv:2111.11139 [quant-ph]} \BibitemShut
\bibitem [{\citenamefont {Gily{\'e}n}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Andr{\'a}s}\
\bibnamefont {Gily{\'e}n}}\ and\ \bibinfo {author} {\bibfnamefont
{Alexander}\ \bibnamefont {Poremba}},\ }\href@noop {} {\enquote {\bibinfo
{title} {Improved {{Quantum Algorithms}} for {{Fidelity Estimation}}},}\ }
(\bibinfo {year} {2022}),\ \Eprint {http://arxiv.org/abs/2203.15993}
{arXiv:2203.15993 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Lin}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Lin}\ \bibnamefont
{Lin}}\ and\ \bibinfo {author} {\bibfnamefont {Yu}~\bibnamefont {Tong}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {Near-optimal ground state
preparation},}\ }\href {\doibase 10.22331/q-2020-12-14-372} {\bibfield
{journal} {\bibinfo  {journal} {Quantum}\ }\textbf {\bibinfo {volume} {4}},\
\bibinfo {pages} {372} (\bibinfo {year} {2020})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Lin}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Lin}\ \bibnamefont
{Lin}}\ and\ \bibinfo {author} {\bibfnamefont {Yu}~\bibnamefont {Tong}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {Heisenberg-limited
ground-state energy estimation for early fault-tolerant quantum computers},}\
{\bibfield  {journal} {\bibinfo  {journal} {PRX Quantum}\ }\textbf {\bibinfo
{volume} {3}},\ \bibinfo {pages} {010318} (\bibinfo {year}
{2022})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Dong}\ \emph {et~al.}(2022)\citenamefont {Dong},
\citenamefont {Lin},\ and\ \citenamefont {Tong}}]{dong2022ground}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Yulong}\ \bibnamefont
{Dong}}, \bibinfo {author} {\bibfnamefont {Lin}\ \bibnamefont {Lin}}, \ and\
\bibinfo {author} {\bibfnamefont {Yu}~\bibnamefont {Tong}},\ }\bibfield
{title} {\enquote {\bibinfo {title} {Ground state preparation and energy
estimation on early fault-tolerant quantum computers via quantum eigenvalue
transformation of unitary matrices},}\ }\href
{https://arxiv.org/abs/2204.05955} {\bibfield  {journal} {\bibinfo  {journal}
{arXiv preprint arXiv:2204.05955}\ } (\bibinfo {year} {2022})}\BibitemShut
\bibitem [{\citenamefont {Low}\ \emph {et~al.}(2016)\citenamefont {Low},
\citenamefont {Yoder},\ and\ \citenamefont {Chuang}}]{low2016methodology}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Guang~Hao}\
\bibnamefont {Low}}, \bibinfo {author} {\bibfnamefont {Theodore~J.}\
\bibnamefont {Yoder}}, \ and\ \bibinfo {author} {\bibfnamefont {Isaac~L.}\
\bibnamefont {Chuang}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Methodology of {{Resonant Equiangular Composite Quantum Gates}}},}\ }\href
{\doibase 10.1103/PhysRevX.6.041067} {\bibfield  {journal} {\bibinfo
{journal} {Physical Review X}\ }\textbf {\bibinfo {volume} {6}},\ \bibinfo
{pages} {041067} (\bibinfo {year} {2016})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Low}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Guang~Hao}\
\bibnamefont {Low}}\ and\ \bibinfo {author} {\bibfnamefont {Isaac~L}\
\bibnamefont {Chuang}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Optimal hamiltonian simulation by quantum signal processing},}\ }\href
{\bibfield  {journal} {\bibinfo  {journal} {Physical review letters}\
}\textbf {\bibinfo {volume} {118}},\ \bibinfo {pages} {010501} (\bibinfo
{year} {2017})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Childs}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Andrew~M.}\
\bibnamefont {Childs}}\ and\ \bibinfo {author} {\bibfnamefont {Nathan}\
\bibnamefont {Wiebe}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Hamiltonian simulation using linear combinations of unitary operations},}\
}\href {\doibase 10.26421/QIC12.11-12-1} {\bibfield  {journal} {\bibinfo
{journal} {Quantum Inf. Comput.}\ }\textbf {\bibinfo {volume} {12}},\
\bibinfo {pages} {901--924} (\bibinfo {year} {2012})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Brassard}\ \emph {et~al.}(2002)\citenamefont
{Brassard}, \citenamefont {H{\o}yer}, \citenamefont {Mosca},\ and\
\citenamefont {Tapp}}]{brassard2002quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Gilles}\ \bibnamefont
{Brassard}}, \bibinfo {author} {\bibfnamefont {Peter}\ \bibnamefont
{H{\o}yer}}, \bibinfo {author} {\bibfnamefont {Michele}\ \bibnamefont
{Mosca}}, \ and\ \bibinfo {author} {\bibfnamefont {Alain}\ \bibnamefont
{Tapp}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Quantum amplitude
amplification and estimation},}\ }\href@noop {} {\bibfield  {journal}
{\bibinfo  {journal} {Contemporary Mathematics}\ }\textbf {\bibinfo {volume}
{305}},\ \bibinfo {pages} {53--74} (\bibinfo {year} {2002})}\BibitemShut
\bibitem [{\citenamefont {Berry}\ \emph {et~al.}(2014)\citenamefont {Berry},
\citenamefont {Childs}, \citenamefont {Cleve}, \citenamefont {Kothari},\ and\
\citenamefont {Somma}}]{berry2014exponential}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Dominic~W.}\
\bibnamefont {Berry}}, \bibinfo {author} {\bibfnamefont {Andrew~M.}\
\bibnamefont {Childs}}, \bibinfo {author} {\bibfnamefont {Richard}\
\bibnamefont {Cleve}}, \bibinfo {author} {\bibfnamefont {Robin}\ \bibnamefont
{Kothari}}, \ and\ \bibinfo {author} {\bibfnamefont {Rolando~D.}\
\bibnamefont {Somma}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Exponential improvement in precision for simulating sparse
{{Hamiltonians}}},}\ }in\ \href {\doibase 10.1145/2591796.2591854} {\emph
{\bibinfo {booktitle} {Proceedings of the Forty-Sixth Annual {{ACM}}
Symposium on {{Theory}} of Computing}}},\ \bibinfo {series and number}
{{{STOC}} '14}\ (\bibinfo  {publisher} {{Association for Computing
Machinery}},\ \bibinfo {address} {{New York, NY, USA}},\ \bibinfo {year}
{2014})\ pp.\ \bibinfo {pages} {283--292}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Haah}(2019)}]{haah2019product}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Jeongwan}\
\bibnamefont {Haah}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Product {{Decomposition}} of {{Periodic Functions}} in {{Quantum Signal
Processing}}},}\ }\href {\doibase 10.22331/q-2019-10-07-190} {\bibfield
{journal} {\bibinfo  {journal} {Quantum}\ }\textbf {\bibinfo {volume} {3}},\
\bibinfo {pages} {190} (\bibinfo {year} {2019})},\ \Eprint
{http://arxiv.org/abs/1806.10236} {arXiv:1806.10236} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Chao}\ \emph {et~al.}(2020)\citenamefont {Chao},
\citenamefont {Ding}, \citenamefont {Gilyen}, \citenamefont {Huang},\ and\
\citenamefont {Szegedy}}]{chao2020findinga}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Rui}\ \bibnamefont
{Chao}}, \bibinfo {author} {\bibfnamefont {Dawei}\ \bibnamefont {Ding}},
\bibinfo {author} {\bibfnamefont {Andras}\ \bibnamefont {Gilyen}}, \bibinfo
{author} {\bibfnamefont {Cupjin}\ \bibnamefont {Huang}}, \ and\ \bibinfo
{author} {\bibfnamefont {Mario}\ \bibnamefont {Szegedy}},\ }\href@noop {}
{\enquote {\bibinfo {title} {Finding {{Angles}} for {{Quantum Signal
Processing}} with {{Machine Precision}}},}\ } (\bibinfo {year} {2020}),\
\Eprint {http://arxiv.org/abs/2003.02831} {arXiv:2003.02831 [quant-ph]}
\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Yu}\ \emph {et~al.}(2022)\citenamefont {Yu},
\citenamefont {Yao}, \citenamefont {Li},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Zhan}\ \bibnamefont
{Yu}}, \bibinfo {author} {\bibfnamefont {Hongshun}\ \bibnamefont {Yao}},
\bibinfo {author} {\bibfnamefont {Mujin}\ \bibnamefont {Li}}, \ and\ \bibinfo
{author} {\bibfnamefont {Xin}\ \bibnamefont {Wang}},\ }\href@noop {}
{\enquote {\bibinfo {title} {Power and limitations of single-qubit native
quantum neural networks},}\ } (\bibinfo {year} {2022}),\ \Eprint
{http://arxiv.org/abs/2205.07848} {arXiv:2205.07848 [cond-mat,
physics:math-ph, physics:quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Kitaev}(1995)}]{kitaev1995quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {A.~Yu}\ \bibnamefont
{Kitaev}},\ }\href {\doibase 10.48550/arXiv.quant-ph/9511026} {\enquote
{\bibinfo {title} {Quantum measurements and the {{Abelian Stabilizer
Problem}}},}\ } (\bibinfo {year} {1995}),\ \Eprint
{http://arxiv.org/abs/quant-ph/9511026} {arXiv:quant-ph/9511026} \BibitemShut
\bibitem [{\citenamefont {Cleve}\ \emph {et~al.}(1998)\citenamefont {Cleve},
\citenamefont {Ekert}, \citenamefont {Macchiavello},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {R.}~\bibnamefont
{Cleve}}, \bibinfo {author} {\bibfnamefont {A.}~\bibnamefont {Ekert}},
\bibinfo {author} {\bibfnamefont {C.}~\bibnamefont {Macchiavello}}, \ and\
\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Mosca}},\ }\bibfield
{title} {\enquote {\bibinfo {title} {Quantum algorithms revisited},}\ }\href
{\doibase 10.1098/rspa.1998.0164} {\bibfield  {journal} {\bibinfo  {journal}
{Proceedings of the Royal Society of London. Series A: Mathematical, Physical
and Engineering Sciences}\ }\textbf {\bibinfo {volume} {454}},\ \bibinfo
{pages} {339--354} (\bibinfo {year} {1998})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Barenco}\ \emph {et~al.}(1997)\citenamefont
{Barenco}, \citenamefont {Berthiaume}, \citenamefont {Deutsch}, \citenamefont
{Ekert}, \citenamefont {Jozsa},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Adriano}\ \bibnamefont
{Barenco}}, \bibinfo {author} {\bibfnamefont {Andr{\'e}}\ \bibnamefont
{Berthiaume}}, \bibinfo {author} {\bibfnamefont {David}\ \bibnamefont
{Deutsch}}, \bibinfo {author} {\bibfnamefont {Artur}\ \bibnamefont {Ekert}},
\bibinfo {author} {\bibfnamefont {Richard}\ \bibnamefont {Jozsa}}, \ and\
\bibinfo {author} {\bibfnamefont {Chiara}\ \bibnamefont {Macchiavello}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {Stabilization of {{Quantum
Computations}} by {{Symmetrization}}},}\ }\href {\doibase
10.1137/S0097539796302452} {\bibfield  {journal} {\bibinfo  {journal} {SIAM
Journal on Computing}\ }\textbf {\bibinfo {volume} {26}},\ \bibinfo {pages}
{1541--1557} (\bibinfo {year} {1997})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Buhrman}\ \emph {et~al.}(2001)\citenamefont
{Buhrman}, \citenamefont {Cleve}, \citenamefont {Watrous},\ and\
\citenamefont {{de Wolf}}}]{buhrman2001quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Harry}\ \bibnamefont
{Buhrman}}, \bibinfo {author} {\bibfnamefont {Richard}\ \bibnamefont
{Cleve}}, \bibinfo {author} {\bibfnamefont {John}\ \bibnamefont {Watrous}}, \
and\ \bibinfo {author} {\bibfnamefont {Ronald}\ \bibnamefont {{de Wolf}}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {Quantum
{{Fingerprinting}}},}\ }\href {\doibase 10.1103/PhysRevLett.87.167902}
{\bibfield  {journal} {\bibinfo  {journal} {Physical Review Letters}\
}\textbf {\bibinfo {volume} {87}},\ \bibinfo {pages} {167902} (\bibinfo
{year} {2001})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Aharonov}\ \emph {et~al.}(2009)\citenamefont
{Aharonov}, \citenamefont {Jones},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Dorit}\ \bibnamefont
{Aharonov}}, \bibinfo {author} {\bibfnamefont {Vaughan}\ \bibnamefont
{Jones}}, \ and\ \bibinfo {author} {\bibfnamefont {Zeph}\ \bibnamefont
{Landau}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {A {{Polynomial
Quantum Algorithm}} for {{Approximating}} the {{Jones Polynomial}}},}\ }\href
{\doibase 10.1007/s00453-008-9168-0} {\bibfield  {journal} {\bibinfo
{journal} {Algorithmica}\ }\textbf {\bibinfo {volume} {55}},\ \bibinfo
{pages} {395--421} (\bibinfo {year} {2009})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Knill}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {E.}~\bibnamefont
{Knill}}\ and\ \bibinfo {author} {\bibfnamefont {R.}~\bibnamefont
{Laflamme}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Power of {{One
Bit}} of {{Quantum Information}}},}\ }\href {\doibase
10.1103/PhysRevLett.81.5672} {\bibfield  {journal} {\bibinfo  {journal}
{Physical Review Letters}\ }\textbf {\bibinfo {volume} {81}},\ \bibinfo
{pages} {5672--5675} (\bibinfo {year} {1998})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Petz}(1986)}]{Petz1986a}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {D{\'{e}}nes}\
\bibnamefont {Petz}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{{Quasi-entropies for finite quantum systems}},}\ }\href {\doibase
10.1016/0034-4877(86)90067-4} {\bibfield  {journal} {\bibinfo  {journal}
{Reports on Mathematical Physics}\ }\textbf {\bibinfo {volume} {23}},\
\bibinfo {pages} {57--65} (\bibinfo {year} {1986})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Silva}\ \emph {et~al.}(2022)\citenamefont {Silva},
\citenamefont {Borges},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Thais de~Lima}\
\bibnamefont {Silva}}, \bibinfo {author} {\bibfnamefont {Lucas}\ \bibnamefont
{Borges}}, \ and\ \bibinfo {author} {\bibfnamefont {Leandro}\ \bibnamefont
{Aolita}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Fourier-based
quantum signal processing},}\ }\href {\doibase 10.48550/arXiv.2206.02826} {\
(\bibinfo {year} {2022}),\ 10.48550/arXiv.2206.02826}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Dong}\ \emph {et~al.}(2021)\citenamefont {Dong},
\citenamefont {Meng}, \citenamefont {Whaley},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Yulong}\ \bibnamefont
{Dong}}, \bibinfo {author} {\bibfnamefont {Xiang}\ \bibnamefont {Meng}},
\bibinfo {author} {\bibfnamefont {K.~Birgitta}\ \bibnamefont {Whaley}}, \
and\ \bibinfo {author} {\bibfnamefont {Lin}\ \bibnamefont {Lin}},\ }\bibfield
{title} {\enquote {\bibinfo {title} {Efficient phase-factor evaluation in
quantum signal processing},}\ }\href {\doibase 10.1103/PhysRevA.103.042419}
{\bibfield  {journal} {\bibinfo  {journal} {Physical Review A}\ }\textbf
{\bibinfo {volume} {103}},\ \bibinfo {pages} {042419} (\bibinfo {year}
{2021})},\ \Eprint {http://arxiv.org/abs/2002.11649} {arXiv:2002.11649
[physics, physics:quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Grinko}\ \emph {et~al.}(2021)\citenamefont {Grinko},
\citenamefont {Gacon}, \citenamefont {Zoufal},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Dmitry}\ \bibnamefont
{Grinko}}, \bibinfo {author} {\bibfnamefont {Julien}\ \bibnamefont {Gacon}},
\bibinfo {author} {\bibfnamefont {Christa}\ \bibnamefont {Zoufal}}, \ and\
\bibinfo {author} {\bibfnamefont {Stefan}\ \bibnamefont {Woerner}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {Iterative quantum amplitude
estimation},}\ }\href {\doibase 10.1038/s41534-021-00379-1} {\bibfield
{journal} {\bibinfo  {journal} {npj Quantum Information}\ }\textbf {\bibinfo
{volume} {7}},\ \bibinfo {pages} {1--6} (\bibinfo {year} {2021})}\BibitemShut
\bibitem [{\citenamefont {Kitaev}\ \emph {et~al.}(2002)\citenamefont {Kitaev},
\citenamefont {Shen},\ and\ \citenamefont {Vyalyi}}]{kitaev2002classical}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {A.}~\bibnamefont
{Kitaev}}, \bibinfo {author} {\bibfnamefont {A.}~\bibnamefont {Shen}}, \ and\
\bibinfo {author} {\bibfnamefont {M.}~\bibnamefont {Vyalyi}},\ }\href
{\doibase 10.1090/gsm/047} {\emph {\bibinfo {title} {{Classical and Quantum
Computation}}}},\ \bibinfo {series} {Graduate Studies in Mathematics},
Vol.~\bibinfo {volume} {47}\ (\bibinfo  {publisher} {American Mathematical
Society},\ \bibinfo {address} {Providence, Rhode Island},\ \bibinfo {year}
{2002})\ p.\ \bibinfo {pages} {272}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Coppersmith}(1994)}]{Coppersmith1994}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {D}~\bibnamefont
{Coppersmith}},\ }\href@noop {} {\emph {\bibinfo {title} {{An approximate
fourier transform useful in quantum computing}}}},\ \bibinfo {type} {Tech.
Rep.}\ (\bibinfo {year} {1994})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Griffiths}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Robert~B.}\
\bibnamefont {Griffiths}}\ and\ \bibinfo {author} {\bibfnamefont {Chi-Sheng}\
\bibnamefont {Niu}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Semiclassical {{Fourier Transform}} for {{Quantum Computation}}},}\ }\href
{\doibase 10.1103/PhysRevLett.76.3228} {\bibfield  {journal} {\bibinfo
{journal} {Physical Review Letters}\ }\textbf {\bibinfo {volume} {76}},\
\bibinfo {pages} {3228--3231} (\bibinfo {year} {1996})},\ \Eprint
{http://arxiv.org/abs/quant-ph/9511007} {arXiv:quant-ph/9511007} \BibitemShut
\bibitem [{\citenamefont {Nielsen}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Michael~A}\
\bibnamefont {Nielsen}}\ and\ \bibinfo {author} {\bibfnamefont {Isaac~L}\
\bibnamefont {Chuang}},\ }\href@noop {} {\emph {\bibinfo {title} {{Quantum
computation and quantum information}}}}\ (\bibinfo  {publisher} {Cambridge
university press},\ \bibinfo {year} {2010})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Belovs}(2019)}]{belovs2019quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Aleksandrs}\
\bibnamefont {Belovs}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Quantum algorithms for classical probability distributions},}\ }\href
{https://arxiv.org/abs/1904.02192} {\bibfield  {journal} {\bibinfo  {journal}
{arXiv preprint arXiv:1904.02192}\ } (\bibinfo {year} {2019})}\BibitemShut
\bibitem [{\citenamefont {von Neumann}(1996)}]{von1932mathematische}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {John}\ \bibnamefont
{von Neumann}},\ }\href@noop {} {\emph {\bibinfo {title} {Mathematische
{Grundlagen} der {Quantenmechanik}}}},\ \bibinfo {edition} {2nd}\ ed.,\
\bibinfo {series} {Die {Grundlehren} der mathematischen {Wissenschaften} in
{Einzeldarstellungen}}\ No.~\bibinfo {number} {38}\ (\bibinfo  {publisher}
{Springer},\ \bibinfo {address} {Berlin Heidelberg},\ \bibinfo {year}
{1996})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {R{\'e}nyi}(1961)}]{renyi1961measures}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Alfr{\'e}d}\
\bibnamefont {R{\'e}nyi}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{On measures of entropy and information},}\ }in\ \href
{\emph {\bibinfo {booktitle} {Proceedings of the Fourth Berkeley Symposium on
Mathematical Statistics and Probability, Volume 1: Contributions to the
Theory of Statistics}}}\ (\bibinfo {organization} {University of California
Press},\ \bibinfo {year} {1961})\ pp.\ \bibinfo {pages}
{547--561}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Johri}\ \emph {et~al.}(2017)\citenamefont {Johri},
\citenamefont {Steiger},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Sonika}\ \bibnamefont
{Johri}}, \bibinfo {author} {\bibfnamefont {Damian~S.}\ \bibnamefont
{Steiger}}, \ and\ \bibinfo {author} {\bibfnamefont {Matthias}\ \bibnamefont
{Troyer}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Entanglement
spectroscopy on a quantum computer},}\ }\href {\doibase
10.1103/PhysRevB.96.195136} {\bibfield  {journal} {\bibinfo  {journal}
{Physical Review B}\ }\textbf {\bibinfo {volume} {96}},\ \bibinfo {pages}
{195136} (\bibinfo {year} {2017})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Subasi}\ \emph {et~al.}(2019)\citenamefont {Subasi},
\citenamefont {Cincio},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Yigit}\ \bibnamefont
{Subasi}}, \bibinfo {author} {\bibfnamefont {Lukasz}\ \bibnamefont {Cincio}},
\ and\ \bibinfo {author} {\bibfnamefont {Patrick~J.}\ \bibnamefont {Coles}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {Entanglement spectroscopy
with a depth-two quantum circuit},}\ }\href {\doibase
10.1088/1751-8121/aaf54d} {\bibfield  {journal} {\bibinfo  {journal} {Journal
of Physics A: Mathematical and Theoretical}\ }\textbf {\bibinfo {volume}
{52}},\ \bibinfo {pages} {044001} (\bibinfo {year} {2019})},\ \Eprint
{http://arxiv.org/abs/1806.08863} {arXiv:1806.08863 [cond-mat,
physics:quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Yirka}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Justin}\ \bibnamefont
{Yirka}}\ and\ \bibinfo {author} {\bibfnamefont {Yigit}\ \bibnamefont
{Subasi}},\ }\bibfield  {title} {\enquote {\bibinfo {title} {Qubit-efficient
entanglement spectroscopy using qubit resets},}\ }\href {\doibase
10.22331/q-2021-09-02-535} {\bibfield  {journal} {\bibinfo  {journal}
{Quantum}\ }\textbf {\bibinfo {volume} {5}},\ \bibinfo {pages} {535}
(\bibinfo {year} {2021})},\ \Eprint {http://arxiv.org/abs/2010.03080}
{arXiv:2010.03080 [quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Kerenidis}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Iordanis}\
\bibnamefont {Kerenidis}}\ and\ \bibinfo {author} {\bibfnamefont {Anupam}\
\bibnamefont {Prakash}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Quantum recommendation systems},}\ }\href {https://arxiv.org/abs/1603.08675}
{\bibfield  {journal} {\bibinfo  {journal} {arXiv preprint arXiv:1603.08675}\
} (\bibinfo {year} {2016})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Wang}\ \emph
{et~al.}(2022{\natexlab{a}})\citenamefont {Wang}, \citenamefont {Guan},
\citenamefont {Liu}, \citenamefont {Zhang},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Qisheng}\ \bibnamefont
{Wang}}, \bibinfo {author} {\bibfnamefont {Ji}~\bibnamefont {Guan}}, \bibinfo
{author} {\bibfnamefont {Junyi}\ \bibnamefont {Liu}}, \bibinfo {author}
{\bibfnamefont {Zhicheng}\ \bibnamefont {Zhang}}, \ and\ \bibinfo {author}
{\bibfnamefont {Mingsheng}\ \bibnamefont {Ying}},\ }\href@noop {} {\enquote
{\bibinfo {title} {New {{Quantum Algorithms}} for {{Computing Quantum
Entropies}} and {{Distances}}},}\ } (\bibinfo {year} {2022}{\natexlab{a}}),\
\Eprint {http://arxiv.org/abs/2203.13522} {arXiv:2203.13522 [quant-ph]}
\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Chakraborty}\ \emph {et~al.}(2019)\citenamefont
{Chakraborty}, \citenamefont {Gily{\'{e}}n},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Shantanav}\
\bibnamefont {Chakraborty}}, \bibinfo {author} {\bibfnamefont {Andr{\'{a}}s}\
\bibnamefont {Gily{\'{e}}n}}, \ and\ \bibinfo {author} {\bibfnamefont
{Stacey}\ \bibnamefont {Jeffery}},\ }\bibfield  {title} {\enquote {\bibinfo
{title} {The power of block-encoded matrix powers: Improved regression
techniques via faster hamiltonian simulation},}\ }in\ \href {\doibase
10.4230/LIPIcs.ICALP.2019.33} {\emph {\bibinfo {booktitle} {46th
International Colloquium on Automata, Languages, and Programming, {ICALP}
2019, July 9-12, 2019, Patras, Greece}}},\ \bibinfo {series} {LIPIcs}, Vol.\
\bibinfo {volume} {132}\ (\bibinfo  {publisher} {Schloss Dagstuhl -
Leibniz-Zentrum f{\"{u}}r Informatik},\ \bibinfo {year} {2019})\ pp.\
\bibinfo {pages} {33:1--33:14}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {{P{\'e}rez-Salinas}}\ \emph
{et~al.}(2020)\citenamefont {{P{\'e}rez-Salinas}}, \citenamefont
{{Cervera-Lierta}}, \citenamefont {{Gil-Fuster}},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Adri{\'a}n}\
\bibnamefont {{P{\'e}rez-Salinas}}}, \bibinfo {author} {\bibfnamefont {Alba}\
\bibnamefont {{Cervera-Lierta}}}, \bibinfo {author} {\bibfnamefont {Elies}\
\bibnamefont {{Gil-Fuster}}}, \ and\ \bibinfo {author} {\bibfnamefont
{Jos{\'e}~I.}\ \bibnamefont {Latorre}},\ }\bibfield  {title} {\enquote
{\bibinfo {title} {Data re-uploading for a universal quantum classifier},}\
}\href {\doibase 10.22331/q-2020-02-06-226} {\bibfield  {journal} {\bibinfo
{journal} {Quantum}\ }\textbf {\bibinfo {volume} {4}},\ \bibinfo {pages}
{226} (\bibinfo {year} {2020})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Rines}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Rich}\ \bibnamefont
{Rines}}\ and\ \bibinfo {author} {\bibfnamefont {Isaac}\ \bibnamefont
{Chuang}},\ }\href {\doibase 10.48550/arXiv.1801.01081} {\enquote {\bibinfo
{title} {High {{Performance Quantum Modular Multipliers}}},}\ } (\bibinfo
{year} {2018}),\ \Eprint {http://arxiv.org/abs/1801.01081} {arXiv:1801.01081
[quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Cho}\ \emph {et~al.}(2020)\citenamefont {Cho},
\citenamefont {Kim}, \citenamefont {Choi}, \citenamefont {Choi},\ and\
\citenamefont {Seo}}]{cho2020quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Seong-Min}\
\bibnamefont {Cho}}, \bibinfo {author} {\bibfnamefont {Aeyoung}\ \bibnamefont
{Kim}}, \bibinfo {author} {\bibfnamefont {Dooho}\ \bibnamefont {Choi}},
\bibinfo {author} {\bibfnamefont {Byung-Soo}\ \bibnamefont {Choi}}, \ and\
\bibinfo {author} {\bibfnamefont {Seung-Hyun}\ \bibnamefont {Seo}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {Quantum {{Modular
Multiplication}}},}\ }\href {\doibase 10.1109/ACCESS.2020.3039167} {\bibfield
{journal} {\bibinfo  {journal} {IEEE Access}\ }\textbf {\bibinfo {volume}
{8}},\ \bibinfo {pages} {213244--213252} (\bibinfo {year}
{2020})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Suzuki}\ \emph {et~al.}(2020)\citenamefont {Suzuki},
\citenamefont {Uno}, \citenamefont {Raymond}, \citenamefont {Tanaka},
\citenamefont {Onodera},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Yohichi}\ \bibnamefont
{Suzuki}}, \bibinfo {author} {\bibfnamefont {Shumpei}\ \bibnamefont {Uno}},
\bibinfo {author} {\bibfnamefont {Rudy}\ \bibnamefont {Raymond}}, \bibinfo
{author} {\bibfnamefont {Tomoki}\ \bibnamefont {Tanaka}}, \bibinfo {author}
{\bibfnamefont {Tamiya}\ \bibnamefont {Onodera}}, \ and\ \bibinfo {author}
{\bibfnamefont {Naoki}\ \bibnamefont {Yamamoto}},\ }\href {\doibase
10.1007/s11128-019-2565-2} {\enquote {\bibinfo {title} {Amplitude estimation
without phase estimation},}\ } (\bibinfo {year} {2020}),\ \Eprint
{http://arxiv.org/abs/1904.10246} {arXiv:1904.10246 [quant-ph]} \BibitemShut
\bibitem [{\citenamefont {Aaronson}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Scott}\ \bibnamefont
{Aaronson}}\ and\ \bibinfo {author} {\bibfnamefont {Patrick}\ \bibnamefont
{Rall}},\ }\href {\doibase 10.1137/1.9781611976014.5} {\enquote {\bibinfo
{title} {Quantum {{Approximate Counting}}, {{Simplified}}},}\ } (\bibinfo
{year} {2021}),\ \Eprint {http://arxiv.org/abs/1908.10846} {arXiv:1908.10846
[quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Rall}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Patrick}\ \bibnamefont
{Rall}}\ and\ \bibinfo {author} {\bibfnamefont {Bryce}\ \bibnamefont
{Fuller}},\ }\href@noop {} {\enquote {\bibinfo {title} {Amplitude
{{Estimation}} from {{Quantum Signal Processing}}},}\ } (\bibinfo {year}
{2022}),\ \Eprint {http://arxiv.org/abs/2207.08628} {arXiv:2207.08628
[quant-ph]} \BibitemShut {NoStop}%
\bibitem [{\citenamefont {Camps}\ \emph {et~al.}(2022)\citenamefont {Camps},
\citenamefont {Lin}, \citenamefont {Van~Beeumen},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Daan}\ \bibnamefont
{Camps}}, \bibinfo {author} {\bibfnamefont {Lin}\ \bibnamefont {Lin}},
\bibinfo {author} {\bibfnamefont {Roel}\ \bibnamefont {Van~Beeumen}}, \ and\
\bibinfo {author} {\bibfnamefont {Chao}\ \bibnamefont {Yang}},\ }\bibfield
{title} {\enquote {\bibinfo {title} {Explicit quantum circuits for block
encodings of certain sparse matrice},}\ }\href
{https://arxiv.org/abs/2203.10236} {\bibfield  {journal} {\bibinfo  {journal}
{arXiv preprint arXiv:2203.10236}\ } (\bibinfo {year} {2022})}\BibitemShut
\bibitem [{\citenamefont {Abramowitz}\ \emph {et~al.}(1988)\citenamefont
{Abramowitz}, \citenamefont {Stegun},\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Milton}\ \bibnamefont
{Abramowitz}}, \bibinfo {author} {\bibfnamefont {Irene~A}\ \bibnamefont
{Stegun}}, \ and\ \bibinfo {author} {\bibfnamefont {Robert~H}\ \bibnamefont
{Romer}},\ }\href
{\enquote {\bibinfo {title} {Handbook of mathematical functions with
formulas, graphs, and mathematical tables},}\ } (\bibinfo {year}
{1988})\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Berry}\ \emph {et~al.}(2015)\citenamefont {Berry},
\citenamefont {Childs},\ and\ \citenamefont {Kothari}}]{Berry2015}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Dominic~W.}\
\bibnamefont {Berry}}, \bibinfo {author} {\bibfnamefont {Andrew~M.}\
\bibnamefont {Childs}}, \ and\ \bibinfo {author} {\bibfnamefont {Robin}\
\bibnamefont {Kothari}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Hamiltonian simulation with nearly optimal dependence on all parameters},}\
\ }(\bibinfo  {publisher} {IEEE},\ \bibinfo {year} {2015})\ pp.\ \bibinfo
{pages} {792--809}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Abrams}\ and\ \citenamefont
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Daniel~S}\
\bibnamefont {Abrams}}\ and\ \bibinfo {author} {\bibfnamefont {Seth}\
\bibnamefont {Lloyd}},\ }\bibfield  {title} {\enquote {\bibinfo {title}
{Quantum algorithm providing exponential speed increase for finding
eigenvalues and eigenvectors},}\ }\href {\doibase
10.1103/PhysRevLett.83.5162} {\bibfield  {journal} {\bibinfo  {journal}
{Physical Review Letters}\ }\textbf {\bibinfo {volume} {83}},\ \bibinfo
{pages} {5162--5165} (\bibinfo {year} {1999})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Poulin}\ \emph {et~al.}(2018)\citenamefont {Poulin},
\citenamefont {Kitaev}, \citenamefont {Steiger}, \citenamefont {Hastings},\
and\ \citenamefont {Troyer}}]{PhysRevLett.121.010501}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {David}\ \bibnamefont
{Poulin}}, \bibinfo {author} {\bibfnamefont {Alexei}\ \bibnamefont {Kitaev}},
\bibinfo {author} {\bibfnamefont {Damian~S.}\ \bibnamefont {Steiger}},
\bibinfo {author} {\bibfnamefont {Matthew~B.}\ \bibnamefont {Hastings}}, \
and\ \bibinfo {author} {\bibfnamefont {Matthias}\ \bibnamefont {Troyer}},\
}\bibfield  {title} {\enquote {\bibinfo {title} {Quantum algorithm for
spectral measurement with a lower gate count},}\ }\href {\doibase
10.1103/PhysRevLett.121.010501} {\bibfield  {journal} {\bibinfo  {journal}
{Phys. Rev. Lett.}\ }\textbf {\bibinfo {volume} {121}},\ \bibinfo {pages}
{010501} (\bibinfo {year} {2018})}\BibitemShut {NoStop}%
\bibitem [{\citenamefont {Wang}\ \emph
{et~al.}(2022{\natexlab{b}})\citenamefont {Wang}, \citenamefont {Zhao},\ and\
\citenamefont {Wang}}]{wang2022quantum}%
\BibitemOpen
\bibfield  {author} {\bibinfo {author} {\bibfnamefont {Youle}\ \bibnamefont
{Wang}}, \bibinfo {author} {\bibfnamefont {Benchi}\ \bibnamefont {Zhao}}, \
and\ \bibinfo {author} {\bibfnamefont {Xin}\ \bibnamefont {Wang}},\
}\href@noop {} {\enquote {\bibinfo {title} {Quantum algorithms for estimating
quantum entropies},}\ } (\bibinfo {year} {2022}{\natexlab{b}}),\ \Eprint
{http://arxiv.org/abs/2203.02386} {arXiv:2203.02386 [quant-ph]} \BibitemShut
\end{thebibliography}%

% Supplementary Material

\clearpage

\appendix

\vspace{2cm}
\onecolumngrid
\vspace{2cm}

\begin{center}
\textbf{
\end{center}

\renewcommand{\theequation}{\thesection.\arabic{equation}}
\renewcommand{\thetheorem}{S\arabic{theorem}}
\renewcommand{\theproposition}{S\arabic{proposition}}
\renewcommand{\thelemma}{S\arabic{lemma}}
\renewcommand{\theremark}{S\arabic{remark}}
\renewcommand{\thecorollary}{S\arabic{corollary}}
\renewcommand{\thefigure}{S\arabic{figure}}
\renewcommand{\thetable}{S\arabic{table}}
\setcounter{equation}{0}
\setcounter{table}{0}
% \setcounter{section}{0}
\setcounter{proposition}{0}
\setcounter{lemma}{0}
\setcounter{corollary}{0}
\setcounter{figure}{0}
\setcounter{remark}{0}
% \setcounter{subsection}{0}
\setcounter{figure}{0}
\setcounter{table}{0}

In this supplementary material, we provide detailed analyses of results stated in this paper, and discuss some further applications of the QPP algorithmic toolbox.

\section{A brief summary of common QSP conventions}

\begin{table}[H]
\centering
\setlength{\tabcolsep}{1em}
\begin{tabular}{ccc}
\toprule
Conventions of QSP & QSP circuits & Type of polynomials \\
\midrule
\multirow{2}{*}{$W_x$~\cite{low2016methodology}}  & \multirow{2}{*}{\raisebox{-0.3\totalheight}{\includegraphics[width=0.26\textwidth]{figs/ZXZ_circuit.png}}} & \multirow{2}{*}{$\CC[x]$ with parity $L \bmod{2} $}  \\
\addlinespace
{} & {} & {and other constraints} \\
\midrule
\addlinespace
\multirow{2}{*}{Reflection~\cite{gilyen2019quantum}} & \multirow{2}{*}{\raisebox{-0.3\totalheight}{\includegraphics[width=0.25\textwidth]{figs/ZRZ_circuit.png}}} & \multirow{2}{*}{$\CC[x]$ with parity $L \bmod{2} $} \\
\addlinespace
{} & {} & {and other constraints} \\
\midrule
\addlinespace
\multirow{2}{*}{$W_z$~\cite{chao2020findinga, haah2019product}} &  \multirow{2}{*}{\raisebox{-0.3\totalheight}{\includegraphics[width=0.25\textwidth]{figs/XZX_circuit.png}}} & \multirow{2}{*}{$\RR[e^{ix/2}, e^{-ix/2}]$ with parity $L \bmod{2} $} \\
\addlinespace
{or, trigonometric} & {} & {} \\
\midrule
\addlinespace
\multirow{2}{*}{Improved} & \multirow{2}{*}{\raisebox{-0.3\totalheight}{\includegraphics[width=0.42\textwidth]{figs/YZZYZ_circuit.png}}} & \multirow{2}{*}{$\CC[e^{ix/2}, e^{-ix/2}]$ with parity $L \bmod{2} $}\\
\addlinespace
{trigonometric~\cite{yu2022power}} & {} & {} \\
\bottomrule
\end{tabular}
\caption{A table that summarizes the quantum circuits and the corresponding types of realizable polynomials retrieved by various conventions of QSP, where most of them were originally done by \citet{martyn2021grand} in their Appendix A.
Note that $W_x(x) \coloneqq \begin{bmatrix} x & i\sqrt{1-x^2}\,\, \\ i\sqrt{1-x^2} & x \end{bmatrix}$, $R(x) \coloneqq \begin{bmatrix} x & \sqrt{1-x^2}\,\, \\ \sqrt{1-x^2} & -x \end{bmatrix}$, and all polynomials are assumed to be normalized.}
\label{tab:qsp circuits}
\end{table}

As shown in Table~\ref{tab:qsp circuits}, the trigonometric QSP can use a single-qubit quantum system to make arbitrary transformation of a polynomial in $\CC[e^{ix/2}, e^{-ix/2}]$ with parity. However, since all normalized and square-integrable functions can be approximated by the polynomials in $\CC[e^{ix/2}, e^{-ix/2}]$ with parity $0$ i.e.\ the polynomials in $\CC[e^{ix}, e^{-ix}]$, the trigonometric QSP can be claimed to be parity-free.

\section{Theorems of Quantum Phase Processing}
% \subsection{Proof of Lemma~\ref{lem:trig_qsp}}\label{appendix:qsp_yzzyz}

% \renewcommand\thetheorem{\ref{thm:trig_qsp}}
% \setcounter{theorem}{\arabic{theorem}-1}
% \begin{theorem}
% There exists $\omega \in \RR$, $\bm\theta = (\theta_0, \theta_1, \ldots, \theta_L)\in \RR^{L+1}$ and $\bm\phi = (\phi_0, \phi_1, \ldots, \phi_L)\in \RR^{L+1}$ such that
% \begin{equation}\label{eqn:Trig form of QSP}
%     \UQSP(x) = \begin{bmatrix}
%         P(x) & -Q(x)\\
%         Q^*(x) & P^*(x)
%     \end{bmatrix}
% \end{equation}
% if and only if Laurent polynomials $P, Q \in \CC[e^{ix/2}, e^{-ix/2}]$ satisfy

% \begin{enumerate}
%     \item $\deg(P)\leq L$ and $\deg(Q) \leq L$,
%     \item $P$ and $Q$ have parity $L \bmod 2$,
%     \item $\forall x\in \RR$, $\abs{P(x)}^2 + \abs{Q(x)}^2 = 1$.
% \end{enumerate}
% \end{theorem}

% \begin{proof}
% First we prove the forward direction by induction on $L$. For the base case, if $L=0$, then $\UQSP(x) = R_z(\omega) R_y(\theta_0)R_z(\phi_0)$ gives $P = e^{-i(\omega + \phi_0)/2} \cos(\theta_0/2)$ and $Q = e^{-i(\omega - \phi_0)/2} \sin(\theta_0/2)$, which clearly satisfies the three conditions.

% For the induction step, suppose Eq.~\eqref{eqn:Trig form of QSP} satisfies the three conditions. Then
% \begin{align}
%     & \begin{bmatrix}
%             P & -Q\\
%             Q^* & P^*
%     \end{bmatrix}R_z(x) R_y(\theta_{k})R_z(\phi_{k})\\
%     &= \begin{bmatrix}
%         P & -Q\\
%         Q^* & P^*
%     \end{bmatrix}
%     \begin{bmatrix}
%         \cos\frac{\theta_k}{2}e^{-i\frac{\phi_k}{2}}e^{-i\frac{x}{2}} & -\sin\frac{\theta_k}{2}e^{i\frac{\phi_k}{2}}e^{-i\frac{x}{2}}\\
%         \sin\frac{\theta_k}{2}e^{-i\frac{\phi_k}{2}}e^{i\frac{x}{2}} & \cos\frac{\theta_k}{2}e^{i\frac{\phi_k}{2}}e^{i\frac{x}{2}}
%     \end{bmatrix}\\
%     &= \begin{bmatrix}
%         \cos\frac{\theta_{k}}{2}e^{-i\frac{\phi_k}{2}}e^{-i\frac{x}{2}} P - \sin\frac{\theta_{k}}{2}e^{-i\frac{\phi_k}{2}}e^{i\frac{x}{2}} Q & - \sin\frac{\theta_{k}}{2}e^{i\frac{\phi_k}{2}}e^{-i\frac{x}{2}} P-\cos\frac{\theta_{k}}{2}e^{i\frac{\phi_k}{2}}e^{i\frac{x}{2}} Q \\
%         \cos\frac{\theta_{k}}{2}e^{-i\frac{\phi_k}{2}}e^{-i\frac{x}{2}} Q^* + \sin\frac{\theta_{k}}{2}e^{-i\frac{\phi_k}{2}}e^{i\frac{x}{2}} P^* & \cos\frac{\theta_{k}}{2}e^{i\frac{\phi_k}{2}}e^{i\frac{x}{2}} P^* - \sin\frac{\theta_{k}}{2}e^{i\frac{\phi_k}{2}}e^{-i\frac{x}{2}} Q^*
%     \end{bmatrix}\\
%     &= \begin{bmatrix}
%         \bar{P} & -\bar{Q}\\
%         \bar{Q}^* & \bar{P}^*
%     \end{bmatrix}
% \end{align}
% where
% \begin{align}
%     \bar{P} &= \cos\frac{\theta_{k}}{2}e^{-i\frac{\phi_k}{2}}e^{-i\frac{x}{2}} P - \sin\frac{\theta_{k}}{2}e^{-i\frac{\phi_k}{2}}e^{i\frac{x}{2}} Q,\\
%     \bar{Q} &=  \sin\frac{\theta_{k}}{2}e^{i\frac{\phi_k}{2}}e^{-i\frac{x}{2}} P + \cos\frac{\theta_{k}}{2}e^{i\frac{\phi_k}{2}}e^{i\frac{x}{2}} Q
% \end{align}
% clearly satisfy the first condition $\deg(\bar{P}) = \deg(\bar{Q}) \leq L+1$. They also satisfy the second condition since multiplying by $e^{-ix/2}$ or $e^{ix/2}$ alters the parity. The third condition is satisfied because of unitarity.

% Next we show the backward direction by induction on $L$ that the three conditions suffice to construct QSP in Eq.~\eqref{eqn:Trig form of QSP}. First we consider the base case of $L=0$, we have $\deg(P)=\deg(Q)=0$, the above condition implies that $P = e^{-i(\omega + \phi_0)/2} \cos(\theta_0/2)$ and $Q = e^{-i(\omega - \phi_0)/2} \sin(\theta_0/2)$ for some $\omega, \theta_0,\phi_0\in\RR$. Thus the matrix
% \begin{equation}
%     \begin{bmatrix}
%         P & -Q,\\
%         Q^* & P^*
%     \end{bmatrix}
% \end{equation}
% can be written as a QSP circuit $\UQSP(x) = R_z(\omega) R_y(\theta_0)R_z(\phi_0)$.

% For the induction step, suppose Laurent polynomials $P$ and $Q$ satisfy the three conditions for some $L>0$. We first observe that condition 3 implies
% \begin{equation}\label{eqn:use condition 3}
%     \abs{P}^2 + \abs{Q}^2 = PP^* + QQ^* = 1,
% \end{equation}
% where $PP^* + QQ^*$ is a polynomial in $e^{ix/2}$ with parity $2n \bmod 2 = 0$.
% Since Eq.~\eqref{eqn:use condition 3} holds for all $x \in \RR$, the leading coefficients must satisfy $p_{d}p_{-d}^* + q_{d}q_{-d}^* = 0$ and $p_{d}^*p_{-d} + q_{d}^*q_{-d} = 0$, where $d \coloneqq \deg(P) = \deg(Q)$. By the first condition, we have $d \leq L$. We choose $\theta_k,\phi_k\in\mathbb{R}$ so that
% \begin{align}
%     \cos{\frac{\theta_k}{2}}e^{i\frac{\phi_k}{2}}p_{d}+\sin{\frac{\theta_k}{2}}e^{-i\frac{\phi_k}{2}}q_d &= 0,\\
%     -\sin{\frac{\theta_k}{2}}e^{i\frac{\phi_k}{2}}p_{-d}+\cos{\frac{\theta_k}{2}}e^{-i\frac{\phi_k}{2}}q_{-d} &= 0.
% \end{align}
% Now we briefly argue that there always exists $\theta_k$ and $\phi_k$ satisfy equations above. If all $p_d, p_{-d}, q_d, q_{-d}$ are not zero, simply let $\tan(\frac{\theta_k}{2})e^{-i\phi_k}=-\frac{p_d}{q_d}$. Then consider the case of zero coefficients. Since $\deg(P)=\deg(Q)=d$, at most two of $p_d, p_{-d}, q_d, q_{-d}$ could be 0. The fact $p_{d}p_{-d}^* + q_{d}q_{-d}^* = 0$ implies that one of one of $p_d, p_{-d}$ is 0 if and only if one of $q_d,q_{-d}$ is 0. If $p_d=q_d=0$ (or $ p_{-d}=q_{-d}=0$), pick $\theta_k$ and $\phi_k$ so that $\tan{(\frac{\theta_k}{2})}e^{i\phi_k} = \frac{q_{-d}}{p_{-d}}$. If $p_d = q_{-d}=0$ or ($p_{-d}=q_d=0$), pick $\theta_k$ so that $\sin{(\frac{\theta_k}{2})}=0$ (or $\cos{(\frac{\theta_k}{2})}=0$).

% Next, for the $\theta_k$ that we pick, consider
% \begin{align}
%     &\begin{bmatrix}
%         P & -Q\\
%         Q^* & P^*
%     \end{bmatrix}R_z^\dagger(\phi_{k})R_y^\dagger(\theta_{k})R_z^\dagger(x)\\
%     &= \begin{bmatrix}
%         e^{i\frac{\phi_k}{2}}\cos\frac{\theta_k}{2}e^{i\frac{x}{2}} P + e^{-i\frac{\phi_k}{2}}\sin\frac{\theta_k}{2}e^{i\frac{x}{2}} Q & e^{i\frac{\phi_k}{2}}\sin\frac{\theta_k}{2}e^{-i\frac{x}{2}} P-e^{-i\frac{\phi_k}{2}}\cos\frac{\theta_k}{2}e^{-i\frac{x}{2}} Q\\
%         e^{i\frac{\phi_k}{2}}\cos\frac{\theta_k}{2}e^{i\frac{x}{2}} Q^* - e^{-i\frac{\phi_k}{2}}\sin\frac{\theta_k}{2}e^{i\frac{x}{2}} P^* & e^{-i\frac{\phi_k}{2}}\cos\frac{\theta_k}{2}e^{-i\frac{x}{2}} P^* + e^{i\frac{\phi_k}{2}}\sin\frac{\theta_k}{2}e^{-i\frac{x}{2}} Q^*
%         \end{bmatrix}\label{eqn:matrixInduct}\\
%     &=\begin{bmatrix}
%         \widehat{P} & -\widehat{Q}\\
%         \widehat{Q}^* & \widehat{P}^*
%     \end{bmatrix}\label{eqn:matrixHat}
% \end{align}
% where
% \begin{align}
%     \widehat{P} &= e^{i\frac{\phi_k}{2}}\cos\frac{\theta_k}{2}e^{i\frac{x}{2}} P + e^{-i\frac{\phi_k}{2}}\sin\frac{\theta_k}{2}e^{i\frac{x}{2}} Q,\\
%     \widehat{Q} &= e^{-i\frac{\phi_k}{2}}\cos\frac{\theta_k}{2}e^{-i\frac{x}{2}} Q - e^{i\frac{\phi_k}{2}}\sin\frac{\theta_k}{2}e^{-i\frac{x}{2}} P.
% \end{align}
% Since $P,Q \in \CC[e^{ix/2}, e^{-ix/2}]$ are Laurent  polynomials with degree $d$, $\widehat{P} \in \RR[e^{ix/2}, e^{-ix/2}]$ might appear to be a Laurent  polynomial with degree $d+1$. In fact it has degree $\deg(\widehat{P})\leq d-1$, because the coefficient of $(e^{i\frac{x}{2}})^{d+1}$ term in $\widehat{P}$ is $\cos{\frac{\theta_k}{2}}e^{i\frac{\phi_k}{2}}p_{d}+\sin{\frac{\theta_k}{2}}e^{-i\frac{\phi_k}{2}}q_d=0$ by the selected $\theta_k$ and $\phi_k$, and the coefficients of $(e^{\frac{ix}{2}})^d$ term is 0 by condition 2. Similarly, $\widehat{Q}$ has leading coefficient $-\sin{\frac{\theta_k}{2}}e^{i\frac{\phi_k}{2}}p_{-d}+\cos{\frac{\theta_k}{2}}e^{-i\frac{\phi_k}{2}}q_{-d}=0$ and has degree $\deg(\widehat{Q})\leq d-1$. Since $d \leq L$, we have $\deg(\widehat{P}) = \deg(\widehat{Q}) \leq L-1$, hence condition 1 is satisfied. From the parity of $P$ and $Q$, it is easy to see that $\widehat{P}$ and $\widehat{Q}$ have parity $(L-1) \bmod{2}$, thus condition 2 is satisfied. Condition 3 follows from unitarity. Thus by the induction hypothesis, Eq.~\eqref{eqn:matrixHat} can be written as a QSP in the form of $\UQSP^{L-1}(x)$, and therefore the matrix
% \begin{equation}
%     \begin{bmatrix}
%         P & -Q\\
%         Q^* & P^*
%     \end{bmatrix}
% \end{equation}
% can be written as a QSP in the form of $\UQSP^{L}(x)$.
% \end{proof}
% \renewcommand{\thetheorem}{S\arabic{theorem}}

\subsection{Existence of Laurent complementary and angle finding }\label{appendix:angle finding}

% In this section we present a detailed analysis for derivation of the rotation angles in Figure~\ref{fig:qsp_circuit_yzzyz}.

% \begin{definition} [Terms for Laurent  polynomial]
% $P$ is a \textbf{Laurent  polynomial} in $\CC[e^{ix/2}, e^{-ix/2}]$ if there exists $L \in \NN$ and a set $\{p_j\}_{j=-L}^L \subset \CC$ such that
% \begin{equation}
%     P: x \mapsto \sum_{j=-L}^L p_j e^{i j x/2}
% .\end{equation}
% The \textbf{degree} of $P$ is defined as
% \begin{equation}
%     \deg (P) \coloneqq \max \{j \in \ZZ: |p_j| > 0 \,\,\forall j \neq 0\}
%  .\end{equation}
% The \textbf{complex conjugate} of $P$ is defined as
% \begin{equation}
%     P^*: x \mapsto \sum_{j=-L}^L p_j^* e^{-i j x/2}
% .\end{equation}

% For $\a \in \{0, 1\}$, $P$ has \textbf{parity} $\a$ if $p_j = 0$ for all $j \equiv \a \pmod 2$. Then $P$ is a \textbf{trigonometric series} if P has parity 0. Moreover, $Q$ is a \textbf{Fourier complementary} of a trigonometric series $P$ if $|P(x)|^2 + |Q(x)|^2 = 1$.
% \end{definition}

Other than the characterization of trigonometric QSP in Lemma~\ref{lem:trig_qsp}, we also need to specify the achievable trigonometric polynomials $P(x)$ for which there exists a corresponding $Q(x)$ satisfying the three conditions in Lemma~\ref{lem:trig_qsp}. First we prove the following lemma, using similar ideas of root finding from previous works~\cite{haah2019product, chao2020findinga, silva2022fourierbased}.

\begin{lemma} \label{lem:sqrt existence}
Suppose $A(x)$ is a non-negative real-valued \tp{}. Then there exists a Laurent polynomial $Q \in \CC[e^{ix/2}, e^{-ix/2}]$ such that $QQ^* = A$.
\end{lemma}
\begin{proof}
Denote $A(x) = \sum_{j=-2L}^{2L} a_j e^{i j x / 2}$. We can decompose $A$ by the set of $4L$ roots $\{\x_k\}_{k=1}^{4L}$ so that
\begin{equation}
A(x) = a_{2L} e^{-i L x} \prod_{k=1}^{4L} (e^{ix / 2} - \x_k),
\end{equation}
where $\{\x_k\}_{k=1}^{4L}$ can be efficiently found by computing all roots of a regular complex polynomial $g(\x) \coloneqq \sum_{j = 0}^{4L} a_{j - 2L} \x^{j}$. In particular, since $A$ is real and non-negative, these roots appear in inverse conjugate pairs i.e.\ $\{\x_k\}_{k=1}^{4L} = \{\x_k, \frac{1}{\x_k^*}\}_{k=1}^{2L}$. Then $A$ can be further simplified to
\begin{equation}
A(x) = a_{2L}e^{-i L x}\left[\prod_{k=1}^{2L} (e^{ix / 2} - \x_k)\right] \left[\prod_{k=1}^{2L}(e^{ix / 2} - \frac{1}{\x_k^*})\right]
From the fact $e^{ix / 2} - \x_k = -e^{ix / 2}\x_k(e^{-ix /2} - \frac{1}{\x_k})$, we have
\begin{equation}