Exact and efficient simulation of concordant computation

Hugo Cable, Daniel E. Browne

Research output: Contribution to journalArticle (Academic Journal)peer-review

6 Citations (Scopus)
285 Downloads (Pure)


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 Eastin in arXiv: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 arXiv: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.
Original languageEnglish
Article number113049
Number of pages16
JournalNew Journal of Physics
Issue number11
Publication statusPublished - 19 Nov 2015

Structured keywords

  • QETLabs


Dive into the research topics of 'Exact and efficient simulation of concordant computation'. Together they form a unique fingerprint.

Cite this