PIRSA:25050025

A Criterion for Post-Selected Quantum Advantage

Fox, M. (2025). A Criterion for Post-Selected Quantum Advantage. Perimeter Institute. https://pirsa.org/25050025

Fox, Matthew. A Criterion for Post-Selected Quantum Advantage. Perimeter Institute, May. 14, 2025, https://pirsa.org/25050025 

          @misc{ pirsa_PIRSA:25050025,
            doi = {10.48660/25050025},
            url = {https://pirsa.org/25050025},
            author = {Fox, Matthew},
            keywords = {Quantum Information},
            language = {en},
            title = {A Criterion for Post-Selected Quantum Advantage},
            publisher = {Perimeter Institute},
            year = {2025},
            month = {may},
            note = {PIRSA:25050025 see, \url{https://pirsa.org}}
          }

Matthew Fox University of Colorado Boulder

Talk numberPIRSA:25050025
DOI10.48660/25050025
Collection
Talk Type Scientific Series
Subject

Abstract

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; C) are essentially either discrete or dense in SL(2; C). 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 made of just U \otimes U-conjugated CZ gates afford a quantum advantage for almost all single-qubit unitaries U.