Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy

Michael J. Bremner, Richard Jozsa, Dan J. Shepherd

We consider quantum computations comprising only commuting gates, known as IQP computations, and provide compelling evidence that the task of sampling their output probability dist…