Qubitization and Quantum Signal Processing

Qubitization turns a normalized encoding of a Hermitian operator into independent rotations in subspaces of dimension at most two, one for each eigenvalue. Quantum signal processing (QSP) interleaves that signal rotation with chosen phase rotations so that a matrix element of the resulting circuit realizes a bounded polynomial of the encoded eigenvalue. For Hamiltonian simulation, the polynomial approximates

$$f(x)=e^{-i\tau x}, \qquad \tau=\frac{\alpha t}{\hbar},$$

where $x=E/\alpha\in[-1,1]$ and $\alpha$ is the block-encoding normalization.

The resulting query complexity can be essentially linear in the magnitude of normalized time $|\tau|$ and nearly logarithmic in inverse error. That statement is conditional. It assumes coherent access to a suitable block encoding, its inverse and controlled variants; an admissible QSP polynomial; accurately synthesized phase angles; and a resource model that expands every oracle query into logical gates. A small query count does not make PREPARE, SELECT, arithmetic, data lookup, or fault tolerance inexpensive.

The derivation below follows a Hermitian signal walk through polynomial processing to evolution and spectral readout. Block Encodings and QSVT extends the construction to general projected maps and singular values.

Required background. Hamiltonian Simulation defines the target operation and its error metric; Algorithmic Primitives introduces coherent queries. The circuit model and matrix functions supply the matrix products and spectral calculus used here.

Normalized Hermitian signal encodings

Let $H=H^\dagger$ act on $n$ system qubits, and take the energy normalization $\alpha>0$. The target may be $e^{-iHt/\hbar}$, a controlled version, an evolved state, a correlator, or an energy estimate. These uses impose different phase, ancilla-success, and measurement requirements.

Block-encoding convention

Let

$$\Pi = \lvert0^a\rangle\langle0^a\rvert\otimes I.$$

A unitary $U_H$ is an $(\alpha,a,\delta_{\mathrm{BE}})$ block encoding of $H$ when

$$\left\| H- \alpha \left( \langle0^a\rvert\otimes I \right) U_H \left( \lvert0^a\rangle\otimes I \right) \right\|_{\mathrm{op}} \leq \delta_{\mathrm{BE}},$$

or, equivalently on the enlarged space,

$$\left\| \Pi \left(I_A\otimes H\right) \Pi - \alpha\Pi U_H\Pi \right\|_{\mathrm{op}} \leq \delta_{\mathrm{BE}}.$$

Here $I_A$ is the identity on the $a$-qubit ancilla register. This form makes the Hilbert spaces explicit: $H$ itself is not subtracted directly from an operator acting on ancilla plus system.

Because a compression of a unitary has norm at most one,

$$\alpha \geq \|H\|_{\mathrm{op}}-\delta_{\mathrm{BE}}.$$

For $H\ne0$, the ratio $\alpha/\|H\|$ measures normalization overhead. It is part of the algorithm, not a disposable constant.

Exact signal convention used below

To expose the geometry, first assume

$$\delta_{\mathrm{BE}}=0, \qquad U_H=U_H^\dagger, \qquad U_H^2=I.$$

Thus $U_H$ is a Hermitian involution whose selected block is $H/\alpha$. Many LCU encodings have this form. A general block encoding need not be Hermitian or involutory. Standard constructions can hermitianize or qubitize more general encodings by adding controls, an ancilla, and calls to $U_H$ and $U_H^\dagger$. Those constant-factor changes must be reflected in the actual query and gate counts. Exercise 1 constructs the required involution explicitly.

Linear-Combination Encoding

Suppose

$$H = \sum_{\ell=0}^{L-1}h_\ell P_\ell,$$

where $h_\ell\in\mathbb R$ and each $P_\ell$ is a Hermitian unitary, as for a Pauli string. Define

$$\lambda = \sum_{\ell=0}^{L-1}|h_\ell|.$$

For $\lambda=0$ the evolution is the identity. Otherwise omit zero coefficients and complete unused index labels with a Hermitian unitary such as $I$, rather than the nonunitary value $\operatorname{sgn}(0)=0$. The coefficient-state oracle PREPARE acts as

$$\operatorname{PREPARE}\lvert0^a\rangle = \lvert G\rangle = \sum_{\ell=0}^{L-1} \sqrt{\frac{|h_\ell|}{\lambda}} \lvert\ell\rangle.$$

The multiplexed operator SELECT is

$$\operatorname{SELECT} = \sum_{\ell=0}^{L-1} \lvert\ell\rangle\langle\ell\rvert \otimes \operatorname{sgn}(h_\ell)P_\ell.$$

The coefficient-state expectation of SELECT is $H/\lambda$, as derived in Hamiltonian Simulation.

In an all-zero ancilla convention,

$$U_H = \left( \operatorname{PREPARE}^\dagger\otimes I \right) \operatorname{SELECT} \left( \operatorname{PREPARE}\otimes I \right)$$

is an exact $(\lambda,a,0)$ block encoding. If every selected $P_\ell$ is a Hermitian involution, then SELECT and $U_H$ are also Hermitian involutions.

This construction explains both the power and the cost of the interface. Qubitization sees the compact parameters $\lambda$ and “one query.” The machine must prepare an amplitude distribution, look up or compute an index, apply a selected unitary, uncompute work registers, and often control the entire operation.

Normalization is representation dependent

The same physical Hamiltonian can have several LCU decompositions with different coefficient one-norms. Low-rank factorizations, basis choices, symmetry reductions, coefficient truncation, and tensor factorizations can reduce the oracle cost or $\lambda$, but may introduce approximation error. The relevant optimization target is not $\lambda$ alone:

$$\text{total cost} \sim d(\lambda|t|/\hbar,\epsilon) \times C_{\mathrm{query}}(\text{encoding}).$$

A decomposition with smaller normalization can lose if its PREPARE and SELECT circuits are much more expensive.

The Qubitized Invariant Plane

Define the reflection about the encoded subspace and the walk operator

$$R=2\Pi-I, \qquad W=RU_H.$$

Let

$$H\lvert E\rangle=E\lvert E\rangle, \qquad x_E=\frac{E}{\alpha}.$$

Lift the eigenstate into the encoded subspace:

$$\lvert g_E\rangle = \lvert0^a\rangle\lvert E\rangle.$$

Since the compression of $U_H$ to the encoded subspace represents $H/\alpha$,

$$\Pi U_H\lvert g_E\rangle = x_E\lvert g_E\rangle.$$

For $|x_E|<1$, define the normalized orthogonal state

$$\lvert b_E\rangle = \frac{ U_H\lvert g_E\rangle-x_E\lvert g_E\rangle }{ \sqrt{1-x_E^2} }.$$

It obeys

$$\Pi\lvert b_E\rangle=0, \qquad \langle g_E\vert b_E\rangle=0.$$

Write $s_E=\sqrt{1-x_E^2}$. The involution property gives

$$\begin{aligned} U_H\lvert g_E\rangle &= x_E\lvert g_E\rangle+s_E\lvert b_E\rangle, \\ U_H\lvert b_E\rangle &= s_E\lvert g_E\rangle-x_E\lvert b_E\rangle. \end{aligned}$$

Because $R$ is $+1$ on $\lvert g_E\rangle$ and $-1$ on $\lvert b_E\rangle$, the walk restricted to

$$\mathcal K_E = \operatorname{span} \left\{ \lvert g_E\rangle, \lvert b_E\rangle \right\}$$

has matrix

$$W\big|_{\mathcal K_E} = \begin{pmatrix} x_E & s_E\\ -s_E & x_E \end{pmatrix}.$$

Set

$$\theta_E=\arccos x_E, \qquad \theta_E\in[0,\pi].$$

Then $W$ is a planar rotation with eigenvalues

$$e^{\pm i\theta_E}.$$

One convenient pair of walk eigenstates is

$$\lvert w_{E,\pm}\rangle = \frac{ \lvert g_E\rangle \pm i\lvert b_E\rangle }{\sqrt2},$$

with

$$W\lvert w_{E,\pm}\rangle = e^{\pm i\theta_E} \lvert w_{E,\pm}\rangle.$$

This is qubitization: each eigenvalue $E$ of a large Hamiltonian becomes the rotation angle of an effective qubit. At $x_E=\pm1$, the orthogonal vector is undefined because the invariant plane collapses to one dimension; the phase relation continues by continuity with $\theta_E=0$ or $\pi$.

Convention warning

Some constructions use $U_HR$ instead of $RU_H$, choose $R=I-2\Pi$, or encode $x_E$ as $\sin\theta_E$ rather than $\cos\theta_E$. These conventions are equivalent after appropriate basis, sign, and phase changes, but their QSP phase lists are not interchangeable. A reproducible implementation must state the signal matrix, multiplication order, reflection sign, and phase-rotation convention.

Quantum Signal Processing

The invariant plane reduces the operator problem to controlled manipulation of one real signal $x\in[-1,1]$. A convenient signal matrix is

$$S(x) = \begin{pmatrix} x & i\sqrt{1-x^2}\\ i\sqrt{1-x^2} & x \end{pmatrix}.$$

On each invariant plane, this convention is related to the walk above by $S(x)=D^\dagger W D$, with $D=\operatorname{diag}(1,i)$. Thus the different off-diagonal phases amount to a fixed basis change.

