We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output probability distribution can be sampled up to an exponentially small additive error in classical polynomial time. First, we show that there exists a commuting quantum circuit that is not classically simulatable unless the polynomial hierarchy collapses to the third level. This is the first formal evidence that a commuting quantum circuit is not classically simulatable even when the number of output qubits is exponentially small. Then, we consider a generalized version of the circuit and clarify the condition under which it is classically simulatable. Lastly, we apply the argument for the above evidence to Clifford circuits in a similar setting and provide evidence that such a circuit augmented by a depth-1 non-Clifford layer is not classically simulatable. These results reveal subtle differences between quantum and classical computation.
We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output probability distribution can be sampled up to an exponentially small additive error in classical polynomial time. First, we show that there exists a commuting quantum circuit that is not classically simulatable unless the polynomial hierarchy collapses to the third level. This is the first formal evidence that a commuting quantum circuit is not classically simulatable even when the number of output qubits is exponentially small. Then, we consider a generalized version of the circuit and clarify the condition under which it is classically simulatable. Lastly, we apply the argument for the above evidence to Clifford circuits in a similar setting and provide evidence that such a circuit augmented by a depth-1 non-Clifford layer is not classically simulatable. These results reveal subtle differences between quantum and classical computation.
We study the classical simulatability of commuting quantum circuits with n input qubits and O(log n) output qubits, where a quantum circuit is classically simulatable if its output probability distribution can be sampled up to an exponentially small additive error in classical polynomial time. Our main result is that there exists a commuting quantum circuit that is not classically simulatable unless the polynomial hierarchy collapses to the third level. This is the first formal evidence that a commuting quantum circuit is not classically simulatable even when the number of output qubits is O(log n). Then, we consider a generalized version of the circuit and clarify the condition under which it is classically simulatable. Lastly, using a proof similar to that of the main result, we provide an evidence that a slightly extended Clifford circuit is not classically simulatable.
We study the classical simulatability of constant-depth polynomial-size quantum circuits followed by only one single-qubit measurement, where the circuits consist of universal gates on at most two qubits and additional gates on an unbounded number of qubits. First, we consider unbounded Toffoli gates as additional gates and deal with the weak simulation, i.e., sampling the output probability distribution. We show that there exists a constant-depth quantum circuit with only one unbounded Toffoli gate that is not weakly simulatable, unless $\bqp \subseteq \postbpp \cap \am$. Then, we consider unbounded fan-out gates as additional gates and deal with the strong simulation, i.e., computing the output probability. We show that there exists a constant-depth quantum circuit with only two unbounded fan-out gates that is not strongly simulatable, unless $\p = \pp$. These results are in contrast to the fact that any constant-depth quantum circuit without additional gates on an unbounded number of qubits is strongly and weakly simulatable.
We study the effect of noise on the classical simulatability of quantum circuits defined by computationally tractable (CT) states and efficiently computable sparse (ECS) operations. Examples of such circuits, which we call CT-ECS circuits, are IQP, Clifford Magic, and conjugated Clifford circuits. This means that there exist various CT-ECS circuits such that their output probability distributions are anti-concentrated and not classically simulatable in the noise-free setting (under plausible assumptions). First, we consider a noise model where a depolarizing channel with an arbitrarily small constant rate is applied to each qubit at the end of computation. We show that, under this noise model, if an approximate value of the noise rate is known, any CT-ECS circuit with an anti-concentrated output probability distribution is classically simulatable. This indicates that the presence of small noise drastically affects the classical simulatability of CT-ECS circuits. Then, we consider an extension of the noise model where the noise rate can vary with each qubit, and provide a similar sufficient condition for classically simulating CT-ECS circuits with anti-concentrated output probability distributions.
The task of learning a probability distribution from samples is ubiquitous across the natural sciences. The output distributions of local quantum circuits are of central importance in both quantum advantage proposals and a variety of quantum machine learning algorithms. In this work, we extensively characterize the learnability of output distributions of local quantum circuits. Firstly, we contrast learnability with simulatability by showing that Clifford circuit output distributions are efficiently learnable, while the injection of a single T gate renders the density modeling task hard for any depth d=n^{Ω(1)}. We further show that the task of generative modeling universal quantum circuits at any depth d=n^{Ω(1)} is hard for any learning algorithm, classical or quantum, and that for statistical query algorithms, even depth d=ω[log(n)] Clifford circuits are hard to learn. Our results show that one cannot use the output distributions of local quantum circuits to provide a separation between the power of quantum and classical generative modeling algorithms, and therefore provide evidence against quantum advantages for practically relevant probabilistic modeling tasks.
We prove under the complexity theoretical assumption of the non-collapse of the polynomial hierarchy that estimating the output probabilities of random quantum circuits to within exp(−Ω(mlogm)) additive error is hard for any classical computer, where m is the number of gates in the quantum computation. More precisely, we show that the above problem is #P-hard under BPPNP reduction. In the recent experiments, the quantum circuit has n−qubits and the architecture is a two-dimensional grid of size n×n. Indeed for constant depth circuits estimating the output probabilities to within 2−Ω(nlogn) is hard, and for circuits of depth n, for which the anti-concentration property holds, estimating the output probabilities to within 2−Ω(n3/2logn) is hard. We prove these results from first principles and do not use the standard techniques such as the Berlekamp--Welch algorithm, the usual Paturi's lemma, and Rakhmanov's result.
We study the classical simulability of a polynomial-size quantum circuit Cn on n qubits followed by sparse classical post-processing (SCP) on m bits, where m≤n≤poly(m). The SCP is described by a non-zero Boolean function fm that is classically computable in polynomial time and is sparse, i.e., has a peaked Fourier spectrum. First, we provide a necessary and sufficient condition on Cn such that, for any SCP fm, Cn followed by fm is classically simulable. This characterization extends the result of Van den Nest and implies that various quantum circuits followed by SCP are classically simulable. Examples include IQP circuits, Clifford Magic circuits, and the quantum part of Simon's algorithm, even though these circuits alone are hard to simulate classically. Then, we consider the case where Cn has constant depth d. While it is unlikely that, for any SCP fm, Cn followed by fm is classically simulable, we show that it is simulable by a polynomial-time probabilistic algorithm with access to commuting quantum circuits on n+1 qubits. Each such circuit consists of at most deg(fm) commuting gates and each commuting gate acts on at most 2d+1 qubits, where deg(fm) is the Fourier degree of fm. This provides a better understanding of the hardness of simulating constant-depth quantum circuits followed by SCP.