Complexity phase transitions in instantaneous quantum polynomial-time circuits

We study the classical hardness of learning the output distribution from instantaneous quantum polynomial-time circuits with a varying density of two-qubit gates. We first investigate the complexity phases relevant to simulating the output distribution. In addition to a known parameter regime for anticoncentration, where the classical simulation is believed to be infeasible, we identify a novel parameter condition such that the classically simulability of the circuit can be proven rigorously. Next, we explore the classical learnability of the output distribution. We prove that a circuit instance whose output distribution is not classically learnable exists, assuming the hardness of learning parity with noise. We numerically study this phenomenon deeply using a classical energy-based model, where we find that the classical model fails to learn the output distribution even when the density of two-qubit gates is much smaller than that for the anticoncentration. We argue that this is mainly due to the fact that an accurate classical description of the output distribution requires exponentially large amount of resources.