1 Introduction↩︎

Quantum phase estimation and quantum energy estimation algorithms (QPE and QEE) have been steadily developed in the circuit model since the 1990s [1], [2]. However, QEE-like problems were already considered in von Neumann’s measurement procedure [3], [4]. QEE with von Neumann’s method has fallen largely out of focus, with newer methods developed for digital quantum devices becoming more popular [5]–[8].

This work does not argue that von-Neumann’s measurement protocol based QEE (vN-QEE) can supersede existing methods. Instead, we show that it can be made competitive, meaning that the asymptotic query complexity is efficient for vN-QEE.

We then show how to efficiently implement QEE for any Hamiltonian given as a linear combination of Pauli strings. In doing so, we highlight that a simple, pedagogically accessible, and physically motivated QEE can still give efficient results for a large and highly relevant class of systems.

In the QPE problem, one assumes access to a unitary \(U=e^{iH}\) and a state preparation scheme for the eigenstate \(\ket{\lambda}\) of \(U\), corresponding to the eigenvalue \(e^{i\lambda}\). QPE is the problem of finding a \(\epsilon\)-accurate estimate of \(\lambda\), succeeding with success probability at least \(1-\delta\) for \(\delta\in(0, 1)\). QPE is closely related to QEE, the problem of finding the eigenstates of the generator \(H\). In QEE, \(H\) is typically accessed through a unitary block-encoding \(BE(H)\).

Block-encodings have quickly become a popular strategy for encoding data [9], [10]; they are convenient to manipulate using a family of templates for quantum computing: quantum signal processing (QSP), and quantum eigenvalue transformation (QET) [11], [12], and quantum singular value transformation (QSVT) [5]. Herein, we will use "QSP+" to refer to QSP/QET/QSVT, whenever the details of the template do not matter.

We show that in combination with efficient Hamiltonian evolution implemented in QSP+, vN-QEE can be a simple, efficient algorithm whenever a bound on the gap between the eigenstate of interest and others is known. Key to this statement is demonstrating that the coupling of the pointer and system of interest introduces only a logarithmic complexity overhead. Then, QSP+ techniques can be used to efficiently encode an approximation of the eigenstate in the pointer system. We then use a result from [5] to derive a QPE routine as a corollary of our main theorem.

It is expected that system-specific parameters will determine the costs of a QEE or QPE algorithm, namely the system dimension \(2^n\), \(n\in\mathbb{I}_{\geq 0}\), the spectral gap \(\Delta_0\), and the spectral norm \(\alpha\). In particular, to resolve eigenstates QEE typically requires \(\epsilon_{vN}<|\lambda_k-\lambda_{j\neq k}|\) and so expected to be \(\alpha, n\) dependent. The exact relationship between \(n, \Delta_0, \alpha\) has been studies both in asymptotic limits [13], [14] and with quantitative studies [15]–[17].

Our QEE algorithm scales optimally, with \(\mathcal{O}(\frac{\alpha}{\epsilon}\log_2(\delta^{-1}))\) in 1. However, 1 demonstrates that our algorithm is logarithmically sub-optimal in the QPE case [18]. A fuller comparison can be found in 1.1 and 1.

In 2, we review basic facts about block-encodings and QSP+. Likewise, in 3 we review the von Neumann measurement protocol and show how either the pointer system or the time-evolution can be used to mediate QEE precision. In 4, we give the main results of this work: a QEE algorithm using QSP+ Hamiltonian simulation and complexity bounds. In all settings, creating oracle access to \(H\otimes P\) introduces only a small overhead.

1 is the result of the most practical interest: we give Clifford plus \(T\) gate complexities and depths for QEE, for any Hamiltonian given as a linear combination of Pauli strings. The depth and ancilla requirements of such a preparation are well understood from [19]. The query complexity of 1 is stated with respect to only the accuracy of the QEE and physically meaningful Hamiltonian parameters. Although this is really a synthesis of existing block-encoding complexities, Hamiltonian simulation, and QPE protocols, our argument demonstrates that a large and highly relevant class of Hamiltonians admit efficient QEE and QPE algorithms.

1.1 Related work↩︎

Quantum phase estimation algorithms almost all follow the same high-level strategyencode an estimate of \(\lambda\) on \(r\) ancillary qubits using controlled powers of \(U\) applied on a superposition of computational basis states in the circuit model (more generally, a superposition of position basis states).

In recent years, strong techniques for problems related to either QEE and QPE have been developed [6]–[8], [20]–[22]. Many also apply to the standard QEE/QPE so we will discuss them herein.

We summarize the relevant literature and our algorithms in 1. To simplify the exposition, we will assume that all sub-normalizations are equal to the spectral norm. The most important distinction is that we assume that the overlap between the initial state and the desired eigenstate, \(\braket{\lambda|\psi_0}\geq \gamma\), is exponentially close to one. More specifically, we assume \(\gamma=1-\mathcal{O}(2^{-n})\). Our algorithm would require \(\mathcal{O}(\gamma^{-2})\) trials to succeed with a smaller \(\gamma\), from the same argument given to bound the necessary number of trials with standard QPE [20], [23].

Finally we will focus on coherent algorithms in this work. In a coherent algorithm, the entire protocol runs on a quantum device and then one measurement of \(r\) qubits occurs at the end of the computation. Crucially, the definition only applies when \(\gamma\rightarrow 1\) and ignores the costs of running many trials to increase the success probability. Kitaev’s phase estimation [1] or Rall’s QSVT-based algorithms [8] can both be implemented non-coherently with \(\mathcal{O}(1)\) qubits. Additionally, [6] can be used for ground state problems.

Leading QPE algorithms use QSP+ subroutines like spectral amplification[5], [22], eigenstate filtering [6], or prepare a specialized oracle that allows for a Kitaev-like algorithm [8]. Because good expositions of the algorithms in 1 can be found elsewhere (especially [6], [21], [23]), we do not discuss each algorithm in depth.

We compare the algorithms for \(\gamma\rightarrow 1\), meaning for the standard QPE or QEE problem. More generally, our algorithm will have subpar \(\gamma\) scaling, and will not be competitive with [7], [20], [21].

