Further extensions of Clifford circuits and their classical simulation complexities

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 [Quant. Info. Comput. 14, 633 (2014)] by studying two 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. 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 complexities of the circuits, and also include new examples of extended Clifford circuits that exhibit "quantum supremacy", in the sense that it is not possible to efficiently classically sample from the output distributions of such circuits, unless the polynomial hierarchy collapses.

19 pages, 3 figures

References in corpus (5)

• Instantaneous non-local computation of low T-depth quantum circuits
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Efficient simulation scheme for a class of quantum optics experiments with non-negative Wigner representation
• Noise Threshold of Quantum Supremacy
• Computational Complexity of Some Quantum Theories in $1+1$ Dimensions

Cited by in corpus (20)

• Classical simulation of Gaussian quantum circuits with non-Gaussian input states
• Robustness of QMA against witness noise
• A quantum primality test with order finding
• Efficient rate-adaptive reconciliation for continuous-variable quantum key distribution
• Magic Resource Can Enhance the Quantum Capacity of Channels
• Experimental demonstration of scalable cross-entropy benchmarking to detect measurement-induced phase transitions on a superconducting quantum processor
• Quantum Non-Local Nonstabilizerness
• Effects of quantum resources on the statistical complexity of quantum circuits
• Classical simulation of quantum circuits by half Gauss sums
• Computing quopit Clifford circuit amplitudes by the sum-over-paths technique
• Magic of Random Matrix Product States
• The principle of majorization: application to random quantum circuits
• Faster Born probability estimation via gate merging and frame optimisation
• Quantum simulation from the bottom up: the case of rebits
• Quantum Ruzsa Divergence to Quantify Magic
• Quantum circuit dynamics via path integrals: Is there a classical action for discrete-time paths?
• Stabilizer Circuits, Quadratic Forms, and Computing Matrix Rank
• Wasserstein Complexity of Quantum Circuits
• Sub-universal variational circuits for combinatorial optimization problems
• Characterization of non-adaptive Clifford channels