Symmetric Quantum Computation

Castro-Silva, Davi; Gur, Tom; Strelchuk, Sergii

doi:10.4230/LIPIcs.ITCS.2026.35

Symmetric Quantum Computation

Davi Castro-Silva

University of Cambridge, UK Tom Gur

University of Cambridge, UK Sergii Strelchuk

University of Oxford, UK

Abstract

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.

Keywords and phrases:

Quantum computing, complexity theory, symmetries

Funding:

Tom Gur: ERC Starting Grant 101163189, UKRI Future Leaders Fellowship MR/X023583/1.

Sergii Strelchuk: Royal Society University Research Fellowship.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Quantum complexity theory

Related Version:

Full Version: https://arxiv.org/abs/2501.01214

Acknowledgements:

We are grateful to Anuj Dawar for insightful discussions.

Funding:

This work was supported by the Engineering and Physical Sciences Research Council on Robust and Reliable Quantum Computing (RoaRQ), Investigation 005 [grant reference EP/W032635/1].

DOI:

10.4230/LIPIcs.ITCS.2026.35

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Symmetry plays a key role in the theory of computation. By taking the symmetries of a computational problem into account when searching for its solution, one can significantly reduce the effective dimension of the search space without impacting the quality of the solution. Consequently, the presence of extensive symmetries is a strong indicator that a problem may admit an efficient algorithm. Identifying such general principles to predict algorithmic efficiency is a central goal of complexity theory and algorithm design.

A systematic way of considering the effect of symmetries in computation was introduced in the context of logic and descriptive complexity. Let $\Gamma$ be a group of permutations on $n$ elements, corresponding to the symmetries of a given problem over $n$ -bit inputs. We say that a Boolean circuit $C$ on $n$ -bit inputs is $\Gamma$ -symmetric¹¹1This classical notion has been considered in various places under different names, such as “generic circuits” in [18] and “explicitly order-invariant circuits” in [27]. if every permutation $\sigma\in\Gamma$ of the inputs can be extended to an automorphism $\pi$ of the circuit $C$ , i.e., $\pi$ moves the input gates of $C$ according to $\sigma$ and preserves operations and wiring of the internal gates of $C$ . It is clear that $\Gamma$ -symmetric circuits can only decide properties that are themselves $\Gamma$ -symmetric. A natural question is to determine which $\Gamma$ -symmetric properties admit efficient $\Gamma$ -symmetric circuits. This turns out to be intimately related to the expressibility of such properties in various logics, and permits the study of asymmetry as a computational resource.

A particularly fruitful model of symmetric circuits was first explicitly considered by Anderson and Dawar [3]. Their model, called symmetric threshold circuits, uses as gate-set the collection comprising the NOT gate and arbitrary threshold gates; this choice is fairly robust, with its important property being that it forms an efficient basis for all permutation-invariant Boolean functions. Loosely speaking, they showed that the properties that can be decided by polynomial-size symmetric threshold circuits are precisely those that can be expressed in fixed-point logic with counting (FPC), a logic of reference in the quest for a logic that captures P. As such, inexpressibility in FPC translates to super-polynomial lower bounds for symmetric threshold circuits. Coupled with the efficient implementation of several important algorithmic methods by these circuits (such as linear programming [4] and semidefinite programming [17, 8]), this provides a strong and natural setting where the limits of efficient computation can be formally studied.

In this paper, we turn to the quantum computing model, where understanding the origins of computational advantage remains a central pursuit. It is therefore natural to ask how symmetries of the problem influence the potential for quantum advantage. More precisely, the line of work on symmetric threshold circuits motivates the enquiry into a corresponding quantum model, in the hope of uncovering analogous characterizations and potential separations in the quantum setting.

Our first contribution is conceptual: we introduce the framework of symmetric quantum circuits, which formally characterises what we mean by performing a symmetric computation on a quantum computer. Loosely speaking, in this framework we require the symmetries of the underlying problem to be respected by the quantum circuits that solve it. This model is well-adapted for determining the role of symmetries in quantum speedups, extending the above notion of symmetric threshold circuit. Note that, as an abundance of symmetries is helpful in designing both classical and quantum algorithms, it is a subtle and intriguing question whether it contributes to quantum advantage.

We then study the power of symmetric quantum computation, proving several results that showcase the (somewhat surprising) strength of this computational paradigm. To explain those results, we first give an informal description of our model.

1.1 Symmetric quantum circuits