1 has competitive scaling with QSVE [5], [22] and QSVT coherent [8]. It is unclear at an asymptotic level which algorithm will better succeed for some given problems, as \(\alpha, \eta\) are not fully equivalent criteria. However, compared to the lower bound [18], and the QSVT algorithm proposed in [8], vN-QPE (1) is logarithmically weaker. If we relax the assumption \(\gamma\approx 1\), then [20] will still have the best complexity scaling with respect to the overlap.

Finally, note that one could derive QPE algorithms from QEE algorithms using 2 from [5], similarly to our 1. However, this would not change the comparison in this section.

2 Preliminaries↩︎

Encoding Hamiltonians in unitary matrices with a larger rank has become standard in quantum algorithms. In QSP+, one encodes the input Hamiltonian and then creates the signal operator, an oracle which is called in each step of the QSP+ protocol.

We will use a slight generalization from the standard definition of a block-encoding¹

By \(\bra{G}BE(H)\ket{G}\), we mean a projection to \(\ket{G}\) and then a partial trace over the \(n_{anc}\) ancillary qubits, that is \(\text{Tr}_{n_{anc}}\left[I_{s} \ket{G}\bra{G}\otimes I_{s}BE(H)\right]\). Below, we will always assume that \(\beta\geq \left|\left|H\right|\right|_{op}\).

In QET, one needs to use block-encodings with a particular property, namely the qubitized standard-form encoding introduced in [11] whose construction is given in 6. A key feature of qubitized block-encodings is that they have eigenvalues of the form² \(e^{\pm i\arcsin(\lambda/\beta)},\) where \(\lambda\) are the eigenvalues of \(H\) [11].

We will consider two ways to create a block-encoding for a given Hamiltonian: either access to the Pauli decomposition of the Hamiltonian or the ability to prepare the unitary oracle \(e^{iH}\).

One can efficiently prepare a block-encoding of \(H\) from \(U\), using a protocol from [5], reproduced in 2. This will allow for the QEE protocol defined in 1 to also solve the QPE problem.

We also consider QEE bounds starting from one of the most common representations of time-independent Hamiltonians, the linear combination of Pauli strings (LCP) \[H=\sum_{l}\alpha_lP_l.\] Above, \(P_l\) is any element in the Pauli basis for \(U(n)\), there are a total of \(\left|P\right|\) terms, and \(\alpha=\sum_l|\alpha_l|\). Note that \(\alpha\) bounds the norm of \(H\). We denote the operator norm of the matrix with \(\left|\left|H\right|\right|_{op}\), which for Hermitian matrices has the simpler forms such as the spectral norm.

Every fermionic quantum system has such a decomposition; spin systems are often represented in this form, and there exist techniques to find the Pauli decomposition of Hermitian matrices [24]–[26]. In many quantum simulation settings, the the number of Pauli terms required to encode \(H\) directly dictates how difficult the system will be to simulate. So, there are strong physical motivations to work with LCP’s.

From [19], one can encode a LCP in a block-encoding with an efficient cost in Clifford and \(T\) gates. Clifford and \(T\) gates are the set of the generators of the Clifford group along with the \(T\) gate; We denote it \(\mathcal{G}_{CpT}\). \(\mathcal{G}_{CpT}\) is approximately universal in the sense of the Solovey-Kitaev theorem [2] and reasonably common, especially for resource theories [27]–[29] and fault-tolerant implementations [30], [31].

2.1 QSP+↩︎

The task of QSP is to perform the following action on some unitary \[\begin{align} U&=\sum e^{\pm i\arccos(\lambda)} \ket{\lambda}\bra{\lambda}\rightarrow \nonumber\\ \bra{a_{QSP}}&U_{QSP}\ket{a_{QSP}}=P(U)\\ &=\sum P(e^{\pm i\arccos(\lambda)}) \ket{\lambda}\bra{\lambda}. \end{align}\] Where \(\ket{a_{QSP}}\) is a basis measurement on the QSP rotation qubit, usually selected as \(\ket{+}\) or \(\ket{0}\).

The task of QET is to apply \(P\) to the eigenvalues of a Hermitian operator accessed within a qubitized block-encoding, that is \[\begin{align} H&=\bra{G'}SBE(H)\ket{G'}\rightarrow\\ P(H)&=\bra{G',a_{QET}}U_{QET}\ket{G',a_{QET}}. \end{align}\] where \(\ket{G'}\bra{G'}\) is the projector which selects \(H\) within the qubitized block-encoding.

QSP+ circuit and theorems are well-known elsewhere for various conditions on the polynomial \(P\) [5], [11], [12], [32]–[34], we review QET in more detail in 7. We consider QSP+ with Laurent polynomials with total degree \(d\), obeying the following

1. \(P: \mathbb{C}\rightarrow \mathbb{C}, \quad \forall z\in U(1), \quad \left|\left|P\right|\right|_{\infty}\leq 1\)

2. \(\text{Re}(P)(z)=\pm \text{Re}(P)(z^{-1})\) and \(\text{Im}(P)(z)=\pm \text{Im}(P)(z^{-1})\) for all \(z\in U(1)\)

3. \(P(z)\) is \(\epsilon_{approx}\)-close in the \(l_\infty\)-norm to some function \(f\).

These polynomials fulfill the conditions for QSP and QET as are found in [11], [33]. With Laurent polynomials of degree \(d\), the QET circuit requires \(2d\) controlled operations of the signal operator and \(2d+1\) single-qubit rotation gates, the signal processing operators.

Say that the initial state has some decomposition in the eigenbasis of the Hamiltonian, \(\sum c_j\ket{\lambda_j}\otimes \ket{G'}\), \(\sum_j c_j=1\). For such initial states, the QET circuit prepares \[\sum_jc_j{P'\left(\frac{\lambda_j}{\alpha}\right)}\ket{\lambda_j}\ket{G',a_{QET}}+\ket{\psi_{QET}^{\perp}}.\] The probability of obtaining the desired branch of the state upon measurement is \[\left|{\sum_jc_j{P'\left(\frac{\lambda_j}{\alpha}\right)}}\right|^{2}\label{eq:qspsuccprob}\tag{1}\]

3 von Neumann measurement scheme↩︎

