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 (52)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- Quantum Mechanics helps in searching for a needle in a haystack
- Adiabatic Quantum Computing
- Strengths and Weaknesses of Quantum Computing
- Quantum Algorithms Revisited
- Quantum Computation and Decision Trees
- Holonomic Quantum Computation
- Exponential algorithmic speedup by quantum walk
- Spatial search by quantum walk
- Quantum Search by Local Adiabatic Evolution
- Quantum Zeno subspaces
- Quantum Computing Using Dissipation to Remain in a Decoherence-Free Subspace
- Efficient Simulation of Quantum Systems by Quantum Computers
- Quantum Zeno dynamics: mathematical and physical aspects
- Quantum Adiabatic Markovian Master Equations
- Quantum back-action of variable-strength measurement
- Analytic control methods for high fidelity unitary operations in a weakly nonlinear oscillator
- Measuring and Suppressing Quantum State Leakage in a Superconducting Qubit
- Decoherence in quantum walks - a review
- Adiabatic approximation in open quantum systems
- Ultra-bright Quantum Photon Sources on Chip
- Spatial search by quantum walk is optimal for almost all graphs
- Confined quantum Zeno dynamics of a watched atomic arrow
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Zeno effect for quantum computation and control
- Modernizing Quantum Annealing using Local Searches
- Stable Quantum-Correlated Many Body States through Engineered Dissipation
- Adiabaticity in open quantum systems
- Annealing by simulating the coherent Ising machine
- Quantum dynamics of an electromagnetic mode that cannot contain N photons
- Quantum search by measurement
- Climbing Mount Scalable: Physical-Resource Requirements for a Scalable Quantum Computer
- Quantum Computing in Plato's Cave
- Adiabatic Approximation for weakly open systems
- Quantum search with hybrid adiabatic-quantum walk algorithms and realistic noise
- Antibunched Emission of Photon-Pairs via Quantum Zeno Blockade
- Finding spin-glass ground states using quantum walks
- Constrained Optimization via Quantum Zeno Dynamics
- Experimental demonstration of interaction-free all-optical switching via the quantum Zeno effect
- One bound to rule them all: from Adiabatic to Zeno
- An energetic perspective on rapid quenches in quantum annealing
- Photonic Nonlinearities via Quantum Zeno Blockade
- Interaction-Free All-Optical Switching via Quantum-Zeno Effect
- Search range in experimental quantum annealing
- Practical designs for permutation symmetric problem Hamiltonians on hypercubes
- Guided quantum walk
- Continuous-time quantum walks for MAX-CUT are hot
- Scalable universal holonomic quantum computation realized with an adiabatic quantum data bus and potential implementation using superconducting flux qubits
- Duality in Quantum Quenches and Classical Approximation Algorithms: Pretty Good or Very Bad
- Coherent interaction-free detection of microwave pulses with a superconducting circuit
- Rapid quantum approaches for combinatorial optimisation inspired by optimal state-transfer
- Tunable Tradeoff between Quantum and Classical Computation via Nonunitary Zeno-like Dynamics