For a real phase list

$$\boldsymbol\phi = (\phi_0,\phi_1,\ldots,\phi_d),$$

define

$$V_{\boldsymbol\phi}(x) = e^{i\phi_0Z} \prod_{j=1}^{d} \left[ S(x)e^{i\phi_jZ} \right].$$

Here the product is written with increasing $j$ from left to right: $e^{i\phi_0Z}S(x)e^{i\phi_1Z}\cdots S(x)e^{i\phi_dZ}$; the rightmost matrix acts first on a state. Each matrix element of $V_{\boldsymbol\phi}(x)$ is a polynomial in $x$ and $\sqrt{1-x^2}$ of degree at most $d$. In a standard form,

$$V_{\boldsymbol\phi}(x) = \begin{pmatrix} P(x) & iQ(x)\sqrt{1-x^2}\\ iQ^*(x)\sqrt{1-x^2} & P^*(x) \end{pmatrix}.$$

Unitarity imposes

$$|P(x)|^2 + (1-x^2)|Q(x)|^2 = 1$$

for real $x\in[-1,1]$. The degree and parity obey

$$\deg P\leq d, \qquad P(-x)=(-1)^dP(x),$$

For $d\ge1$, $Q$ has degree at most $d-1$ and the opposite parity; at $d=0$ it is zero. The exact reality and reciprocity conditions depend on the QSP convention.

Why arbitrary polynomial coefficients are not enough

A proposed polynomial is not implementable merely because its degree is small. It must satisfy:

1. the parity required by the sequence length;
2. boundedness or a unitary completion on $[-1,1]$;
3. the convention’s reality and endpoint conditions;
4. a numerically realizable phase factorization;
5. sufficient coefficient and angle precision.

If a target lacks definite parity, it can often be decomposed into even and odd parts and combined coherently, or implemented in an equivalent generalized QSP convention. Hamiltonian evolution is a canonical example:

$$e^{-i\tau x} = \cos(\tau x)-i\sin(\tau x),$$

where the real part is even and the imaginary part is odd. Also, in the bare sequence written above, unitarity forces $|P(\pm1)|=1$. The bounded, even polynomial $P(x)=1/2$ cannot itself be its entire upper-left response. Extracting a real component or using extra ancillas changes which polynomial can be the selected output.

An explicit degree-two response

For phases $(0,\phi,0)$, direct multiplication gives

$$\begin{aligned} P(x)&=\cos\phi\,(2x^2-1)+i\sin\phi,\\ Q(x)&=2x\cos\phi. \end{aligned}$$

Thus $\phi=\pi/3$ produces a real quadratic response together with a constant imaginary part. The latter supplies the unitary completion; it cannot simply be discarded. For an initial signal basis state $\lvert0\rangle$, the return probability is $|P(x)|^2$, while the probability of the complementary outcome is $(1-x^2)|Q(x)|^2$. This short sequence illustrates QSP admissibility; it is not a Hamiltonian-evolution approximation.

For $V(x)=S(x)e^{i\pi Z/3}S(x)$, the real part is $x^2-1/2$, the imaginary part is $\sqrt3/2$, and the return probability is $(x^2-1/2)^2+3/4$. Amplitude and probability are different functions. At $x=\pm1$ the return probability is one, as the bare-sequence endpoint condition requires.

Chebyshev interpretation

Write

$$x=\cos\theta.$$

Then

$$T_k(x)=\cos(k\theta),$$

so repeated signal rotations naturally generate Chebyshev modes. This is the link between single-qubit phase sequences and polynomial approximation on an entire Hamiltonian spectrum. QSP does not estimate $x$ and classically compute $f(x)$; it transforms all occupied spectral components coherently.

Hamiltonian Evolution as a Polynomial

The target normalized response is

$$f_\tau(x)=e^{-i\tau x}, \qquad \tau=\frac{\alpha t}{\hbar}.$$

Using $x=\cos\theta$, the Jacobi–Anger expansion gives

$$e^{-i\tau\cos\theta} = J_0(\tau) + 2\sum_{k=1}^{\infty} (-i)^kJ_k(\tau)\cos(k\theta),$$

or equivalently

$$e^{-i\tau x} = J_0(\tau) + 2\sum_{k=1}^{\infty} (-i)^kJ_k(\tau)T_k(x).$$

Here $J_k$ is a Bessel function of the first kind. Truncating at degree $d$ gives a uniform error bounded by the Bessel tail,

$$\epsilon_{\mathrm{poly}} \leq 2\sum_{k=d+1}^{\infty}|J_k(\tau)|.$$

