Time complexity of a monitored quantum search with resetting

• URL: http://arxiv.org/abs/2601.20560v1
• Date: Wed, 28 Jan 2026 12:55:49 GMT
• Title: Time complexity of a monitored quantum search with resetting
• Authors: Emma C. King, Sayan Roy, Francesco Mattiotti, Maximilian Kiefer-Emmanouilidis, Markus Bläser, Giovanna Morigi,
• Abstract summary: We study the time complexity of a quantum analog of a randomized algorithm, which implements feedback in a simple form.<n>The search is a continuous-time quantum walk on a complete graph, where the target is continuously monitored by a detector.<n>We optimize the search time as a function of the hopping amplitude, detection rate, and resetting rate, and identify the conditions under which time complexity could outperform Grover's scaling.
• Score: 7.7152006741337615
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Searching a database is a central task in computer science and is paradigmatic of transport and optimization problems in physics. For an unstructured search, Grover's algorithm predicts a quadratic speedup, with the search time $τ(N)=Θ(\sqrt{N})$ and $N$ the database size. Numerical studies suggest that the time complexity can change in the presence of feedback, injecting information during the search. Here, we determine the time complexity of the quantum analog of a randomized algorithm, which implements feedback in a simple form. The search is a continuous-time quantum walk on a complete graph, where the target is continuously monitored by a detector. Additionally, the quantum state is reset if the detector does not click within a specified time interval. This yields a non-unitary, non-Markovian dynamics. We optimize the search time as a function of the hopping amplitude, detection rate, and resetting rate, and identify the conditions under which time complexity could outperform Grover's scaling. The overall search time does not violate Grover's optimality bound when including the time budget of the physical implementation of the measurement. For databases of finite sizes monitoring can warrant rapid convergence and provides a promising avenue for fault-tolerant quantum searches.

Related papers

• Adiabatic quantum unstructured search in parallel [0.0]
  We present an optimized adiabatic quantum schedule for unstructured search building.<n>In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time.<n>Our findings suggest that quantum advantage may still be achievable under constrained coherence times.
  arXiv  Detail & Related papers  (2025-02-12T17:32:27Z)
• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  lattice-based cryptography is one of the main candidates of post-quantum cryptography.<n> cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP)<n>Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
  arXiv  Detail & Related papers  (2024-10-17T16:54:41Z)
• Constant-Time Quantum Search with a Many-Body Quantum System [39.58317527488534]
  We consider a many-body quantum system that naturally effects parallel queries. We show that its parameters can be tuned to search a database in constant time.
  arXiv  Detail & Related papers  (2024-08-09T22:57:59Z)
• Dynamical localization in 2D topological quantum random walks [0.0]
  We study the dynamical localization of discrete time evolution of topological split-step quantum random walk (QRW) on a single-site defect.<n>By investigating the spectral properties of the discrete-time evolution operators, we show that trapped states have large overlap with the initial uniformly distributed state.<n>We show that mechanism of localization we identified is robust against the influence of disorder.
  arXiv  Detail & Related papers  (2024-06-26T21:36:47Z)
• Quantum algorithms for Hopcroft's problem [45.45456673484445]
  We study quantum algorithms for Hopcroft's problem which is a fundamental problem in computational geometry. The classical complexity of this problem is well-studied, with the best known algorithm running in $O(n4/3)$ time. Our results are two different quantum algorithms with time complexity $widetilde O(n5/6)$.
  arXiv  Detail & Related papers  (2024-05-02T10:29:06Z)
• Deterministic Search on Complete Bipartite Graphs by Continuous Time Quantum Walk [0.8057006406834466]
  This paper presents a deterministic search algorithm on complete bipartite graphs. We address the most general case of multiple marked states, so there is a problem of estimating the number of marked states. We construct a quantum counting algorithm based on the spectrum structure of the search operator.
  arXiv  Detail & Related papers  (2024-04-02T05:09:33Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45:19Z)
• Iterative Qubits Management for Quantum Index Searching in a Hybrid System [56.39703478198019]
  IQuCS aims at index searching and counting in a quantum-classical hybrid system. We implement IQuCS with Qiskit and conduct intensive experiments. Results demonstrate that it reduces qubits consumption by up to 66.2%.
  arXiv  Detail & Related papers  (2022-09-22T21:54:28Z)
• Quantum speedup for track reconstruction in particle accelerators [51.00143435208596]
  We identify four fundamental routines present in every local tracking method and analyse how they scale in the context of a standard tracking algorithm. Although the found quantum speedups are mild, this constitutes to the best of our knowledge, the first rigorous evidence of a quantum advantage for a high-energy physics data processing task.
  arXiv  Detail & Related papers  (2021-04-23T13:32:14Z)
• Hardware Efficient Quantum Search Algorithm [17.74233101199813]
  We propose a novel hardware efficient quantum search algorithm to overcome this challenge. Our key idea is to replace the global diffusion operation with low-cost local diffusions. The circuit cost reduction leads to a remarkable improvement in the system success rates.
  arXiv  Detail & Related papers  (2021-03-26T01:08:50Z)
• Efficient Algorithms for Causal Order Discovery in Quantum Networks [44.356294905844834]
  Given black-box access to the input and output systems, we develop the first efficient quantum causal order discovery algorithm. We model the causal order with quantum combs, and our algorithms output the order of inputs and outputs that the given process is compatible with. Our algorithms will provide efficient ways to detect and optimize available transmission paths in quantum communication networks.
  arXiv  Detail & Related papers  (2020-12-03T07:12:08Z)
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed [0.0]
  We report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state.
  arXiv  Detail & Related papers  (2020-01-13T19:01:09Z)

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.