The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
Fixed-point quantum search with an optimal number of queries
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
abstract
Grover's quantum search and its generalization, quantum amplitude amplification, provide quadratic advantage over classical algorithms for a diverse set of tasks, but are tricky to use without knowing beforehand what fraction $\lambda$ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction, but, as a consequence, lose the very quadratic advantage that makes Grover's algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability, and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of $\lambda$.
fields
quant-ph 2representative citing papers
FinITE gives an exact identity linking LCU success probability to ground-subspace fidelity for diagonal Pauli-Z Hamiltonians, yielding a closed-form imaginary-time threshold beta-star based on spectral gap and initial overlap estimates.
citing papers explorer
-
A shortcut to an optimal quantum linear system solver
The paper gives a QLSS with query complexity (1+O(ε))κ ln(2√2/ε) using one kernel reflection when ||x|| is known, or O(κ log(1/ε)) overall, with explicit bound 56κ + 1.05κ ln(1/ε).
-
Finite Imaginary-Time Evolution for Polynomial Unconstrained Binary Optimization
FinITE gives an exact identity linking LCU success probability to ground-subspace fidelity for diagonal Pauli-Z Hamiltonians, yielding a closed-form imaginary-time threshold beta-star based on spectral gap and initial overlap estimates.