This bounds the unconstrained series approximation. Its truncation can slightly exceed unit modulus, and contains both parities. A usable circuit must rescale or complete the appropriate components and combine them, including any amplification and ancilla-failure error. The Bessel-tail bound alone is not a full-circuit error guarantee.

The coefficients decay rapidly once $k$ exceeds the effective bandwidth set by $|\tau|$. This is why the degree grows approximately linearly with normalized time and only mildly with inverse precision.

Query-optimal degree

Let $T=\alpha|t|/\hbar$. For an exact block encoding, $T\ge1$ and $0<\epsilon<1/2$, the worst-case query complexity for an $\epsilon$-accurate block encoding of the evolution has the joint scaling (Gilyén and colleagues, Corollary 60)

$$Q = O\!\left[ T + \frac{ \log(1/\epsilon) }{ \log\!\left( e+\log(1/\epsilon)/T \right) } \right].$$

A simpler but weaker summary is

$$Q = O\!\left( T+\log(1/\epsilon) \right).$$

The first expression captures two limits:

• for long evolution at fixed precision, $Q=O(T)$;
• for very high precision at fixed nonzero $T$, the precision contribution is approximately $O(\log(1/\epsilon)/\log\log(1/\epsilon))$.

Under the standard block-encoding query model, matching lower bounds make the joint dependence query optimal up to constants. The denominator depends on both time and error; replacing it by $\log\log(1/\epsilon)$ outside the fixed-time limit is not justified. For very short times, $\lVert e^{-iHt/\hbar}-I\rVert\le T$, so $T\le\epsilon$ is already solved by doing nothing. Worst-case lower bounds do not become stronger merely because a particular implementation chooses an artificially large normalization.

What one query means

A degree-$d$ QSP sequence uses $O(d)$ calls to its signal operation, with the exact count depending on parity, completion, and whether the sequence alternates $W$ and $W^\dagger$. Each bare degree-$d$ sequence uses $d+1$ phase rotations; parity combination or amplification can add sequences and gates. Query optimality therefore says nothing yet about the elementary-gate cost of one walk call.

Worked Example: Two Pauli Terms

Consider

$$H=aX+bZ, \qquad a,b\in\mathbb R.$$

For $|a|+|b|>0$, an LCU encoding has

$$\lambda=|a|+|b|,$$

coefficient state

$$\lvert G\rangle = \sqrt{\frac{|a|}{\lambda}}\lvert0\rangle + \sqrt{\frac{|b|}{\lambda}}\lvert1\rangle,$$

and

$$\operatorname{SELECT} = \lvert0\rangle\langle0\rvert \otimes\operatorname{sgn}(a)X + \lvert1\rangle\langle1\rvert \otimes\operatorname{sgn}(b)Z.$$

The compression is $H/\lambda$. The physical eigenvalues are

$$E_\pm=\pm\Omega, \qquad \Omega=\sqrt{a^2+b^2},$$

and the qubitized walk phases obey

$$\cos\theta_\pm = \frac{E_\pm}{\lambda} = \pm\frac{\Omega}{\lambda}.$$

QSP targets

$$e^{-i\tau(E_\pm/\lambda)} = e^{-iE_\pm t/\hbar}, \qquad \tau=\frac{\lambda t}{\hbar}.$$

If $a$ and $b$ are both nonzero, then

$$\lambda>\Omega=\|H\|.$$

For $a=b\ne0$,

$$\frac{\lambda}{\|H\|} = \sqrt2.$$

The walk therefore processes a normalized time $\sqrt2$ larger than the minimum spectral scale would suggest. If one coefficient vanishes, the ratio becomes one and a direct Pauli rotation is already exact. Qubitization remains valid after assigning a unitary to any zero-weight SELECT branch, but a direct rotation is simpler. If $a=b=0$, use the identity without defining the coefficient state.

Direct Spectral Readout from the Walk

QSP is not the only use of the qubitized walk. Controlled phase estimation on $W$ can estimate $\theta_E$ directly, then recover

$$E=\alpha\cos\theta_E.$$

The lifted state is

$$\lvert g_E\rangle = \frac{ \lvert w_{E,+}\rangle + \lvert w_{E,-}\rangle }{\sqrt2}.$$

Phase estimation can therefore return either branch $+\theta_E$ or $-\theta_E$. Both give the same energy after applying cosine. For a small phase error $\delta\theta$,

$$\delta E \approx -\alpha\sin\theta_E\,\delta\theta,$$

and hence

$$|\delta E| \leq \alpha|\delta\theta|.$$