Suppose we are dealing with a symmetry group $\Gamma$ which acts on a finite set $X$ . For instance, $X$ could be a set of labels for some collection of objects and $\Gamma$ could be the permutation group $\mathcal{S}_{X}$ ; being symmetric under $\Gamma$ means that the problem is invariant under any relabelling of the objects. Another important example concerns graph properties – such as connectedness, triangle-freeness and 3-colourability. These are properties that depend only on the abstract structure of the graph, and not on its representation; in such cases, we can take $X$ to be all pairs of vertices representing the potential edges in the graph, and $\Gamma$ to be the permutation of pairs induced by vertex permutations (i.e., graph isomorphisms).

We are interested in computing functions over $X$ which are symmetric with respect to $\Gamma$ . However, we do not wish to introduce any extraneous breaking of symmetries during the computation, but instead require that the whole computation respect the symmetries of the problem. In other words, we do not rely on asymmetry as a computational resource.

To better illustrate our notion of symmetry in circuits, we exemplify it using a simple state discrimination problem: to distinguish whether two single-qubit states $\ket{\phi}$ , $\ket{\psi}\in\mathbb{C}^{2}$ are equal or have inner product at most $\delta<1$ (in modulus), under the promise that one of these two cases holds. This task involves only two qubits, and it is naturally symmetric under exchanging the roles of $\ket{\phi}$ and $\ket{\psi}$ ; we can then take $X=\{1,2\}$ to label the relevant qubits and take the symmetry group $\Gamma$ to be $\mathcal{S}_{2}$ (the permutation group on two elements).

It is well known that the problem above can be solved with (one-sided) bounded error by the SWAP test proposed in [12], as shown below:

In this circuit, measuring the first qubit produces outcome $1$ with probability $\frac{1}{2}-\frac{1}{2}|\langle\phi|\psi\rangle|^{2}$ . This probability is zero if $\ket{\phi}=\ket{\psi}$ , and it is at least $\frac{1}{2}(1-\delta)^{2}$ if $|\langle\phi|\psi\rangle|\leq\delta$ . Thus, the test determines which case holds with one-sided error $\frac{1}{2}(1+\delta^{2})$ .

Importantly for us, note that the circuit above is symmetric with respect to $\Gamma=\mathcal{S}_{2}$ : since the SWAP gate is symmetric, exchanging the roles of $\ket{\phi}$ and $\ket{\psi}$ does not alter the circuit.²²2This circuit is not symmetric with respect to all qubits, but the symmetry of the problem is only relevant for the “active” qubits labelled by $\ket{\phi}$ and $\ket{\psi}$ . This would serve as an illustrative example of a quantum circuit that respects the symmetries of the problem it solves, were it not for one issue: the circuit uses a (controlled) SWAP gate, which is not typically considered to be an elementary gate. Instead, a SWAP gate can be implemented using three CNOT gates, which are normally seen as elementary.

Suppose that our gate set includes only single-qubit gates, CNOTs and Toffoli gates. Using the usual implementation of a SWAP gate as three CNOTs, we arrive at the following equivalent circuit:

Now we have a problem: even though this last circuit is precisely equivalent to the one we started with, it no longer preserves the same symmetries! Indeed, the wire carrying $\ket{\phi}$ can be distinguished from the one carrying $\ket{\psi}$ because it contains only one “head” of a Toffoli gate.

One might wonder whether it is at all possible to implement the SWAP test symmetrically using our specified gate set. Indeed, this appears to be impossible if we only have access to three wires as above. However, if we allow for an extra ancilla qubit, then one can implement the SWAP test circuit as shown below:

This last circuit implements exactly the same operation as the original SWAP test, but now using an extra ancilla qubit (which is returned to its initial state $\ket{0}$ at the end of the computation). Its gates are grouped into five layers, where the gates inside any given layer commute and thus have no intrinsic order in their implementation. Crucially, this circuit is now symmetric: changing the roles of $\ket{\phi}$ and $\ket{\psi}$ only permutes the Toffoli gates inside each layer; since there is no order of implementation of gates within a layer, this represents an automorphism of the circuit. (For the precise definition of circuit automorphism, see the full paper.) This example motivates the following notion of symmetry in circuits.

Let $X$ be a finite set and $\Gamma$ be a symmetry group acting on $X$ . A $\Gamma$ -symmetric quantum circuit will have qubits labelled by the elements of $X$ (the “active qubits”) and additional “workspace qubits” (ancillas) to help with the computation. As usual, the workspace qubits are initialised to $\ket{0}$ while the input to the circuit is encoded in the active qubits. We require the circuit to be invariant under the induced action of $\Gamma$ : any symmetry acting on the active qubits must be extendable to an automorphism of the circuit itself. More precisely, for any $\sigma\in\Gamma$ there must exist a permutation $\pi$ of the workspace qubits such that permuting the active (resp., workspace) qubits by applying $\sigma$ (resp., $\pi$ ) we get an isomorphic circuit, as in the example above.

