Quantum Search without Global Diffusion

• URL: http://arxiv.org/abs/2604.15435v1
• Date: Thu, 16 Apr 2026 18:00:27 GMT
• Title: Quantum Search without Global Diffusion
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum search is among the most important algorithms in quantum computing. At its core is quantum amplitude amplification, a technique that achieves a quadratic speedup over classical search by combining two global reflections: the oracle, which marks the target, and the diffusion operator, which reflects about the initial state. We show that this speedup can be preserved when the oracle is the only global operator, with all other operations acting locally on non-overlapping partitions of the search register. We present a recursive construction that, when the initial and target states both decompose as tensor products over these chosen partitions, admits an exact closed-form solution for the algorithm's dynamics. This is enabled by an intriguing degeneracy in the principal angles between successive reflections, which collapse to just two distinct values governed by a single recursively defined angle. Applied to unstructured search, a problem that naturally satisfies the tensor decomposition, the approach retains the $O(\sqrt{N})$ oracle complexity of Grover search when each partition contains at least $\log_2(\log_2 N)$ qubits. On an 18-qubit search problem, partitioning into two stages reduces the non-oracle circuit depth by as much as 51%-96% relative to Grover, requiring up to 9% additional oracle calls. For larger problem sizes this oracle overhead rapidly diminishes, and valuable depth reductions persist when the oracle circuit is substantially deeper than the diffusion operator. More broadly, these results show that a global diffusion operator is not necessary to achieve the quadratic speedup in quantum search, offering a new perspective on this foundational algorithm. Moreover, the scalar reduction at the heart of our analysis inspires and motivates new directions and innovations in quantum algorithm design and evaluation.

Related papers

• Exact and Optimal Recursive Quantum Search via Hilbert-Space Decomposition [0.0]
  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.
  arXiv  Detail & Related papers  (2026-08-24T09:05:00Z)
• Exponential convergence dynamics in Grover's search algorithm [0.0]
  Grover's search algorithm is the cornerstone of many applications of quantum computing.<n>We modify Grover's algorithm to eliminate the oscillatory dynamics, such that the search proceeds as an exponential decay into the solution states.<n>The basic idea is to convert the solution states into a reservoir by using ancilla qubits such that the initial state is nonreflectively absorbed.
  arXiv  Detail & Related papers  (2025-12-17T05:43:07Z)
• 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)
• QAMA: Scalable Quantum Annealing Multi-Head Attention Operator for Deep Learning [48.12231190677108]
  Quantum Annealing Multi-Head Attention (QAMA) is proposed, a novel drop-in operator that reformulates attention as an energy-based Hamiltonian optimization problem.<n>In this framework, token interactions are encoded into binary quadratic terms, and quantum annealing is employed to search for low-energy configurations.<n> Empirically, evaluation on both natural language and vision benchmarks shows that, across tasks, accuracy deviates by at most 2.7 points from standard multi-head attention.
  arXiv  Detail & Related papers  (2025-04-15T11:29:09Z)
• 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)
• Distributed Exact Generalized Grover's Algorithm [9.675088142486729]
  We propose a distributed Exactized Grover's Algorithm (DEGGA) to solve a generalized search problem. Our algorithm ensures accuracy, with a theoretical probability of identifying the target states at $100%$. Our method requires a total of $n$ qubits, eliminating the need for auxiliary qubits.
  arXiv  Detail & Related papers  (2024-05-11T09:17:11Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  We show that quantum Las Vegas query complexity is exactly equal to the quantum adversary bound. This is achieved by transforming a feasible solution to the adversary inversion problem into a quantum query algorithm.
  arXiv  Detail & Related papers  (2023-01-05T11:05:22Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Deterministic Grover search with a restricted oracle [2.976027966501599]
  Grover's quantum search algorithm provides a quadratic quantum advantage over classical algorithms. We present a modified version to return the correct result with certainty without having user control over the quantum search oracle.
  arXiv  Detail & Related papers  (2022-01-01T02:04:11Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

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.