In von Neumann’s measurement scheme, the system Hamiltonian is coupled to a free particle with momentum \(p\), so the full Hamiltonian is \[H(s)\otimes \vec{p}.\] Once one assumes that the particle mass is large enough to neglect kinetic energy (and sets \(\hbar=1\)), the evolution is \(e^{-itH(s)\otimes p}\). Assuming the free particle starts off very localized in space, initially \(\ket{x}\) is a narrow Gaussian wave packet centered at \(x=0\). Because the simulation algorithm used herein assumes a time-independent Hamiltonian, we immediately simplify the notation to \(H(s)=H, \lambda(s)=\lambda\).

The evolution starting from the \(k\)th eigenstate \(\ket{{\lambda}_k, x=0}\) evolves to \[\ket{{\lambda}_k,x=t\lambda_k}\] All one has to do to obtain \(\lambda_k\) after this evolution is measure the pointer state. This is already von Neumann’s measurement prescription for obtaining \(i \ln(U)\); reference [3] makes this connection more explicit and presents an unstructured search algorithm using the procedure.

Implementing time evolution of \(e^{-itH\otimes p}\) with QET in a digital/discrete system requires one to discretize the continuous variable \(\Vec{x}\), and the momentum operator becomes either \[\vec{\tilde{p}}=\sum_{j=1}^{r}2^{-j}\frac{1-\sigma_z^{(j)}}{2} \Rightarrow \vec{\tilde{p}}\ket{z}=\frac{z}{2^r}\ket{z}\label{eq:discretemomentumop}.\tag{2}\] or \[\begin{align} \vec{{p}}&=\sum_{j=0}^{{r}-1}2^j\frac{I-\sigma_Z^{(j)}}{2}, \Rightarrow {p}\ket{z}=z\ket{z}\label{eq:largenormmomentum}. \end{align}\tag{3}\]

In both 2 and 3 , the momentum operator basis is fixed to be the computational basis states over a \(2^r\) dimensional space, \(\{\ket{z}\}\) for \(z\in \mathbb{Z}_+\) where \(z< 2^r\) for some integer \(r\). 3 corresponds to the standard register size used in QPE, and 2 is a register used in [3] to create a quantum search algorithm, which is expected to work with \(r=\mathcal{O}(1)\) register. Herein, we consider only 3 .

The system initial state is \[\ket{\lambda_{k}}\ket{x(0)}=\frac{1}{2^{{r}/2}}\sum_{z=0}^{2^{{r}}-1}\ket{\lambda_k, z}.\] Beginning from \(\ket{\lambda_{k}}\ket{x(0)}\), after the evolution the state is \[{\ket{\lambda_k}\otimes \ket{x(0)}\rightarrow\frac{1}{2^{r/2}}\ket{\lambda_k}\sum_{z=0}^{2^r-1} e^{-i{t\lambda_kz}}\ket{z}.}\label{eq:eigstatepostHS}\tag{4}\]

Finally the inverse quantum Fourier transform (iQFT) [2] on the \(r\) register results in state \[\begin{align} iQFT \ket{x({t}), \lambda}&=\frac{1}{2^{{r}}}\sum_{z=0}^{2^{{r}}-1}\sum_{x=0}^{2^{{r}}-1} e^{i\frac{2\pi x z}{2^{{r}}}}e^{-i{t}\lambda z}\ket{z, \lambda}\label{eq:vNmfinalstate} \end{align}\tag{5}\] where the probability amplitude of any pointer computational basis state is \[\begin{align} \kappa_x=\frac{1}{2^{{r}}}\sum_{z=0}^{2^{{r}}-1}e^{iz\left(\frac{2\pi x}{2^{{r}}}-{t}\lambda_k\right)}.\label{eq:QEEperfectprobamp} \end{align}\tag{6}\] This is already a similar state to the result of textbook QPE, and so we can replicate the usual analysis of [2], [35]. Expanding 6 as a complex geometric series, one arrives at the usual expression, where \(n\in\mathbb{Z}_{\geq 0}\) and \(x\neq \frac{2^{r}\lambda t}{2\pi}\) \[\begin{align} \left|k_{x}\right|^2&= \frac{\sin^2\left({\pi\left(x-2^r\frac{\lambda t}{2\pi}\right)}\right)}{4^r\sin^2\left(\frac{\pi}{2^r}\left(x-2^r\frac{\lambda t}{2\pi}\right)\right)}\label{eq:childssuccprop} \end{align}\tag{7}\] When \(x\) is measured with certainty, then \(\lambda=\frac{2\pi x}{2^rt}\). In the phase estimation problem, usually only one eigenvalue \(\lambda_k\) is of interest.

Beginning from 7 , one can derive the result using similar methods to [35]. We get \[|\kappa_x|^2\geq 1-\frac{1}{2(k-1)}, \quad k>1\label{eq:kappaboundbrassard}\tag{8}\] where \(|\kappa_x|^2\) is the probability that answer \(\tilde{x}/2^r\) is such that \[\left|\frac{2\pi\tilde{x}}{t2^r}-\lambda\right|\leq \frac{k}{2^r}.\] For \(\kappa_x\) to have success probability higher than \(1-\delta\) for some \(\delta\in[0, 1)\), then \(k\) can be restricted by \(\delta\) \[\begin{align} k&=\lceil\frac{1}{2\delta}\rceil+1.\label{eq:kconstraint} \end{align}\tag{9}\]

Denote the distance (gap) between any two eigenvalues as \[\begin{align} \Delta_{ij}=\left|\lambda_j-\lambda_i\right|, \end{align}\] and then fix \(\Delta_k=\max_{l}\Delta_{kl}\). If one is interested in measuring the ground state energy, then \(\Delta_0=\Delta\) is the spectral gap.