It is clear that symmetric circuits can only compute symmetric maps, meaning those whose value is unchanged by permutations of the input corresponding to a symmetry in $\Gamma$ . The reverse direction is more subtle, and it becomes especially hard when the complexity of implementing the circuits is taken into account (which is indeed our goal).

While the notion of symmetric circuits can be defined in a way that is agnostic to the gate set, we will study those equipped with a gate set formed by unbounded-fan-in threshold gates together with arbitrary single-qubit gates. We argue that this is a natural family of gates to consider for the following reasons:

$\blacksquare$

These gates are mathematically simple, and they generate a robust gate set for symmetric circuits.
$\blacksquare$

They form a minimal quantum extension of the classical notion of symmetric circuits [15, 16]. Indeed, if we allow only single-bit reversible gates instead of arbitrary single-qubit gates, we arrive precisely at the standard notion of symmetric (threshold) circuits that has been studied in the classical setting.
$\blacksquare$

Threshold gates are very natural from the perspective of classical circuits, forming the basis for the complexity classes TC^k. In the quantum setting, they were shown to be efficiently implemented by bounded-depth quantum circuits equipped with two-qubit gates and fan-out gates [22]. Moreover, threshold gates were shown to have the same power as fan-out in the setting of bounded-depth quantum circuits [20]. They were also shown to be efficiently implemented in the hybrid quantum class LAQCC [13].
$\blacksquare$

The class of symmetric circuits generated by them is rather powerful, as we expand upon below.

2 Our results

Equipped with the foregoing notion of symmetric quantum circuits, we proceed to study the power of symmetric quantum computation, proving several results that showcase the strength of this computational paradigm. In particular, we show that symmetric quantum circuits can efficiently perform inherently quantum tasks, and admit a provable exponential advantage over their classical counterparts.

Our first result provides efficient symmetric circuits for central quantum subroutines. In what follows, we denote by $s(\mathcal{G})$ the size (i.e., number of gates) of a circuit $\mathcal{G}$ . Whenever a symmetry group $\Gamma$ is left undefined, the result holds uniformly over all groups that $\Gamma$ could represent.

Theorem 1 (Symmetric quantum subroutines).

The following procedures can be efficiently implemented by symmetric quantum circuits:

1.

Amplitude amplification. Let $\mathcal{A}$ and $\mathcal{D}$ be $\Gamma$ -symmetric circuits, where $\mathcal{A}$ prepares a state as follows

$\mathcal{A}\ket{0}^{n}=\sqrt{p}\ket{\psi_{1}}+\sqrt{1-p}\ket{\psi_{0}},$

while $\mathcal{D}$ flags $\ket{\psi_{1}}$ in the sense that $\mathcal{D}\ket{\psi_{i}}\ket{0}=\ket{\psi_{i}}\ket{i}$ for $i\in\{0,1\}$ . Then we can construct a $\Gamma$ -symmetric circuit that maps $\ket{0}^{n}$ to $\ket{\psi_{1}}$ using $O\big((s(\mathcal{A})+s(\mathcal{D}))/\sqrt{p}\big)$ gates.
2.

Phase estimation. Let $\mathcal{A}$ be a $\Gamma$ -symmetric circuit and $0<\varepsilon<1$ . We can implement a $\Gamma$ -symmetric circuit of size $O\big(s(\mathcal{A})/\varepsilon+1/\varepsilon^{2}\big)$ which estimates the eigenvalue of any given eigenstate $\ket{\psi}$ of $\mathcal{A}$ up to accuracy $\varepsilon$ .
3.

Linear combination of unitaries. Let $U_{0},\dots,U_{k-1}$ be $n$ -qubit unitaries, let $\alpha_{0},\dots$ , $\alpha_{k-1}\in\mathbb{C}$ and denote $L:=\big\|\sum_{i=0}^{k-1}\alpha_{i}U_{i}\ket{0}^{n}\big\|.$ Given $\Gamma$ -symmetric circuits $\mathcal{G}_{0},\dots,\mathcal{G}_{k-1}$ such that each $\mathcal{G}_{i}$ implements $\ket{0}^{n}\mapsto U_{i}\ket{0}^{n}$ , we can construct a $\Gamma$ -symmetric circuit that implements

$\ket{0}^{n}\mapsto\frac{1}{L}\bigg(\sum_{i=0}^{k-1}\alpha_{i}U_{i}\bigg)\ket{0% }^{n}$

