Noisy computation and reversible computation have been studied separately, and it is known that they are as powerful as unrestricted computation. We study the case where both noise and reversibility are combined and show that the combined model is weaker than unrestricted computation. In our noisy reversible circuits, each wire is flipped with probability p each time step, and all the inputs to the circuit are present in time 0. We prove that any noisy reversible circuit must have size exponential in its depth in order to compute a function with high probability. This is tight as we show that any circuit can be converted into a noise-resistant reversible one with a blow up in size which is exponential in the depth. This establishes that noisy reversible computation has the power of the complexity class NC^1. We extend this to quantum circuits(QC). We prove that any noisy QC which is not worthless, and for which all inputs are present at time 0, must have size exponential in its depth. (This high-lights the fact that fault tolerant QC must use a constant supply of inputs all the time.) For the lower bound, we show that quasi-polynomial noisy QC are at least powerful as logarithmic depth QC, (or QNC^1). Making these bounds tight is left open in the quantum case.

We construct a polynomial-time classical algorithm that samples from the output distribution of noisy geometrically local Clifford circuits with any product-state input and single-qubit measurements in any basis. Our results apply to circuits with nearest-neighbor gates on an \(O(1)\text{-D}\) architecture with depolarizing noise after each gate. Importantly, we assume that the circuit does not contain qubit resets or mid-circuit measurements. This class of circuits includes Clifford-magic circuits and Conjugated-Clifford circuits, which are important candidates for demonstrating quantum advantage using non-universal gates. Additionally, our results can be extended to the case of IQP circuits augmented with CNOT gates, which is another class of non-universal circuits that are relevant to current experiments. Importantly, these results do not require randomness assumptions over the circuit families considered (such as anticoncentration properties) and instead hold for every circuit in each class as long as the depth is above a constant threshold. This allows us to rule out the possibility of fault-tolerance in these circuit models. As a key technical step, we prove that interspersed noise causes a decay of long-range entanglement at depths beyond a critical threshold. To prove our results, we merge techniques from percolation theory and Pauli path analysis.

Sampling from the output distributions of quantum computations comprising only commuting gates, known as instantaneous quantum polynomial (IQP) computations, is believed to be intractable for classical computers, and hence this task has become a leading candidate for testing the capabilities of quantum devices. Here we demonstrate that for an arbitrary IQP circuit undergoing dephasing or depolarizing noise, whose depth is greater than a critical O (1) threshold, the output distribution can be efficiently sampled by a classical computer. Unlike other simulation algorithms for quantum supremacy tasks, we do not require assumptions on the circuit’s architecture, on anti-concentration properties, nor do we require Ω(log (n )) circuit depth. We take advantage of the fact that IQP circuits have deep sections of diagonal gates, which allows the noise to build up predictably and induce a large-scale breakdown of entanglement within the circuit. Our results suggest that quantum supremacy experiments based on IQP circuits may be more susceptible to classical simulation than previously thought. Furthermore, we show that the critical depth threshold of our algorithm is tight, and below this threshold there are noisy IQP circuits which are hard to sample from. Thus we demonstrate that noisy IQP circuits exhibit a phase transition in the computational complexity of sampling, as circuit depth is increased.

The Quantum Alternating Operator Ansatz (QAOA) is a prominent variational quantum algorithm for solving combinatorial optimization problems. Its effectiveness depends on identifying input parameters that yield high-quality solutions. However, understanding the complexity of training QAOA remains an under-explored area. Previous results have given analytical performance guarantees for a small, fixed number of parameters. At the opposite end of the spectrum, barren plateaus are likely to emerge at Ω (n) parameters for n qubits. In this work, we study the difficulty of training in the intermediate regime, which is the focus of most current numerical studies and near-term hardware implementations. Through extensive numerical analysis of the quality and quantity of local minima, we argue that QAOA landscapes can exhibit a superpolynomial growth in the number of low-quality local minima even when the number of parameters scales logarithmically with n. This means that the common technique of gradient descent from randomly initialized parameters is doomed to fail beyond small n, and emphasizes the need for good initial guesses of the optimal parameters.