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 · 2025

Read Fixed-point quantum continuous search algorithm with optimal query complexity by Shan Jin, Yuhan Huang, Shaojun Wu, Guanyu Zhou, Chang-Ling Zou, Luyan Sun, Xiaoting Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-15556.txt.

Introduction

Searching a smooth, endless space for a target is a quantum task with no floor known. Shan Jin and co-authors supply both the method and the floor, in work from twenty twenty-five. Their fixed-point search rides continuous variables and keeps the famous square-root speedup. No wandering off target occurs as rounds grow.

A matching lower bound proves no quantum search can ask fewer questions, so the method is optimal. Oracle designs for real cases are spelled out. The frame covers both tuning problems and eigenvalue hunts. Continuous search now stands on the same firm ground as its discrete cousin.

Catalog record

CREATORShan Jin, Yuhan Huang, Shaojun Wu, Guanyu Zhou, Chang-Ling Zou, Luyan Sun, Xiaoting Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-15556

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

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 Abstract Continuous search problems (CSPs), which involve finding solutions within a continuous domain, frequently arise in fields such as optimization, physics, and engineering. Unlike discrete search problems, CSPs require navigating an uncountably infinite space, presenting unique computational challenges. In this work, we propose a fixed-point quantum search algorithm that leverages continuous variables to address these challenges, achieving a quadratic speedup. Inspired by the discrete search results, we manage to establish a lower bound on the query complexity of arbitrary quantum search for CSPs, demonstrating the optimality of our approach. In addition, we demonstrate how to design the internal structure of the quantum search oracle for specific problems. Furthermore, we develop a general framework to apply this algorithm to a range of problem types, including optimization and eigenvalue problems involving continuous variables. I Introduction Continuous search problems (CSPs) focus on finding solutions within continuous domains, distinguishing them from discrete search problems that involve finite or countable sets. CSPs are common in fields where variables take values from uncountably infinite spaces, such as constrained optimization [ 1 ] , nonconvex optimization [ 2 ] , derivative-free optimization [ 3 ] , energy landscape [ 4 ] , as well as continuous-variable (CV) spectral problem [ 5 ] . The challenges of CSPs arise from the need to explore vast, often high-dimensional continuous spaces efficiently, which introduces huge computational complexities not present in discrete problems. With the advent of quantum computing, CSPs have gained new momentum due to the potential for quantum speedup. Quantum algorithms, such as the Deutsch-Jozsa algorithm [ 6 , 7 ] , Simon’s algorithm [ 8 ] , Shor’s algorithm [ 9 ] , Grover’s search algorithm [ 10 ] , and the HHL algorithm [ 11 ] , have demonstrated the advantages of quantum computation over classical computation. In particular, Grover’s quantum search algorithm offers a quadratic speedup compared to classical algorithms for solving a wide range of problems [ 10 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 ] . Furthermore, the concept of the quantum search algorithm can be extended to the amplitude amplification algorithm, facilitating quantum state preparation [ 13 , 15 , 21 ] . In spite of great success, due to the lack of precise determination of the number of marked states, the original Grover’s quantum search cannot effectively avoid “undercooking” or “overcooking” the initial states [ 26 ] . To address these issues, fixed-point quantum search algorithms have been proposed, which allow the quantum state to converge towards the target state without prior knowledge of the number of target items [ 22 , 23 ] . Several experimental platforms have been proposed for implementing quantum search algorithms, including cavity quantum electrodynamics (QED) [ 27 , 28 , 29 ] , trapped ions [ 30 , 31 , 32 ] , nuclear magnetic resonance (NMR) [ 33 , 34 ] , and optics [ 35 ] . Most established quantum search algorithms primarily focus on discrete search problems. Directly applying discrete quantum search to solve CSPs poses challenges due to the necessity of discretization. CSPs involve searching for solutions within continuous domains in \mathbb{R}^{d} . The discretization process requires (\frac{1}{\epsilon})^{d} points, where \epsilon represents the precision of the error and depends on the specific search problem. Complex problems demand higher accuracy level, i.e., smaller values for \epsilon , thereby increasing the complexity. In contrast to discrete-variable (DV), e.g. qubit-based quantum computing models, CV quantum computing models [ 36 ] possess unique characteristics and they are ideal models to deal with CV-related problems [ 37 , 38 , 39 , 40 , 41 , 42 , 43 , 44 , 45 , 46 , 47 , 48 , 49 , 50 , 51 , 52 ] . In fact, a CV-based quantum search algorithm has been proposed to solve discrete search problems [ 53 ] , which is unfortunately not immediately applicable to CSPs. To address this problem, in this work, we propose a CV fixed-point quantum search algorithm to solve CSPs while maintaining a quadratic speedup. Its fixed-point property ensures the convergence to the target solution without the issues of “undercooking” or “overcooking”. Similar to the quadratic speedup proven to be optimal in discrete quantum search [ 12 , 16 , 17 , 54 , 55 ] , we show that our algorithm achieves an optimal quadratic speedup for CSPs. Specifically, the complexity of our algorithm is \mathcal{O}(\frac{1}{\sqrt{\lambda}}) , where \lambda is the overlap between the target solution space and the search space. We prove that the lower bound on query complexity of an arbitrary query-based quantum algorithm to solving CSPs is \frac{1}{2\sqrt{2}}[(1+\sqrt{p}-\sqrt{1-p})\sqrt{n}-2] queries, where n\equiv\lceil\frac{1}{\lambda}\rceil and p is the probability of success. This confirms the optimality of our algorithm for CSPs. We also present how to design the internal structure of oracles for the desired CSPs and provide a practical scheme for their physical construction. Finally, we demonstrate applications of our algorithm to optimization and eigenvalue problems involving CVs, illustrating its versatility and potential impact across various domains. Figure 1: The quantum circuit of the proposed quantum search algorithm for CSPs. The circuit demonstrates a sequence of q Grover’s iterations with each iteration G(\alpha,\beta)\equiv R_{\varphi}(\alpha)R_{t}(\beta) , and Z(\alpha)\equiv e^{-i\alpha\hat{x}} and X(\beta)\equiv e^{-i\beta\hat{p}} are defined as the parametrized translation operators generated by \hat{x} and \hat{p} . The left part of the circuit implements \tilde{R}_{t}(\beta) , which is equal to R_{t}(\beta) when restricted to the 2D subspace \mathcal{T} . The right part implements R_{\varphi}(\alpha) , where |\varphi\rangle is the initial state with |\varphi\rangle=U|s\rangle . The unitary operation with |s\rangle as the control is |s\rangle\langle s|\otimes X(-1)+(I-|s\rangle\langle s|)\otimes I , with X(-1)=e^{i\hat{p}} . II Fixed-point quantum continuous search design In a CSP, we assume the search space is a compact, measurable region A\subset\mathbb{R}^{d} . In addition, we assume that the solution to the CSP constitutes a measurable sub-region Q\subset A , and is unknown to us prior to search. Our objective is to identify and locate at least one point in Q . We assume the availability of an oracle f which indicates whether a given input x\in A belongs to Q or not. Specifically, f is an indicator function, f:\bm{x}\in A\to\{0,1\} where f(\bm{x})=1 if \bm{x}\in Q and f(\bm{x})=0 if \bm{x}\in A/Q . Letting \lambda_{0}\equiv\frac{m(Q)}{m(A)} , where m(\cdot) denotes the measure, the average query complexity of finding out a solution in an unstructured CSP through oracle evaluation is \mathcal{O}(\frac{1}{\lambda_{0}}) . Our goal is to design a quantum continuous search algorithm that achieves a quadratic speedup, reducing the query complexity to \mathcal{O}(\frac{1}{\sqrt{\lambda_{0}}}) . Specifically, in Sec. II.1 , based on the unique features of CV quantum computing, we design the fundamental structure of the fixed-point quantum continuous search algorithm, including the choices of the initial and the target states, as well as the construction of the Grover’s iteration, composed of two consecutive rotation gates restricted in a 2-dimensional subspace. In Sec. II.2 , we focus on the specific design of the quantum continuous

Read the complete text