PIRSA:18120019

Classifying the simulation complexities of extended Clifford circuits

Koh, D. (2018). Classifying the simulation complexities of extended Clifford circuits. Perimeter Institute. https://pirsa.org/18120019

Koh, Dax. Classifying the simulation complexities of extended Clifford circuits. Perimeter Institute, Dec. 05, 2018, https://pirsa.org/18120019 

          @misc{ pirsa_PIRSA:18120019,
            doi = {10.48660/18120019},
            url = {https://pirsa.org/18120019},
            author = {Koh, Dax},
            keywords = {Quantum Information},
            language = {en},
            title = {Classifying the simulation complexities of extended Clifford circuits},
            publisher = {Perimeter Institute},
            year = {2018},
            month = {dec},
            note = {PIRSA:18120019 see, \url{https://pirsa.org}}
          }

Dax Koh Institute of High Performance Computing

DOI 10.48660/18120019
Collection
Talk Type Scientific Series
Subject

Abstract

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, which might just be slightly different, lead to circuits which are likely not. We extend the results of Jozsa and Van den Nest [Quantum Inf. Comput. 14, 633 (2014)] by studying various further extensions of Clifford circuits. First, we consider how the classical simulation complexity changes when we allow for more general measurements. Second, we investigate different notions of what it means to "classically simulate" a quantum circuit. Third, we consider the class of conjugated Clifford circuits, where one conjugates every qubit in a Clifford circuit by the same single-qubit gate. Our results provide more examples where seemingly modest changes to the ingredients of Clifford circuits lead to "large" changes in the classical simulation complexities of the circuits, and also include new examples of extended Clifford circuits that are potential candidates for "quantum supremacy". Based on Quantum Inf. Comput. 17, 0262 (2017) and proceedings of CCC’18 pp.21:1–21:25 (2018) (joint work with Adam Bouland and Joseph F. Fitzsimons).