Direct walk-based phase estimation avoids first compiling a long-time exponential, but it still requires a trial-state overlap with the desired eigenstate, controlled walk powers, the correct walk/reflection convention, and enough coherent queries to resolve the energy. Cosine is $2\pi$ periodic, so no phase unwrapping is required for this energy conversion: either signed branch modulo $2\pi$ gives the same answer. The block normalization again sets the natural energy scale.

Approximate Encodings and Robustness

Suppose the selected block corresponds to a Hermitian effective Hamiltonian $\widetilde H$ with

$$\|H-\widetilde H\| \leq \delta_{\mathrm{BE}}.$$

Duhamel’s formula gives

$$\left\| e^{-iHt/\hbar} - e^{-i\widetilde Ht/\hbar} \right\| \leq \frac{|t|}{\hbar} \delta_{\mathrm{BE}}.$$

A general approximate block need not be Hermitian. Construct its Hermitian part as in Exercise 1 or apply a robust block-transformation theorem before invoking this generator bound. Hamiltonian Simulation gives an explicit non-Hermitian counterexample.

This contribution is separate from polynomial processing. If the realized signal query $\widetilde W$ satisfies

$$\|W-\widetilde W\|\leq\eta_W,$$

then a degree-$d$ sequence has the coarse telescoping bound

$$\epsilon_W \leq d\eta_W.$$

Likewise, if the $j$th phase rotation has operator error $\eta_{\phi,j}$,

$$\epsilon_\phi \leq \sum_{j=0}^{d}\eta_{\phi,j}.$$

Block error and coherent ancilla error

Let $J\lvert\psi\rangle=\lvert0^a\rangle\lvert\psi\rangle$, and let $\mathcal V$ be the complete ideal simulation circuit. The selected block is $K=J^\dagger\mathcal VJ$. If $\lVert K-U\rVert\le\epsilon_K$ for a target unitary $U$, then every input has success probability at least $(1-\epsilon_K)^2$ for $0\le\epsilon_K<1$. However, the stronger coherent requirement is

$$\lVert\mathcal VJ-JU\rVert\le\epsilon_{\mathrm{alg}},$$

which also controls amplitude in the unwanted ancilla subspace. In fact, $\lVert\mathcal VJ-JU\rVert\le\sqrt{2\epsilon_K}$ follows by expanding the squared norm and using $K=J^\dagger\mathcal VJ$. This square-root dependence cannot generally be improved; Exercise 8 attains it exactly. One can set a sufficiently small block tolerance or use the complete amplification theorem for the chosen construction. A successful postselection accuracy is a third, conditional statement and includes its success probability.

Once $\epsilon_{\mathrm{alg}}$ bounds the complete coherent implementation for the represented Hermitian $\widetilde H$, a consistent total estimate is

$$\epsilon_{\mathrm{coh}}\le \frac{|t|\delta_{\mathrm{BE}}}{\hbar} +\epsilon_{\mathrm{alg}}+N_W\eta_W +\sum_j\eta_{\phi,j}+\epsilon_{\mathrm{other}}.$$

Here $N_W$ counts all signal calls, including combination or amplification, and $\epsilon_{\mathrm{other}}$ covers additional coherent control/compilation errors. Avoid counting the same coefficient error both in $\delta_{\mathrm{BE}}$ and in the query perturbation. All terms must refer to the same ideal circuit and compatible norm. Logical failure probabilities and measurement uncertainty require their own output-level interpretation.

The cheapest allocation need not be equal: improving coefficient-state preparation can cost far more than improving an axial rotation. Optimize the implementation subject to the required total error, including ancilla behavior.

Phase Finding Is Part of the Algorithm

Polynomial design and phase finding are distinct classical tasks:

1. choose or compute an admissible polynomial approximating the target;
2. complete it to a unitary QSP response;
3. factor that response into phases $\boldsymbol\phi$;
4. verify the phases in the exact circuit convention to be used;
5. round or synthesize them to the allocated precision.

High-degree phase recovery can be numerically delicate. Root-based methods may require extended precision; optimization, Prony-like, fixed-point, and structured-factorization methods have improved the stable range. A claimed degree is not yet an executable circuit if no phase list has been generated and checked.

For a computed list, reconstruct the realized response on a dense spectral grid and, when a rigorous guarantee is required, supplement sampling with an interval or coefficient-based error certificate. Grid agreement alone can miss a narrow excursion between points.

Phase precision and non-Clifford cost

If $d+1$ arbitrary axial rotations each receive tolerance of order $\epsilon_\phi/(d+1)$, a representative fault-tolerant synthesis cost is

$$N_T^{(\phi)} = O\!\left[ d\log\!\left( \frac{d}{\epsilon_\phi} \right) \right],$$

up to synthesis method and gate-set constants. This can be smaller than the oracle cost, but it is not zero. Phase-gradient states, repeat-until-success methods, catalysis, or native logical rotations change these costs and must be included in the comparison.

