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• 78 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•147 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

Partial randomized benchmarking and noise

Kirill S. Dubovitskii, Yuriy Makhlin

In practical randomized benchmarking of logical gates for quantum computation, partial averaging is sometimes used to simplify the implementation. For instance, for two-qubit gates, averaging over only single-qubit operations is much easier to realize than the full averaging. We analyze such simplified, partial averaging and demonstrate that, unlike for the standard randomized benchmarking, the measured decay law of fidelity is a linear combination of several exponentials with different decay factors (3 for two qubits and single-bit averaging). The evolution with the sequence length is given by an iteration matrix, whose eigenvalues give the decay factors. For generic two-qubit gates two contributions decay fast and are barely visible, while the third factor characterizes a combination of gate errors in three channels. While the decay factor of this slowest exponential is close to that in the standard randomized benchmarking, we demonstrate that they differ in general and find this correction to the leading order. Furthermore, via a connection to the local invariants of two-qubit gates we find all exceptional gates, with more than one slow exponential, and analyze possibilities to extract their decay factors from the measured curves.

•Nov 7, 2021•0 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•13 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•187 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​.
In practical randomized benchmarking of logical gates for quantum computation, partial averaging is sometimes used to simplify the implementation. For instance, for two-qubit gates, averaging over only single-qubit operations is much easier to realize than the full averaging. We analyze such simplified, partial averaging and demonstrate that, unlike for the standard randomized benchmarking, the measured decay law of fidelity is a linear combination of several exponentials with different decay factors (3 for two qubits and single-bit averaging). The evolution with the sequence length is given by an iteration matrix, whose eigenvalues give the decay factors. For generic two-qubit gates two contributions decay fast and are barely visible, while the third factor characterizes a combination of gate errors in three channels. While the decay factor of this slowest exponential is close to that in the standard randomized benchmarking, we demonstrate that they differ in general and find this correction to the leading order. Furthermore, via a connection to the local invariants of two-qubit gates we find all exceptional gates, with more than one slow exponential, and analyze possibilities to extract their decay factors from the measured curves.
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.