Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR16-004 | 26th December 2015 02:46

Further extensions of Clifford circuits and their classical simulation complexities


Authors: Dax Enshan Koh
Publication: 22nd January 2016 12:52
Downloads: 464


Extended Clifford circuits straddle the boundary between classical and quantum computational power. Whether such circuits are efficiently classically simulable seems to depend delicately on the ingredients of the circuits. While some combinations of ingredients lead to efficiently classically simulable circuits, other combinations that might just be slightly different, lead to circuits which are likely not. We extend the results of Jozsa and Van den Nest (arXiv:1305.6190) by studying two further extensions of Clifford circuits. Firstly, we consider how the classical simulation complexity changes when we allow for more general measurements. Secondly, we investigate different notions of what it means to "classically simulate" a quantum circuit. These further extensions give us 24 new combinations of ingredients compared to Jozsa and Van den Nest, and we give a complete classification of their classical simulation complexities. Our results provide more examples where seemingly modest changes to the ingredients of Clifford circuits lead to large changes in the classical simulation complexity under plausible complexity assumptions.

ISSN 1433-8092 | Imprint