With a system prepared in 5 , the \(r\)-register estimate, \(\tilde{x}\), defines the phase estimate \[\tilde{\lambda}=\frac{2\pi\tilde{x}}{2^rt}.\] The QEE will only succeed if (i) the probability of measuring another bit string \(\tilde{x}'\neq \tilde{x}\) is always small, which is managed by 9 , and (ii) the pointer system is large enough to encode an answer to some desired accuracy \(\epsilon_{vN}\).

With \(\left|{x}-{\tilde{x}}\right|\leq {k}\), \[\begin{align} \left|\lambda-\tilde{\lambda}\right|&= \frac{2\pi}{2^{{r}} {t}}\left|x-\tilde{x}\right|\leq {\frac{2\pi k}{2^{{r}}{t}}}\label{eq:epsilonvN}. \end{align}\tag{10}\]

The algorithm cannot successfully distinguish between eigenvalues unless the required precision is less than the gap, i.e. \(\left|\lambda-\tilde{\lambda}\right|\leq \epsilon_{vN}\leq \Delta_k\).

The bit precision is \(k/2^r\leq \epsilon_{bit}\in(0, 1)\), with \[r\geq \log_2\left(\frac{k}{\epsilon_{bit}}\right).\] leading to \[r\geq \log\left(\frac{1}{\epsilon_{vN}}\right)\label{eq:rconstraintoptimalquery},\tag{11}\] matching the register used in the standard QPE problem.

The resulting choice of \(t\) is \[\begin{align} {{t}} &\geq 2\pi \label{eq:tauconstraintoptimalquery},\\ \Rightarrow \left|\lambda-\tilde{\lambda}\right|&\leq \frac{k}{2^{{r}}}. \end{align}\tag{12}\]

3.1 Hamiltonian Simulation approximation↩︎

The polynomial approximation and bounds for QET Hamiltonian simulation were developed in [5], [11] by truncating the Jacobi-Anger expansion. In coordinate \(z\in U(1)\), \[\begin{align} \label{eq:laurent95HSpoly} P_{HS}&=\mathcal{A}(z)-i\mathcal{B}(z),\\ \mathcal{A}(z)&=J_0(t)+\sum_{k=-R}^{R}(-1)^k{J_{2k}(t)}z^{2k},\\ \mathcal{B}(z)&=\sum_{-R-1}^R(-1)^k{J_{2k+1}(t)}z^{2k+1}. \end{align}\tag{13}\] where the total degree is \(d=2R+1\). To obtain an \(\epsilon_{QET}\)-close approximation, one can use the following bound

\[\label{eq:rupperbound} d=\mathcal{O}\left(t\log\left(\frac{1}{\epsilon_{QET}}\right)\right).\tag{14}\] \(\epsilon_{QET}\) is a bound on the error introduced by using \(P_{HS}\), an imperfect estimate of the target function in the QET routine.

3.2 QPE with imperfect subroutines↩︎

So far, we have assumed that \(e^{it H\otimes p}\), \(\ket{\lambda}\), and the QFT’s can be perfectly implemented. However, these assumptions can all be relaxed.

Say one implements a Hamiltonian simulation algorithm to precision \(\epsilon_{HS}\in[0, 1)\). Beginning from some \(\ket{\lambda_k, z}\), we have \[\begin{align} \left|\left|U_{QSP}\ket{\lambda_k, z}-e^{-it H}\ket{\lambda_k, z}\right|\right|\leq \epsilon_{QET} \end{align}\] After the iQFT is applied to \(U_{QSP}\ket{\lambda_k, z}\), one obtains \[\begin{align} \left|\left|\ket{\lambda_k}\sum_{x=0}^{2^r-1} \kappa_{x}\ket{{x}}-iQFT\cdot U_{QSP}\ket{\lambda_k, z}\right|\right|\leq \epsilon_{QET}\label{eq:tonorm} \end{align}\tag{15}\] So then, the norm of \(iQFT\cdot U_{QSP}\ket{\lambda_k, z}\) is at most \(1+\epsilon_{HS}\), leading to a normalized state \[\begin{align} \frac{iQFT\cdot U_{QSP}\ket{\lambda_k, z}}{\sqrt{1+\epsilon_{QET}}} \end{align}\] instead of 5 .

The success probability becomes \[\left|\tilde{\kappa}_x(\epsilon_{HS})\right|^2\geq\frac{ \left|{\kappa}_x\right|^2}{(1+\epsilon_{HS})}.\] We also consider imperfect eigenstate preparation \(\ket{\psi_0}=\sum c_j\ket{\lambda_j}\), where \(c_{j\neq k}\) will be assumed to be small. Measuring in the Hamiltonian eigenbasis, the success probability of obtaining \(\lambda_k\) is \(1-\sum_{j\neq k}c_j^2\). Using \(\ket{\psi_0}\) instead of \(\ket{\lambda_k}\) as the initial state in QPE, one must account for the possibility of measuring a result for eigenstate \(\lambda_j\neq \lambda_k\). By linearity, \[\begin{align} \left|\tilde{\kappa}_x(\epsilon_{HS}, \{c_j\})\right|^2& {\geq \frac{{1-\sum_{j\neq k}c_j^2}}{(1+\epsilon_{HS})}|\kappa_x|^2\label{eq:succprobvnapproxhs}.} \end{align}\tag{16}\]

4 vN-QPE algorithms↩︎

We state 1 showing that the QEE problem can be solved with 1, and then in 1 we show that QPE can be solved with near-optimal query complexity with the same strategy.

We will state the results in terms of any \(1, 2\) qubit gates, and in the next we will take advantage of the clearer complexity and depth statements available through 2.

4.1 QEE with near-optimal complexity↩︎

4.2 vN-QEE with LCP oracles↩︎

Now, we focus on QEE and explicitly assume that the oracle is prepared using an LCP approach. This allows us to write the algorithm costs accounting for non-generic features of the Hamiltonian: the number of Pauli terms, the spectral gap, and the Hamiltonian norm.

5 Discussion↩︎

We have presented an efficient QEE algorithm, which can easily be modified to perform QPE, at the cost of a logarithmic overhead compared to the QPE lower bound [18]. We have focused on the standard QPE/QEE problem, meaning that we assume access to \(\ket{\lambda}\), or a state exponentially close to it.

1 then underscores that this efficiency holds when one adopts a common access model. The result illustrates how vN-QPE (and the underlying QET Hamiltonian simulation) complexity scales with physically relevant parameters \(\alpha, \left|P\right|\) in practice. This is because while QSP+ templates provide an easy conceptual framework for algorithm development, important Hamiltonian parameters, usually \(|P|, \Delta_k, \alpha\), are subsumed into block-encoding costs. This point is not truly novel, it can be derived straightforwardly from the complexity statements of block-encoding costs in for example [5], [19]. However, it is a key feature of algorithms on block-encodings data which deserves prominence.

1 is amenable to simplifications that we have not discussed directly. First, for simple or particularly structured problems, then the block-encoding step might be done more cheaply than we have assumed (generic \(e^{iH}\) oracles or some LCP). Regardless of whether the block-encodings are prepared with the methods we used, our work demonstrates that preparing and coupling the pointer system introduces minimal additional costs or assumptions to the problem.

Next, sometimes the initial QFT step in QPE can be replaced with a window function [37]. In analogy to classical signal processing, the window functions are designed to dampen spectral leaking, or the spreading of the probability distribution across all eigenstates of \(U\) due to the QFT step or time-evolution. Window function-based QPE algorithms will have the same asymptotic query complexity as standard QPE, but could have a higher success probability, at the cost of a more expensive initial QFT step. Window function-QPE has been explicitly compared to QSVT-QPE, and numerically outperforms QSVT-based algorithms by a low constant factor [38] in the test cases. The approach can be combined with ours, leading to a possible numeric boost to the success probability in \(\gamma=1-\text{poly}(n)\) cases.

Finally, note that [39] shows that a variant of QPE, which explicates the depth-precision tradeoff inherent to all QPE algorithms, \(\alpha\)-QPE, can also be formulated in QSVT. It is possible that by changing the subnormalization on \(\Vec{p}\) , one could derive a similar result to \(\alpha\)-QPE.

Acknowledgments↩︎

Discussions with Tobias Osborne, Andreea Lefterovici, René Schwonnek, and Martin Steinbach are gratefully acknowledged. We thank the anonymous reviewers for constructive feedback which improved the manuscript.

We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC), PGS D - 587455 - 2024.

