Exact and Optimal Recursive Quantum Search via Hilbert-Space Decomposition

• URL: http://arxiv.org/abs/2608.23002v1
• Date: Mon, 24 Aug 2026 09:05:00 GMT
• Title: Exact and Optimal Recursive Quantum Search via Hilbert-Space Decomposition
• Abstract summary: Current approaches to quantum search fail to deeply exploit extant structure in the underlying Hilbert space.<n>We present a new decomposition technique acting directly on this structure.<n>When initial and target states factorise over this partition, dynamics reduce to a single rotation in a two-dimensional plane.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Current approaches to quantum search fail to deeply exploit extant structure in the underlying Hilbert space. Decomposing the search by this structure empowers new strategies and formulations for quantum search and algorithm design. We present a new decomposition technique acting directly on this structure by recursively decomposing the Hilbert space and constructing the search operator from reflections over the resulting partition. When initial and target states factorise over this partition, dynamics reduce to a single rotation in a two-dimensional plane at each level, with angle given by a scalar recurrence. This recurrence avoids error accumulation from separately bounding success probabilities at each level, yielding an exact state description enabling treatment of the recursion as a whole. We obtain the target state deterministically and derive oracle and non-oracle costs independently of the search setting. For unstructured search, our approach attains the simultaneously optimal $Θ(\sqrt{N})$ oracle and non-oracle gate counts. For spatial search on $d$-dimension grids, it recovers the $O(\sqrt{N})$ time for $d\geq3$ and the $O\bigl(\sqrt{N}(\log N)^{3/2}\bigr)$ bound of Aaronson and Ambainis for $d=2$. The exact description of the recursion extends over our decomposition to new subdivision structures and provides a new approach for applying and analysing recursion in quantum algorithm design.

Related papers

• Ancilla-mediated fixed-point quantum search using Grover iterations [0.0]
  Grover's quantum search algorithm provides a fundamental quadratic speedup for unstructured datasets.<n>We present an ancilla-mediated fixed-point quantum search algorithm that achieves robust convergence.
  arXiv  Detail & Related papers  (2026-08-30T15:13:14Z)
• SILAGE: Memory-Efficient, Full-Gradient-Free Nonconvex Optimization for Nested Finite Sums [51.49970814177172]
  Empirical risk on datasets naturally exhibits similarities in $N=nm$ total samples.<n>We provide an analysis that avoids pessimistic convergence analysis.<n>Our results improve existing state-of-the-art regimes.
  arXiv  Detail & Related papers  (2026-06-14T14:11:07Z)
• Quantum Search without Global Diffusion [0.0]
  Quantum search is among the most important algorithms in quantum computing.<n>At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search.<n>We show that this speedup can be preserved when the oracle is the only global operator.
  arXiv  Detail & Related papers  (2026-04-16T18:00:27Z)
• Achieving double-logarithmic precision dependence in optimization-based quantum unstructured search [17.013842168748127]
  We show that the RMN method numerically achieves a quadratic convergence rate with respect to the error $varepsilon$, implying a complexity of $O(sqrtN/M loglog (1/varepsilon)$.
  arXiv  Detail & Related papers  (2026-03-27T03:19:27Z)
• A Grover-compatible manifold optimization algorithm for quantum search [17.013842168748127]
  Grover's algorithm is a fundamental quantum algorithm that offers a quadratic speedup for the unstructured search problem.<n>We show that Grover's algorithm matches the speedup of $O(qrstN)$ achieved by Grover's algorithm.
  arXiv  Detail & Related papers  (2025-12-09T10:01:55Z)
• Deterministic Quantum Search via Recursive Oracle Expansion [0.0]
  We introduce a novel deterministic quantum search algorithm that provides a practical alternative to conventional probabilistic search approaches.<n>Our scheme eliminates the inherent uncertainty of quantum search without relying on arbitrary phase rotations.<n>We show that, despite the increased query complexity, this design reduces the total number of two-qubit gates required for diffusion by more than an order of magnitude for search spaces up to at least 18 qubits.
  arXiv  Detail & Related papers  (2025-07-21T16:57:15Z)
• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs [60.40452803295326]
  We propose a new reward-free algorithm for learning linear Markov decision processes (MDPs) At the core of our algorithm is uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward. We show that our algorithm only needs to explore $tilde O( d2varepsilon-2)$ episodes to find an $varepsilon$-optimal policy.
  arXiv  Detail & Related papers  (2023-03-17T17:53:28Z)
• Deterministic Nonsmooth Nonconvex Optimization [82.39694252205011]
  We show that randomization is necessary to obtain a dimension-free dimension-free algorithm.<n>Our algorithm yields the first deterministic dimension-free algorithm for optimizing ReLU networks.
  arXiv  Detail & Related papers  (2023-02-16T13:57:19Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  We propose a new Hessian inverse free Fully Single Loop Algorithm for bilevel optimization problems. We show that our algorithm converges with the rate of $O(epsilon-2)$.
  arXiv  Detail & Related papers  (2021-12-09T02:27:52Z)
• On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
  This paper analyzes the trajectories of gradient descent (SGD) We show that SGD avoids saddle points/manifolds with $1$ for strict step-size policies.
  arXiv  Detail & Related papers  (2020-06-19T14:11:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.