2026-07-22T06:34:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25322 2026-03-19T13:03:29Z ddc:004 open_access

Symmetric Quantum Computation Castro-Silva, Davi Gur, Tom Strelchuk, Sergii Quantum computing complexity theory symmetries We introduce a systematic study of symmetric quantum circuits, a new restricted model of quantum computation that preserves the symmetries of the problems it solves. This model is well-adapted for studying the role of symmetry in quantum speedups, extending a central notion of symmetric computation studied in the classical setting. Our results establish that symmetric quantum circuits are fundamentally more powerful than their classical counterparts. First, we give efficient symmetric circuits for key quantum techniques such as amplitude amplification, phase estimation and linear combination of unitaries. In addition, we show how the task of symmetric state preparation can be performed efficiently in several natural cases. Finally, we demonstrate an exponential separation in the symmetric setting for the problem XOR-SAT, which requires exponential-size symmetric classical circuits but can be solved by polynomial-size symmetric quantum circuits. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Davi Castro-Silva and Tom Gur and Sergii Strelchuk 2026 Is Part Of LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2026.35 urn:nbn:de:0030-drops-253223 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.35 eng https://creativecommons.org/licenses/by/4.0/legalcode