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:2001.04486 · Scientific Reports

Quantifying computational advantage of Grover’s algorithm with the trace speed

Valentin Gebhart, Luca Pezzè, Augusto Smerzi

Published Jan 14, 2021• 11 citations
arXivHTMLPDF

Abstract

Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.

DOI
10.1038/s41598-020-80153-z

Related papers

Coherence Fraction in Grover Search Algorithm

Si-Qi Zhou, Hai Jin, Jin-Min Liang +3 more

The question of which resources drive the advantages in quantum algorithms has long been a fundamental challenge. While entanglement and coherence are critical to many quantum algorithms, our results indicate that they do not fully explain the quantum advantage achieved by the Grover search algorithm. By introducing a generalized Grover search algorithm, we demonstrate that the success probability depends not only on the querying number of oracles but also on the coherence fraction, which quantifies the fidelity between an arbitrary initial quantum state and the equal superposition state. Additionally, we explore the role of the coherence fraction in the quantum minimization algorithm, which offers a framework for solving complex problems in quantum machine learning. These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.

quant-pharXiv:2511.06835•Physical Review A•Nov 11, 2025•6 citations

Coherence and Entanglement Monogamy in the Discrete Analogue of Analog Grover Search

Namit Anand, Arun Kumar Pati

Grover's search algorithm is the optimal quantum algorithm that can search an unstructured database quadratically faster than any known classical algorithm. The role of entanglement and correlations in the search algorithm have been studied in great detail and it is known that entanglement between the qubits is necessary to gain a quadratic speedup, for pure state implementation of the Grover search algorithm. Here, we systematically investigate the behavior of quantum coherence and monogamy of entanglement in the discrete analogue of the $\textit{analog analogue of Grover search algorithm}$. The analog analogue of Grover search is a continuous time quantum algorithm based on the adiabatic Hamiltonian evolution that gives a quadratic speedup, similar to the original Grover search algorithm. We show that the decrease of quantum coherence, quantified using various coherence monotones, is a clear signature of attaining the maximum success probability in the analog Grover search. We also show that for any two qubit reduced density matrix of the system, the concurrence evolves in close vicinity to the increasing rate of success probability. Furthermore, we show that the system satisfies a $n$-party monogamy inequality for arbitrary times, hence bounding the amount of $n$-qubit entanglement during the quantum search.

arXiv:1611.04542•Nov 14, 2016•24 citations

Analysis of Grover’s quantum search algorithm as a dynamical system

Ofer Biham, Daniel Shapira, Yishai Shimoni

Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success ${P}_{\mathrm{s}}$ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ and is shown to be independent of r. A class of states, which includes fixed points and cycles of the Grover iteration operator, is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states.

arXiv:quant-ph/0307141•Physical Review A•Aug 29, 2003•15 citations

Deriving Grover's lower bound from simple physical principles

Ciarán M. Lee, John H. Selby

Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between computational paths has been posited as a key resource behind this computational speed-up. However there is a limit to this interference, at most pairs of paths can ever interact in a fundamental way. Could more interference imply more computational power? Sorkin has defined a hierarchy of possible interference behaviours—currently under experimental investigation—where classical theory is at the first level of the hierarchy and quantum theory belongs to the second. Informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In this work, we consider how Grover's speed-up depends on the order of interference in a theory. Surprisingly, we show that the quadratic lower bound holds regardless of the order of interference. Thus, at least from the point of view of the search problem, post-quantum interference does not imply a computational speed-up over quantum theory.

arXiv:1604.03118•New Journal of Physics•Sep 23, 2016•39 citations

Quantifying Grover speed-ups beyond asymptotic analysis

Chris Cade, Marten Folkertsma, Ido Niesen +1 more

