Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2305.11146 · Quantum

Grover Speedup from Many Forms of the Zeno Effect

Jesse Berwald, Nicholas Chancellor, Raouf Dridi

Published Nov 20, 2024• 7 citations
arXivHTMLPDF

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 N 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.

DOI
10.22331/q-2024-11-20-1532

Related papers

Quantum Zeno effect versus adiabatic quantum computing and quantum annealing

Naser Ahmadiniaz, Dennis Kraft, Gernot Schaller +1 more

Abstract For the adiabatic version of Grover’s quantum search algorithm as proposed by Roland and Cerf, we study the impact of decoherence caused by a rather general coupling to some environment. For quite generic conditions, we find that the quantum Zeno effect poses strong limitations on the performance (quantum speed-up) since the environment effectively measures the state of the system permanently and thereby inhibits or slows down quantum transitions. Generalizing our results, we find that similar restrictions should apply universally to adiabatic quantum algorithms and quantum annealing schemes which are based on analogous isolated Landau–Zener type transitions at avoided level crossings (similar to first-order phase transitions). As a possible resort, more gradual changes of the quantum state (as in second-order phase transitions) or suitable error-correcting schemes such as the spin-echo method may alleviate this problem.

arXiv:2509.04057•New Journal of Physics•May 15, 2026•0 citations

Zeno-effect computation: Opportunities and challenges

Jesse Berwald, Nicholas Chancellor, Raouf Dridi

Adiabatic quantum computing has demonstrated how the quantum Zeno effect can be used to construct quantum optimizers. However, much less work has been done to understand how more general Zeno effects could be used in a similar setting. We use a construction based on three-state systems rather than directly in qubits, so that a qubit can remain after projecting out one of the states. We find that our model of computing is able to recover the dynamics of a transverse field Ising model. Several generalizations are possible, but our methods allow for constraints to be implemented nonperturbatively and do not need tunable couplers, unlike simple transverse field implementations. We further discuss how to implement the protocol physically using methods building on stimulated Raman adiabatic passage (STIRAP) protocols for state transfer. We find a substantial challenge that settings defined exclusively by measurement or dissipative Zeno effects do not allow for frustration, and in these settings pathological spectral features arise leading to unfavorable runtime scaling. We discuss methods to overcome this challenge, for example including gain as well as loss as is often done in an optical setting.

arXiv:2311.08432•Physical Review A•Apr 28, 2025•4 citations

Open-System Adiabatic Quantum Search under Dephasing

Afaf El Kalai, Peter J. Eder, Christian B. Mendl

Adiabatic quantum algorithms must evolve slowly enough to suppress non-adiabatic transitions while remaining fast enough to be practical. In open systems, this trade-off is reshaped by decoherence. For Hamiltonians subject to dephasing Lindbladians, Avron et al. [Phys. Rev. A 82, 040304(R) (2010)] showed that a unique timetable exists that maximizes the fidelity with a target state. This optimal schedule is characterized by a constant tunneling rate along the adiabatic path. In this work, we revisit their analysis and apply it to the adiabatic Grover search framework, obtaining closed-form expressions for the optimal evolution schedule, the minimum runtime, and the resulting achievable fidelity. Moreover, by invoking an energy-time uncertainty argument, we identify a critical dephasing threshold beyond which further noise-assisted acceleration is prohibited, showing that the apparent advantage of strong dephasing is a Zeno-type stabilization mechanism rather than a conventional algorithmic speedup over unitary Grover search.

quant-pharXiv:2603.28506•Physical Review A•Mar 31, 2026•0 citations

Quantum Computation Based Grover’s Search Algorithm and its Variations

Kapil Kumar Soni, Akhtar Rasool

