Exact and efficient simulation of concordant computation
From MaRDI portal
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.
Recommendations
- Classical simulation of quantum computation, the Gottesman-Knill theorem and slightly beyond
- Invited Talk: Embedding Classical into Quantum Computation
- A LOGIC FOR QUANTUM COMPUTATION AND CLASSICAL SIMULATION OF QUANTUM ALGORITHMS
- Quantum discord and quantum computing -- an appraisal
- Classical simulation and complexity of quantum computations (invited talk)
Cites work
- Advanced linear algebra
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy.
- Classical, quantum and total correlations
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- Necessary and sufficient condition for nonzero quantum discord
- Negative quasi-probability as a resource for quantum computation
- On the role of entanglement in quantum-computational speed-up
- Parts of quantum states
- Quantum discord: a measure of the quantumness of correlations
- Simulating quantum computers with probabilistic methods
- The computational complexity of linear optics
Cited in
(2)
This page was built for publication: Exact and efficient simulation of concordant computation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5144311)
