Exact and Efficient Simulation of Concordant Computation
arXiv:1507.07196 · doi:10.1088/1367-2630/17/11/113049
Abstract
Concordant computation is a circuit-based model of quantum computation for mixed states, that assumes that all correlations within the register are discord-free (i.e. the correlations are essentially classical) at every step of the computation. The question of whether concordant computation always admits efficient simulation by a classical computer was first considered by B. Eastin in quant-ph/1006.4402v1, where an answer in the affirmative was given for circuits consisting only of one- and two-qubit gates. Building on this work, we develop the theory of classical simulation of concordant computation. We present a new framework for understanding such computations, argue that a larger class of concordant computations admit efficient simulation, and provide alternative proofs for the main results of quant-ph/1006.4402v1 with an emphasis on the exactness of simulation which is crucial for this model. We include detailed analysis of the arithmetic complexity for solving equations in the simulation, as well as extensions to larger gates and qudits. We explore the limitations of our approach, and discuss the challenges faced in developing efficient classical simulation algorithms for all concordant computations.
arXiv comment16 pages
References in corpus (21)
- Introducing Quantum Discord
- Efficient classical simulation of slightly entangled quantum computations
- Classical, quantum and total correlations
- The classical-quantum boundary for correlations: discord and related measures
- Quantum discord and the power of one qubit
- Necessary and sufficient condition for non-zero quantum discord
- On the Power of One Bit of Quantum Information
- On the role of entanglement in quantum computational speed-up
- A Thermodynamical Approach to Quantifying Quantum Correlations
- Almost all quantum states have non-classical correlations
- Positive Wigner functions render classical simulation of quantum computation efficient
- Negative Quasi-Probability as a Resource for Quantum Computation
- Entanglement and the Power of One Qubit
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Einselection and Decoherence from an Information Theory Perspective
- Estimating outcome probabilities of quantum circuits using quasiprobabilities
- Universal quantum computation with little entanglement
- Detecting Multipartite Classical States and their Resemblances
- Parts of Quantum States
- Quantum interference as a resource for quantum speedup
- Measurement-based classical computation
Cited by in corpus (6)
- Measures and applications of quantum correlations
- The Degree of Quantum Correlation Required to Speed-Up a Computation
- Witnessing nonclassical correlations via a single-shot experiment on an ensemble of spins using NMR
- Nonclassical correlations in subsystems of globally entangled quantum states
- Generation and Detection of Quantum Correlations and Entanglement on a Spin-Based Quantum Information Processor
- Oracle problems as communication tasks and optimization of quantum algorithms