Unified framework for efficiently computable quantum circuits

Abstract

Quantum circuits consisting of Clifford and matchgates are two classes of circuits that are known to be efficiently simulatable on a classical computer. We introduce a unified framework that shows in a transparent way the special structure that allows these circuits to be efficiently simulatable. The approach involves analyzing the transformation of operators in the Heisenberg picture, and viewing this as a spread within a network of basis operators. The operator amplitudes are found to follow a single variable Porter-Thomas distribution for random universal quantum circuits. The number of operators with amplitude above a threshold value is shown to have a characteristic form involving an initial exponential growth, saturation, then exponential decay in the presence of decoherence. We show the number of significant operators can be used to estimate the complexity of a numerical algorithm where errors can be consistently controlled as a function of the complexity of the simulation.