Run-times of quantum algorithms are often studied via an asymptotic, worst-case analysis. Whilst useful, such a comparison can often fall short: it is not uncommon for algorithms with a large worst-case run-time to end up performing well on instances of practical interest. To remedy this it is necessary to resort to run-time analyses of a more empirical nature, which for sufficiently small input sizes can be performed on a quantum device or a simulation thereof. For larger input sizes, alternative approaches are required.In this paper we consider an approach that combines classical emulation with detailed complexity bounds that include all constants. We simulate quantum algorithms by running classical versions of the sub-routines, whilst simultaneously collecting information about what the run-time of the quantum routine would have been if it were run instead. To do this accurately and efficiently for very large input sizes, we describe an estimation procedure and prove that it obtains upper bounds on the true expected complexity of the quantum algorithms.We apply our method to some simple quantum speedups of classical heuristic algorithms for solving the well-studied MAX- k -SAT optimization problem. This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines: Grover search with an unknown number of marked items, and quantum maximum-finding. These improve upon existing results and might be of broader interest.Amongst other results, we found that the classical heuristic algorithms we studied did not offer significant quantum speedups despite the existence of a theoretical per-step speedup. This suggests that an empirical analysis such as the one we implement in this paper already yields insights beyond those that can be seen by an asymptotic analysis alone.

arXiv:2203.04975•Quantum•Oct 10, 2023•4 citations

Quantum speed limit for observables from quantum asymmetry

Agung Budiyono, Michael Moody, Hadyan L. Prihadi +2 more

Quantum asymmetry and coherence are genuinely quantum resources that are essential to realize quantum advantage in information technologies. However, all quantum processes are fundamentally constrained by quantum speed limits, which raises the question on the corresponding bounds on the rate of consumption of asymmetry and coherence. In the present work, we derive a formulation of the quantum speed limit for observables in terms of the trace-norm asymmetry of the time-dependent quantum state relative to the observable. This quantum speed limit can be directly observed in experiment through weak value measurement and provides a lower bound to the quantum Fisher information about the parameter conjugate to the observable. It can be further related to quantum coherence relative to the eigenbasis of the observable. We obtain a complementary relation for the speed of three mutually unbiased observables for a single qubit. As an application, we derive a notion of a quantum thermodynamic speed limit.

