2026-07-23T20:02:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20677 2024-08-26T09:43:29Z ddc:004 open_access

Eigenpath Traversal by Poisson-Distributed Phase Randomisation Cunningham, Joseph Roland, Jérémie Randomisation method Non-unitary adiabatic theorems Grover problem Quantum linear systems problem We present a framework for quantum computation, similar to Adiabatic Quantum Computation (AQC), that is based on the quantum Zeno effect. By performing randomised dephasing operations at intervals determined by a Poisson process, we are able to track the eigenspace associated to a particular eigenvalue. We derive a simple differential equation for the fidelity, leading to general theorems bounding the time complexity of a whole class of algorithms. We also use eigenstate filtering to optimise the scaling of the complexity in the error tolerance ε. In many cases the bounds given by our general theorems are optimal, giving a time complexity of O(1/Δ_m) with Δ_m the minimum of the gap. This allows us to prove optimal results using very general features of problems, minimising the problem-specific insight necessary. As two applications of our framework, we obtain optimal scaling for the Grover problem (i.e. O(√N) where N is the database size) and the Quantum Linear System Problem (i.e. O(κlog(1/ε)) where κ is the condition number and ε the error tolerance) by direct applications of our theorems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joseph Cunningham and Jérémie Roland 2024 Is Part Of LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2024.7 urn:nbn:de:0030-drops-206779 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.7 eng https://creativecommons.org/licenses/by/4.0/legalcode