using $O\big(\|\alpha\|_{1}\big(k\log k+\sum_{i=0}^{k-1}s(\mathcal{G}_{i})\big)/L\big)$ gates.

An important example of how symmetry can be useful in quantum information theory and quantum computing is given by the symmetric subspace $\vee^{n}\mathbb{C}^{2}$ . This is the vector space formed by all $n$ -qubit states which are invariant under permutations of the qubits, and has been proven useful in state estimation, optimal cloning and the quantum de Finetti theorem; see [21] for an account of these applications. We show that every state in the symmetric subspace can be efficiently prepared by a permutation-symmetric circuit.

Theorem 2 (Symmetric state preparation).

Given the classical description of an $n$ -qubit symmetric state $\ket{\varphi}\in\vee^{n}\mathbb{C}^{2}$ , we can construct an $\mathcal{S}_{n}$ -symmetric quantum circuit which prepares $\ket{\varphi}$ using $O(n^{2.75})$ gates.

Note that elements of the symmetric subspace are the only states which can be prepared by an $\mathcal{S}_{n}$ -symmetric circuit (when starting from $\ket{0}^{n}$ ), even in information-theoretic terms. The last theorem then provides an equivalence between what is possible to prepare and what is efficient to prepare in the setting of $\mathcal{S}_{n}$ -symmetric circuits, a result which has no clear analogue in the non-symmetric setting.

In addition to preparing states belonging to the symmetric subspace $\vee^{n}\mathbb{C}^{2}$ , similar techniques to those used in Theorem 2 can also be applied for efficiently implementing the full action of a given permutation-symmetric unitary on $\vee^{n}\mathbb{C}^{2}$ . This is shown by our next theorem.

Theorem 3 (Symmetric subspace unitaries).

Given a permutation-symmetric $n$ -qubit unitary $U$ , we can implement the restricted action of $U$ on the symmetric subspace by an $\mathcal{S}_{n}$ -symmetric circuit with $O(n^{3.75})$ gates.

Another important setting where symmetry considerations prove crucial within quantum computing is the setting of quantum machine learning. In that context, Schatzki et al [29] recently proposed a class of equivariant quantum neural networks that encode the symmetries of the considered problem into their learning architectures. Here we show how their proposed class of QNNs naturally falls within our framework of symmetric quantum circuits.

Theorem 4 (Equivariant QNNs).

Permutation-equivariant quantum neural networks (as defined in [29]) can be implemented by $\mathcal{S}_{n}$ -symmetric circuits with only a linear increase in the number of gates.

Finally, we provide an example of a decision problem for which one obtains unconditional quantum advantage in the symmetric setting. The problem XOR-SAT is a Boolean satisfiability problem where each clause is given by the exclusive OR of some subset of the variables (or their negations). This problem is clearly symmetric with respect to permuting clauses and relabelling variables, that is, it is $\mathcal{S}_{m}\times\mathcal{S}_{n}$ -symmetric (where $n$ is the number of variables and $m$ is the number of clauses).

Despite the fact that XOR-SAT is solvable in polynomial time (e.g., via Gaussian elimination), it was proven by Atserias, Bulatov and Dawar [6] that it cannot be solved by polynomial-size symmetric classical circuits. This lower bound was later made more explicit and strengthened by Atserias and Dawar [7]. Here we show that symmetric quantum circuits can solve this problem in polynomial time.

Theorem 5 (Symmetric quantum advantage).

The problem XOR-SAT on $n$ variables and $m$ clauses can be solved (with certainty) by $\mathcal{S}_{m}\times\mathcal{S}_{n}$ -symmetric quantum circuits of size $\tilde{O}(m^{2}n^{2})$ . By contrast, any $\mathcal{S}_{m}\times\mathcal{S}_{n}$ -symmetric threshold circuit that solves XOR-SAT with $m\geq n$ must have size $2^{\Omega(n)}$ .

3 Outlook

This paper initiates the study of symmetric quantum circuits, with the aim of studying the relationship between symmetries and quantum speedups. In order to do so, we introduce a new restricted model of computation – akin to the query model [2], where the input to a problem can only be accessed through black-box queries, or to shallow circuits [10], where computation is restricted to circuits of bounded depth. In contrast to those two other settings, however, the restriction in our model is not uniform across all problems but is instead problem-specific, depending on the symmetries of the task at hand.