Expanding Queries into Fault-Tolerant Resources

For the LCU construction,

$$C_{U_H} = C_{\mathrm{PREPARE}} +C_{\mathrm{SELECT}} +C_{\mathrm{PREPARE}^\dagger}.$$

One walk call also requires the reflection $R$. A degree-$d$ implementation therefore has a schematic logical cost

$$C_{\mathrm{QSP}} \approx d\left( C_{U_H}+C_R \right) +C_{\mathrm{phase}} +C_{\mathrm{control}} +C_{\mathrm{boundary}}.$$

The exact constants depend on whether the sequence uses $W$, $W^\dagger$, alternating phase conventions, parity completion, and postselection or oblivious amplification.

PREPARE

PREPARE may require:

• QROM or arithmetic for coefficient data;
• alias sampling or inequality tests;
• reversible normalization and square-root approximations;
• work registers that must be uncomputed;
• precision sufficient to meet $\delta_{\mathrm{BE}}$.

Its qubit and Toffoli costs can dominate. Treating an arbitrary coefficient state as one elementary gate is an oracle-model statement, not a physical resource estimate.

SELECT

SELECT may require:

• multiplexed Pauli strings or fermionic operations;
• address decoding and swaps;
• basis rotations and parity networks;
• reversible evaluation of sparse indices;
• additional controls for phase estimation.

Symmetry, low-rank factorization, unary iteration, and data layout can change both normalization and gate cost. The best encoding is therefore application and architecture dependent.

Reflection and controls

The reflection

$$R=2\Pi-I$$

is a multi-register phase conditioned on all block ancillas being zero. Its cost depends on available clean or dirty ancillas and the fault-tolerant gate set. If the QSP simulator will be controlled, the global phase convention and every oracle control must be implemented consistently; a phase that is global for the uncontrolled unitary becomes relative between control branches.

Ancilla accounting

QSP and qubitization need only a small number of signal-processing ancillas beyond the block encoding. This does not mean the complete algorithm uses a constant number of ancillas. PREPARE, SELECT, QROM, arithmetic, phase estimation, error correction, and magic-state factories can require many more.

Energy Shifts and Rescaling

For a known scalar $c$,

$$H=\left(H-cI\right)+cI$$

and

$$e^{-iHt/\hbar} = e^{-ict/\hbar} e^{-i(H-cI)t/\hbar}.$$

If shifting the identity reduces the available block normalization from $\alpha$ to $\alpha(c)$, it can reduce QSP degree. The scalar phase can be discarded for an uncontrolled channel, but must be restored for controlled evolution, interferometry, and absolute phase estimation.

The optimization should minimize the implemented cost

$$d\!\left( \frac{\alpha(c)|t|}{\hbar}, \epsilon \right) C_{\mathrm{query}}(c),$$

not merely the spectral radius of $H-cI$. An LCU decomposition may respond to the identity shift differently from an abstract optimal block encoding.

Comparison with Product Formulas

Product formulas and qubitization consume different access primitives.

Feature	Trotter–Suzuki	Qubitization and QSP
required access	exponentials of Hamiltonian terms	coherent block encoding, inverse, reflection, and controls
main structural parameter	nested commutators, locality, ordering	normalization $\alpha$ and query implementation cost
precision dependence	polynomial for fixed order	near-logarithmic query contribution
ancillas	often few	few signal ancillas, potentially many oracle work qubits
natural setting	local/native terms, moderate precision	fault-tolerant coherent access, high precision
chief practical risk	many term rotations and routed depth	expensive PREPARE/SELECT and controlled oracle expansion

Qubitization is compelling when a favorable block encoding is already known, its queries compile efficiently, and high coherent accuracy is valuable. Product formulas can win when local exponentials are native, commutators are sparse, precision is moderate, or coherent data access is expensive. The comparison must use the same Hamiltonian truncation, output, tolerance, architecture, and failure probability.

Trotter–Suzuki Methods develops the product-formula side of this comparison.

Checking the implemented response

For a small Hamiltonian, reconstruct the PREPARE/SELECT block, the walk’s invariant subspaces and eigenphases, and the complete phase sequence separately. Check coefficient signs, work-register cleanup, and the stated Hermitian and unitary assumptions. Include interior eigenvalues and $E=\pm\alpha$, where the signal plane becomes one-dimensional. The full walk can also have unused subspaces; compare the spectrum reached from the selected input, not every unrelated eigenvalue of the enlarged circuit.

Verify the realized polynomial’s parity, completion identity, and approximation error in the declared convention, both before and after angle rounding. Then compare the complete circuit against exact evolution, measuring ancilla leakage as well as the selected block. A grid can expose mistakes but needs a rigorous between-point bound for a uniform certificate.

