A unitary can respect a permutation of its qubits while its elementary gate decomposition distinguishes them. The swap of two qubits is a basic example: it commutes with interchanging the two wires, but its usual three-CNOT realization starts with a gate whose control and target are exchanged by that permutation. The first layer is therefore not preserved. Operator equivariance alone does not guarantee the wire automorphisms required of a symmetric circuit.

Castro-Silva, Gur, and Strelchuk formalize this requirement using circuits of arbitrary one-qubit gates and reversible threshold gates, organized into layers of pairwise commuting gates [1]. Every permutation of the active wires in the prescribed group must extend to a permutation of all circuit wires preserving each layer. Workspace qubits may be permuted among themselves. Their universality theorem handles partition groups $S{}_{n_1}\times \cdots \times S{}_{n_t}$, acting on disjoint blocks, and they leave universality for arbitrary permutation actions open [1, Theorem 12 and Section 1.5]. We prove that commutation with the action is sufficient in every case, with exact implementation on the full Hilbert space and workspace returned to zero.

The partition-group proof combines simple equivariant unitaries by a symmetric linear-combination construction [1, Lemma 10]. A Pauli expansion supplies simple unitaries for an arbitrary action, but loses the hypothesis that each summand is equivariant. Taking orbit sums does not repair this: even for two interchangeable qubits, the exchanged words ${\sigma }_1\otimes I_2$ and $I_2\otimes {\sigma }_1$ have a sum with a nontrivial kernel. Orbit sums supply equivariant operators but do not give the unitary summands required by the linear-combination lemma.

We retain the individual Pauli words and give each one a selector wire. Under an active-wire permutation, the selector wires are permuted by the induced action on Pauli words. Equal coefficients on each orbit then allow a symmetric superposition of one-hot selector states. Selection respects the joint action on the active and selector wires, although selecting an individual word need not respect the active action alone. This is the role of permutable workspace in the proof: it carries the labels needed to apply the individual summands without choosing an orbit representative.

There are two further circuit constraints. First, controlled Pauli words can fail to commute when several selector bits are one. Their behavior on those inputs matters even though the prepared selector is one-hot, because commutation within a layer is an operator identity on the full Hilbert space. We split selection according to the three nonidentity Pauli symbols; each stage uses a commuting CNOT incidence layer between uniform local basis changes. Second, preparation and selection produce a normalized block of the target unitary, rather than the unitary itself. Its normalization is independent of the active input, so exact oblivious amplification applies. The required all-zero workspace test is preserved by every workspace permutation, allowing amplification to use the same wire action as selection.

We first fix the circuit conventions, then construct the selector state used in the Pauli expansion. Besides arbitrary gates in $U(2)$, the elementary gates are reversible threshold gates ${\mathrm{Th}}_t^{S,h}$, where the control set $S$ does not contain the head wire $h$. On a computational-basis state, this gate toggles $h$ if and only if ${\sum }_{u\in S}{b}_u\ge t$, leaving all other bits unchanged. We also write ${\mathrm{Eq}}_t^{S,h}$ for the corresponding equality test ${\sum }_{u\in S}{b}_u=t$. For $0\le t\le |S|$,

where ${\mathrm{Th}}_0^{S,h}$ is the one-qubit bit flip and ${\mathrm{Th}}_{|S|+1}^{S,h}=I$. Thus an equality gate abbreviates at most two allowed gates and uses no additional qubit. The control sets are unbounded in size; the gate count does not count control incidences separately. Throughout, operator products act from right to left.

The symmetry condition is Definition 12 of [1]; cleanliness is the additional implementation requirement in (3). A lift $\tilde{\gamma }$ necessarily preserves $W$ setwise, but it need not fix its wires individually. The definition asks for a lift separately for each $\gamma$, without requiring a homomorphism. Our construction supplies a single explicit group action on all wires. This also ensures that the same lifts work for every subcircuit we concatenate.

For the converse, the Pauli coefficients determine both the selector amplitudes and the phases to be applied during selection. Assume $n\ge 1$. Orthogonality of the Hermitian Pauli basis gives

For $\gamma \in \mathrm{\Gamma }$, define $\gamma P=R_X(\gamma )P{R}_X{(\gamma )}^{†}$. This action only permutes tensor factors; it introduces no signs.

It follows that $J$ is $\mathrm{\Gamma }$-stable and

Indeed, the lower bound is ${\parallel \alpha \parallel }_1\ge {\parallel \alpha \parallel }_2=1$, and the upper bound is Cauchy–Schwarz on the $M$ nonzero coefficients. Define

Both parameters are constant on each orbit, and ${\sum }_{P\in J}{d}_P^2=1$.

Introduce selector wires $Q=\{q_P:P\in J\}$, with group action $q_P\mapsto q_{\gamma P}$. Let $|e_P⟩$ be the computational-basis state whose only nonzero bit is on $q_P$. We will prepare

Each distinct Pauli word has one selector wire, irrespective of its stabilizer. Thus there is no multiplicity from indexing by group elements.