We stress that each of the restricted computational models mentioned above has its own advantages and disadvantages, and they are fundamentally incomparable to each other. Each model highlights a different facet of quantum computation, and the specific insights gleaned from any one model can be lost when translating the same problem to a different setting. While limitations on the power of unrestricted quantum computation are still beyond our grasp, it is only through a combination of insights obtained from each restricted model that we can get a more complete picture.

A significant advantage of classical symmetric circuits is that they provide a natural model for proving exponential lower bounds for the complexity of certain computational problems. This raises two intriguing possibilities in the quantum setting: that these lower bound techniques may be extended so that we can prove strong quantum lower bounds for symmetric computation; and that we can unconditionally prove an exponential separation between the power of classical and quantum symmetric computation. In this paper we show that this second possibility is indeed true, while the first possibility remains open and is left for future work. In Section 5 we provide several other open questions and possible lines of study which will further our understanding of the role of symmetries in quantum computation.

4 Related work

The literature regarding the influence of symmetries in computational complexity and algorithm design is vast. There are consequently many papers which are related to the present work, either directly or tangentially, and here we mention the ones we believe are most relevant to our line of investigation.

The closest line of work to ours is certainly that of (classical) symmetric computation and symmetric threshold circuits [3, 15, 16]. This is far from coincidental: our paper builds upon that work to extend it to the quantum setting, and we rely on their insights both for inspiration and as a source of motivation for what we do. Indeed, the great success of their computational model in solving nontrivial problems combined with the existence of (unconditional) exponential circuit lower bounds were what drove us to start this work. We were also motivated by the close connection between classical symmetric computation and logic [3], which was essential in obtaining the aforementioned lower bounds; we hope to bring such connections and techniques to the quantum setting as well.

Instances of symmetric quantum circuits (in the sense considered in this paper) were implicitly explored in the context of quantum machine learning, where they lead to efficient equivariant quantum neural networks [23] and other variational quantum machine learning primitives [26]. Properties of symmetric circuits were also used to design efficient classical simulation algorithms for a broad range of quantum systems [5].

Symmetry considerations are often useful in optimisation tasks, as they can significantly reduce complexity, speed up computations and improve solution quality by reducing the search space or simplifying the problem structure and optimisation landscape. For instance, in neural network optimisation, taking advantage of parameter space symmetries (where different parameter values lead to the same loss) via the so-called symmetry teleportation [30] increases the likelihood of moving to a point where gradient descent is more efficient, due to a flatter or more favourable curvature of the loss function. Similarly, symmetry-restricted quantum circuits used to realize equivariant unitary transformations remarkably lead to rigorous performance guarantees [31] and an improved runtime for quantum variational algorithms [26, 28].

Finally, the role of symmetries in quantum speedups has been studied in the query model of computation [1, 14, 9]. Those results have mainly been negative, showing a significant amount of symmetries precludes super-polynomial quantum advantage in the number of queries used. Symmetries have also been shown to limit the performance of variational algorithms [11], and to impose additional constraints on the evolution of quantum systems with local interactions [24, 25]. To avoid confusion, we note that our model of symmetric quantum computation is different from that of Marvian et al [24, 25]: those authors consider continuous symmetries and local gates, while we consider permutation symmetries and non-local gates, so their no-go theorems do not apply.

5 Open problems

Our work opens a number of questions that can shed further light on the computational power and limitations of symmetric quantum computation.

The peculiar structure of this class of quantum computations may lead to stronger (non-) uniform circuit lower bounds which are simpler to obtain. This possibility is motivated by the availability of powerful methods for proving circuit lower bounds in the classical symmetric setting. It would be very interesting to extend such methods to the quantum setting.

Another interesting question is whether the definition of symmetric circuits is robust to changes in the quantum gate set. We show that reversible symmetric circuits are fairly robust to changes in the allowed gate set, and its proof extends to the quantum setting when we consider only changes in the “classical part” of the gate set. It seems plausible that allowing for arbitrary $k$ -qubit permutation-symmetric unitaries (for any constant $k$ ) should similarly be of little consequence to symmetric quantum complexity, but proving this seems rather challenging due to the unconventional symmetry constraints.

The quantum setting also gives rise to a richer class of symmetric problems than the classical setting we build upon. In particular, there are important discrete translation-invariant systems whose symmetries differ from the “relational structure”-type of symmetries so prevalent in the classical setting. Such discrete symmetries feature prominently in quantum chemistry applications and pose a number of unique challenges [19]. How can we work with these systems from the point of view of symmetric circuits?

An important complexity-theoretic question is whether symmetric quantum circuits are universal for implementing symmetric operations: Given some finite group $\Gamma$ , can we perform arbitrary $\Gamma$ -symmetric unitaries using $\Gamma$ -symmetric circuits? It seems plausible that this is the case (for any group $\Gamma$ ), and we leave it as an open question for future work.