Background: The future computations need parallelism, and a way to achieve the same is through quantum-based specific properties. Quantum computation supports exponential operation to be performed in parallel over a single execution step and hence achieves computational speedup. Objective: One of the quantum-based algorithms allows to search the key element over an index based unstructured database and succeeds to obtain the speedup. In the whole context of article writing, our approach reviews the significance of quantum computing, the basics required for quantum computation and their quantum logic-based circuit operations. Method: The article focuses on Grover’s search algorithm and its variations, and then illustrates the relevant amplitude amplification & phase matching techniques in accordance with the advantages and limitation to the specific perspective. Results: We made the comparative analysis between the amplitude amplification-based static & dynamic Grover’s searching and phase estimation technique. Along with this, we justified the possibilities of the empirical results and observed facts over Grover’s variant approaches. Conclusion: Finally, we conclude the analytical comparison between quantum-based searching techniques along with the applicability of Grover’s algorithm in practical computational science.

Recent Patents on Engineering•Jul 16, 2020•0 citations

Fixed-point adiabatic quantum search

Alexander M. Dalzell, Theodore J. Yoder, Isaac L. Chuang

Fixed-point quantum search algorithms succeed at finding one of $M$ target items among $N$ total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property---the fraction of target items must be known precisely to know when to terminate the algorithm. Recently, Yoder, Low, and Chuang [Phys. Rev. Lett. 113, 210501 (2014)] gave an optimal gate-model search algorithm with the fixed-point property. Previously, it had been discovered by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)] that an adiabatic quantum algorithm, operating by continuously varying a Hamiltonian, can reproduce the quadratic speedup of gate-model Grover search. We ask, can an adiabatic algorithm also reproduce the fixed-point property? We show that the answer depends on what interpolation schedule is used, so as in the gate model, there are both fixed-point and non-fixed-point versions of adiabatic search, only some of which attain the quadratic quantum speedup. Guided by geometric intuition on the Bloch sphere, we rigorously justify our claims with an explicit upper bound on the error in the adiabatic approximation. We also show that the fixed-point adiabatic search algorithm can be simulated in the gate model with neither loss of the quadratic Grover speedup nor of the fixed-point property. Finally, we discuss natural uses of fixed-point algorithms such as preparation of a relatively prime state and oblivious amplitude amplification.

arXiv:1609.03603•Physical Review A•Jan 11, 2017•26 citations

Quantum search with hybrid adiabatic–quantum-walk algorithms and realistic noise

James G. Morley, Nicholas Chancellor, Sougato Bose +1 more

Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.

