Revisiting fixed-point quantum search: proof of the quasi-Chebyshev lemma

Abstract

The original Grover’s algorithm suffers from the souffle problem, which means that the success probability of quantum search decreases dramatically if the iteration time is too small or too large from the right time. To overcome the souffle problem, the fixed-point quantum search with an optimal number of queries was proposed [Phys. Rev. Lett. 113, 210501 (2014)], which always finds a marked state with a high probability when a lower bound of the proportion of marked states is given. The fixed-point quantum search relies on a key lemma regarding the explicit formula of recursive quasi-Chebyshev polynomials, but its proof is not given explicitly. In this work, we give a detailed proof of this lemma, thus providing a sound foundation for the correctness of the fixed-point quantum search. This lemma may be of independent interest as well, since it expands the mathematical form of the recursive relation of Chebyshev polynomials of the first kind, and it also constitutes a key component in overcoming the souffle problem of quantum walk-based search algorithms, for example, robust quantum walk search on complete bipartite graphs [Phys. Rev. A 106, 052207 (2022)]. The lemma is also central to a recently proposed quantum algorithm named quantum phase discrimination, which has become a fundamental subroutine in quantum search on graphs [arxiv: 2504.15194]. Hopefully, more applications of the lemma will be found in the future.

Graphical abstract

Keywords

quantum algorithm / Grover’s algorithm / fixed-point quantum search / quasi-Chebyshev polynomials

References

[1] Grover L K. A fast quantum mechanical algorithm for database search. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing. 1996, 212−219

[2] Brassard G, Høyer P, Mosca M, Tapp A . Quantum amplitude amplification and estimation. AMS Contemporary Mathematics Series, 2002, 305: 53–74

[3] Høyer P . Arbitrary phases in quantum amplitude amplification. Physical Review A, 2000, 62( 5): 052304

[4] Long G L . Grover algorithm with zero theoretical failure rate. Physical Review A, 2001, 64( 2): 022307

[5] Li G, Li L . Deterministic quantum search with adjustable parameters: implementations and applications. Information and Computation, 2023, 292: 105042

[6] Ambainis A . Quantum search with variable times. Theory of Computing Systems, 2010, 47( 3): 786–807

[7] Ambainis A, Kokainis M, Vihrovs J. Improved algorithm and lower bound for variable time quantum search. In: Proceedings of the 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). 2023, 7: 1−7: 18

[8] Høyer P, Mosca M, de Wolf R. Quantum search on bounded-error inputs. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 2003, 291−299

[9] Rosmanis A. Quantum search with noisy oracle. 2023, arXiv preprint arXiv: 2309.14944

[10] Brassard G . Searching a quantum phone book. Science, 1997, 275( 5300): 627–628

[11] Boyer M, Brassard G, Høyer P, Tapp A . Tight bounds on quantum searching. Fortschritte der Physik, 1998, 46( 4−5): 493–505

[12] Grover L K . Fixed-point quantum search. Physical Review Letters, 2005, 95( 15): 150501

[13] Yoder T J, Low G H, Chuang I L . Fixed-point quantum search with an optimal number of queries. Physical Review Letters, 2014, 113( 21): 210501

[14] Benjamin A T, Walton D . Counting on chebyshev polynomials. Mathematics Magazine, 2009, 82( 2): 117–126

[15] Gilyén A, Su Y, Low G H, Wiebe N. 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. 2019, 193−204

[16] Martyn J M, Rossi Z M, Tan A K, Chuang I L . Grand unification of quantum algorithms. PRX Quantum, 2021, 2( 4): 040203

[17] Haah J . Product decomposition of periodic functions in quantum signal processing. Quantum, 2019, 3: 190

[18] Chao R, Ding D, Gilyen A, Huang C, Szegedy M. Finding angles for quantum signal processing with machine precision. 2020, arXiv preprint arXiv: 2003.02831v2

[19] Dong Y, Meng X, Whaley K B, Lin L . Efficient phase-factor evaluation in quantum signal processing. Physical Review A, 2021, 103( 4): 042419

[20] Xu Y, Zhang D, Li L . Robust quantum walk search without knowing the number of marked vertices. Physical Review A, 2022, 106( 5): 052207

[21] Li G, Li L, Luo J. Quantum phase discrimination with applications to quantum search on graphs. 2025, arXiv preprint arXiv: 2504.15194

[22] Li J, Zur S . Multidimensional electrical networks and their application to exponential speedups for graph problems. Quantum, 2025, 9: 1733

RIGHTS & PERMISSIONS

Higher Education Press