Finally, even though we show that permutation-symmetric circuits are universal for permutation-symmetric operations, there still remains the question of their complexity: Given a general permutation-symmetric unitary on $n$ qubits, what is the cost of implementing it using $\mathcal{S}_{n}$ -symmetric circuits? Answering this question would provide the first symmetric-circuit upper bounds concerning a full class of symmetries.

References

[1] Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory of Computing, 10(6):133–166, 2014. doi:10.4086/toc.2014.v010a006.
[2] Andris Ambainis. Understanding quantum algorithms via query complexity. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3265–3285. World Scientific, 2018.
[3] Matthew Anderson and Anuj Dawar. On symmetric circuits and fixed-point logics. Theory of Computing Systems, 60:521–551, 2017. doi:10.1007/S00224-016-9692-2.
[4] Matthew Anderson, Anuj Dawar, and Bjarki Holm. Solving linear programs without breaking abstractions. J. ACM, 62(6), December 2015. doi:10.1145/2822890.
[5] Eric R. Anschuetz, Andreas Bauer, Bobak T. Kiani, and Seth Lloyd. Efficient classical algorithms for simulating symmetric quantum systems. Quantum, 7:1189, November 2023. doi:10.22331/q-2023-11-28-1189.
[6] Albert Atserias, Andrei Bulatov, and Anuj Dawar. Affine systems of equations and counting infinitary logic. Theoretical Computer Science, 410(18):1666–1683, 2009. Automata, Languages and Programming (ICALP 2007). doi:10.1016/j.tcs.2008.12.049.
[7] Albert Atserias and Anuj Dawar. Definable inapproximability: new challenges for duplicator. Journal of Logic and Computation, 29(8):1185–1210, 2019. doi:10.1093/LOGCOM/EXZ022.
[8] Albert Atserias and Joanna Fijalkow. Definable ellipsoid method, sums-of-squares proofs, and the graph isomorphism problem. SIAM Journal on Computing, 52(5):1193–1229, 2023. doi:10.1137/20M1338435.
[9] Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang. Symmetries, graph properties, and quantum speedups. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 649–660, 2020. doi:10.1109/FOCS46700.2020.00066.
[10] Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308–311, 2018.
[11] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Physical review letters, 125(26):260505, 2020.
[12] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87:167902, September 2001. doi:10.1103/PhysRevLett.87.167902.
[13] Harry Buhrman, Marten Folkertsma, Bruno Loff, and Niels M. P. Neumann. State preparation by shallow circuits using feed forward. Quantum, 8:1552, December 2024. doi:10.22331/q-2024-12-09-1552.
[14] André Chailloux. A Note on the Quantum Query Complexity of Permutation Symmetric Functions. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:7, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2019.19.
[15] Anuj Dawar. Symmetric Computation. In Maribel Fernández and Anca Muscholl, editors, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020), volume 152 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:12, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CSL.2020.2.
[16] Anuj Dawar. Limits of Symmetric Computation. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:8, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.1.
[17] Anuj Dawar and Pengming Wang. Definability of semidefinite programming and lasserre lower bounds for csps. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12, 2017. doi:10.1109/LICS.2017.8005108.
[18] Larry Denenberg, Yuri Gurevich, and Saharon Shelah. Definability by constant-depth polynomial-size circuits. Information and Control, 70(2):216–240, 1986. doi:10.1016/S0019-9958(86)80006-7.
[19] Roberto Dovesi, Bartolomeo Civalleri, Carla Roetti, Victor R Saunders, and Roberto Orlando. Ab initio quantum simulation in solid state chemistry. Reviews in computational chemistry, 21:1–125, 2005.
[20] Daniel Grier and Jackson Morris. Quantum threshold is powerful, 2024. doi:10.48550/arXiv.2411.04953.
[21] Aram W. Harrow. The church of the symmetric subspace, 2013. arXiv:1308.6595.
[22] Peter Høyer and Robert Špalek. Quantum fan-out is powerful. Theory of Computing, 1(5):81–103, 2005. doi:10.4086/toc.2005.v001a005.
[23] Martín Larocca, Frédéric Sauvage, Faris M. Sbahi, Guillaume Verdon, Patrick J. Coles, and M. Cerezo. Group-invariant quantum machine learning. PRX Quantum, 3:030341, September 2022. doi:10.1103/PRXQuantum.3.030341.
[24] Iman Marvian. Restrictions on realizable unitary operations imposed by symmetry and locality. Nature Physics, 18(3):283–289, 2022.
[25] Iman Marvian, Hanqing Liu, and Austin Hulse. Qudit circuits with su(d) symmetry: Locality imposes additional conservation laws, 2022. arXiv:2105.12877.
[26] Johannes Jakob Meyer, Marian Mularski, Elies Gil-Fuster, Antonio Anna Mele, Francesco Arzani, Alissa Wilms, and Jens Eisert. Exploiting symmetry in variational quantum machine learning. PRX Quantum, 4:010328, March 2023. doi:10.1103/PRXQuantum.4.010328.
[27] Martin Otto. The logic of explicitly presentation-invariant circuits. In Selected Papers from The10th International Workshop on Computer Science Logic, CSL ’96, pages 369–384, Berlin, Heidelberg, 1996. Springer-Verlag. doi:10.1007/3-540-63172-0_50.
[28] Michael Ragone, Paolo Braccia, Quynh T Nguyen, Louis Schatzki, Patrick J Coles, Frederic Sauvage, Martin Larocca, and Marco Cerezo. Representation theory for geometric quantum machine learning. arXiv preprint arXiv:2210.07980, 2022. doi:10.48550/arXiv.2210.07980.
[29] Louis Schatzki, Martin Larocca, Quynh T Nguyen, Frederic Sauvage, and Marco Cerezo. Theoretical guarantees for permutation-equivariant quantum neural networks. npj Quantum Information, 10(1):12, 2024.
[30] Bo Zhao, Nima Dehmamy, Robin Walters, and Rose Yu. Symmetry teleportation for accelerated optimization. Advances in neural information processing systems, 35:16679–16690, 2022.
[31] Han Zheng, Zimu Li, Junyu Liu, Sergii Strelchuk, and Risi Kondor. Speeding up learning quantum states through group equivariant convolutional quantum ansätze. PRX Quantum, 4(2):020327, 2023.

