



@article {3487,
	title = {Polynomial-Time Classical Simulation of Noisy IQP Circuits with Constant Depth},
	year = {2024},
	month = {3/21/2024},
	abstract = {<p>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\&$\#$39;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.</p>},
	url = {https://arxiv.org/abs/2403.14607},
	author = {Joel Rajakumar and James D. Watson and Yi-Kai Liu}
}
@article {3509,
	title = {Trainability Barriers in Low-Depth QAOA Landscapes},
	year = {2024},
	month = {2/15/2024},
	abstract = {<p>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.</p>},
	url = {https://arxiv.org/abs/2402.10188},
	author = {Joel Rajakumar and John Golden and Andreas B{\"a}rtschi and Stephan Eidenbenz}
}