Finally compare the requested state, observable, correlator, or energy with an independent calculation in a tractable regime. Preparation, success probability, and measurement uncertainty affect that prediction even when the signal-processing subroutine is correct.

Exercises

1. Construct a Hermitian involution

For any unitary $U$, introduce an extra qubit and define

$$V=\begin{pmatrix}0&U\\U^\dagger&0\end{pmatrix}.$$

Show that $V=V^\dagger$ and $V^2=I$. If the selected block of $U$ is $B$, what block results when the new qubit is selected in $\lvert+\rangle$?

Solution

Hermitian conjugation exchanges the two off-diagonal blocks, leaving $V$ unchanged. Squaring gives $\operatorname{diag}(UU^\dagger,U^\dagger U)=I$. Selecting the new qubit in $\lvert+\rangle$ gives $(U+U^\dagger)/2$, and selecting the original ancillas gives $(B+B^\dagger)/2$. Thus an exact Hermitian block is preserved. For a target $H=H^\dagger$,

$$\left\|\alpha\frac{B+B^\dagger}{2}-H\right\| \le\|\alpha B-H\|.$$

Hadamard gates convert the extra $\lvert+\rangle$ selection to an all-zero convention. The construction needs controlled access to $U$ and $U^\dagger$; the extra qubit does not make those operations free.

2. Derive the invariant-plane matrix

Starting from

$$U_H\lvert g\rangle=x\lvert g\rangle+s\lvert b\rangle, \qquad s=\sqrt{1-x^2},$$

and $U_H^2=I$, derive the action of $U_H$ on $\lvert b\rangle$ and the matrix of $W=RU_H$.

Solution

By definition,

$$s\lvert b\rangle = U_H\lvert g\rangle-x\lvert g\rangle.$$

Apply $U_H$ and use $U_H^2=I$:

$$\begin{aligned} sU_H\lvert b\rangle &= \lvert g\rangle-xU_H\lvert g\rangle \\ &= (1-x^2)\lvert g\rangle-xs\lvert b\rangle. \end{aligned}$$

Thus

$$U_H\lvert b\rangle = s\lvert g\rangle-x\lvert b\rangle.$$

Since $R\lvert g\rangle=\lvert g\rangle$ and $R\lvert b\rangle=-\lvert b\rangle$,

$$W = \begin{pmatrix} x&s\\ -s&x \end{pmatrix}$$

in the ordered basis $(\lvert g\rangle,\lvert b\rangle)$.

3. Recover energy from a walk phase

Suppose phase estimation returns $\widetilde\theta$ with a shortest circular angular distance at most $\delta_\theta$ from the true walk phase. Bound the resulting energy error for $\widetilde E=\alpha\cos\widetilde\theta$.

Solution

The mean-value theorem gives

$$|\widetilde E-E| = \alpha |\cos\widetilde\theta-\cos\theta_E| \leq \alpha\delta_\theta,$$

because $|\sin\theta|\leq1$. Locally,

$$\widetilde E-E = -\alpha\sin\theta_E (\widetilde\theta-\theta_E) +O(\delta_\theta^2).$$

At the endpoints $E=\pm\alpha$, the stronger bound is $|\widetilde E-E|\le\alpha\delta_\theta^2/2$, since $1-\cos u\le u^2/2$. This is a local improvement, not a uniform replacement for the linear bound across the spectrum. The same bounds apply to either signed branch modulo $2\pi$ because cosine is periodic and even.

4. Propagate block-encoding error

An approximate block encoding represents a Hermitian $\widetilde H$ with $\|H-\widetilde H\|\leq\delta$. For $t\ne0$, show that choosing

$$\delta\leq\frac{\hbar\epsilon}{4|t|}$$

allocates at most $\epsilon/4$ to the induced evolution error.

Solution

Duhamel’s formula and unitary invariance give

$$\left\| e^{-iHt/\hbar} -e^{-i\widetilde Ht/\hbar} \right\| \leq \frac{|t|}{\hbar} \|H-\widetilde H\|.$$

Substituting the proposed bound on $\delta$ yields

$$\frac{|t|}{\hbar}\delta \leq \frac{\epsilon}{4}.$$

5. Account for phase-rotation precision

A degree-$d$ sequence has $d+1$ phase rotations. If each realized rotation is within operator norm $\eta$ of its ideal value, give a sufficient per-rotation tolerance for a total phase-synthesis budget $\epsilon_\phi$.

Solution

A telescoping product bound gives

$$\epsilon_\phi \leq (d+1)\eta.$$

It is therefore sufficient to choose