[bib.bib1] [1] Scott Aaronson and Andris Ambainis. The need for structure in quantum speedups. Theory of Computing, 10(6):133–166, 2014. doi:10.4086/toc.2014.v010a006.

[bib.bib2] [2] Andris Ambainis. Understanding quantum algorithms via query complexity. In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 3265–3285. World Scientific, 2018.

[bib.bib3] [3] Matthew Anderson and Anuj Dawar. On symmetric circuits and fixed-point logics. Theory of Computing Systems, 60:521–551, 2017. doi:10.1007/S00224-016-9692-2.

[bib.bib4] [4] Matthew Anderson, Anuj Dawar, and Bjarki Holm. Solving linear programs without breaking abstractions. J. ACM, 62(6), December 2015. doi:10.1145/2822890.

[bib.bib5] [5] Eric R. Anschuetz, Andreas Bauer, Bobak T. Kiani, and Seth Lloyd. Efficient classical algorithms for simulating symmetric quantum systems. Quantum, 7:1189, November 2023. doi:10.22331/q-2023-11-28-1189.

[bib.bib6] [6] Albert Atserias, Andrei Bulatov, and Anuj Dawar. Affine systems of equations and counting infinitary logic. Theoretical Computer Science, 410(18):1666–1683, 2009. Automata, Languages and Programming (ICALP 2007). doi:10.1016/j.tcs.2008.12.049.

[bib.bib7] [7] Albert Atserias and Anuj Dawar. Definable inapproximability: new challenges for duplicator. Journal of Logic and Computation, 29(8):1185–1210, 2019. doi:10.1093/LOGCOM/EXZ022.

[bib.bib8] [8] Albert Atserias and Joanna Fijalkow. Definable ellipsoid method, sums-of-squares proofs, and the graph isomorphism problem. SIAM Journal on Computing, 52(5):1193–1229, 2023. doi:10.1137/20M1338435.

[bib.bib9] [9] Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang. Symmetries, graph properties, and quantum speedups. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 649–660, 2020. doi:10.1109/FOCS46700.2020.00066.

[bib.bib10] [10] Sergey Bravyi, David Gosset, and Robert König. Quantum advantage with shallow circuits. Science, 362(6412):308–311, 2018.

[bib.bib11] [11] Sergey Bravyi, Alexander Kliesch, Robert Koenig, and Eugene Tang. Obstacles to variational quantum optimization from symmetry protection. Physical review letters, 125(26):260505, 2020.

[bib.bib12] [12] Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87:167902, September 2001. doi:10.1103/PhysRevLett.87.167902.