quant-pharXiv:2511.16526•Physical Review A•Nov 21, 2025•0 citations
Despite intensive research, the physical origin of the speed-up offered by quantum algorithms remains mysterious. No general physical quantity, like, for instance, entanglement, can be singled out as the essential useful resource. Here we report a close connection between the trace speed and the quantum speed-up in Grover's search algorithm implemented with pure and pseudo-pure states. For a noiseless algorithm, we find a one-to-one correspondence between the quantum speed-up and the polarization of the pseudo-pure state, which can be connected to a wide class of quantum statistical speeds. For time-dependent partial depolarization and for interrupted Grover searches, the speed-up is specifically bounded by the maximal trace speed that occurs during the algorithm operations. Our results quantify the quantum speed-up with a physical resource that is experimentally measurable and related to multipartite entanglement and quantum coherence.
The question of which resources drive the advantages in quantum algorithms has long been a fundamental challenge. While entanglement and coherence are critical to many quantum algorithms, our results indicate that they do not fully explain the quantum advantage achieved by the Grover search algorithm. By introducing a generalized Grover search algorithm, we demonstrate that the success probability depends not only on the querying number of oracles but also on the coherence fraction, which quantifies the fidelity between an arbitrary initial quantum state and the equal superposition state. Additionally, we explore the role of the coherence fraction in the quantum minimization algorithm, which offers a framework for solving complex problems in quantum machine learning. These findings offer insights into the origins of quantum advantage and open pathways for the development of new quantum algorithms.
Grover's search algorithm is the optimal quantum algorithm that can search an unstructured database quadratically faster than any known classical algorithm. The role of entanglement and correlations in the search algorithm have been studied in great detail and it is known that entanglement between the qubits is necessary to gain a quadratic speedup, for pure state implementation of the Grover search algorithm. Here, we systematically investigate the behavior of quantum coherence and monogamy of entanglement in the discrete analogue of the analog analogue of Grover search algorithm\textit{analog analogue of Grover search algorithm}analog analogue of Grover search algorithm. The analog analogue of Grover search is a continuous time quantum algorithm based on the adiabatic Hamiltonian evolution that gives a quadratic speedup, similar to the original Grover search algorithm. We show that the decrease of quantum coherence, quantified using various coherence monotones, is a clear signature of attaining the maximum success probability in the analog Grover search. We also show that for any two qubit reduced density matrix of the system, the concurrence evolves in close vicinity to the increasing rate of success probability. Furthermore, we show that the system satisfies a nnn-party monogamy inequality for arbitrary times, hence bounding the amount of nnn-qubit entanglement during the quantum search.
Grover's quantum search algorithm is analyzed for the case in which the initial state is an arbitrary pure quantum state $|\ensuremath{\varphi}〉$ of n qubits. It is shown that the optimal time to perform the measurement is independent of $|\ensuremath{\varphi}〉,$ namely, it is identical to the optimal time in the original algorithm in which $|\ensuremath{\varphi}〉=|0〉,$ with the same number of marked states, r. The probability of success Ps{P}_{\mathrm{s}}Ps​ is obtained in terms of the amplitudes of the state $|\ensuremath{\varphi}〉$ and is shown to be independent of r. A class of states, which includes fixed points and cycles of the Grover iteration operator, is identified. The relevance of these results in the context of using the success probability as an entanglement measure is discussed. In particular, the Groverian entanglement measure, previously limited to a single marked state, is generalized to the case of several marked states.
Grover's algorithm constitutes the optimal quantum solution to the search problem and provides a quadratic speed-up over all possible classical search algorithms. Quantum interference between computational paths has been posited as a key resource behind this computational speed-up. However there is a limit to this interference, at most pairs of paths can ever interact in a fundamental way. Could more interference imply more computational power? Sorkin has defined a hierarchy of possible interference behaviours—currently under experimental investigation—where classical theory is at the first level of the hierarchy and quantum theory belongs to the second. Informally, the order in the hierarchy corresponds to the number of paths that have an irreducible interaction in a multi-slit experiment. In this work, we consider how Grover's speed-up depends on the order of interference in a theory. Surprisingly, we show that the quadratic lower bound holds regardless of the order of interference. Thus, at least from the point of view of the search problem, post-quantum interference does not imply a computational speed-up over quantum theory.
Run-times of quantum algorithms are often studied via an asymptotic, worst-case analysis. Whilst useful, such a comparison can often fall short: it is not uncommon for algorithms with a large worst-case run-time to end up performing well on instances of practical interest. To remedy this it is necessary to resort to run-time analyses of a more empirical nature, which for sufficiently small input sizes can be performed on a quantum device or a simulation thereof. For larger input sizes, alternative approaches are required.In this paper we consider an approach that combines classical emulation with detailed complexity bounds that include all constants. We simulate quantum algorithms by running classical versions of the sub-routines, whilst simultaneously collecting information about what the run-time of the quantum routine would have been if it were run instead. To do this accurately and efficiently for very large input sizes, we describe an estimation procedure and prove that it obtains upper bounds on the true expected complexity of the quantum algorithms.We apply our method to some simple quantum speedups of classical heuristic algorithms for solving the well-studied MAX- k -SAT optimization problem. This requires rigorous bounds (including all constants) on the expected- and worst-case complexities of two important quantum sub-routines: Grover search with an unknown number of marked items, and quantum maximum-finding. These improve upon existing results and might be of broader interest.Amongst other results, we found that the classical heuristic algorithms we studied did not offer significant quantum speedups despite the existence of a theoretical per-step speedup. This suggests that an empirical analysis such as the one we implement in this paper already yields insights beyond those that can be seen by an asymptotic analysis alone.
Quantum asymmetry and coherence are genuinely quantum resources that are essential to realize quantum advantage in information technologies. However, all quantum processes are fundamentally constrained by quantum speed limits, which raises the question on the corresponding bounds on the rate of consumption of asymmetry and coherence. In the present work, we derive a formulation of the quantum speed limit for observables in terms of the trace-norm asymmetry of the time-dependent quantum state relative to the observable. This quantum speed limit can be directly observed in experiment through weak value measurement and provides a lower bound to the quantum Fisher information about the parameter conjugate to the observable. It can be further related to quantum coherence relative to the eigenbasis of the observable. We obtain a complementary relation for the speed of three mutually unbiased observables for a single qubit. As an application, we derive a notion of a quantum thermodynamic speed limit.