Joseph Cunningham, Jérémie Roland
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(\sqrt{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.