Cette recherche a été financée par le Conseil de recherches en sciences naturelles et en génie du Canada (CRSNG), PGS D - 587455 - 2024.

This work was also directly or indirectly supported by the following project funding: Quantum Valley Lower Saxony; the Deutsche Forschungsgemeinschaft project SFB 1227 (DQ-mat); Germany’s Excellence Strategy EXC-2123 QuantumFrontiers 390837967; the BMWK project ProvideQ, and by the BMBF projects QuBRA and ATIQ.

6 Block-encodings and qubitized block-encodings↩︎

In QSP+ literature, the first proposals used the nomenclature "standard-form-encodings" which perfectly encoded some \(H\) and used \(\ket{G}\) to project to the subspace of \(BE(H)\) containing it [11]. From this definition, one defines a "qubitized standard-form-encoding operator" and then constructs a QET circuit.

In [11], it was shown that a qubitized block-encoding can be built from \(BE(H)\) using two queries to the block-encoding or its inverse and one additional qubit, when \(\epsilon=0\). It is simple to show that a \(\epsilon\neq 0\) block-encoding can be used to create an \(\epsilon\)-close qubitized block-encodingfor completeness this is done in 7. We usually define \(S\) so that the qubitized rotation basis is \(\ket{+, G}\), and everywhere below we will use \(\ket{G}=\ket{0^{\otimes n_{anc}}}\).

6.1 Block-encodings from LCP Hamiltonians↩︎

The standard way to prepare a block-encoding of a LCP is to construct two matrices, \(U_{PREP}\) and \(U_{SELECT}\) [41], [42], \[\begin{align} U_{PREP} &:\ket{0^{\otimes \log_2(|P|)}}\rightarrow \frac{1}{\sqrt{\alpha}}\sum_{l\in [\left|P\right|]}\sqrt{\alpha_l}\ket{l},\tag{18}\\ U_{SELECT}&=\sum_l\ket{l}\bra{l}\otimes P_l\tag{19}\\ \end{align}\] One can verify by explicit construction that \(U_{PREP}^{\dagger}U_{SELECT}U_{PREP}\) prepares a \(\beta={\alpha}\) block-encoding of \(H\).

The construction of [19] gives algorithms for approximately creating \(U_{SELECT}, U_{PREP}\), allowing for a variable number of ancillary qubits to be used. As in [19], we assume that \(H\) has dimension \(N=2^n\) and that \(\log_2\left|P\right|\) is an integer³.

