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:quant-ph/0310038 · Physical Review Letters

Exponential Speedup with a Single Bit of Quantum Information: Measuring the Average Fidelity Decay

David Poulin, Robin Blume-Kohout, Raymond Laflamme, Harold Ollivier

Published Apr 30, 2004• 79 citations
arXivHTMLPDF

Abstract

We present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation. Thus for those maps admitting an efficient gate decomposition, it provides an exponential speedup over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of eigenvector statistics. Our result also illustrates the role of chaos in the process of decoherence.

DOI
10.1103/physrevlett.92.177906

Related papers

Fidelity Decay as an Efficient Indicator of Quantum Chaos

Joseph Emerson, Yaakov S. Weinstein, Seth Lloyd +1 more

We demonstrate that a system's rate of fidelity decay under repeated perturbations may be measured efficiently on a quantum information processor, and analyze the conditions under which this indicator is a reliable probe of quantum chaos. The type and rate of the decay are not dependent on the eigenvalue statistics of the unperturbed system, but depend on the system's eigenvector statistics in the eigenbasis of the perturbation. For random eigenvector statistics, the decay is exponential with a rate fixed by the variance of the perturbation's energy spectrum. Hence, even classically regular models can exhibit an exponential fidelity decay under generic quantum perturbations. These results clarify which perturbations can distinguish classically regular and chaotic quantum systems.

arXiv:quant-ph/0207099•Physical Review Letters•Dec 31, 2002•144 citations

Entanglement versus relaxation and decoherence in a quantum algorithm for quantum chaos

Stefano Bettelli, Dima L. Shepelyansky

We study analytically and numerically the behavior of the concurrence (a measure of the entanglement of formation) of a pair of qubits in a quantum computer operating an efficient algorithm for quantum chaos. Our results show that in an ideal algorithm the entanglement decays exponentially with the diffusive relaxation rate induced by classical chaos. This decay reaches a residual level which drops exponentially with increasing number of qubits ${n}_{q}.$ Decoherence destroys the residual entanglement with a rate exponential in ${n}_{q}.$

arXiv:quant-ph/0301086•Physical Review A•May 27, 2003•37 citations

Characterization of Complex Quantum Dynamics with a Scalable NMR Information Processor

Colm A. Ryan, Joseph Emerson, David Poulin +2 more

We present experimental results on the measurement of fidelity decay under contrasting system dynamics using a nuclear magnetic resonance quantum information processor. The measurements were performed by implementing a scalable circuit in the model of deterministic quantum computation with only one quantum bit. The results show measurable differences between regular and complex behavior and for complex dynamics are faithful to the expected theoretical decay rate. Moreover, we illustrate how the experimental method can be seen as an efficient way for either extracting coarse-grained information about the dynamics of a large system or measuring the decoherence rate from engineered environments.

arXiv:quant-ph/0506085•Physical Review Letters•Dec 15, 2005•39 citations

Quantum chaos algorithms and dissipative decoherence with quantum trajectories

Jae Weon Lee, Dima L. Shepelyansky

Using the methods of quantum trajectories we investigate the effects of dissipative decoherence in a quantum computer algorithm simulating dynamics in various regimes of quantum chaos including dynamical localization, the quantum ergodic regime, and quasi-integrable motion. As an example we use the quantum sawtooth algorithm which can be implemented in a polynomial number of quantum gates. It is shown that the fidelity of quantum computation decays exponentially with time and that the decay rate is proportional to the number of qubits, number of quantum gates, and per gate dissipation rate induced by external decoherence. In the limit of strong dissipation the quantum algorithm generates a quantum attractor which may have a complex or simple structure. We also compare the effects of dissipative decoherence with the effects of static imperfections.

arXiv:quant-ph/0501120•Physical Review E•May 5, 2005•16 citations

General relation between quantum ergodicity and fidelity of quantum dynamics

Tomaž Prosen

A general relation is derived, which expresses the fidelity of quantum dynamics, measuring the stability of time evolution to small static variation in the Hamiltonian, in terms of ergodicity of an observable generating the perturbation as defined by its time correlation function. Fidelity for ergodic dynamics is predicted to decay exponentially on time scale proportional to delta(-2), delta approximately strength of perturbation, whereas faster, typically Gaussian decay on shorter time scale proportional delta(-1) is predicted for integrable, or generally nonergodic dynamics. This result needs the perturbation delta to be sufficiently small such that the fidelity decay time scale is larger than any (quantum) relaxation time, e.g., mixing time for mixing dynamics, or averaging time for nonergodic dynamics (or Ehrenfest time for wave packets in systems with chaotic classical limit). Our surprising predictions are demonstrated in a quantum Ising spin-(1/2) chain periodically kicked with a tilted magnetic field where we find finite parameter-space regions of nonergodic and nonintegrable motion in the thermodynamic limit.

arXiv:quant-ph/0106149•Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics•Feb 11, 2002•196 citations

A study of chaos and randomness in quantum systems

Sreeram PG

How classical chaos emerges from the underlying quantum world is a fundamental problem in physics. The origin of this question is in the correspondence principle. Classical chaos arises due to non-linear dynamics, whereas quantum mechanics, driven by unitary evolution, is linear. The question that still remains is - what are the footprints of classical chaos in the quantum world? One can understand the quantum signatures of classical chaos by studying a quantum system whose classical analogue is chaotic. In this thesis, we use the quantum kicked top model of few qubits in the deep quantum regime to investigate signatures that can be considered as a precursor to chaos in the classical limit. In particular, we study out-of-time-ordered correlators (OTOCs) and Loschmidt echo, the two well-known dynamical diagnostics of chaos. We find vestiges of classical chaos even in such a deep quantum regime. Another arena where one can study the effects of chaos and randomness is quantum state tomography. We study quantum tomography from a continuous measurement record obtained by measuring expectation values of a set of Hermitian operators generated by a unitary evolution of an initial observable. The rate of information gain and reconstruction fidelity shows vestiges of chaos. As another contribution of this thesis, we have harnessed the power of randomness inherent in the maximally mixed state to give an efficient quantum algorithm to measure OTOCs. The protocol achieves an exponential speedup over the best known classical algorithm, provided the OTOC operator to be estimated admits an efficient gate decomposition. This protocol also helps benchmark unitary gates, which is important from the quantum computation and control perspective.