arXiv:1709.00371•Physical Review A•Feb 28, 2019•46 citations
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 N 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.
Abstract For the adiabatic version of Grover’s quantum search algorithm as proposed by Roland and Cerf, we study the impact of decoherence caused by a rather general coupling to some environment. For quite generic conditions, we find that the quantum Zeno effect poses strong limitations on the performance (quantum speed-up) since the environment effectively measures the state of the system permanently and thereby inhibits or slows down quantum transitions. Generalizing our results, we find that similar restrictions should apply universally to adiabatic quantum algorithms and quantum annealing schemes which are based on analogous isolated Landau–Zener type transitions at avoided level crossings (similar to first-order phase transitions). As a possible resort, more gradual changes of the quantum state (as in second-order phase transitions) or suitable error-correcting schemes such as the spin-echo method may alleviate this problem.
Adiabatic quantum computing has demonstrated how the quantum Zeno effect can be used to construct quantum optimizers. However, much less work has been done to understand how more general Zeno effects could be used in a similar setting. We use a construction based on three-state systems rather than directly in qubits, so that a qubit can remain after projecting out one of the states. We find that our model of computing is able to recover the dynamics of a transverse field Ising model. Several generalizations are possible, but our methods allow for constraints to be implemented nonperturbatively and do not need tunable couplers, unlike simple transverse field implementations. We further discuss how to implement the protocol physically using methods building on stimulated Raman adiabatic passage (STIRAP) protocols for state transfer. We find a substantial challenge that settings defined exclusively by measurement or dissipative Zeno effects do not allow for frustration, and in these settings pathological spectral features arise leading to unfavorable runtime scaling. We discuss methods to overcome this challenge, for example including gain as well as loss as is often done in an optical setting.
Adiabatic quantum algorithms must evolve slowly enough to suppress non-adiabatic transitions while remaining fast enough to be practical. In open systems, this trade-off is reshaped by decoherence. For Hamiltonians subject to dephasing Lindbladians, Avron et al. [Phys. Rev. A 82, 040304(R) (2010)] showed that a unique timetable exists that maximizes the fidelity with a target state. This optimal schedule is characterized by a constant tunneling rate along the adiabatic path. In this work, we revisit their analysis and apply it to the adiabatic Grover search framework, obtaining closed-form expressions for the optimal evolution schedule, the minimum runtime, and the resulting achievable fidelity. Moreover, by invoking an energy-time uncertainty argument, we identify a critical dephasing threshold beyond which further noise-assisted acceleration is prohibited, showing that the apparent advantage of strong dephasing is a Zeno-type stabilization mechanism rather than a conventional algorithmic speedup over unitary Grover search.
Background: The future computations need parallelism, and a way to achieve the same is through quantum-based specific properties. Quantum computation supports exponential operation to be performed in parallel over a single execution step and hence achieves computational speedup. Objective: One of the quantum-based algorithms allows to search the key element over an index based unstructured database and succeeds to obtain the speedup. In the whole context of article writing, our approach reviews the significance of quantum computing, the basics required for quantum computation and their quantum logic-based circuit operations. Method: The article focuses on Grover’s search algorithm and its variations, and then illustrates the relevant amplitude amplification & phase matching techniques in accordance with the advantages and limitation to the specific perspective. Results: We made the comparative analysis between the amplitude amplification-based static & dynamic Grover’s searching and phase estimation technique. Along with this, we justified the possibilities of the empirical results and observed facts over Grover’s variant approaches. Conclusion: Finally, we conclude the analytical comparison between quantum-based searching techniques along with the applicability of Grover’s algorithm in practical computational science.
Fixed-point quantum search algorithms succeed at finding one of MMM target items among NNN total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property---the fraction of target items must be known precisely to know when to terminate the algorithm. Recently, Yoder, Low, and Chuang [Phys. Rev. Lett. 113, 210501 (2014)] gave an optimal gate-model search algorithm with the fixed-point property. Previously, it had been discovered by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)] that an adiabatic quantum algorithm, operating by continuously varying a Hamiltonian, can reproduce the quadratic speedup of gate-model Grover search. We ask, can an adiabatic algorithm also reproduce the fixed-point property? We show that the answer depends on what interpolation schedule is used, so as in the gate model, there are both fixed-point and non-fixed-point versions of adiabatic search, only some of which attain the quadratic quantum speedup. Guided by geometric intuition on the Bloch sphere, we rigorously justify our claims with an explicit upper bound on the error in the adiabatic approximation. We also show that the fixed-point adiabatic search algorithm can be simulated in the gate model with neither loss of the quadratic Grover speedup nor of the fixed-point property. Finally, we discuss natural uses of fixed-point algorithms such as preparation of a relatively prime state and oblivious amplitude amplification.
Computing using a continuous-time evolution, based on the natural interaction Hamiltonian of the quantum computer hardware, is a promising route to building useful quantum computers in the near term. Adiabatic quantum computing, quantum annealing, computation by a continuous-time quantum walk, and special purpose quantum simulators all use this strategy. In this work, we carry out a detailed examination of adiabatic and quantum-walk implementation of the quantum search algorithm, using the more physically realistic hypercube connectivity, rather than the complete graph, for our base Hamiltonian. We calculate optimal adiabatic schedules both analytically and numerically for the hypercube and then interpolate between adiabatic and quantum-walk searching, obtaining a family of hybrid algorithms. We show that all of these hybrid algorithms provide the quadratic quantum speedup when run with optimal parameter settings, which we determine and discuss in detail. We incorporate the effects of multiple runs of the same algorithm, noise applied to the qubits, and two types of problem misspecification, determining the optimal hybrid algorithm for each case. Our results reveal a rich structure of how these different computational mechanisms operate and should be balanced in different scenarios. For large systems with low noise and good control, a quantum walk is the best choice, while hybrid strategies can mitigate the effects of many shortcomings in hardware and problem misspecification.