Bereiche | Tage | Auswahl | Suche | Aktualisierungen | Downloads | Hilfe
Q: Fachverband Quantenoptik und Photonik
Q 46: Open Quantum Systems II
Q 46.6: Vortrag
Donnerstag, 5. März 2026, 12:30–12:45, P 4
Time complexity of dissipative quantum search with resetting — •Sayan Roy1,2, Emma King1,2, Francesco Mattiotti2, Markus Bläser3,4, and Giovanna Morigi2,4 — 1Equal contribution — 2Theoretical Physics, Saarland University, 66123 Saarbrücken, Germany — 3FR Informatics, Saarland University, 66123 Saarbrücken, Germany — 4Center for Quantum Technologies (QuTe), Saarland University, Campus, 66123 Saarbrücken, Germany
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 scaling of the search time with the database size N, ts∼ √N. Numerical studies suggest that the time complexity ts can change in the presence of feedback, injecting information during the search. We determine the time complexity of the quantum analog of a randomized algorithm, which implements feedback in its simplest 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 to the initial state 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. We identify parameter regimes in which the search time scales as ts∼ Nα with α<1/2, achieving a time complexity that may surpass the Grover optimal bound.
Keywords: Quantum Search; Quantum Resetting; Algorithimic Complexity; Non-Hermitian Dynamics; Continuous-Time Quantum Walk