arXiv:2404.01396

A case study against QSVT: assessment of quantum phase estimation improved by signal processing techniques

Sean Greenaway, William Pol, Sukin Sim

Published Apr 1, 2024• 4 citations

Abstract

In recent years, quantum algorithms have been proposed which use quantum phase estimation (QPE) coherently as a subroutine without measurement. In order to do this effectively, the routine must be able to distinguish eigenstates with success probability close to unity. In this paper, we provide the first systematic comparison between two approaches towards maximizing this success probability, one using the quantum singular value transform and the other leveraging window functions, which have been previously studied as priors of the phase value distribution. We find that the quantum singular value transform is significantly outclassed by the window function approach, with the latter able to achieve between 3 and 5 orders of magnitude improvement in the success probability with approximately 1/4 the query cost. Our circuit simulation results indicate that QPE is not a domain which benefits from the integration of QSVT and we show that the use of the Kaiser window function is currently the most practical choice for realizing QPE with high success probability.

DOI: 10.48550/arxiv.2404.01396

Related papers

Windowed Quantum Phase Estimation: Signal Processing Approach to a Quantum Algorithm

Xue Wen

Quantum phase estimation (QPE) is a key ingredient to some of the most important results of quantum computing. In this paper we examine the QPE algorithm through the looking glass of signal processing. This perspective helps to reveal a relation between the distribution of quantum phase estimates and the shape of the discrete Fourier transform (DFT) of a pure complex sinusoid. Guided by spectral shaping theory, we design a class of quantum circuits that are the quantum equivalents to classical windowing operators, for a family of window functions that have compact support in the DFT. These circuits have complexity linear in the number of target qubits, strictly lower than QPE itself. Using these circuits we are able to reshape QPE's performance characteristics. In particular, the asymptotic marginal cost for 2x reduction in fail rate (2x improvement in reliability) is reduced from one qubit to 1/3 qubit or lower, which can help reduce the qubit budget for a preset accuracy-reliability target, especially in high-reliability scenarios. This makes a demonstration of the value of signal processing principles in designing quantum algorithms.

IEEE International Conference on Acoustics Speech and Signal ProcessingMar 12, 20250 citations

Reducing quantum resources for observable estimation with window-assisted coherent QPE

Harriet Apel, Cristian L. Cortes, Jessica Lemieux +1 more

Quantum Phase Estimation (QPE) routines are known to fail probabilistically even with perfect gates and input states. This effect stems from an incompatibility of finite-sized quantum registers to capture a phase within QPE with phase angles of infinite precision, and the effect extend even beyond what would be reasonably expected from rounding. This effect can be partially mitigated by biasing the phase register with a window, or taper state, from classical signal processing. This paper focuses on how windowing a coherent QPE used as a subroutine can improve the accuracy of the overall algorithm. Specifically we study the quantum task of estimating observables where window-assisted coherent QPE is used as a subroutine to implement a reflection about an eigenstate. Quantum resource estimates show over 2-orders-of-magnitude reduction in Toffoli counts over the previous costed techniques -- also assisted by the use of improved block encoding techniques -- demonstrating an encouraging decrease in resources for quantum computation of molecular observables. Since QPE, as one of only a few quantum building blocks, appears as a subroutine in many algorithms; this analysis also provides a model for understanding how window functions propagate to an improved error in composite algorithms.

arXiv:2508.06677Aug 8, 20250 citations

Noise analysis of Grover and phase estimation algorithms implemented as quantum singular value transformations for a small number of noisy qubits

Muhammad Abdullah Ijaz, Muhammad Faryad

The quantum singular value transformation (QSVT) algorithm is a general framework to implement most of the known algorithms and provides a way forward for designing new algorithms. In the present work, the impact of noise on the QSVT algorithm is examined for bit flip, phase flip, bit-phase flip, and depolarizing noise models for a small number of qubits. The small number of noisy qubits approximates the currently available noisy quantum computers. For simulation results, the QSVT implementation of the Grover search and quantum phase estimation (QPE) algorithms is considered. These algorithms are among the basic quantum algorithms and form the building blocks of various applications of quantum algorithms. The results showed that the QSVT implementation of the Grover search and QPE algorithms has a consistently worse dependence upon noise than the original implementation for all four noise models. The probability of success of the Grover algorithm and phase measured by the QPE algorithm were found to exponentially depend upon the error probability in the noisy channels but only linearly dependent on the number of qubits.

Scientific ReportsNov 17, 20231 citation

Simplifying a classical-quantum algorithm interpolation with quantum singular value transformations

Duarte Magano, Miguel Murça

The problem of phase estimation (or amplitude estimation) admits a quadratic quantum speedup. Wang, Higgott, and Brierley [Wang, Higgott, and Brierley, Phys. Rev. Lett. 122, 140504 (2019)] have shown that there is a continuous tradeoff between quantum speedup and circuit depth [by defining a family of algorithms known as $\ensuremath{\alpha}$-quantum phase estimation $(\ensuremath{\alpha}\text{\ensuremath{-}}\mathrm{QPE})$]. In this paper, we show that the scaling of $\ensuremath{\alpha}\text{\ensuremath{-}}\mathrm{QPE}$ can be naturally and succinctly derived within the framework of quantum singular value transformation (QSVT). From the QSVT perspective, a greater number of coherent oracle calls translates into a better polynomial approximation to the sign function, which is the key routine for solving phase estimation. The better the approximation to the sign function, the fewer samples one needs to determine the sign accurately. With this idea, we simplify the proof of $\ensuremath{\alpha}\text{\ensuremath{-}}\mathrm{QPE}$, while providing an interpretation of the interpolation parameters, and show that QSVT is a promising framework for reasoning about classical-quantum interpolations.

arXiv:2207.14810Physical Review ADec 16, 20223 citations

Quantum state preparation via piecewise QSVT

Oliver O'Brien, Christoph Sünderhauf

Efficient state preparation is essential for implementing efficient quantum algorithms. Whilst several techniques for low-cost state preparation exist, this work facilitates further classes of states, whose amplitudes are well approximated by piecewise polynomials. We show how such states can be efficiently prepared using a piecewise Quantum Singular Value Transformation along with a new piecewise linear diagonal block encoding. We illustrate this with the explicit examples of x α | x ⟩ and log ⁡ x | x ⟩ . Further, our technique reduces the cost of window boosted Quantum Phase Estimation by efficiently preparing the B-spline window state. We demonstrate this window state requires 50 times fewer Toffolis to prepare than the state-of-the-art Kaiser window state, and we show that the B-spline window replicates the Kaiser window's exponential reduction in tail probability for QPE.

arXiv:2409.07332QuantumJul 3, 20252 citations

Quantum signal processing and the quantum singular value transformation

Steven Herbert

Abstract The quantum algorithms presented in the previous chapters are underpinned by three fundamental features of quantum computation. First, it is possible to construct Grover iterates that amplify amplitude and concentrate probability mass on desired outcomes quadratically faster than their classical counterparts; second, quantum phase estimation is a subroutine that uses the quantum Fourier transform to interfere a quantum state such that wrong answers cancel out, leaving a state from which the solution to the problem can be extracted; and finally, using a digital quantum computer, Hamiltonian evolution can be simulated. Remarkably, these three phenomena can be seen to be instances of the same underlying computational effect: the quantum singular value transformation – a breakthrough that has been dubbed ‘the grand unification of quantum algorithms’, and which is introduced and analysed in this chapter.

Dec 8, 20250 citations