2 has the following trivial generalization for \(\alpha\neq 1\). For a given \(H\), consider the renormalized Hamiltonian \(H'=\frac{H}{\alpha}\). \(\left|\left|H'\right|\right|_{op}=1\) and the construction in [19] prepares \(BE(H'),\) encoding some Hamiltonian \(\tilde{H}\), which is \(\epsilon\)-close to \(H'\), and therefore also \(\epsilon\)-close to \(\frac{H}{\alpha}\). Thus, \(BE(H')\) is also an \(\alpha\epsilon\)-close block-encoding of \(H\).

6.2 Block-encodings from QPE oracles↩︎

Recall that in QPE, one assumes access to \(U=e^{iH}\), which in our setting will need to be converted into a block-encoding of \(H\). A protocol from [5] shows how to create⁴ a \(BE(H)\) from \(U\).

Heuristically speaking, 2 implements \(U\rightarrow i\log(U)\). The proof is simple, and relies on two steps: (i) Show that \(-iCU^{\dagger}\left(ZX\otimes I\right)CU\) is a block-encoding of \(\sin(H)\), where \(C\) denotes a controlled operation. (ii) Implement a polynomial expansion of \(\arcsin\) in QSVT, resulting in \(BE(H)\).

We refer the reader to [5] for details on the functional approximation of \(\arcsin\) and the bounds.

6.3 Tensor products of block-encodings↩︎

Finally, we need a small lemma to show that block-encoding structure is preserved by the tensor product, [lemma:betensorlemma]⁵.

7 Qubitization and QET↩︎

Qubitization is the process of taking a block-encoding and transforming it into an iterate \(W\) such that \(W\) encodes the complex-exponential of the eigenvalues of \(H\) in a direct product form. This can be done for any \((1, n_{anc}, 0)\) block-encoding \(BE(H)\) with a constant number of calls to \(BE(H), BE(H)^{\dagger}\) and controlled versions. Below is a review of the standard reference [11]. We could instead have followed [40], which presents a derivation of QET more closely in alignment with QSVT (promoting the signal processing operator to a controlled rotation, instead of promoting the block-encoding to a qubitized block-encoding).

Consider iterates of the form \(W=\left(2\ket{G}\bra{G}-I\right)\cdot S BE(H)\), and for now ignore the definition of rotation \(S\). Denote \(\ket{G_{\lambda}}=\ket{G}\otimes \ket{\lambda}\), then one can show

\[\ket{G_{\lambda}^{\perp}}=\frac{-\lambda\ket{G_{\lambda}}+W\ket{G_{\lambda}}}{\sqrt{1-|\lambda|^2}}.\] One can then define operations which act as the Pauli matrices in each \(\ket{G_{\lambda}}\) subspace. That is, there exist \(X_{\lambda}, Y_{\lambda}, Z_{\lambda}\) such that \[\begin{align} X_{\lambda}\ket{G_{\lambda}}&=\ket{G_{\lambda}^{\perp}}\\ Y_{\lambda}\ket{G_{\lambda}}&=i\ket{G_{\lambda}^{\perp}}\\ Z_{\lambda}\ket{G_{\lambda}}&=\ket{G_{\lambda}}\\ \end{align}\] And then finally \(W\) is written as a direct product of these subspaces, \[W=\bigoplus\begin{bmatrix} \lambda & \sqrt{1-|\lambda|^2}\\ \sqrt{1-|\lambda|^2} & \lambda \end{bmatrix}=\bigoplus_{\lambda}e^{-i\arccos(\lambda)Y_{\lambda}}.\] One can easily verify that \(\cup_{\lambda}\{\ket{G_{\lambda}}, \ket{G_{\lambda}^{\perp}}\}\) form an orthonormal basis, with the following action on \(W\) \[\begin{align} W\ket{G_{\lambda}}&=\begin{bmatrix} \lambda & \sqrt{1-|\lambda|^2}\\ \sqrt{1-|\lambda|^2} & \lambda \end{bmatrix}\begin{bmatrix} \ket{G_{\lambda}}\\ 0 \end{bmatrix}=\begin{bmatrix} \lambda\ket{G_{\lambda}}\\ \sqrt{1-|\lambda|^2}\ket{G_{\lambda}^{\perp}} \end{bmatrix}\\ W\ket{G_{\lambda}^{\perp}}&=\begin{bmatrix} \lambda & \sqrt{1-|\lambda|^2}\\ \sqrt{1-|\lambda|^2} & \lambda \end{bmatrix}\begin{bmatrix} 0\\ \ket{G_{\lambda}^{\perp}} \end{bmatrix}=\begin{bmatrix} -\sqrt{1-|\lambda|^2}\ket{G_{\lambda}}\\ \lambda\ket{G_{\lambda}^{\perp}} \end{bmatrix} \label{eq:WGlambdadag}. \end{align}\tag{20}\] The eigenvectors of \(W\) are derived as linear combinations of 20 ; the eigenvalues are \(e^{i\Phi\mp i\arccos(\lambda)}\). Additionally, one can introduce a global phase to the operator; \(e^{i\Phi}W\) has the same eigenvectors and eigenvalues \(e^{i\Phi\mp i\arccos(\lambda)}\). Finally, the direct product carries through the exponentiation, so the generator of \(W\) is \(\bigoplus \arccos(\lambda)Y_{\lambda}\).

With \(W\) and its eigenspectrum, one can define a phased iterate \(W_{\phi},\) which applies a sequence of phases on \(W\) that ultimately represents a polynomial in the eigenvalues. This will be the QET circuit. First, define operation \[Z_{\phi}=\bigoplus \begin{bmatrix} e^{-i\phi} & 0\\ 0 & -1\\ \end{bmatrix}=\bigoplus_{\lambda}e^{-\phi/2}e^{-i\phi/2Z_{\lambda}},\] and then consider the product operation which builds up polynomials of \(H\).⁶ \[\begin{align} W_{QET}=\prod_{\{\phi_j\}}Z_{\phi_j}WZ_{-\phi_j}. \end{align}\] This isn’t a real circuit yet, but it can be implemented with one additional qubit and a series of controlled \(Z\) operations about \(G\) [11], [40]. In QSP+ language, the signal processor has been promoted to \(\left(2\ket{G}\bra{G}-I\right))\left(e^{i(\phi_j)}\otimes I\right)\left(2\ket{G}\bra{G}-I\right)\) , and \(W\) is the signal operator.

We now promote the \(W\) operation to a controlled operation on \(C_{+}W\) for even polynomials, which is single-ancilla QSP in [11]. In this case, a global phase is allowed on \(W\), so \(e^{i\Phi}W\) is the qubitized block-encoding used. The QET circuit for Chebyshev polynomials is then \[\begin{align} U_{QET}=(e^{i\frac{\phi_0}{2}Z}\otimes I)\prod_{\{\phi_j\}}(e^{i\frac{\phi_j}{2}Z}\otimes I)C_{-}W(e^{-i\frac{\phi_j-\phi_{j+1}}{2}Z}\otimes I)C_{+}W^{\dagger}(e^{-i\frac{\phi_{j+1}}{2}Z}\otimes I). \end{align}\] One can actually implement more general rotations than \(Z_{\phi}\), or subsume the control basis change into \(Z\), resulting in a circuit with \(C_1W\) and gates with \(1\)-qubit parameterized rotations \(R(\phi)\). The QSP convention from [33] immediately extends to the direct product notation for QET, and the most general QSP convention of [32] allows any \(U(2)\) rotation to be used (and is extendable to QET or QSVT). One must take care that the QSP+ circuit design of choice admits polynomials of the desired form.

7.1 Approximate qubitized block-encodings↩︎

Given \(\left(1, n_{anc}, 0\right)\) block-encoding \(BE(H)\), one could try to identify an \(S\) such that \[\begin{align} \bra{G}S\cdot BE(H)\ket{G}=H & \text{ and } \bra{G}S\cdot BE(H)\cdot S\cdot BE(H)\ket{G}=I_{rank(H)}. \end{align}\] More generally, [11] showed that one can construct qubitized block-encoding \(W(H)\) for any block-encoding \(BE(H)\) using an additional ancilla qubit. Specifically, \[W(H)=\left(\sigma_X\otimes I_{n_{anc}+rank(BE)}\right)C_1BE(H)^{\dagger}C_0BE(H).\label{eq:qubitizedBE}\tag{21}\] \(W(H)\) will project around the subspace defined by \(\ket{G'}=\ket{+}\otimes\ket{G}\).

We now verify that the construction above extends to \(\left(\beta, n_{anc}, \epsilon\right)\) block-encodings. In this case, there is another Hamiltonian, \(H'\), which is \(\epsilon\)-close to \(H/\beta\) and \(BE(H)\) is a perfect block-encoding for \(H'\). Then \(H'\) admits a qubitized oracle, \(W(H')\), such that \[\begin{align} \left|\left|H-\beta\bra{G'}W(H')\ket{G'}\right|\right|_{op}= \left|\left|H-\beta H'\right|\right|_{op}\leq \epsilon. \end{align}\] Thus, \(W(H')\) is a \(\left(\beta, n_{anc}+1, \epsilon\right)\) block-encoding for \(H\).

8 QET error↩︎

We consider three sources of error in QET circuits. First, in QET one usually considers a polynomial which is \(\epsilon_{approx}\in[0,1)\) close to a desired function \(f\) in the \(l_{\infty}\)-norm, and then has some controllable⁷ error from the QSP-processing step to derive a QSP circuit from the input polynomial. We jointly capture the functional and decomposition error with \(\epsilon_{QET}\in[0, 1)\), and one can say that the QET circuit implements a polynomial \(P'\) which is \(\epsilon_{QET}\)-close to \(f\). After post-selecting the ancilla qubits from the QET rotation qubit and the block-encoding ancillary qubits, one arrives at \[\begin{align} &\left|\left|\sum_{\lambda}P'\left(\frac{\lambda}{\alpha}\right)\ket{\lambda}\bra{\lambda}-\sum_{\lambda}f\left(\frac{\lambda}{\alpha}\right)\ket{\lambda}\bra{\lambda}\right|\right|_{op}\nonumber\\ &\leq \left|\left|\sum\epsilon_{QET} \ket{\lambda}\bra{\lambda}\right|\right|_{op}\leq \epsilon_{QET}. \end{align}\] Thus, \(\epsilon_{QET}\) is the QET circuit error if gates are implemented perfectly and a perfect qubitized block-encoding is used.

Next, one must consider how the error in the signal operator, \(\epsilon_{BE}\in[0, 1),\) propagates through the QET circuit. If \(\epsilon_{BE}\) is the error in the \(\mathcal{G}_{CpT}\) decomposition, then for consistency we also account for the costs of decomposing the signal processing gates in \(\mathcal{G}_{CpT}\), implemented up to some precision \(\epsilon_{R}\in[0, 1)\).

In 8.1, we show that \(\epsilon_R, \epsilon_{BE}\) can be jointly managed and that the distance between the approximately-implemented QET circuit \(\tilde{U}_{QET}\) and the ideally-implemented circuit \(U_{QET}\) is constrained by \[\left|\left|U_{QET}-\tilde{U}_{QET}\right|\right|_{op}\leq d\left(\epsilon_{R}+\epsilon_{BE}\right)+\epsilon_R.\]

The error arising from the approximate implementation and the functional approximation are additive, so overall, \[\begin{align} &\left|\left|\sum f(\lambda)\ket{\lambda}\bra{\lambda}-\bra{G',a_{QET}}\tilde{U}_{QET}\ket{G',a_{QET}}\right|\right|_{op}\nonumber\\ \quad &\leq \epsilon_{QET}+2d\epsilon_{BE}+\left(2d+1\right)\epsilon_R. \end{align}\]

8.1 QET gate error↩︎

The algorithms in the main text rely on being able to bound the propagation of gate error through QET circuits. This can easily be derived for any QSP+ circuit; for completeness we do so in 3. A QSP+ circuit encoding an degree-\(d\) Laurent polynomial, where \(d\) is even, has the following general form \[W_{QSP+}=R_0\prod_{d} CW\cdot\left(R_{2j-1}\otimes I\right)\cdot CW^{\dagger}\cdot \left( R_{2j}\otimes I\right)\label{eq:qsppluscircuit}.\tag{22}\] The odd-degree circuit has an analogous description with an additional \(CW\cdot\left(R_{2n+1}\otimes I\right)\) gate outside of the product.

Say that signal operator(s) \(CW\), \(CW^{\dagger}\), are implemented by unitaries \(C\tilde{W}\), \(CW^{\dagger}\) with some error at most \(\epsilon_W\), and the signal processing operators \(R_j\) are implemented by unitaries \(\tilde{R}_j\) with some error at most \(\epsilon_{R}\). In this analysis, it is not important whether \(\epsilon_R, \epsilon_W\) arise from a limited accuracy decomposition into some convenient elementary gate set, or because the oracle and/or QET circuit are derived to limited accuracy.

8.2 Approximate QET circuit depth↩︎

We now consider the \(\mathcal{G}_{CpT}\) complexity and depth of a QET circuit. The Toffoli count of one-qubit gates can be found in [47], [48] for exact decompositions or in [49]–[51] for \(\epsilon_R\)-close approximations.

We will assume access to a \(\left(\beta, n_{anc}, \epsilon_{BE}\right)\) block-encoding of \(H\) with some decomposition into Clifford and \(T\) gates, \(\mathcal{C}(BE(H))\). From \(BE(H)\), \(W(H)\) is given in 21 , which involves the cost of two controlled block-encodings and one Clifford gate. Then, the signal operator is the controlled version of \(W(H)\), and we will assume that \(W(H)\) and \(W(H)^{\dagger}\) have the same cost.

From [36], the \(\mathcal{G}_{CpT}\) cost of \(CV\) for any unitary \(V\) will be linear in \(\mathcal{C}(V)\), using at most one ancilla qubit. With this construction, \(\mathcal{O}\left(W(H)\right)\) has a \(\mathcal{O}\left(\mathcal{C}(BE(H))\right)\) complexity and depth in \(\mathcal{G}_{CpT}\). The signal processing oracle, \(CW(H)\), is a controlled gate which can be prepared with the same process, so \(\mathcal{O}\left(CW\right)=\mathcal{O}\left(BE(H)\right)\) in \(\mathcal{G}_{CpT}\), for both the depth and the complexity. That is, the signal oracle \(CW\) (or \(CW^{\dagger}\)) will need at most two ancilla qubits in addition to \(n+n_{anc}+2\) qubits for the \(CW\) gate, but will remains linear in the costs of \((BE(H))\).

Because QET signal processing gates are in \(SU(2)\) for our implementation [33], they can be prepared to accuracy \(\epsilon_R\) with \(\mathcal{O}\left(\log(2/\epsilon_R)\right)\) \(\mathcal{G}_{CpT}\) gates and no ancillary qubits [51]. For a single-qubit rotation, this is also the \(\mathcal{G}_{CpT}\) depth.

Overall, one requires \(\log_2(\text{rank}(H))+n_{anc}+2\) qubits for the QET circuit, and up to two ancillary qubits used in the \(\mathcal{G}_{CpT}\) decomposition. From 22 , the QET circuit uses \(\mathcal{O}\left((2d+1)(\log(1/\epsilon_R)\right)\) \(\mathcal{G}_{CpT}\) gates for the signal processing gates and \(\mathcal{O}\left(d\mathcal{C}(BE(H))\right)\) gates for the signal oracle steps overall, so that \[\mathcal{C}\left(W_{QSP+}(H)\right)=\mathcal{O}\left(d\mathcal{C}(BE(H))+(2d+1)(\log(1/\epsilon_R)\right)\label{eq:qet-cpt-scaling}.\tag{23}\] These are all consecutive operations, and so discounting circuit optimization techniques, 23 is also the \(\mathcal{G}_{CpT}\) depth.

9 Example and Circuits↩︎

We take \(H=\omega \sigma_X\) as an example Hamiltonian, for some \(\omega<1\). This system has two eigenstates \(\omega, -\omega\), eigenvectors \(\ket{\pm}=\frac{1}{\sqrt{2}}\left(\ket{0}+\ket{1}\right)\), spectral gap \(\Delta_0=2\omega\), and spectral norm \(\alpha=\omega\). We will use a pointer system with \(2\) qubits, meaning that \(\epsilon_{vN}\geq \frac{1}{4}\). The dicretized pointer system is \[\begin{align} p=\frac{1-\sigma_z^{(0)}}{2}\otimes I+I\otimes 2\frac{I-\sigma_Z^{(1)}}{2} \end{align}\] and the discretized time-evolution is given by \[\begin{align} e^{-it\omega \sigma_X\otimes p}. \end{align}\] The initial state will be \[\begin{align} \ket{\lambda_k, x(0)}&=\ket{+}\otimes\frac{1}{{2}}\left(\ket{00}+\ket{01}+\ket{10}+\ket{11}\right)\\ &=\ket{+}\otimes \ket{+}\otimes \ket{+}. \end{align}\] Below, we specialize in the case where \(\lambda_k=\omega\).

Evolved for a time \(t\), we have \[\begin{align} e^{-it\omega \sigma_X\otimes p}\ket{+}\otimes \ket{+}\otimes \ket{+}&=\frac{1}{2}\ket{+}\left(\ket{00}+e^{-it\omega(0+\frac{1}{2})}\ket{01}+e^{-it\omega}\ket{10}+e^{-it\omega(1+\frac{1}{2})}\ket{11}\right)\\ &=\frac{1}{2}\ket{+}\left(\ket{00}+e^{-it\omega\frac{1}{2}}\ket{01}+e^{-it\omega}\ket{10}+e^{-it\omega\frac{3}{2}}\ket{11}\right) \end{align}\] The iQFT results in \[\begin{align} iQFTe^{-i\omega \sigma_X\otimes p}\ket{+}\otimes \ket{+}\otimes \ket{+}&=\frac{1}{2\cdot {2}}\ket{+}\left(\sum_{x=0}^{3}e^{i\frac{\pi x\cdot 0}{2}}\ket{x}+e^{-it\omega\frac{1}{2}}\sum_{x=0}^{3}e^{i\frac{\pi x\cdot 1}{2}}\ket{x}\right.\nonumber\\ &\left.+e^{-it\omega}\sum_{x=0}^{3}e^{i\frac{\pi x\cdot 2}{2}}\ket{x}+e^{-it\omega\frac{3}{2}}\sum_{x=0}^{3}e^{i\frac{\pi x\cdot 3}{2}}\ket{x}\right)\\ &=\frac{\ket{+}}{4}\otimes \left[\left(1+e^{-i\frac{t\omega}{2}}+e^{-i{t\omega}}+e^{-i\frac{3t\omega}{2}}\right)\ket{00}+\right.\nonumber\\ &\left. ...+\left(1+e^{i\frac{3\pi}{2}}e^{-i\frac{t\omega}{2}}+e^{i3\pi}e^{-i{t\omega}}+e^{i\frac{9\pi}{2}}e^{-i\frac{3t\omega}{2}}\right)\ket{01}\right]. \end{align}\] The success probability of some \(x\in\{0, 1, 2, 3\}\) is \[\begin{align} \left|\kappa_x\right|&=\frac{1}{16}\frac{\sin^2\left[\pi \left(x-4{\omega}\right)\right]}{\sin^2\left[\frac{\pi}{4} \left(x-4{\omega}{}\right)\right]}. \end{align}\] In 3, we show that the four success probabilities spike in the expected regions of \(w\in[0, 1]\). The success probability is still relatively low in our example, but increasing \(r\) will improve it.

For example, say we measure in the computational basis and get \(\ket{01}\), then the estimate will be \[\begin{align} \left|\tilde{\omega}_k\right|= \frac{1}{2}\pm \frac{1}{4}. \end{align}\]

To implement this with vN-QEE, we first would need to block-encoding \(H\otimes \Vec{p}\). The LCP block-encoding is prepared through access to \(U_{SELECT}, U_{PREP}\) as defined in 19 , 18 , leading to \(BE(H)\) in 4. We then qubitize the block-encoding, leading to \(W(H)\). vN-QEE is performed with 7, with the Hamiltonian simulation subroutine given in 6.

For this Hamiltonian, vN-QEE has no advantage over textbook QPE using to estimate \(\omega\). The textbook QPE has controlled powers of \(U^{j}\) sandwiched between a QFT and iQFT step; the discretized vN-QPE essentially replaces the controlled powers with a Hamiltonian simulation subroutine as in 6 and 7. Using QET for the Hamiltonian simulation, one must build controlled block-encodings and one-qubit rotations.

However, for a commuting Hamiltonian like \(\omega \sigma_X\), \(e^{i\omega}\) is as plausible to prepare as \(e^{i j\omega \sigma_X}\), meaning that preparing the block-encoded system-pointer system instead of \(e^{i j\omega \sigma_X}\) will not give a computational advantage. Where vN-QEE could provide an advantage is when it is not clear how to implement \(U^{j}\) without overhead costs, such as for non-commuting Hamiltonians with many terms.

References↩︎