2024/11/04 by Karamchedu, Chaitanya, Fox, Matthew, Gottesman, Daniel
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2411.02369
Assuming the polynomial hierarchy is infinite, we prove a sufficient condition for determining if uniform and polynomial size quantum circuits over a non-universal gate set are not efficiently classically simulable in the weak multiplicative sense. Our criterion exploits the fact that subgroups of SL(2;ℂ) are essentially either discrete or dense in SL(2;ℂ). Using our criterion, we give a new proof that both instantaneous quantum polynomial (IQP) circuits and conjugated Clifford circuits (CCCs) afford a quantum advantage. We also prove that both commuting CCCs and CCCs over various fragments of the Clifford group afford a quantum advantage, which settles two questions of Bouland, Fitzsimons, and Koh. Our results imply that circuits over just (U^† ⊗ U^†) CZ (U ⊗ U) afford a quantum advantage for almost all U ∈ U(2).