Computational quantum-classical boundary of complex and noisy quantum systems
arXiv:1406.6932
Abstract
It is often said that the transition from quantum to classical worlds is caused by decoherence originated from an interaction between a system of interest and its surrounding environment. Here we establish a computational quantum-classical boundary from the viewpoint of classical simulatability of a quantum system under decoherence. Specifically, we consider commuting quantum circuits being subject to decoherence. Or equivalently, we can regard them as measurement-based quantum computation on decohered weighted graph states. To show intractability of classical simulation above the boundary, we utilize the postselection argument introduced by M. J. Bremner, R. Jozsa, and D. J. Shepherd [Proceedings of the Royal Society A: Mathematical, Physical and Engineering Science 465, 1413 (2009).] and crucially strengthen its statement by taking noise effect into account. Classical simulatability below the boundary is also shown constructively by using both separable criteria in a projected-entangled-pair-state picture and the Gottesman-Knill theorem for mixed state Clifford circuits. We found that when each qubit is subject to a single-qubit complete-positive-trace-preserving noise, the computational quantum-classical boundary is sharply given by the noise rate required for the distillability of a magic state. The obtained quantum-classical boundary of noisy quantum dynamics reveals a complexity landscape of controlled quantum systems. This paves a way to an experimentally feasible verification of quantum mechanics in a high complexity limit beyond classically simulatable region.
arXiv comment7 pages, 3 figures, v2,v3: improved versions
References in corpus (34)
- Entanglement of Formation of an Arbitrary State of Two Qubits
- Decoherence, einselection, and the quantum origins of the classical
- Universal Quantum Computation with ideal Clifford gates and noisy ancillas
- Quantum Computing with Very Noisy Devices
- On the Power of One Bit of Quantum Information
- Quantum annealing with more than one hundred qubits
- Topological fault-tolerance in cluster state quantum computation
- Contextuality supplies the magic for quantum computation
- Defining and detecting quantum speedup
- Valence Bond Solids for Quantum Computation
- Average-case complexity versus approximate simulation of commuting quantum computations
- Unconditionally verifiable blind computation
- Long-range quantum entanglement in noisy cluster states
- Instantaneous Quantum Computation
- Improved magic states distillation for quantum universality
- Noise thresholds for optical quantum computers
- The BQP-hardness of approximating the Jones Polynomial
- Standard forms of noisy quantum operations via depolarization
- On the hardness of classically simulating the one clean qubit model
- Trading inverses for an irrep in the Solovay-Kitaev theorem
- Impossibility of Classically Simulating One-Clean-Qubit Computation
- Fully fault tolerant quantum computation with non-deterministic gates
- Quantum Commuting Circuits and Complexity of Ising Partition Functions
- Thermal States as Universal Resources for Quantum Computation with Always-on Interactions
- Diagonal quantum circuits: their computational power and applications
- Topologically protected measurement-based quantum computation on the thermal state of a nearest-neighbor two-body Hamiltonian with spin-3/2 particles
- Quantum Computation with Topological Codes: from qubit to topological fault-tolerance
- Measurement-Based Quantum Computation on Symmetry Breaking Thermal States
- Transitions in the computational power of thermal states for measurement-based quantum computation
- Topological One-Way Quantum Computation on Verified Logical Cluster States
- Cluster-based architecture for fault-tolerant quantum computation
- A quantum algorithm for additive approximation of Ising partition functions
- Will boson-sampling ever disprove the Extended Church-Turing thesis?
- An introduction to reliable quantum computation