The amplitudes in (6) have no preferred order within an orbit, so we prepare them through simultaneous local rotations and a Hamming-weight test. A product of one-qubit states with amplitude ratios $d_P$ already has the desired relative amplitudes on weight one. The probability of that subspace lies between $e^{-1}$ and $1/2$, regardless of $M$. We lower it to ${\sin }^2(\pi /10)$ with one auxiliary rotation, making two amplification steps exact. We record the reflection identity first; its isometry formulation will later amplify every active input at once.

We use the rotation convention

In particular, $R_y(-\pi /2)|0⟩=|-⟩$ and $R_y(\pi /2)|-⟩=|0⟩$. A reversible predicate test with head in $|-⟩$ leaves that head unchanged and contributes a minus sign exactly when the predicate holds. We use this phase-kickback implementation for all reflections below.

This is an explicit instance of exact amplitude amplification [2, Section 2.1], with the symmetry preserved as in [1, Lemma 6]. Here the initial product rotations and predicate tests supply the entire state-preparation circuit, together with its action on the workspace wires.

A prepared one-hot selector asks for exactly one Pauli word to be applied. The circuit implementing this request must still be a unitary on every selector input. In particular, controlled Pauli words cannot all be put in one commuting layer: two anticommuting words still anticommute on the branch where both of their controls are one. Ordering these whole-word gates arbitrarily would distinguish labels that the group may exchange. We instead order the three Pauli symbols, which are fixed by wire permutations, and put every incidence of a given symbol in the same commuting stage.

For $s\in \{1,2,3\}$, let $L_s$ be the unitary of the incidence layer

Here $P_x$ denotes the factor of $P$ at wire $x$. All controls lie in $Q$ and all targets in $X$, so no target is a control of another gate. Gates with a common target apply the same bit flip, and gates with distinct targets also commute. Thus ${\mathcal{L}}_s$ is a legal layer. Each CNOT is a threshold gate with one control.

Let $H$ be the Hadamard gate and $S=\mathrm{diag}(1,i)$. The identities $H{\sigma }_{1}H={\sigma }_3$ and $S{\sigma }_1{S}^{†}={\sigma }_2$ give controlled-symbol stages

Each uniform tensor product is a layer of identical one-qubit gates on $X$. Define the selector phase layer and the selection circuit by

For a one-hot selector, only the incidences belonging to its selected word are active. The three stages then act on disjoint positions in that word, so their order introduces no Pauli phase. It follows that

Equation (13) specifies the action needed for the block encoding. The same elementary circuit defines a unitary on all other selector inputs, and every incidence layer remains a legal commuting layer.

For every $\gamma \in \mathrm{\Gamma }$, use the lift

The phase layer is preserved because ${\omega }_{\gamma P}={\omega }_P$. The identity ${(\gamma P)}_{\gamma x}=P_x$ shows that each incidence layer is preserved. The uniform basis-change layers are preserved as well. Lemma 2.5 supplies precisely the same lift for $B$, and also for $B^{†}$. More generally, a lift preserving a circuit’s layers preserves its inverse layers: taking adjoints preserves commutativity and reverses only the order of the layers.

Let $W_0$ contain the $M$ selectors and the three preparation wires. Extend $\mathrm{SELECT}$ trivially to the latter wires, and put

This is a $\mathrm{\Gamma }$-symmetric circuit under (14), which in fact defines a homomorphism on all its wires. Its all-zero workspace block is

The first equality only uses the action of $B$ on the all-zero state and its adjoint. Thus the unspecified action of the preparation circuit on other inputs does not enter the block identity. The normalization $\lambda$ leaves a nonzero-workspace component when $\lambda >1$; its norm is determined by unitarity, as follows.

In that case, with ${\mathrm{\Pi }}_0=I_X\otimes |0^{W_0}⟩⟨0^{W_0}|$, unitarity of $A$ and $U$ gives, for each unit vector $|\psi ⟩$,

where

is a unit vector in $\ker {\mathrm{\Pi }}_0$. In particular, the success probability ${\lambda }^{-2}$ is independent of the input.

There are at most $nM$ CNOT incidences across the three symbol stages, $M$ selector phases, and $4n$ basis-change gates. Together with Lemma 2.5, this yields

The block encoding succeeds with the same probability on every active input. This allows amplification without a reflection about the unknown input state. This is the input-independent setting of oblivious amplitude amplification used for linear combinations of unitaries [3, Section I]. The symmetric oblivious-amplification statement in [1, Lemma 7] assumes workspace fixed pointwise, whereas our selector wires are permuted. The proof only needs a reflection about the whole zero-workspace subspace. Its equality test uses the workspace as an unordered control set, so it remains symmetric under precisely those permutations. We give the construction with its exact phase to obtain literal equality with the target unitary.

Applying the lemma to the Pauli block encoding completes the construction. The unit-normalization case can be handled directly, so no singular amplification parameters are needed.

The selector cost is controlled by the number of Pauli words, not the number of their orbits. Replacing an orbit by a single selector label would no longer specify which of its individual words should be applied; the corresponding orbit sum need not be unitary. Thus orbit-constant coefficients explain symmetry of the construction but do not, by themselves, compress it. Appendix A records a different route through symmetric Choi-state preparation, with that preparation made an explicit hypothesis.