Grover Speedup from Many Forms of the Zeno Effect
arXiv:2305.11146 · doi:10.22331/q-2024-11-20-1532
Abstract
It has previously been established that adiabatic quantum computation, operating based on a continuous Zeno effect due to dynamical phases between eigenstates, is able to realise an optimal Grover-like quantum speedup. In other words, is able to solve an unstructured search problem with the same scaling as Grover's original algorithm. A natural question is whether other manifestations of the Zeno effect can also support an optimal speedup in a physically realistic model (through direct analogue application rather than indirectly by supporting a universal gateset). In this paper we show that they can support such a speedup, whether due to measurement, decoherence, or even decay of the excited state into a computationally useless state. Our results also suggest a wide variety of methods to realise speedup which do not rely on Zeno behaviour. We group these algorithms into three families to facilitate a structured understanding of how speedups can be obtained: one based on phase kicks, containing adiabatic computation and continuous-time quantum walks; one based on dephasing and measurement; and finally one based on destruction of the amplitude within the excited state, for which we are not aware of any previous results. These results suggest that there may be exciting opportunities for new paradigms of analog quantum computing based on these effects.
Referee recommended changes in v3 and v4 accepted in Quantum, v5 is accepted version
References in corpus (16)
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Quantum Zeno dynamics: mathematical and physical aspects
- Quantum back-action of variable-strength measurement
- Analytic control methods for high fidelity unitary operations in a weakly nonlinear oscillator
- Decoherence in quantum walks - a review
- Adiabatic approximation in open quantum systems
- Stable Quantum-Correlated Many Body States through Engineered Dissipation
- Quantum dynamics of an electromagnetic mode that cannot contain N photons
- Quantum Computing in Plato's Cave
- Constrained Optimization via Quantum Zeno Dynamics
- One bound to rule them all: from Adiabatic to Zeno
- Guided quantum walk
- Continuous-time quantum walks for MAX-CUT are hot
- Coherent interaction-free detection of microwave pulses with a superconducting circuit
- Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer