Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2502.15556 · Science China Physics Mechanics and Astronomy

Fixed-point quantum continuous search algorithm with optimal query complexity

Shan Jin, Yuhan Huang, Shaojun Wu, Guanyu Zhou, Chang‐Ling Zou, Luyan Sun, Xiaoting Wang

Published Apr 22, 2025• 4 citations
arXivHTMLPDF
DOI
10.1007/s11433-024-2629-1

Related papers

Quantum Algorithms for Highly Structured Search Problems

Markus Hunziker, DAVID A. MEYER

Quantum Information Processing•Jun 1, 2002•12 citations

Quantum search for unknown number of target items by hybridizing fixed-point method with trail-and-error method*

Tan Li, Shuo Zhang, Xiang-Qun Fu +4 more

For the unsorted database quantum search with the unknown fraction λ of target items, there are mainly two kinds of methods, i.e., fixed-point and trail-and-error. (i) In terms of the fixed-point method, Yoder et al. [Phys. Rev. Lett. 113 210501 (2014)] claimed that the quadratic speedup over classical algorithms has been achieved. However, in this paper, we point out that this is not the case, because the query complexity of Yoder’s algorithm is actually in O ( 1 / λ 0 ) rather than O ( 1 / λ ) , where λ 0 is a known lower bound of λ. (ii) In terms of the trail-and-error method, currently the algorithm without randomness has to take more than 1 times queries or iterations than the algorithm with randomly selected parameters. For the above problems, we provide the first hybrid quantum search algorithm based on the fixed-point and trail-and-error methods, where the matched multiphase Grover operations are trialed multiple times and the number of iterations increases exponentially along with the number of trials. The upper bound of expected queries as well as the optimal parameters are derived. Compared with Yoder’s algorithm, the query complexity of our algorithm indeed achieves the optimal scaling in λ for quantum search, which reconfirms the practicality of the fixed-point method. In addition, our algorithm also does not contain randomness, and compared with the existing deterministic algorithm, the query complexity can be reduced by about 1/3. Our work provides a new idea for the research on fixed-point and trial-and-error quantum search.

arXiv:1912.01773•Chinese Physics B•Nov 1, 2019•8 citations

Novel optimization of quantum search algorithm to minimize complexity

Tarun Kumar, Dilip Kumar, Gurmohan Singh

Chinese Journal of Physics•Mar 9, 2023•7 citations

Paths Beyond Local Search: A Nearly Tight Bound for Randomized Fixed-Point Computation

Xi Chen, Shang‐Hua Teng

In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomization helps fixed-point computation. Inspired by this open problem and recent advances on equilibrium computation, we have been fascinated by the following question: Is a fixed-point or an equilibrium fundamentally harder to find than a local optimum? In this paper, we give a nearly-tight bound of Omega(n)^{d-1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over [1:n]^d. Since the randomized query complexity of global optimization over [1:n]^d is Theta (n^{d}), the randomized query model over [1:n]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the query model; the deterministic complexity of this problem is Theta (n^{d-1}).

arXiv:cs/0702088•Feb 16, 2007•2 citations

An N/4 fixed-point duality quantum search algorithm

Liang Hao, Dan Liu, GuiLu Long

Science China Physics Mechanics and Astronomy•Jul 26, 2010•23 citations

Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation

Xi Chen, Shang‐Hua Teng

In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid \left[ {1:n} \right]^d from \Theta (n^{d - 1} ) to {\rm O}(d^{1/2} n^{d/2} ). It remains open whether randomization helps fixed-point computation. Inspired by the recent advances on the complexity of equilibrium computation, we solve this open problem by giving an asymptotically tight bound of (\Omega (n))^{d - 1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid \left[ {1:n} \right]^d Our result can be extended to the black-box query model for Sperner's Lemma in any dimension. It also yields a tight bound for the computation of d-dimensional approximate Brouwer fixed points as defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. Since the randomized query complexity of global optimization over \left[ {1:n} \right]^d is \Theta (n^d ), the randomized query model over \left[ {1:n} \right]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the black-box query model. Our randomized lower bound matches the deterministic complexity of this problem, which is \Theta (n^{d - 1} ).

Annual Symposium on Foundations of Computer Science•Oct 1, 2007•0 citations
For the unsorted database quantum search with the unknown fraction λ of target items, there are mainly two kinds of methods, i.e., fixed-point and trail-and-error. (i) In terms of the fixed-point method, Yoder et al. [Phys. Rev. Lett. 113 210501 (2014)] claimed that the quadratic speedup over classical algorithms has been achieved. However, in this paper, we point out that this is not the case, because the query complexity of Yoder’s algorithm is actually in O ( 1 / λ 0 ) rather than O ( 1 / λ ) , where λ 0 is a known lower bound of λ. (ii) In terms of the trail-and-error method, currently the algorithm without randomness has to take more than 1 times queries or iterations than the algorithm with randomly selected parameters. For the above problems, we provide the first hybrid quantum search algorithm based on the fixed-point and trail-and-error methods, where the matched multiphase Grover operations are trialed multiple times and the number of iterations increases exponentially along with the number of trials. The upper bound of expected queries as well as the optimal parameters are derived. Compared with Yoder’s algorithm, the query complexity of our algorithm indeed achieves the optimal scaling in λ for quantum search, which reconfirms the practicality of the fixed-point method. In addition, our algorithm also does not contain randomness, and compared with the existing deterministic algorithm, the query complexity can be reduced by about 1/3. Our work provides a new idea for the research on fixed-point and trial-and-error quantum search.
In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over [1:n]^d from Theta (n^{d-1}) to O (d^{1/2}n^{d/2}). It remains open whether randomization helps fixed-point computation. Inspired by this open problem and recent advances on equilibrium computation, we have been fascinated by the following question: Is a fixed-point or an equilibrium fundamentally harder to find than a local optimum? In this paper, we give a nearly-tight bound of Omega(n)^{d-1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over [1:n]^d. Since the randomized query complexity of global optimization over [1:n]^d is Theta (n^{d}), the randomized query model over [1:n]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the query model; the deterministic complexity of this problem is Theta (n^{d-1}).
In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid \left[ {1:n} \right]^d from \Theta (n^{d - 1} ) to {\rm O}(d^{1/2} n^{d/2} ). It remains open whether randomization helps fixed-point computation. Inspired by the recent advances on the complexity of equilibrium computation, we solve this open problem by giving an asymptotically tight bound of (\Omega (n))^{d - 1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid \left[ {1:n} \right]^d Our result can be extended to the black-box query model for Sperner's Lemma in any dimension. It also yields a tight bound for the computation of d-dimensional approximate Brouwer fixed points as defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. Since the randomized query complexity of global optimization over \left[ {1:n} \right]^d is \Theta (n^d ), the randomized query model over \left[ {1:n} \right]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the black-box query model. Our randomized lower bound matches the deterministic complexity of this problem, which is \Theta (n^{d - 1} ).