Exact and Efficient Simulation of Concordant Computation

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.

16 pages

References in corpus (6)

• Quantum discord and the power of one qubit
• Necessary and sufficient condition for non-zero quantum discord
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Universal quantum computation with little entanglement
• Detecting Multipartite Classical States and their Resemblances

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