Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect

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, so for those maps admitting an efficient gate decomposition, it provides an exponential speed up over known classical procedures. Fidelity decay is important in the study of complex dynamical systems, where it is conjectured to be a signature of quantum chaos. Our result also illustrates the role of chaos in the process of decoherence.

4 pages, 2 eps figures

References in corpus (19)

• Elementary gates for quantum computation
• On the volume of the set of mixed entangled states
• On the Power of One Bit of Quantum Information
• Environment-independent decoherence rate in classically chaotic systems
• Separability of very noisy mixed states and implications for NMR quantum computing
• Efficient Simulation of Quantum Systems by Quantum Computers
• Golden rule decay versus Lyapunov decay of the quantum Loschmidt echo
• Quantum Algorithms: Entanglement Enhanced Information Processing
• NMR Based Quantum Information Processing: Achievements and Prospects
• Stability of quantum motion and correlation decay
• Fidelity Decay as an Efficient Indicator of Quantum Chaos
• Using a quantum computer to investigate quantum chaos
• Efficient Quantum Computing of Complex Dynamics
• Exponential Gain in Quantum Computing of Quantum Chaos and Localization
• Quantum and classical correlations in quantum Brownian motion
• Classical model for bulk-ensemble NMR quantum computation
• Climbing Mount Scalable: Physical-Resource Requirements for a Scalable Quantum Computer
• Testing integrability with a single bit of quantum information
• Classicality of quantum information processing

Cited by in corpus (48)

• The classical-quantum boundary for correlations: discord and related measures
• Experimental quantum computing without entanglement
• Entanglement and the Power of One Qubit
• On the role of entanglement and correlations in mixed-state quantum computation
• Quantum Computing with NMR
• Quasi-probability representations of quantum theory with applications to quantum information science
• Conservation law for distributed entanglement of formation and quantum discord
• Using Quantum Computers for Quantum Simulation
• On the hardness of classically simulating the one clean qubit model
• Compressed sensing quantum process tomography for superconducting quantum gates
• Quantum Computing with black-box Subroutines
• Impossibility of Classically Simulating One-Clean-Qubit Computation
• Decoherence by a chaotic many-spin bath
• Unitary quantum gates, perfect entanglers and unistochastic maps
• Hardness of classically sampling one clean qubit model with constant total variation distance error
• Quantum Discord and Quantum Computing - An Appraisal
• Parameter Estimation with Mixed-State Quantum Computation
• Experimental approximation of the Jones polynomial with DQC1
• Characterization of complex quantum dynamics with a scalable NMR information processor
• The power of one qumode for quantum computation
• Quantum Computation Beyond the Circuit Model
• Quantum Fidelity Decay of Quasi-Integrable Systems
• Computing partition functions in the one clean qubit model
• Quantum Computation with Topological Codes: from qubit to topological fault-tolerance
• Deterministic Quantum Computation With One Photonic Qubit
• Operational Metric for Quantum Chaos and the Corresponding Spatiotemporal Entanglement Structure
• Power of One Bit of Quantum Information in Quantum Metrology
• Power of one non-clean qubit
• Probing quantum chaos in multipartite systems
• A cold-atoms based processor for deterministic quantum computation with one qubit in intractably large Hilbert spaces
• One-Dimensional Quantum Walks with a Position-Dependent Coin
• The Power of One Clean Qubit in Supervised Machine Learning
• Classical versus quantum errors in quantum computation of dynamical systems
• Promoting quantum correlations in DQC1 model via post-selection
• Intermediate quantum maps for quantum computation
• Exponential speedup in measuring out-of-time-ordered correlators with a single bit of quantum information
• The Effects of Symmetries on Quantum Fidelity Decay
• Quantum dissonance provide power to deterministic quantum computation with single qubit
• Quantum non-Markovian behavior at the chaos border
• Normalizer Circuits and Quantum Computation
• Impact of dynamics, entanglement, and Markovian noise on the fidelity of few-qubit digital quantum simulation
• The one clean qubit model without entanglement is classically simulable
• Studies on the Role of Entanglement in Mixed-state Quantum Computation
• Stabilization of quantum information by combined dynamical decoupling and detected-jump error correction
• Efficient Classical Simulation of the DQC1 Circuit with Zero Discord
• Fine-grained quantum computational supremacy
• A Temperature Change can Solve the Deutsch-Jozsa Problem : An Exploration of Thermodynamic Query Complexity
• Power of photonic states: from quantum computation to cosmology