[bib.bib13] [13] Harry Buhrman, Marten Folkertsma, Bruno Loff, and Niels M. P. Neumann. State preparation by shallow circuits using feed forward. Quantum, 8:1552, December 2024. doi:10.22331/q-2024-12-09-1552.

[bib.bib14] [14] André Chailloux. A Note on the Quantum Query Complexity of Permutation Symmetric Functions. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019), volume 124 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1–19:7, Dagstuhl, Germany, 2019. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ITCS.2019.19.

[bib.bib15] [15] Anuj Dawar. Symmetric Computation. In Maribel Fernández and Anca Muscholl, editors, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020), volume 152 of Leibniz International Proceedings in Informatics (LIPIcs), pages 2:1–2:12, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.CSL.2020.2.

[bib.bib16] [16] Anuj Dawar. Limits of Symmetric Computation. In Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson, editors, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), volume 297 of Leibniz International Proceedings in Informatics (LIPIcs), pages 1:1–1:8, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2024.1.

[bib.bib17] [17] Anuj Dawar and Pengming Wang. Definability of semidefinite programming and lasserre lower bounds for csps. In 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12, 2017. doi:10.1109/LICS.2017.8005108.

[bib.bib18] [18] Larry Denenberg, Yuri Gurevich, and Saharon Shelah. Definability by constant-depth polynomial-size circuits. Information and Control, 70(2):216–240, 1986. doi:10.1016/S0019-9958(86)80006-7.

[bib.bib19] [19] Roberto Dovesi, Bartolomeo Civalleri, Carla Roetti, Victor R Saunders, and Roberto Orlando. Ab initio quantum simulation in solid state chemistry. Reviews in computational chemistry, 21:1–125, 2005.

[bib.bib20] [20] Daniel Grier and Jackson Morris. Quantum threshold is powerful, 2024. doi:10.48550/arXiv.2411.04953.

[bib.bib21] [21] Aram W. Harrow. The church of the symmetric subspace, 2013. arXiv:1308.6595.

[bib.bib22] [22] Peter Høyer and Robert Špalek. Quantum fan-out is powerful. Theory of Computing, 1(5):81–103, 2005. doi:10.4086/toc.2005.v001a005.

[bib.bib23] [23] Martín Larocca, Frédéric Sauvage, Faris M. Sbahi, Guillaume Verdon, Patrick J. Coles, and M. Cerezo. Group-invariant quantum machine learning. PRX Quantum, 3:030341, September 2022. doi:10.1103/PRXQuantum.3.030341.

[bib.bib24] [24] Iman Marvian. Restrictions on realizable unitary operations imposed by symmetry and locality. Nature Physics, 18(3):283–289, 2022.

[bib.bib25] [25] Iman Marvian, Hanqing Liu, and Austin Hulse. Qudit circuits with su(d) symmetry: Locality imposes additional conservation laws, 2022. arXiv:2105.12877.

[bib.bib26] [26] Johannes Jakob Meyer, Marian Mularski, Elies Gil-Fuster, Antonio Anna Mele, Francesco Arzani, Alissa Wilms, and Jens Eisert. Exploiting symmetry in variational quantum machine learning. PRX Quantum, 4:010328, March 2023. doi:10.1103/PRXQuantum.4.010328.

[bib.bib27] [27] Martin Otto. The logic of explicitly presentation-invariant circuits. In Selected Papers from The10th International Workshop on Computer Science Logic, CSL ’96, pages 369–384, Berlin, Heidelberg, 1996. Springer-Verlag. doi:10.1007/3-540-63172-0_50.

[bib.bib28] [28] Michael Ragone, Paolo Braccia, Quynh T Nguyen, Louis Schatzki, Patrick J Coles, Frederic Sauvage, Martin Larocca, and Marco Cerezo. Representation theory for geometric quantum machine learning. arXiv preprint arXiv:2210.07980, 2022. doi:10.48550/arXiv.2210.07980.

[bib.bib29] [29] Louis Schatzki, Martin Larocca, Quynh T Nguyen, Frederic Sauvage, and Marco Cerezo. Theoretical guarantees for permutation-equivariant quantum neural networks. npj Quantum Information, 10(1):12, 2024.

[bib.bib30] [30] Bo Zhao, Nima Dehmamy, Robin Walters, and Rose Yu. Symmetry teleportation for accelerated optimization. Advances in neural information processing systems, 35:16679–16690, 2022.

[bib.bib31] [31] Han Zheng, Zimu Li, Junyu Liu, Sergii Strelchuk, and Risi Kondor. Speeding up learning quantum states through group equivariant convolutional quantum ansätze. PRX Quantum, 4(2):020327, 2023.