arXiv:2402.00287•Feb 1, 2024•0 citations
We present an efficient quantum algorithm to measure the average fidelity decay of a quantum map under perturbation using a single bit of quantum information. Our algorithm scales only as the complexity of the map under investigation. Thus for those maps admitting an efficient gate decomposition, it provides an exponential speedup over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of eigenvector statistics. Our result also illustrates the role of chaos in the process of decoherence.
We demonstrate that a system's rate of fidelity decay under repeated perturbations may be measured efficiently on a quantum information processor, and analyze the conditions under which this indicator is a reliable probe of quantum chaos. The type and rate of the decay are not dependent on the eigenvalue statistics of the unperturbed system, but depend on the system's eigenvector statistics in the eigenbasis of the perturbation. For random eigenvector statistics, the decay is exponential with a rate fixed by the variance of the perturbation's energy spectrum. Hence, even classically regular models can exhibit an exponential fidelity decay under generic quantum perturbations. These results clarify which perturbations can distinguish classically regular and chaotic quantum systems.
We study analytically and numerically the behavior of the concurrence (a measure of the entanglement of formation) of a pair of qubits in a quantum computer operating an efficient algorithm for quantum chaos. Our results show that in an ideal algorithm the entanglement decays exponentially with the diffusive relaxation rate induced by classical chaos. This decay reaches a residual level which drops exponentially with increasing number of qubits nq.{n}_{q}.nq​. Decoherence destroys the residual entanglement with a rate exponential in nq.{n}_{q}.nq​.
We present experimental results on the measurement of fidelity decay under contrasting system dynamics using a nuclear magnetic resonance quantum information processor. The measurements were performed by implementing a scalable circuit in the model of deterministic quantum computation with only one quantum bit. The results show measurable differences between regular and complex behavior and for complex dynamics are faithful to the expected theoretical decay rate. Moreover, we illustrate how the experimental method can be seen as an efficient way for either extracting coarse-grained information about the dynamics of a large system or measuring the decoherence rate from engineered environments.
Using the methods of quantum trajectories we investigate the effects of dissipative decoherence in a quantum computer algorithm simulating dynamics in various regimes of quantum chaos including dynamical localization, the quantum ergodic regime, and quasi-integrable motion. As an example we use the quantum sawtooth algorithm which can be implemented in a polynomial number of quantum gates. It is shown that the fidelity of quantum computation decays exponentially with time and that the decay rate is proportional to the number of qubits, number of quantum gates, and per gate dissipation rate induced by external decoherence. In the limit of strong dissipation the quantum algorithm generates a quantum attractor which may have a complex or simple structure. We also compare the effects of dissipative decoherence with the effects of static imperfections.
A general relation is derived, which expresses the fidelity of quantum dynamics, measuring the stability of time evolution to small static variation in the Hamiltonian, in terms of ergodicity of an observable generating the perturbation as defined by its time correlation function. Fidelity for ergodic dynamics is predicted to decay exponentially on time scale proportional to delta(-2), delta approximately strength of perturbation, whereas faster, typically Gaussian decay on shorter time scale proportional delta(-1) is predicted for integrable, or generally nonergodic dynamics. This result needs the perturbation delta to be sufficiently small such that the fidelity decay time scale is larger than any (quantum) relaxation time, e.g., mixing time for mixing dynamics, or averaging time for nonergodic dynamics (or Ehrenfest time for wave packets in systems with chaotic classical limit). Our surprising predictions are demonstrated in a quantum Ising spin-(1/2) chain periodically kicked with a tilted magnetic field where we find finite parameter-space regions of nonergodic and nonintegrable motion in the thermodynamic limit.
How classical chaos emerges from the underlying quantum world is a fundamental problem in physics. The origin of this question is in the correspondence principle. Classical chaos arises due to non-linear dynamics, whereas quantum mechanics, driven by unitary evolution, is linear. The question that still remains is - what are the footprints of classical chaos in the quantum world? One can understand the quantum signatures of classical chaos by studying a quantum system whose classical analogue is chaotic. In this thesis, we use the quantum kicked top model of few qubits in the deep quantum regime to investigate signatures that can be considered as a precursor to chaos in the classical limit. In particular, we study out-of-time-ordered correlators (OTOCs) and Loschmidt echo, the two well-known dynamical diagnostics of chaos. We find vestiges of classical chaos even in such a deep quantum regime. Another arena where one can study the effects of chaos and randomness is quantum state tomography. We study quantum tomography from a continuous measurement record obtained by measuring expectation values of a set of Hermitian operators generated by a unitary evolution of an initial observable. The rate of information gain and reconstruction fidelity shows vestiges of chaos. As another contribution of this thesis, we have harnessed the power of randomness inherent in the maximally mixed state to give an efficient quantum algorithm to measure OTOCs. The protocol achieves an exponential speedup over the best known classical algorithm, provided the OTOC operator to be estimated admits an efficient gate decomposition. This protocol also helps benchmark unitary gates, which is important from the quantum computation and control perspective.