$$\eta \leq \frac{\epsilon_\phi}{d+1}.$$

This uniform allocation is convenient, not necessarily cost optimal. Some angles may synthesize exactly or more cheaply than others.

6. Optimize a scalar shift

Explain why minimizing $\|H-cI\|$ need not minimize the fault-tolerant cost of qubitization. What must be compared instead?

Solution

The available block normalization $\alpha(c)$ need not equal $\|H-cI\|$. It depends on the chosen decomposition and data structure. The identity shift can also change PREPARE, SELECT, arithmetic, and phase-correction costs. The relevant comparison is therefore something like

$$d\!\left( \frac{\alpha(c)|t|}{\hbar}, \epsilon \right) C_{\mathrm{query}}(c) +C_{\mathrm{phase\ correction}}(c),$$

with the scalar phase restored whenever the simulation is controlled or used interferometrically.

7. Complete a real quadratic response

Multiply $S(x)e^{i\phi Z}S(x)$ to find $P$ and $Q$. Check unitarity for $\phi=\pi/3$. Why is the real part $x^2-1/2$ alone not the entire upper-left entry of a bare QSP sequence?

Solution

The diagonal entry is

$$P=e^{i\phi}x^2-e^{-i\phi}(1-x^2) =\cos\phi(2x^2-1)+i\sin\phi,$$

and $Q=2x\cos\phi$. At $\phi=\pi/3$, $Q=x$ and

$$|P|^2+(1-x^2)|Q|^2 =(x^2-1/2)^2+3/4+(1-x^2)x^2=1.$$

The real part alone has magnitude $1/2$ at both endpoints, contradicting $|P(\pm1)|=1$ for the full bare response. An additional interference or ancilla construction can select a real component, but it changes the circuit and its success behavior.

8. A small block error with larger coherent leakage

Let $0<\delta<1$ and let an ancilla rotation satisfy

$$R\lvert0\rangle=(1-\delta)\lvert0\rangle +\sqrt{2\delta-\delta^2}\,\lvert1\rangle.$$

Use $\mathcal V=R\otimes I$ to approximate the identity on the system. Find the selected-block error, success probability, and full encoded-state error. What block tolerance suffices for a coherent error $\epsilon$ in this example?

Solution

The selected block is $(1-\delta)I$, whose error from $I$ is $\delta$. Success has probability $(1-\delta)^2$; conditioned on success, the system state is exact. Before measuring the ancilla, the difference from $\lvert0\rangle\lvert\psi\rangle$ has squared norm

$$\delta^2+(2\delta-\delta^2)=2\delta.$$

Hence the coherent isometry error is $\sqrt{2\delta}$, for every normalized input. It is at most $\epsilon$ when $\delta\le\epsilon^2/2$. Block error, accepted-state error, failure probability, and coherent leakage are distinct accuracy statements even for this elementary circuit.

References

• D. W. Berry, C. Gidney, M. Motta, J. R. McClean, and R. Babbush, “Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization,” Quantum 3, 208 (2019), doi:10.22331/q-2019-12-02-208.
• Y. Dong, X. Meng, K. B. Whaley, and L. Lin, “Efficient Phase-Factor Evaluation in Quantum Signal Processing,” Physical Review A 103, 042419 (2021), doi:10.1103/PhysRevA.103.042419.
• A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, “Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics,” in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 193–204 (2019), doi:10.1145/3313276.3316366.
• J. Haah, “Product Decomposition of Periodic Functions in Quantum Signal Processing,” Quantum 3, 190 (2019), doi:10.22331/q-2019-10-07-190.
• L. Lin, “Lecture Notes on Quantum Algorithms for Scientific Computation,” arXiv:2201.08309 (2022), doi:10.48550/arXiv.2201.08309.
• G. H. Low and I. L. Chuang, “Optimal Hamiltonian Simulation by Quantum Signal Processing,” Physical Review Letters 118, 010501 (2017), doi:10.1103/PhysRevLett.118.010501.
• G. H. Low and I. L. Chuang, “Hamiltonian Simulation by Qubitization,” Quantum 3, 163 (2019), doi:10.22331/q-2019-07-12-163.
• G. H. Low, T. J. Yoder, and I. L. Chuang, “Methodology of Resonant Equiangular Composite Quantum Gates,” Physical Review X 6, 041067 (2016), doi:10.1103/PhysRevX.6.041067.
• J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, “Grand Unification of Quantum Algorithms,” PRX Quantum 2, 040203 (2021), doi:10.1103/PRXQuantum.2.040203.
• L. Ying, “Stable Factorization for Phase Factors of Quantum Signal Processing,” Quantum 6, 842 (2022), doi:10.22331/q-2022-10-20-842.