2024/06/06 by Joseph Cunningham, Cunningham, Joseph, Jérémie Roland +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #Diffusion and Search Dynamics #FOS: Computer and information sciences #FOS: Physical sciences #Modular Robots and Swarm Intelligence #Optimization and Search Problems #Quantum Physics (quant-ph)
paper · pdf · doi:10.48550/arxiv.2406.03972
openalex publication_date 2024/06/06 · openalex created_date 2024/06/08 · openalex updated_date 2026/07/28
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.