2026-07-22T08:26:27Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8867 2024-03-12T11:58:03Z ddc:004 open_access

Complexity Classification of Conjugated Clifford Circuits Bouland, Adam Fitzsimons, Joseph F. Koh, Dax Enshan gate set classification quantum advantage sampling problems polynomial hierarchy Clifford circuits - i.e. circuits composed of only CNOT, Hadamard, and pi/4 phase gates - play a central role in the study of quantum computation. However, their computational power is limited: a well-known result of Gottesman and Knill states that Clifford circuits are efficiently classically simulable. We show that in contrast, "conjugated Clifford circuits" (CCCs) - where one additionally conjugates every qubit by the same one-qubit gate U - can perform hard sampling tasks. In particular, we fully classify the computational power of CCCs by showing that essentially any non-Clifford conjugating unitary U can give rise to sampling tasks which cannot be efficiently classically simulated to constant multiplicative error, unless the polynomial hierarchy collapses. Furthermore, by standard techniques, this hardness result can be extended to allow for the more realistic model of constant additive error, under a plausible complexity-theoretic conjecture. This work can be seen as progress towards classifying the computational power of all restricted quantum gate sets. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Adam Bouland and Joseph F. Fitzsimons and Dax Enshan Koh 2018 Is Part Of LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2018.21 urn:nbn:de:0030-drops-88677 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.21 eng https://creativecommons.org/licenses/by/3.0/legalcode