Introduction
Graph properties such as 3-colorability and Hamiltonicity give rise to fundamental computational problems, with numerous applications in both theory and practice. Although these properties are, by definition, invariant under relabelling of vertices, algorithms that decide them need not respect these symmetries: they may single out an arbitrary vertex or use the vertex labels to impose an ordering. This mismatch between the levels of abstraction at which computational problems are formulated and at which algorithms are designed and analyzed was a central motivation for the study of choiceless polynomial time by Blass, Gurevich, and Shelah [3 ] , and is closely related to the longstanding problem of capturing polynomial-time computation in descriptive complexity theory.
This line of research has led to the systematic study of symmetric circuits , a model of computation in which the symmetries inherent to a problem are required to extend to the structure of the computation itself. Symmetric circuits thus provide a natural framework for investigating when symmetry-breaking, a form of algorithmic choice, is necessary for efficient computation.
Symmetric circuits were shown to admit exact characterizations in terms of mathematical logic, establishing a deep connection with descriptive complexity theory. In particular, Anderson and Dawar [1 ] established a correspondence between uniform families of polynomial-size symmetric circuits (with threshold gates) and definability in fixed-point logic with counting (FPC). This connection has made techniques from finite model theory available for studying circuit complexity, most notably pebble games between Spoiler and Duplicator. Building on these ideas, Dawar [6 ] and Dawar and Wilsenach [9 , 10 ] developed methods for deriving symmetric circuit lower bounds from winning strategies for Duplicator in pebble games.
With a view to extending this programme to quantum computation, Castro-Silva, Gur, and Strelchuk [5 ] introduced the notion of symmetric quantum circuits . They showed how such circuits can efficiently implement fundamental quantum algorithmic techniques and, moreover, demonstrated exponential quantum advantage in the symmetric setting. In this paper, we turn to the complementary question: can the symmetry restriction itself be exploited to prove lower bounds for quantum circuits? Developing such a technique would be particularly valuable given the scarcity of methods for establishing quantum circuit lower bounds.
Here, we introduce a quantum-inspired generalization of pebble games tailored to the study of symmetric quantum circuits. Our notion of quantum pebble games takes a group-theoretic perspective, interpreting pebbles as restrictions on the symmetries available to Duplicator. The classical notion of partial isomorphism is replaced by a quantum analogue formulated in terms of reduced density matrices, recovering the classical notion for computational-basis states. By recasting pebble games in terms of symmetries and the local structure of quantum states, our framework offers a new perspective that we believe may be of independent interest.
Our main technical contribution is to turn this framework into a method for proving superpolynomial lower bounds on symmetric quantum circuits with restricted entanglement. In particular, we establish such lower bounds for an explicit graph property that is decidable in classical polynomial time: no family of polynomial-size symmetric quantum circuits with entanglement width o ( n / log n ) o(n/\log n) o ( n / log n ) can compute this property. Thus, even for classically tractable problems, symmetry together with restrictions on entanglement can impose fundamental limitations on the power of quantum computation.
To complement this result, we show that bounding some quantum resource is needed for a result of this type to hold: without such restrictions, polynomial-size symmetric quantum circuits capture the full power of BQP on graph problems (and on more general relational structures). Even in the total absence of entanglement, however, we prove that polynomial-size symmetric quantum circuits using only two-qubit gates can still compute all FPC-definable properties. This sharply contrasts with the classical setting, where polynomial-size symmetric circuits with Boolean gates cannot even compute the parity of the number of edges [7 ] .
Finally, we give a direct symmetric implementation of QAOA for MAX 3XOR, together with a test of whether an assignment satisfies a prescribed number of equations. The resulting symmetric circuit accepts with the same probability that QAOA finds an assignment satisfying at least the prescribed number of equations.
Main results
Our results will be described in terms of the graph input model. A graph on [ n ] [n] [ n ] is encoded by its n 2 n^2 n 2 adjacency bits in the computational basis, with one input qubit for each ordered pair of vertices. Additional ancilla qubits begin in ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ . A circuit applies layers of pairwise commuting gates and measures a distinguished output qubit. Its size s ( C ) s(C) s ( C ) is the total number of gates. Computing a property means producing the correct Boolean answer with probability at least 2 / 3 2/3 2/3 on every input.
Let Sym n \operatorname{Sym}_n Sym n be the group of permutations of [ n ] [n] [ n ] . Graph properties are invariant under the action of Sym n \operatorname{Sym}_n Sym n on its vertices. Quantum circuits are said to be symmetric if they are likewise invariant under these symmetries: we require every σ ∈ Sym n \sigma\in\operatorname{Sym}_n σ ∈ Sym n to extend from the input qubits, by ( u , v ) ↦ ( σ ( u ) , σ ( v ) ) (u,v) \mapsto(\sigma(u),\sigma(v)) ( u , v ) ↦ ( σ ( u ) , σ ( v )) , to a permutation of the circuit wires that preserves each layer and fixes the output wire. (See § 2.2 for a precise definition.)
The entanglement width3 of a state ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ is the smallest number b b b such that ∣ ψ ⟩ \lvert\psi\rangle ∣ ψ ⟩ can be written as a tensor product of states on disjoint sets of at most b b b qubits. For example, a product state has width 1 1 1 , while a tensor product of Bell pairs has width 2 2 2 regardless of the number of pairs. The entanglement width η ( C ) \eta(C) η ( C ) of a quantum circuit C C C is the smallest integer such that, on every computational-basis input and after each circuit layer, the global state of all wires has entanglement width at most η ( C ) \eta(C) η ( C ) ; the partition of the state into blocks is allowed to depend on both the input and the layer. Formal definitions appear in § 2 .
The hard property P C F I A l t \mathcal{P}_{\mathrm{CFI}}^{\mathrm{Alt}} P CFI Alt is a fixed polynomial-time graph property separating two families obtained from the construction of Cai, Fürer, and Immerman [4 ] . Their members are nonisomorphic but remain indistinguishable in an appropriate pebble game with linearly many pebbles. § 6 describes these families and the separating property.
We note that the property P C F I A l t \mathcal{P}_{\mathrm{CFI}}^{\mathrm{Alt}} P CFI Alt admits a classical polynomial-time algorithm. Our main result identifies a restriction to computing it symmetrically, even in the quantum setting: polynomial-size circuits must generate near-linear entanglement (on the number of vertices) in order to compute it.
Theorem 1.1. Let f : Z + → Z + f:\mathbb{Z}_{+}\to\mathbb{Z}_{+} f : Z + → Z + be any increasing function with f ( n ) = ω ( log n ) f(n)=\omega(\log n) f ( n ) = ω ( log n ) . There is no family of symmetric quantum circuits ( C n ) n (C_n)_n ( C n ) n using one-qubit and two-qubit gates computing P C F I A l t \mathcal{P}_{\mathrm{CFI}}^{\mathrm{Alt}} P CFI Alt which has size s ( C n ) = 2 o ( f ( n ) ) s(C_n)=2^{o(f(n))} s ( C n ) = 2 o ( f ( n )) and entanglement width η ( C n ) = O ( n / f ( n ) ) \eta(C_n)=O(n/f(n)) η ( C n ) = O ( n / f ( n )) .
In this theorem, the function f f f relates the allowed entangled block size to the excluded circuit size. If the blocks have size O ( n / f ( n ) ) O(n/f(n)) O ( n / f ( n )) , a family computing the property cannot have gate count 2 o ( f ( n ) ) 2^{o(f(n))} 2 o ( f ( n )) . The condition f ( n ) = ω ( log n ) f(n)=\omega(\log n) f ( n ) = ω ( log n ) ensures that this excluded range includes every polynomial gate count. We note that the exact result we prove is stronger, as it also holds for circuits which are only symmetric with respect to the alternating group Alt n \operatorname{Alt}_n Alt n of even permutations; see Theorem 6.1 . As previously mentioned, the theorem is proven via a more general framework of Spoiler–Duplicator pebble games, which we describe in § 2.4 . The following immediate consequences give the polynomial-size case and the case of a power-law bound on the block size.
Corollary 1.2. There is no polynomial-size family of symmetric quantum circuits ( C n ) n (C_n)_n ( C n ) n using one-qubit and two-qubit gates that computes P C F I A l t \mathcal{P}^{\mathrm{Alt}}_{\mathrm{CFI}} P CFI Alt and has entanglement width η ( C n ) = o ( n / log n ) \eta(C_n) = o(n/\log n) η ( C n ) = o ( n / log n ) .
Corollary 1.3. Let 0 < γ ≤ 1 0 < \gamma\le1 0 < γ ≤ 1 . There is no family of symmetric quantum circuits ( C n ) n (C_n)_n ( C n ) n using one-qubit and two-qubit gates computing P C F I A l t \mathcal{P}^{\mathrm{Alt}}_{\mathrm{CFI}} P CFI Alt which has size s ( C n ) = 2 o ( n γ ) s(C_n) = 2^{o(n^\gamma)} s ( C n ) = 2 o ( n γ ) and entanglement width η ( C n ) = O ( n 1 − γ ) \eta(C_n) = O(n^{1-\gamma}) η ( C n ) = O ( n 1 − γ ) .
Our next result shows that restricting some quantum resource is essential for obtaining the lower bounds above: unrestricted polynomial-time symmetric computation attains the full power of BQP.
Theorem 1.4. Let P \mathcal{P} P be a graph property. Suppose that a polynomial-time uniform family of quantum circuits computes P \mathcal{P} P using q ( n ) q(n) q ( n ) one-qubit and two-qubit gates on inputs of order n n n . Then, P \mathcal{P} P can also be computed by a polynomial-time uniform family of symmetric quantum circuits using O ( q ( n ) + n 4 log 2 ( n ) ) O(q(n) + n^4\log^2(n)) O ( q ( n ) + n 4 log 2 ( n )) one-qubit and two-qubit gates.
Furthermore, restricting entanglement width does not trivialize our model of computation. Fixed-point logic with counting (FPC) extends first-order logic with inductive definitions and counting, without assuming an ordering of the input vertices. It can express connectivity and the existence of a perfect matching, and captures all polynomial-time graph properties on planar graphs [7 ] . Our next result shows that every FPC-definable graph property can be computed by a polynomial-time uniform family of polynomial-size symmetric quantum circuits of entanglement width 1, using only one-qubit and two-qubit gates.
Theorem 1.5. Let P \mathcal{P} P be an FPC-definable graph property. Then P \mathcal{P} P can be computed by a polynomial-time uniform family of symmetric quantum circuits with entanglement width 1 using only one-qubit and two-qubit gates.
Finally, we connect our framework to quantum optimization by giving an efficient symmetric implementation of the Quantum Approximate Optimization Algorithm which we apply to MAX 3XOR. An instance of this problem is given by J = ( A , d ) J = (A,d) J = ( A , d ) , and consists of m m m equations A y = d Ay = d A y = d over F 2 \mathbb{F}_2 F 2 with n n n Boolean variables, where each row of A A A contains three nonzero entries. The aim is to find an assignment satisfying as many equations as possible. QAOA begins with the uniform superposition of all assignments and at each round applies phases determined by the number of satisfied equations, followed by the application of e − i β r X e^{-i\beta_r X} e − i β r X on every variable qubit. The parameters γ r \gamma_r γ r and β r \beta_r β r control these two operations in round r r r , respectively.
Permuting the equations permutes the rows of A A A and the corresponding entries of d d d , permuting the variables permutes the columns of A A A . We call a circuit symmetric for this problem if every such independent permutation of the equations and variables extends to a permutation of all circuit wires that preserves each layer and fixes the output wire.
Theorem 1.6 (Symmetric implementation of QAOA). For positive integers m , n , p ∈ N m,n,p \in\mathbb{N} m , n , p ∈ N , a threshold t ∈ { 0 , … , m } t \in\{0,\ldots,m\} t ∈ { 0 , … , m } , and angles γ = ( γ 1 , … , γ p ) \gamma= (\gamma_1,\ldots,\gamma_p) γ = ( γ 1 , … , γ p ) and β = ( β 1 , … , β p ) ∈ R p \beta= (\beta_1,\ldots,\beta_p) \in\mathbb{R}^p β = ( β 1 , … , β p ) ∈ R p , there is a symmetric quantum circuit C C C that uses O ( p m n + m log m ) O(pmn + m\log m) O ( p mn + m log m ) one-qubit and two-qubit gates and satisfies the following: on every MAX 3XOR instance J = ( A , d ) J = (A,d) J = ( A , d ) with m m m equations and n n n variables, encoded as ∣ J ⟩ = ∣ A ⟩ ∣ d ⟩ |J\rangle= |A\rangle|d\rangle ∣ J ⟩ = ∣ A ⟩ ∣ d ⟩ , its acceptance probability equals the probability that QAOA with angles γ , β \gamma,\beta γ , β produces an assignment satisfying at least t t t equations.
This construction connects our lower bound methods to quantum optimization. The computation accepts when the QAOA algorithm produces an assignment satisfying at least t t t equations (so its acceptance probability measures success in the optimization task). Our techniques can therefore be used to study the entanglement required by the full symmetric implementation, including its auxiliary qubits.
Prior work
Anderson and Dawar [1 ] characterize fixed-point logic with counting by polynomially uniform families of symmetric circuits over a suitable gate set. Symmetry here is a property of the circuit structure: every permutation of the input labels respecting the encoding extends to an automorphism of the whole circuit. Inexpressibility in FPC, as in the result of Cai, Fürer, and Immerman [4 ] , consequently yields lower bounds for symmetric circuits [7 ] .
Dawar [6 ] and Dawar and Wilsenach [9 , 10 ] formulate the lower-bound argument directly using pebble games. Their method also applies to symmetric arithmetic circuits computing the permanent [9 ] and determinant [10 ] . Dawar extends the CFI lower bound to other properties through symmetric circuit reductions [6 ] . Our quantum indistinguishability theorem has the same role: it transfers a winning Duplicator strategy into equality of circuit output probabilities.
The symmetric quantum model of Castro-Silva, Gur, and Strelchuk supports amplitude amplification and phase estimation [5 ] . They also give polynomial-size symmetric quantum circuits for XOR-SAT, obtaining an exponential separation from symmetric classical threshold circuits. These upper bounds use arbitrary single-qubit gates and unbounded-fan-in threshold gates. Using our symmetric implementation of threshold gates using 1-qubit and 2-qubit gates (Lemma 7.1), we show that our models are equivalent in power.
Jozsa and Linden [14 ] show that polynomial-size uniform quantum computations over two-qubit gates can be simulated efficiently when, after every gate, their states factor into blocks of bounded size. Our result addresses the entanglement needed under a symmetry requirement, for a property that already has a classical polynomial-time algorithm. Note that we allow the block-size bound to grow to n 1 − o ( 1 ) n^{1-o(1)} n 1 − o ( 1 ) , thus going beyond the remit of their results.
AI disclosure statement
The definition of the quantum pebble game and the associated lower bounds were obtained and written without AI assistance. Theorems 1.4–1.6 were later obtained by Google Antigravity when prompted by the authors. The authors subsequently simplified and rewrote the proofs of those results.
Circuit model, pebble games, and proof overview
Here, we formally describe our symmetric quantum circuit model. While our main results are stated for graphs, this model holds in greater generality for any finite relational structure, as given below.
Preliminary definitions
Definition 2.1. A relational vocabulary is a nonempty finite tuple τ = ( R 1 r 1 , … , R k r k ) \tau= (R_1^{r_1}, \ldots, R_k^{r_k}) τ = ( R 1 r 1 , … , R k r k ) of relation symbols, where for each i ∈ [ k ] i \in[k] i ∈ [ k ] , the relation symbol R i R_i R i has an associated arity r i ∈ Z + r_i \in\mathbb{Z}_+ r i ∈ Z + .
Definition 2.2. A τ \tau τ -structure with respect to a relational vocabulary τ = ( R 1 r 1 , … , R k r k ) \tau= (R_1^{r_1}, \ldots, R_k^{r_k}) τ = ( R 1 r 1 , … , R k r k ) is a tuple A = ⟨ A ; R 1 A , … , R k A ⟩ \mathcal{A} = \langle A; R_1^{\mathcal{A}}, \ldots, R_k^{\mathcal{A}} \rangle A = ⟨ A ; R 1 A , … , R k A ⟩ , where A A A is a set called the domain of A \mathcal{A} A and for each i ∈ [ k ] i \in[k] i ∈ [ k ] , we have R i A ⊆ A r i R_i^{\mathcal{A}} \subseteq A^{r_i} R i A ⊆ A r i .
Let fin [ τ ] \operatorname{fin}[\tau] fin [ τ ] denote the set of finite τ \tau τ -structures. The elements of the domain A A A are called the elements of A \mathcal{A} A . The size of a structure is the size of its domain. A structure A \mathcal{A} A is finite if its domain is finite.
For example, consider the relational vocabulary τ g r a p h = ( E 2 ) \tau_{\mathrm{graph}} = (E^{2}) τ graph = ( E 2 ) consisting of one binary relation E E E . A directed graph can then be described as a τ g r a p h \tau_{\mathrm{graph}} τ graph -structure G = ⟨ V ; E G ⟩ \mathcal{G} = \langle V; E^{\mathcal{G}}\rangle G = ⟨ V ; E G ⟩ where the domain is the set of vertices V V V and the edges are described by E G ⊆ V 2 E^{\mathcal{G}} \subseteq V^{2} E G ⊆ V 2 .
A τ \tau τ -property P \mathcal{P} P is a subset of fin [ τ ] \operatorname{fin}[\tau] fin [ τ ] . A τ \tau τ -property P \mathcal{P} P is said to be polynomial time if there is a polynomial-time algorithm which, given an efficient representation of a finite τ \tau τ -structure A \mathcal{A} A , decides whether A ∈ P \mathcal{A} \in\mathcal{P} A ∈ P . Say that a τ \tau τ -property P \mathcal{P} P separates two structures A , B ∈ fin [ τ ] \mathcal{A}, \mathcal{B} \in\operatorname{fin}[\tau] A , B ∈ fin [ τ ] if A \mathcal{A} A and B \mathcal{B} B do not agree on membership in P \mathcal{P} P , and P \mathcal{P} P separates two families of τ \tau τ -structures ( A n ) n ∈ Z ≥ 1 (\mathcal{A}_{n})_{n\in\mathbb{Z}_{\geq1}} ( A n ) n ∈ Z ≥ 1 and ( B n ) n ∈ Z ≥ 1 (\mathcal{B}_{n})_{n\in\mathbb{Z}_{\geq1}} ( B n ) n ∈ Z ≥ 1 if it separates A n \mathcal{A}_{n} A n and B n \mathcal{B}_{n} B n for each n n n .
For a finite set S S S , let Sym S \operatorname{Sym}_{S} Sym S denote the symmetric group of all permutations on S S S . Let Alt S ≤ Sym S \operatorname{Alt}_{S} \leq\operatorname{Sym}_{S} Alt S ≤ Sym S denote the alternating group of even permutations on S S S . Write Sym n \operatorname{Sym}_{n} Sym n for Sym [ n ] \operatorname{Sym}_{[n]} Sym [ n ] and Alt n \operatorname{Alt}_{n} Alt n for Alt [ n ] \operatorname{Alt}_{[n]} Alt [ n ] . If G G G is a group acting on S S S and s ∈ S s \in S s ∈ S , let Stab G ( s ) = { σ ∈ G : σ ( s ) = s } \operatorname{Stab}_{G}(s) = \{\sigma\in G : \sigma(s) = s\} Stab G ( s ) = { σ ∈ G : σ ( s ) = s } denote the stabilizer group of s s s and Orb G ( s ) = { σ ( s ) : σ ∈ G } \operatorname{Orb}_{G}(s) = \{\sigma(s) : \sigma\in G\} Orb G ( s ) = { σ ( s ) : σ ∈ G } denote the orbit of s s s under G G G . If T ⊆ S T \subseteq S T ⊆ S , let σ ( T ) = { σ ( t ) : t ∈ T } \sigma(T) = \{\sigma(t) : t \in T\} σ ( T ) = { σ ( t ) : t ∈ T } and let Stab G ( T ) = ⋂ t ∈ T Stab G ( t ) \operatorname{Stab}_{G}(T) = \bigcap_{t\in T}\operatorname{Stab}_{G}(t) Stab G ( T ) = ⋂ t ∈ T Stab G ( t ) denote the pointwise stabilizer of T T T .
Denote the group of unitaries on a Hilbert space H \mathcal{H} H by U ( H ) U(\mathcal{H}) U ( H ) . If H S = ( C 2 ) ⊗ S \mathcal{H}_{S} = (\mathbb{C}^{2})^{\otimes S} H S = ( C 2 ) ⊗ S and G G G is a group acting on S S S , there is a natural embedding G → U ( H S ) G \to U(\mathcal{H}_{S}) G → U ( H S ) which maps σ ∈ G \sigma\in G σ ∈ G to the unitary on H S \mathcal{H}_{S} H S which permutes the qubits according to the action of σ \sigma σ . Write U σ U_{\sigma} U σ for this unitary, which is defined as follows: if ∣ ψ ⟩ = ∣ ψ s 1 ⟩ ⊗ ⋯ ⊗ ∣ ψ s N ⟩ |\psi\rangle= |\psi_{s_{1}}\rangle\otimes\cdots\otimes|\psi_{s_{N}}\rangle ∣ ψ ⟩ = ∣ ψ s 1 ⟩ ⊗ ⋯ ⊗ ∣ ψ s N ⟩ where S = { s 1 , … , s N } S = \{s_{1},\ldots,s_{N}\} S = { s 1 , … , s N } , then
U σ ∣ ψ ⟩ = ∣ ψ σ − 1 ( s 1 ) ⟩ ⊗ ⋯ ⊗ ∣ ψ σ − 1 ( s N ) ⟩ . (1) U_{\sigma}|\psi\rangle= |\psi_{\sigma^{-1}(s_{1})}\rangle\otimes\cdots\otimes|\psi_{\sigma^{-1}(s_{N})}\rangle. \tag*{(1)} U σ ∣ ψ ⟩ = ∣ ψ σ − 1 ( s 1 ) ⟩ ⊗ ⋯ ⊗ ∣ ψ σ − 1 ( s N ) ⟩ . (1)
That is, qubit s ∈ S s \in S s ∈ S of a state ∣ ψ ⟩ ∈ H S |\psi\rangle\in\mathcal{H}_{S} ∣ ψ ⟩ ∈ H S corresponds to qubit σ ( s ) \sigma(s) σ ( s ) of U σ ∣ ψ ⟩ U_{\sigma}|\psi\rangle U σ ∣ ψ ⟩ : hence qubit s s s of U σ ∣ ψ ⟩ U_{\sigma}|\psi\rangle U σ ∣ ψ ⟩ is qubit σ − 1 ( s ) \sigma^{-1}(s) σ − 1 ( s ) of ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ . Write Γ G = { U σ : σ ∈ G } \Gamma_{G} = \{U_{\sigma} : \sigma\in G\} Γ G = { U σ : σ ∈ G } for the image of G G G in U ( H S ) U(\mathcal{H}_{S}) U ( H S ) under this embedding.
Fix a relational vocabulary τ = ( R 1 r 1 , … , R k r k ) \tau= (R_{1}^{r_{1}},\ldots,R_{k}^{r_{k}}) τ = ( R 1 r 1 , … , R k r k ) , and let fin n [ τ ] \operatorname{fin}_{n}[\tau] fin n [ τ ] denote the τ \tau τ -structures of size n ∈ Z + n \in\mathbb{Z}_{+} n ∈ Z + . For simplicity, assume every structure in fin n [ τ ] \operatorname{fin}_{n}[\tau] fin n [ τ ] has domain [ n ] [n] [ n ] . We encode each structure A ∈ fin n [ τ ] \mathcal{A} \in\operatorname{fin}_{n}[\tau] A ∈ fin n [ τ ] as a bitstring b ( A ) b(\mathcal{A}) b ( A ) of length ℓ τ ( n ) = ∑ i = 1 k n r i \ell_{\tau}(n) = \sum_{i=1}^{k} n^{r_{i}} ℓ τ ( n ) = ∑ i = 1 k n r i as follows. Index the bitstring by the tuples
Q τ = { ( i , n 1 , … , n r i ) : i ∈ [ k ] , n 1 , … , n r i ∈ [ n ] } , (2) Q^{\tau} = \{(i,n_{1},\ldots,n_{r_{i}}) : i \in[k],\ n_{1},\ldots,n_{r_{i}} \in[n]\}, \tag*{(2)} Q τ = {( i , n 1 , … , n r i ) : i ∈ [ k ] , n 1 , … , n r i ∈ [ n ]} , (2)
which we refer to as qubit labels , and define the bit labelled by each ( i , n 1 , … , n r i ) ∈ Q τ (i,n_{1},\ldots,n_{r_{i}}) \in Q^{\tau} ( i , n 1 , … , n r i ) ∈ Q τ as
b ( A ) ( i , n 1 , … , n r i ) = { 1 if ( n 1 , … , n r i ) ∈ R i A , 0 if ( n 1 , … , n r i ) ∉ R i A . (3) b(\mathcal{A})_{(i,n_{1},\ldots,n_{r_{i}})} =
\begin{cases}
1 & \text{if } (n_{1},\ldots,n_{r_{i}}) \in R_{i}^{\mathcal{A}},\\
0 & \text{if } (n_{1},\ldots,n_{r_{i}}) \notin R_{i}^{\mathcal{A}}.
\end{cases} \tag*{(3)} b ( A ) ( i , n 1 , … , n r i ) = { 1 0 if ( n 1 , … , n r i ) ∈ R i A , if ( n 1 , … , n r i ) ∈ / R i A . (3)
This encoding forms a bijection between the bitstrings { 0 , 1 } ℓ τ ( n ) \{0,1\}^{\ell_{\tau}(n)} { 0 , 1 } ℓ τ ( n ) and the structures in fin n [ τ ] \operatorname{fin}_{n}[\tau] fin n [ τ ] . Observe furthermore that ℓ τ ( n ) \ell_{\tau}(n) ℓ τ ( n ) is polynomial in n n n . We can then define H n τ = ( C 2 ) ⊗ Q τ \mathcal{H}_{n}^{\tau} = (\mathbb{C}^{2})^{\otimes Q^{\tau}} H n τ = ( C 2 ) ⊗ Q τ , and encode each structure A ∈ fin n [ τ ] \mathcal{A} \in\operatorname{fin}_{n}[\tau] A ∈ fin n [ τ ] as the computational basis state ∣ A ⟩ = ∣ b ( A ) ⟩ |\mathcal{A}\rangle= |b(\mathcal{A})\rangle ∣ A ⟩ = ∣ b ( A )⟩ . We often abbreviate ( i , n 1 , … , n r i ) (i,n_{1},\ldots,n_{r_{i}}) ( i , n 1 , … , n r i ) to ( i , n ⃗ ) (i,\vec{n}) ( i , n ) .
We refer to general states ∣ A ⟩ ∈ H n τ |\mathcal{A}\rangle\in\mathcal{H}_{n}^{\tau} ∣ A ⟩ ∈ H n τ as quantum τ \tau τ -structures .
The action of a group G G G on the domain [ n ] [n] [ n ] of A \mathcal{A} A can be extended to an action on Q τ Q^{\tau} Q τ by letting σ ( i , n ⃗ ) = ( i , σ ( n ⃗ ) ) \sigma(i,\vec{n}) = (i,\sigma(\vec{n})) σ ( i , n ) = ( i , σ ( n )) , where if n ⃗ = ( n 1 , … , n r i ) \vec{n} = (n_{1},\ldots,n_{r_{i}}) n = ( n 1 , … , n r i ) then σ ( n ⃗ ) = ( σ ( n 1 ) , … , σ ( n r i ) ) \sigma(\vec{n}) = (\sigma(n_{1}),\ldots,\sigma(n_{r_{i}})) σ ( n ) = ( σ ( n 1 ) , … , σ ( n r i )) . Γ G ≤ U ( H n τ ) \Gamma_{G} \leq U(\mathcal{H}_{n}^{\tau}) Γ G ≤ U ( H n τ ) is then the group of unitaries which permutes the qubits according to G G G : we say Γ G \Gamma_{G} Γ G is the *classical unitary group corresponding to G G G .
Symmetric quantum circuits
We now define symmetric quantum circuits, following [5 ] . A quantum circuit consists of a set of wires W W W which define a Hilbert space H W = ( C 2 ) ⊗ W \mathcal{H}_{W} = (\mathbb{C}^{2})^{\otimes W} H W = ( C 2 ) ⊗ W upon which a sequence of unitary operators called gates act, chosen from a quantum gate set. Our gate set G \mathbb{G} G corresponds to all unitaries acting on at most two qubits.
Remark. Note that this formally differs from the gate set G t h r \mathsf{G}_{\mathrm{thr}} G thr considered in [5 ] , which also includes threshold gates. However, since 2-qubit gates can symmetrically implement threshold gates with only logarithmic overhead (see Lemma 7.1), it easily follows from the arguments in that paper that our classes of symmetric circuits are equivalent up to a logarithmic factor in complexity.
We define quantum circuits in terms of layers of commuting gates.
Definition 2.3 (Quantum circuit and layers). A quantum circuit over gate set G \mathcal{G} G consists of a set of wires W W W and a sequence of layers ( L 1 , … , L m ) (\mathcal{L}_1,\ldots,\mathcal{L}_m) ( L 1 , … , L m ) . Each layer L \mathcal{L} L is a set of pairwise commuting unitary gates U g U_g U g from G \mathcal{G} G acting on H W \mathcal{H}_W H W .
To define a model of computation, we fix an output wire.
Definition 2.4 (Output τ \tau τ -circuit). An output quantum τ \tau τ -circuit of order n n n is a quantum circuit whose wires are partitioned as W = X ⊔ A W=X\sqcup A W = X ⊔ A , where X = { x ( i , n ⃗ ) : ( i , n ⃗ ) ∈ Q τ } X=\{x_{(i,\vec{n})}:(i,\vec{n})\in Q^\tau\} X = { x ( i , n ) : ( i , n ) ∈ Q τ } is the set of input wires and A A A is the set of ancilla wires , which has a distinguished output wire w o u t ∈ W w_{\mathrm{out}}\in W w out ∈ W .
We often leave τ \tau τ implicit for brevity. The Hilbert space of an output quantum τ \tau τ -circuit of order n n n is partitioned as H W = H n τ ⊗ H A \mathcal{H}_W=\mathcal{H}^\tau_n\otimes\mathcal{H}_A H W = H n τ ⊗ H A , where H n τ \mathcal{H}^\tau_n H n τ is encoded on the input wires X X X and the ancilla wires A A A form the space H A = ( C 2 ) ⊗ A \mathcal{H}_A=(\mathbb{C}^2)^{\otimes A} H A = ( C 2 ) ⊗ A . Such a circuit C C C on layers ( L 1 , … , L m ) (\mathcal{L}_1,\ldots,\mathcal{L}_m) ( L 1 , … , L m ) then defines a function H n τ → [ 0 , 1 ] \mathcal{H}^\tau_n\to[0,1] H n τ → [ 0 , 1 ] as follows: we begin by initializing the input wires X X X to a quantum τ \tau τ -structure ∣ ψ ⟩ ∈ H n τ |\psi\rangle\in\mathcal{H}^\tau_n ∣ ψ ⟩ ∈ H n τ and each ancilla wire to ∣ 0 ⟩ |0\rangle ∣0 ⟩ , forming the state ∣ ψ ⟩ ∣ 0 ⟩ ⊗ A ∈ H W |\psi\rangle|0\rangle^{\otimes A}\in\mathcal{H}_W ∣ ψ ⟩ ∣0 ⟩ ⊗ A ∈ H W . We then apply the unitaries from each layer in turn. For each layer L i \mathcal{L}_i L i , let L i L_i L i denote the product of the unitaries in L i \mathcal{L}_i L i (in arbitrary order, since they commute). We say that L i \mathcal{L}_i L i is represented by the unitary L i L_i L i . We then form the state
∣ ψ ′ ⟩ : = L m L m − 1 ⋯ L 2 L 1 ∣ ψ ⟩ ∣ 0 ⟩ ⊗ A . (4) |\psi'\rangle:= L_mL_{m-1}\cdots L_2L_1|\psi\rangle|0\rangle^{\otimes A}. \tag*{(4)} ∣ ψ ′ ⟩ := L m L m − 1 ⋯ L 2 L 1 ∣ ψ ⟩ ∣0 ⟩ ⊗ A . (4)
Finally, we measure the wire w o u t w_{\mathrm{out}} w out in the computational basis using the observable O o u t : = ∣ 1 ⟩ w o u t ⟨ 1 ∣ w o u t ⊗ I W ∖ { w o u t } O_{\mathrm{out}}:=|1\rangle_{w_{\mathrm{out}}}\langle1|_{w_{\mathrm{out}}}\otimes I_{W\setminus\{w_{\mathrm{out}}\}} O out := ∣1 ⟩ w out ⟨ 1 ∣ w out ⊗ I W ∖ { w out } . The probability of outcome 1 is C [ ∣ ψ ⟩ ] : = ⟨ ψ ′ ∣ O o u t ∣ ψ ′ ⟩ C[|\psi\rangle]:=\langle\psi'|O_{\mathrm{out}}|\psi'\rangle C [ ∣ ψ ⟩] := ⟨ ψ ′ ∣ O out ∣ ψ ′ ⟩ .
Our model of quantum computation takes a quantum τ \tau τ -structure as input and produces a classical probabilistic Boolean output. In our results, we will typically be concerned only with inputs ∣ A ⟩ |A\rangle ∣ A ⟩ which represent classical τ \tau τ -structures A A A . As before, a family of output quantum τ \tau τ -circuits ( C n ) n (C_n)_n ( C n ) n consists of one such circuit C n C_n C n of order n n n for each n ∈ Z + n\in\mathbb{Z}_+ n ∈ Z + .
Definition 2.5. A family of output quantum τ \tau τ -circuits ( C n ) n (C_n)_n ( C n ) n computes a τ \tau τ -property P \mathcal{P} P if for every n ∈ Z + n\in\mathbb{Z}_+ n ∈ Z + and A ∈ fin n [ τ ] A\in\operatorname{fin}_n[\tau] A ∈ fin n [ τ ] , we have C n [ ∣ A ⟩ ] ≥ 2 / 3 C_n[|A\rangle]\ge2/3 C n [ ∣ A ⟩] ≥ 2/3 if A ∈ P A\in\mathcal{P} A ∈ P and C n [ ∣ A ⟩ ] ≤ 1 / 3 C_n[|A\rangle]\le1/3 C n [ ∣ A ⟩] ≤ 1/3 if A ∉ P A\notin\mathcal{P} A ∈ / P .
The size s ( C ) s(C) s ( C ) is the number of gates in an output quantum circuit C C C and the number of ancillas a ( C ) a(C) a ( C ) is the size of its set A A A of ancilla wires.
Definition 2.6 (Circuit automorphism). An automorphism of a quantum circuit C C C with wires W W W is a unitary V ∈ U ( H W ) V\in\mathrm{U}(\mathcal{H}_W) V ∈ U ( H W ) , which acts by permuting the wires W W W , such that for each layer L \mathcal{L} L of C C C we have L = V L V † : = { V U g V † : U g ∈ L } \mathcal{L}=V\mathcal{L}V^\dagger:=\{VU_gV^\dagger:U_g\in\mathcal{L}\} L = V L V † := { V U g V † : U g ∈ L } .
That is, an automorphism is a permutation of the wires which leaves each layer unchanged up to an unimportant rearrangement of the gates. In other words, an automorphism V V V acts on the gates in each layer by conjugation. We also say that a unitary V ∈ U ( H W ) V\in\mathrm{U}(\mathcal{H}_W) V ∈ U ( H W ) which acts by permuting the wires is an automorphism of a layer L \mathcal{L} L if L = { V U g V † : U g ∈ L } \mathcal{L}=\{VU_gV^\dagger:U_g\in\mathcal{L}\} L = { V U g V † : U g ∈ L } , and of a unitary L ∈ U ( H W ) L\in\mathrm{U}(\mathcal{H}_W) L ∈ U ( H W ) if L = V L V † L=VLV^\dagger L = V L V † (that is, V V V commutes with L L L ). Observe that if a unitary L L L represents a layer L \mathcal{L} L and V V V is an automorphism of L \mathcal{L} L , then V V V is also an automorphism of L L L . Given a permutation π ∈ Sym W \pi\in\operatorname{Sym}_W π ∈ Sym W , we write U π ∈ U ( H W ) U_\pi\in\mathrm{U}(\mathcal{H}_W) U π ∈ U ( H W ) for the unitary which permutes the wires according to π \pi π as in equation (2.1).
Consider an output quantum τ \tau τ -circuit C C C of order n n n with wires W = X ⊔ A W=X\sqcup A W = X ⊔ A and a symmetry group Γ ≤ U ( H n τ ) \Gamma\le\mathrm{U}(\mathcal{H}^\tau_n) Γ ≤ U ( H n τ ) . A unitary U ∈ Γ U\in\Gamma U ∈ Γ induces an automorphism V V V of C C C if V = U ⊗ U A V=U\otimes U_A V = U ⊗ U A for some
unitary U A ∈ U ( H A ) U_A \in\mathrm{U}(\mathcal{H}_A) U A ∈ U ( H A ) which permutes the ancilla wires. Note that the automorphism must act separately on the input wires and ancillas.
Definition 2.7 (Symmetric circuit). Suppose G ≤ S y m n G \leq\mathrm{Sym}_n G ≤ Sym n . Recall that Γ G ≤ U ( H ⊗ n ) \Gamma_G \leq\mathrm{U}(\mathcal{H}^{\otimes n}) Γ G ≤ U ( H ⊗ n ) is the unitary group which permutes the qubits according to the action of G G G . An output quantum τ \tau τ -circuit of order n n n is Γ G \Gamma_G Γ G -symmetric if every U σ ∈ Γ G U_\sigma\in\Gamma_G U σ ∈ Γ G induces an automorphism V V V of C C C which acts trivially on w o u t w_{\mathrm{out}} w out , in the sense that V = I w o u t ⊗ V W ∖ { w o u t } ′ V = I_{w_{\mathrm{out}}} \otimes V'_{W \setminus\{w_{\mathrm{out}}\}} V = I w out ⊗ V W ∖ { w out } ′ for some V ′ V' V ′ acting on the other qubits.
That is, in a Γ G \Gamma_G Γ G -symmetric circuit, every permutation of the input wires U ∈ Γ G U \in\Gamma_G U ∈ Γ G induces a permutation of the ancillas V ′ V' V ′ such that V = U ⊗ V ′ V = U \otimes V' V = U ⊗ V ′ is an automorphism fixing w o u t w_{\mathrm{out}} w out . This is the permutation symmetry requirement of [5 ] , with the output wire fixed.
When working with Γ G \Gamma_G Γ G -symmetric circuits C C C of order n n n , we also say that π ∈ S y m W \pi\in\mathrm{Sym}_W π ∈ Sym W is an automorphism of C C C if U π U_\pi U π is an automorphism of C C C , and we say σ ∈ S y m n \sigma\in\mathrm{Sym}_n σ ∈ Sym n induces an automorphism π ∈ S y m W \pi\in\mathrm{Sym}_W π ∈ Sym W if U σ ∈ U ( H ⊗ n ) U_\sigma\in\mathrm{U}(\mathcal{H}^{\otimes n}) U σ ∈ U ( H ⊗ n ) induces U π U_\pi U π . Observe that if σ \sigma σ induces π \pi π , then σ \sigma σ and π \pi π act identically on the input wires of C C C .
Entanglement width
We focus on quantum circuits taking classical structures as input, encoded as computational basis states ∣ A ⟩ |A\rangle ∣ A ⟩ , and thereby obtain lower bounds on the size of quantum circuits solving classical problems. Our technique is heavily dependent on the amount of entanglement used by the circuit in the following sense.
Definition 2.8. Let ∣ ψ ⟩ ∈ ( C 2 ) ⊗ n |\psi\rangle\in(\mathbb{C}^{2})^{\otimes n} ∣ ψ ⟩ ∈ ( C 2 ) ⊗ n be a state on n n n qubits. The entanglement width of ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ , denoted η ( ∣ ψ ⟩ ) \eta(|\psi\rangle) η ( ∣ ψ ⟩) , is the smallest integer such that ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ admits a decomposition ∣ ψ ⟩ = ∣ ψ 1 ⟩ ⊗ ⋯ ⊗ ∣ ψ k ⟩ |\psi\rangle= |\psi_1\rangle\otimes\cdots\otimes|\psi_k\rangle ∣ ψ ⟩ = ∣ ψ 1 ⟩ ⊗ ⋯ ⊗ ∣ ψ k ⟩ , where each state ∣ ψ i ⟩ |\psi_i\rangle ∣ ψ i ⟩ is defined over a block S i S_i S i of a partition [ n ] = S 1 ⊔ ⋯ ⊔ S k [n] = S_1 \sqcup\cdots\sqcup S_k [ n ] = S 1 ⊔ ⋯ ⊔ S k , with ∣ S i ∣ ≤ η ( ∣ ψ ⟩ ) |S_i| \leq\eta(|\psi\rangle) ∣ S i ∣ ≤ η ( ∣ ψ ⟩) .
That is, if η ( ∣ ψ ⟩ ) ≤ η \eta(|\psi\rangle) \leq\eta η ( ∣ ψ ⟩) ≤ η , then the state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ uses at most η \eta η -partite entanglement. Entanglement width was previously defined by Jozsa and Linden [14 Def. 4] , where it was called being “p p p -blocked”.
Definition 2.9. Let C C C be an output quantum τ \tau τ -circuit of order n n n whose layers are represented by unitaries L 1 , … , L m L_1, \ldots, L_m L 1 , … , L m . Let L ≤ 0 = I L_{\leq0} = I L ≤ 0 = I and L ≤ i = L i L i − 1 ⋯ L 1 L_{\leq i} = L_iL_{i-1} \cdots L_1 L ≤ i = L i L i − 1 ⋯ L 1 for each i ∈ [ m ] i \in[m] i ∈ [ m ] . The entanglement width of C C C is defined as
η ( C ) : = max 0 ≤ i ≤ m A ∈ f i n n [ τ ] η ( L ≤ i ∣ A ⟩ ∣ 0 ⟩ ⊗ a ( C ) ) . (5) \eta(C) := \max_{\substack{0 \leq i \leq m \\ A \in\mathrm{fin}_n[\tau]}} \eta\left(L_{\leq i}|A\rangle|0\rangle^{\otimes a(C)}\right). \tag*{(5)} η ( C ) := 0 ≤ i ≤ m A ∈ fin n [ τ ] max η ( L ≤ i ∣ A ⟩ ∣0 ⟩ ⊗ a ( C ) ) . (5)
That is, if η ( C ) ≤ η \eta(C) \leq\eta η ( C ) ≤ η , then when a classical structure ∣ A ⟩ |A\rangle ∣ A ⟩ (i.e., a computational basis state) is given as input, after every layer, the state of the circuit uses at most η \eta η -partite entanglement. States ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ with η ( ∣ ψ ⟩ ) = 1 \eta(|\psi\rangle) = 1 η ( ∣ ψ ⟩) = 1 are product states, and circuits C C C with η ( C ) = 1 \eta(C) = 1 η ( C ) = 1 operate (between layers) only on product states. The block partition may change between layers and between inputs. Including layer 0 gives width 1 to a circuit with no layers, since the initial state is a product state. The maximum in Definition 2.9 is taken over basis inputs. It does not impose a bound on computations starting from arbitrary quantum superpositions of structures.
Partial trace-based pebble games
A pebble records a constraint on the allowed relabellings of the input domain. In the classical game, Spoiler tries to expose a difference between two structures using a bounded number of such constraints, while Duplicator chooses compatible relabellings. In the quantum game, the comparison is made through the reduced density matrices on the qubits fixed by the current constraints. The number of pebbles counts domain elements associated with the considered constraints, whereas the partial trace acts on input qubits.
Denote the set of density matrices on H \mathcal{H} H by D ( H ) \mathrm{D}(\mathcal{H}) D ( H ) . If H = ( C 2 ) ⊗ X \mathcal{H} = (\mathbb{C}^{2})^{\otimes X} H = ( C 2 ) ⊗ X is composed of ∣ X ∣ |X| ∣ X ∣ qubits labelled by elements of a finite set X X X and S ⊆ X S \subseteq X S ⊆ X is nonempty, let Tr S \operatorname{Tr}_{S} Tr S denote the partial trace operation which “traces out” the qubits S S S . Additionally, let
Tr S ‾ = Tr X ∖ S : D ( ( C 2 ) ⊗ X ) → D ( ( C 2 ) ⊗ S ) (6) \operatorname{Tr}_{\overline{S}} = \operatorname{Tr}_{X\setminus S} : \mathrm{D}((\mathbb{C}^{2})^{\otimes X}) \to\mathrm{D}((\mathbb{C}^{2})^{\otimes S}) \tag*{(6)} Tr S = Tr X ∖ S : D (( C 2 ) ⊗ X ) → D (( C 2 ) ⊗ S ) (6)
denote the partial trace operation which “traces out” the other qubits, leaving only the qubits S S S . If x ∈ X x \in X x ∈ X is a single qubit, write Tr x \operatorname{Tr}_{x} Tr x for Tr { x } \operatorname{Tr}_{\{x\}} Tr { x } .
Definition 2.10 (Pebble set). Given a group Γ ≤ U ( H τ ) \Gamma\leq\mathrm{U}(\mathcal{H}_{\tau}) Γ ≤ U ( H τ ) , a pebble set P \mathcal{P} P for Γ \Gamma Γ is a set of subgroups of Γ \Gamma Γ , called pebble groups or simply pebbles and denoted Γ p ∈ P \Gamma_{p} \in\mathcal{P} Γ p ∈ P , obeying the following properties:
(a) P \mathcal{P} P is closed under conjugation by Γ \Gamma Γ : for every Γ p ∈ P \Gamma_{p} \in\mathcal{P} Γ p ∈ P and every U ∈ Γ U \in\Gamma U ∈ Γ , U Γ p U † ∈ P U\Gamma_{p}U^{\dagger} \in\mathcal{P} U Γ p U † ∈ P .
(b) Each pebble group Γ p ∈ P \Gamma_{p} \in\mathcal{P} Γ p ∈ P is a self-normalizing subgroup of Γ \Gamma Γ : for every U ∈ Γ U \in\Gamma U ∈ Γ , if U Γ p U † = Γ p U\Gamma_{p}U^{\dagger} = \Gamma_{p} U Γ p U † = Γ p then U ∈ Γ p U \in\Gamma_{p} U ∈ Γ p .
Write ⋂ P : = ⋂ Γ p ∈ P Γ p \bigcap\mathcal{P} := \bigcap_{\Gamma_{p}\in\mathcal{P}} \Gamma_{p} ⋂ P := ⋂ Γ p ∈ P Γ p for the intersection of the pebble groups in P \mathcal{P} P , which is just the group of symmetries respecting all the pebbles in P \mathcal{P} P . By convention, we set ⋂ ∅ : = Γ \bigcap\varnothing:= \Gamma ⋂ ∅ := Γ . We say that a permutation group G ≤ Sym n G \leq\operatorname{Sym}_{n} G ≤ Sym n has distinct stabilizers if for every a , b ∈ [ n ] a,b \in[n] a , b ∈ [ n ] with a ≠ b a \ne b a = b , we have Stab G ( a ) ≠ Stab G ( b ) \operatorname{Stab}_{G}(a) \ne\operatorname{Stab}_{G}(b) Stab G ( a ) = Stab G ( b ) .
Definition 2.11 (Classical pebble set). Suppose Γ G ≤ U ( H τ ) \Gamma_{G} \leq\mathrm{U}(\mathcal{H}_{\tau}) Γ G ≤ U ( H τ ) is the classical unitary group corresponding to a group G ≤ Sym n G \leq\operatorname{Sym}_{n} G ≤ Sym n which has distinct stabilizers, and let φ : G → Γ G \varphi: G \to\Gamma_{G} φ : G → Γ G be the isomorphism mapping σ ↦ U σ \sigma\mapsto U_{\sigma} σ ↦ U σ . The classical pebble set for Γ G \Gamma_{G} Γ G is
P G = { φ ( Stab G ( a ) ) : a ∈ [ n ] } . (7) \mathcal{P}_{G} = \{\varphi(\operatorname{Stab}_{G}(a)) : a \in[n]\}. \tag*{(7)} P G = { φ ( Stab G ( a )) : a ∈ [ n ]} . (7) That is, the classical pebble groups in P G \mathcal{P}_{G} P G are just the subgroups which fix each domain element. The condition that G G G has distinct stabilizers is sufficient to show that each pebble in P G \mathcal{P}_{G} P G is a self-normalizing subgroup of Γ G \Gamma_{G} Γ G : if φ ( Stab G ( a ) ) = U σ φ ( Stab G ( a ) ) U σ † \varphi(\operatorname{Stab}_{G}(a)) = U_{\sigma}\varphi(\operatorname{Stab}_{G}(a))U_{\sigma}^{\dagger} φ ( Stab G ( a )) = U σ φ ( Stab G ( a )) U σ † , then Stab G ( a ) = σ Stab G ( a ) σ − 1 = Stab G ( σ a ) \operatorname{Stab}_{G}(a) = \sigma\operatorname{Stab}_{G}(a)\sigma^{-1} = \operatorname{Stab}_{G}(\sigma a) Stab G ( a ) = σ Stab G ( a ) σ − 1 = Stab G ( σ a ) , so the distinct stabilizers property tells us that σ a = a \sigma a = a σ a = a , i.e. σ ∈ Stab G ( a ) \sigma\in\operatorname{Stab}_{G}(a) σ ∈ Stab G ( a ) .
For each qubit label ( i , n ⃗ ) ∈ Q τ (i,\vec{n}) \in Q^{\tau} ( i , n ) ∈ Q τ , write Stab Γ ( i , n ⃗ ) \operatorname{Stab}_{\Gamma}(i,\vec{n}) Stab Γ ( i , n ) for the subgroup of Γ \Gamma Γ which acts trivially on that qubit. In particular, if Γ G \Gamma_{G} Γ G is a classical unitary group and φ \varphi φ is the natural embedding of G G G into Γ G \Gamma_{G} Γ G , then
Stab Γ G ( i , n ⃗ ) = φ ( Stab G ( ( i , n ⃗ ) ) ) . \operatorname{Stab}_{\Gamma_{G}}(i,\vec{n}) = \varphi(\operatorname{Stab}_{G}((i,\vec{n}))). Stab Γ G ( i , n ) = φ ( Stab G (( i , n ))) . Definition 2.12 [10 ] . Let P ⊆ P \mathcal{P} \subseteq\mathcal{P} P ⊆ P be a set of pebbles. The lift of P \mathcal{P} P is the set of qubits
Q P τ = { ( i , n ⃗ ) ∈ Q τ : ⋂ P ≤ Stab Γ ( i , n ⃗ ) } . (8) Q^{\tau}_{\mathcal{P}} = \{(i,\vec{n}) \in Q^{\tau} : \bigcap\mathcal{P} \leq\operatorname{Stab}_{\Gamma}(i,\vec{n})\}. \tag*{(8)} Q P τ = {( i , n ) ∈ Q τ : ⋂ P ≤ Stab Γ ( i , n )} . (8) That is, Q P τ Q^{\tau}_{\mathcal{P}} Q P τ is the set of qubit labels which are pointwise stabilized by the pebbles. This definition of lift is similar to that given by Dawar and Wil-senach [10 ] .
Definition 2.13. A unitary U ∈ Γ U \in\Gamma U ∈ Γ is an ℓ \ell ℓ -partial trace-based partial isomorphism, abbreviated ℓ \ell ℓ -PT partial isomorphism, from ∣ A ⟩ |A\rangle ∣ A ⟩ to ∣ B ⟩ |B\rangle ∣ B ⟩ with respect to P ⊆ P \mathcal{P} \subseteq\mathcal{P} P ⊆ P if for every S ⊆ Q P τ S \subseteq Q^{\tau}_{\mathcal{P}} S ⊆ Q P τ with 1 ≤ ∣ S ∣ ≤ ℓ 1 \leq|S| \leq\ell 1 ≤ ∣ S ∣ ≤ ℓ we have
Tr S ‾ ( ∣ A ⟩ ⟨ A ∣ ) = Tr S ‾ ( U † ∣ B ⟩ ⟨ B ∣ U ) . (9) \operatorname{Tr}_{\overline{S}}(|A\rangle\langle A|) = \operatorname{Tr}_{\overline{S}}(U^{\dagger}|B\rangle\langle B|U). \tag*{(9)} Tr S ( ∣ A ⟩ ⟨ A ∣ ) = Tr S ( U † ∣ B ⟩ ⟨ B ∣ U ) . (9)
Definition 2.14. A unitary U ∈ Γ U \in\Gamma U ∈ Γ is a partial trace-based partial isomorphism , abbreviated P T PT P T partial isomorphism , from ∣ A ⟩ \lvert A\rangle ∣ A ⟩ to ∣ B ⟩ \lvert B\rangle ∣ B ⟩ with respect to P ⊆ P P \subseteq\mathcal{P} P ⊆ P if
Tr Q P ‾ ( ∣ A ⟩ ⟨ A ∣ ) = Tr Q P ‾ ( U † ∣ B ⟩ ⟨ B ∣ U ) . (10) \operatorname{Tr}_{\overline{Q_P}}(\lvert A\rangle\langle A\rvert)=\operatorname{Tr}_{\overline{Q_P}}(U^\dagger\lvert B\rangle\langle B\rvert U). \tag*{(10)} Tr Q P (∣ A ⟩ ⟨ A ∣) = Tr Q P ( U † ∣ B ⟩ ⟨ B ∣ U ) . (10)
Definition 2.15. The ( Γ , P , k ) (\Gamma,\mathcal{P},k) ( Γ , P , k ) -partial trace-based quantum pebble game , abbreviated as the ( Γ , P , k ) (\Gamma,\mathcal{P},k) ( Γ , P , k ) -P T PT P T quantum pebble game , on ∣ A ⟩ \lvert A\rangle ∣ A ⟩ and ∣ B ⟩ \lvert B\rangle ∣ B ⟩ is defined as follows. The state of the game consists of a subset of pebbles P ⊆ P P \subseteq\mathcal{P} P ⊆ P with ∣ P ∣ ≤ k \lvert P\rvert\leq k ∣ P ∣ ≤ k and a unitary U ∈ Γ U \in\Gamma U ∈ Γ . Initially, no pebbles are placed and U = I U=I U = I . Each round proceeds as follows.
Optionally, Spoiler removes a pebble from P P P . If ∣ P ∣ = k \lvert P\rvert=k ∣ P ∣ = k , Spoiler must remove a pebble.
Duplicator chooses a unitary V ∈ ⋂ P V \in\bigcap P V ∈ ⋂ P and sets U : = U V U:=UV U := U V .
Spoiler chooses a pebble from P ∖ P \mathcal{P}\setminus P P ∖ P and adds it to P P P .
Spoiler wins if U U U is not a PT partial isomorphism from ∣ A ⟩ \lvert A\rangle ∣ A ⟩ to ∣ B ⟩ \lvert B\rangle ∣ B ⟩ with respect to P P P . Otherwise, play continues, and Duplicator wins if it has a strategy to play forever. The ( Γ , P , k ) (\Gamma,\mathcal{P},k) ( Γ , P , k ) -ℓ \ell ℓ -P T PT P T quantum pebble game is defined identically with the notion of PT partial isomorphism replaced by ℓ \ell ℓ -PT partial isomorphism.
Clearly if Duplicator wins the ( Γ , P , k ) (\Gamma,\mathcal{P},k) ( Γ , P , k ) -PT quantum pebble game, then it also wins the ( Γ , P , k ) (\Gamma,\mathcal{P},k) ( Γ , P , k ) -ℓ \ell ℓ -PT quantum pebble game for every ℓ \ell ℓ . The PT quantum pebble game provides a simple and natural quantum generalization of Dawar and Wilsenach’s ( G , k ) (G,k) ( G , k ) -pebble game from [10 ] .
The lower-bound technique
The lower bound combines small supports with inputs that require many pebbles to distinguish. A support is a set of input vertices such that fixing those vertices fixes the gate or wire under consideration. The classical argument applies this idea to gates. For a quantum circuit, the reduced state of one wire need not determine the effect of a later gate, because that wire can be entangled with other wires. We instead use reduced density matrices on tuples of wires, with the entanglement width determining the tuple sizes needed for reconstruction.
There are three steps. First, bounds on circuit size give bounds on the orbits of wire tuples and hence on their support sizes. Second, reconstruction and the action of each commuting layer yield an indistinguishability theorem: if the required supports have size at most k k k , a circuit cannot distinguish inputs on which Duplicator wins with 2 k 2k 2 k pebbles. Third, the CFI construction supplies pairs that remain indistinguishable with linearly many pebbles. Since P C F I A l t \mathcal{P}^{\mathrm{Alt}}_{\mathrm{CFI}} P CFI Alt separates those pairs, any circuit computing it must violate the combined size and entanglement restrictions.
The conclusion of the indistinguishability theorem is equality of output probabilities. Thus the argument excludes any nonzero distinguishing bias on a hard pair whenever its hypotheses hold. The error bound 1 / 3 1/3 1/3 is the convention used to define computation of a property.
We apply essentially the same technique abstractly to tuples of distinct wires. Fix a set of wires W W W and ℓ ∈ Z + \ell\in\mathbb{Z}_{+} ℓ ∈ Z + and assume ∣ W ∣ ≥ ℓ \lvert W\rvert\geq\ell ∣ W ∣ ≥ ℓ , and define
W ℓ = { ( w 1 , … , w ℓ ) ∈ W ℓ : w 1 , … , w ℓ are all distinct } . W^{\ell}=\{(w_1,\ldots,w_{\ell})\in W^{\ell}:w_1,\ldots,w_{\ell}\text{ are all distinct}\}. W ℓ = {( w 1 , … , w ℓ ) ∈ W ℓ : w 1 , … , w ℓ are all distinct } .
Any group G G G acting on W W W , in particular Sym W \operatorname{Sym}_W Sym W , then also acts on W ℓ W^{\ell} W ℓ elementwise.
Fix a symmetry group G ≤ Sym n G \leq\operatorname{Sym}_n G ≤ Sym n and let C C C be a G G G -symmetric output quantum circuit of order n n n . Suppose C C C has wires W=X\mathbin{\mathaccent\cdot\cup} A , where X X X are the input wires and A A A are the ancillary wires, and let w o u t w_{\mathrm{out}} w out be its output wire. Let Aut ( C ) ≤ Sym W \operatorname{Aut}(C)\leq\operatorname{Sym}_W Aut ( C ) ≤ Sym W be the group of automorphisms of C C C , i.e., the group of permutations of the wires which map the input wires X X X to X X X , fix w o u t w_{\mathrm{out}} w out , and induce an automorphism of the circuit. Let In ( C ) = Stab Aut ( C ) ( X ) \operatorname{In}(C) = \operatorname{Stab}_{\operatorname{Aut}(C)}(X) In ( C ) = Stab Aut ( C ) ( X ) be the group of internal automorphisms of C C C , which are the automorphisms that pointwise fix each input wire x ∈ X x \in X x ∈ X . Observe that In ( C ) \operatorname{In}(C) In ( C ) is a normal subgroup of Aut ( C ) \operatorname{Aut}(C) Aut ( C ) .
An input permutation need not have a unique extension to the circuit wires. Any two extensions differ by an internal automorphism. Passing from wire tuples to their orbits under In ( C ) \operatorname{In}(C) In ( C ) makes the induced action independent of this choice. For each ℓ \ell ℓ -size tuple of distinct wires w ⃗ ∈ W ℓ \vec{w} \in W^\ell w ∈ W ℓ , define its orbit under In ( C ) \operatorname{In}(C) In ( C ) as
[ w ⃗ ] : = { π w ⃗ : π ∈ In ( C ) } , [\vec{w}] := \{\pi\vec{w} : \pi\in\operatorname{In}(C)\}, [ w ] := { π w : π ∈ In ( C )} ,
where we recall that Aut ( C ) \operatorname{Aut}(C) Aut ( C ) acts elementwise on tuples of wires. The collection of these orbits is denoted W ℓ / In ( C ) W^\ell/\operatorname{In}(C) W ℓ / In ( C ) . Observe that Aut ( C ) / In ( C ) \operatorname{Aut}(C)/\operatorname{In}(C) Aut ( C ) / In ( C ) , and hence G G G , acts on W ℓ / In ( C ) W^\ell/\operatorname{In}(C) W ℓ / In ( C ) as [ π ] [ w ⃗ ] : = [ π w ⃗ ] [\pi][\vec{w}] := [\pi\vec{w}] [ π ] [ w ] := [ π w ] , where [ π ] = π In ( C ) [\pi] = \pi\operatorname{In}(C) [ π ] = π In ( C ) .
Explicitly, the action of σ ∈ G \sigma\in G σ ∈ G takes [ w ⃗ ] [\vec{w}] [ w ] to [ π σ w ⃗ ] [\pi_\sigma\vec{w}] [ π σ w ] , where π σ \pi_\sigma π σ is an automorphism induced by σ \sigma σ . A support for [ w ⃗ ] [\vec{w}] [ w ] is a set of input vertices such that fixing those vertices fixes the entire orbit [ w ⃗ ] [\vec{w}] [ w ] . It need not fix each representative tuple individually. Small supports allow the relevant tuples to be described using few pebbles. Definition 4.4 gives the group-theoretic formulation.
We define a “directional partial trace” DTr w ⃗ ( ρ ) \operatorname{DTr}_{\vec{w}}(\rho) DTr w ( ρ ) of a density matrix ρ ∈ D ( H W ) \rho\in D(\mathcal{H}_W) ρ ∈ D ( H W ) with respect to a tuple w ⃗ ∈ W ℓ \vec{w} \in W^\ell w ∈ W ℓ which essentially traces out the qubits not in w ⃗ \vec{w} w and arranges the remaining qubits in the order specified by w ⃗ \vec{w} w . This ordering allows reduced states on different tuples of the same length to be compared as density matrices on the same tensor-product space. The reconstruction argument in § 4 relates matching collections of these reduced states to permutations of the underlying wires.
For the indistinguishability theorem, we prove the contrapositive: assume C [ ∣ A ⟩ ] ≠ C [ ∣ B ⟩ ] C[|A\rangle] \ne C[|B\rangle] C [ ∣ A ⟩] = C [ ∣ B ⟩] . We give a Spoiler strategy. Let the layers of C C C be represented by unitaries L 1 , … , L m L_1,\ldots,L_m L 1 , … , L m , let L ≤ i = L i L i − 1 ⋯ L 1 L_{\leq i} = L_iL_{i-1}\cdots L_1 L ≤ i = L i L i − 1 ⋯ L 1 , with L ≤ 0 = I L_{\leq0} = I L ≤ 0 = I , and let
ρ i A = L ≤ i ( ∣ A ⟩ ⟨ A ∣ ⊗ ∣ 0 ⟩ ⟨ 0 ∣ ⊗ A ) L ≤ i † \rho_i^A = L_{\leq i}\left(|A\rangle\langle A| \otimes|0\rangle\langle0|^{\otimes A}\right)L_{\leq i}^{\dagger} ρ i A = L ≤ i ( ∣ A ⟩ ⟨ A ∣ ⊗ ∣0 ⟩ ⟨ 0 ∣ ⊗ A ) L ≤ i †
ρ i B = L ≤ i ( ∣ B ⟩ ⟨ B ∣ ⊗ ∣ 0 ⟩ ⟨ 0 ∣ ⊗ A ) L ≤ i † . \rho_i^B = L_{\leq i}\left(|B\rangle\langle B| \otimes|0\rangle\langle0|^{\otimes A}\right)L_{\leq i}^{\dagger}. ρ i B = L ≤ i ( ∣ B ⟩ ⟨ B ∣ ⊗ ∣0 ⟩ ⟨ 0 ∣ ⊗ A ) L ≤ i † .
For each i i i from m m m to 0 0 0 , Spoiler plays to maintain the invariant that there is some w ⃗ i ∈ W c i \vec{w}_i \in W^{c_i} w i ∈ W c i for some c i ≤ ℓ c_i \leq\ell c i ≤ ℓ such that [ w ⃗ i ] [\vec{w}_i] [ w i ] is supported by the current set of pebbles P P P and for every automorphism π \pi π induced by the current σ ∈ G \sigma\in G σ ∈ G , we have
DTr w ⃗ i ( ρ i A ) ≠ DTr w ⃗ i ( U π † ρ i B U π ) . \operatorname{DTr}_{\vec{w}_i}(\rho_i^A) \ne\operatorname{DTr}_{\vec{w}_i}(U_\pi^\dagger\rho_i^B U_\pi). DTr w i ( ρ i A ) = DTr w i ( U π † ρ i B U π ) .
Different output probabilities provide the initial discrepancy on the output wire. The partition-symmetry argument transfers a discrepancy backwards through each original layer, using tuples of at most ℓ = η ( C ) \ell= \eta(C) ℓ = η ( C ) wires. Supports translate these tuples into pebble positions. At the initial layer, the remaining discrepancy contradicts the winning strategy of Duplicator on the encoded classical inputs. § 4 and § 5 contain the corresponding technical arguments.
Symmetric simulation without an entanglement restriction
We now give an overview of the proof technique for Theorem 1.4 , which shows that polynomial-time uniform families of symmetric quantum circuits without a restriction on entanglement width can compute every graph property in BQP \mathsf{P} P . To prove this, we simulate an arbitrary quantum algorithm which computes a graph property. The main idea is to satisfy the symmetry requirement by running the original algorithm on all orderings of the vertices in superposition. To do so, we create an auxiliary register which represents a map λ : [ n ] → { 0 , … , M − 1 } \lambda: [n] \to\{0,\ldots,M-1\} λ : [ n ] → { 0 , … , M − 1 } , where n n n is the number of vertices in the input graph and M M M is a power of two chosen to be large enough that such a map λ \lambda λ chosen uniformly at random is likely to be injective. We initialize the register in a uniform superposition of all such maps: 1 M n ∑ λ : [ n ] → { 0 , … , M − 1 } ∣ λ ⟩ \frac{1}{\sqrt{M^n}}\sum_{\lambda:[n]\to\{0,\ldots,M-1\}}|\lambda\rangle M n 1 ∑ λ : [ n ] → { 0 , … , M − 1 } ∣ λ ⟩ . A symmetric Boolean circuit sorts the vertices according to their values under λ \lambda λ and writes the input graph in the resulting order, provided these values are all distinct. Among the branches of the superposition where this condition holds, every ordering of the vertices occurs equally often.
Every permutation of the input vertices extends to a permutation of the circuit wires that fixes the output wires of the sorting gadget. We can apply the original quantum algorithm on these wires, with any additional workspace wires also fixed. The sorting gadget produces the input graph with its vertices reordered whenever λ \lambda λ is injective. Otherwise, the computation may give an incorrect answer. Since we retain the label register, the acceptance probability is the average over the choices of λ \lambda λ , so the additional error is at most the probability that λ \lambda λ is not injective. We first reduce the error of the original algorithm by a constant number of repetitions, leaving room for this additional error. Choosing M M M sufficiently large relative to n n n then ensures that the overall computation satisfies the required bounded-error guarantee.
The sorting gadget is expressed in terms of threshold gates, which compute whether the Hamming weight of the input is at least a fixed threshold t t t . We show that threshold gates have an efficient symmetric implementation using one-qubit and two-qubit gates. The construction first encodes the Hamming weight in the phases of a counter register, then applies an inverse quantum Fourier transform to recover its binary representation. We compare this value with t t t and uncompute the workspace while retaining the result of the comparison. The technical arguments are in Section 7.
This result shows that the classical exponential lower bound on the size of symmetric circuits computing the hard property does not directly extend to the quantum setting: indeed, Theorem 1.4 implies that P C F I A l t \mathcal{P}^{\mathrm{Alt}}_{\mathrm{CFI}} P CFI Alt can be computed by polynomial-size symmetric quantum circuits. A superpolynomial size lower bound for symmetric quantum circuits deciding this property therefore requires an additional restriction. Theorem 1.1 gives such a lower bound when entanglement width is restricted.
Symmetric simulation without entanglement
Theorem 1.4 shows that without a restriction on entanglement width, symmetric quantum circuits can compute every graph property in BQP. Theorem 1.5 shows that even without entanglement, they can compute every graph property definable in FPC. Here, the absence of entanglement means that the state is a product of single-qubit states at every layer boundary on computational-basis inputs (the condition of entanglement width being 1). Our proof uses Anderson and Dawar’s characterization of FPC in terms of classical symmetric circuits with threshold gates [1 ] . We simulate these circuits using one-qubit and two-qubit gates while preserving this product structure.
Theorem 2.16 [1 ] . A graph property is computed by a polynomial-time uniform family of symmetric classical circuits using threshold and NOT gates if and only if it is definable in FPC.
Hence, we show that symmetric quantum circuits without entanglement can efficiently simulate any symmetric classical circuit using threshold and NOT gates. Our threshold gate construction described above does not use entanglement if the input is in the computational basis, so this simply requires translating from the DAG-based classical circuit model to reversible circuits. A simple algorithm for doing so was given in [5 Prop. 1] . The technical discussion appears at the end of Section 7.
Symmetric implementation of QAOA
Finally, we outline the construction for Theorem 1.6. The input qubits store the equations of the MAX 3XOR instance. We use a separate set of qubits, one for each variable, to prepare the QAOA state. To implement each cost operation, we compute whether each equation is satisfied, apply the corresponding phase, and undo the computation. The mixer applies the same single-qubit operation to every assignment wire.
After the final round, we again compute which equations are satisfied. The symmetric threshold computation of Lemma 7.1 then records whether their number is at least t t t , without measuring the assignment. This uses the same counting construction as the preceding simulation results.
The product and parity wires follow the equation and variable labels under permutation. The counter, comparison, and output wires are fixed. The gates can be arranged into commuting layers preserved by these permutations, using only one-qubit and two-qubit gates. The output probability is therefore the probability that QAOA produces an assignment meeting the threshold. Appendix A gives the construction and gate count.
Discussion and open questions
One might wonder whether imposing sub-linear entanglement width is overly restrictive in the presence of permutation symmetry. Indeed, a well-known property of permutation-invariant pure states is that they are either fully separable or genuinely multipartite entangled [12 ] . However, this dichotomy does not apply to our computational model: vertex permutations may induce nontrivial permutations of the workspace qubits, allowing the circuit to maintain multiple entangled blocks that are themselves permuted by the symmetry group. It is not hard to construct examples that illustrate this.
In particular, symmetric quantum circuits of entanglement width at most n 1 − ε n^{1-\varepsilon} n 1 − ε need not be restricted to separable states or trivial quantum dynamics. They can generate and manipulate genuinely multipartite entanglement involving a polynomially growing number of qubits, while remaining equivariant under all vertex permutations. More generally, the restriction allows nontrivial quantum computations within entangled blocks, whose size may grow polynomially with n n n . Establishing lower bounds in this setting therefore requires exploiting the interplay between the symmetry of the computation and the limitations imposed on its entanglement structure, rather than either restriction in isolation.
Our results raise fundamental questions about the power of symmetric quantum computation, the role of entanglement in determining that power, and the extent to which it can be characterized by quantum pebble games.
Is linear entanglement width necessary? Corollary 1.2 rules out polynomial-size symmetric circuits of entanglement width o ( n / log n ) o(n/\log n) o ( n / log n ) for Q C F I A l t \mathcal{Q}_{\mathrm{CFI}}^{\mathrm{Alt}} Q CFI Alt . Can this bound be strengthened to linear width? More precisely, for each fixed d > 0 d > 0 d > 0 , does there exist c d > 0 c_d > 0 c d > 0 such that, for all sufficiently large Alt-CFI pairs on n n n vertices from § 6 , every symmetric circuit C C C with s ( C ) ≤ n d s(C) \le n^d s ( C ) ≤ n d and different acceptance probabilities on the two graphs reaches a state of entanglement width at least c d n c_d n c d n on each input?
Here we allow arbitrary ancillary qubits and do not require a unique extension of an input permutation to the circuit. In particular, internal automorphisms can permute many ancillary wires while fixing every input wire. Can this freedom reduce the entanglement needed to distinguish the hard pairs, or is linear width necessary even in its presence?
How does the quantum pebble game compare with Weisfeiler–Leman refinement?
On computational-basis encodings of graphs, our partial-trace game recovers the classical pebble game underlying the Weisfeiler–Leman hierarchy. How does this correspondence change when graphs are encoded as entangled quantum states? In particular, does comparing their reduced density matrices reveal distinctions that classical refinement misses, or conceal distinctions it detects, at comparable numbers of pebbles?
Consider the ℓ \ell ℓ -PT quantum pebble game of § 2.4 on general quantum inputs, with k k k pebbles. At each position, the game compares reduced density matrices on at most ℓ \ell ℓ qubits. Can this notion of indistinguishability be characterized by a refinement procedure analogous to classical Weisfeiler–Leman refinement? How does it relate to the distinguishing power of symmetric quantum circuits with restricted entanglement?
We conjecture that symmetric quantum circuits of any fixed entanglement width have the power of FPC. More precisely, fix an integer b ≥ 1 b \ge1 b ≥ 1 . Every graph property computed with bounded error by a polynomial-time uniform family ( C n ) n (C_n)_n ( C n ) n of polynomial-size symmetric quantum circuits with η ( C n ) ≤ b \eta(C_n) \le b η ( C n ) ≤ b is definable in FPC. The circuits use one-qubit and two-qubit gates, whose entries are uniformly approximable to r r r bits of precision in time polynomial in n n n and r r r . No further restriction is imposed on depth, and the partition into entangled blocks may depend on both the input and the layer.
Theorem 1.5 proves the converse already at width 1. The conjecture asserts that allowing entangled blocks of any fixed size does not enlarge the class of graph properties that can be computed. Together with Theorem 1.4 , this would identify a boundary between the computational power available with bounded and unbounded entanglement width: every graph property in BQP admits an efficient symmetric implementation, but deciding a property beyond FPC requires unbounded entanglement width.
Internal automorphisms and partition symmetry
Properties of internal automorphisms
We begin by characterizing the automorphisms of the circuit C C C in terms of G G G and In ( C ) \operatorname{In}(C) In ( C ) .
Proposition 4.1. Let G ≤ Sym n G \le\operatorname{Sym}_n G ≤ Sym n and let C C C be a Γ G \Gamma_G Γ G -symmetric output quantum circuit. There is an embedding χ : G → Aut ( C ) / In ( C ) \chi: G \to\operatorname{Aut}(C)/\operatorname{In}(C) χ : G → Aut ( C ) / In ( C ) given by σ ↦ [ π σ ] = π σ In ( C ) \sigma\mapsto[\pi_\sigma] = \pi_\sigma\operatorname{In}(C) σ ↦ [ π σ ] = π σ In ( C ) which maps σ ∈ G \sigma\in G σ ∈ G to exactly the set of automorphisms induced by σ \sigma σ , where π σ \pi_\sigma π σ is any automorphism induced by σ \sigma σ .
Proof. Any π ∈ Aut ( C ) \pi\in\operatorname{Aut}(C) π ∈ Aut ( C ) induced by σ \sigma σ acts identically to σ \sigma σ , and so π σ \pi_\sigma π σ , on the input wires X X X of C C C , so π σ − 1 π ∈ In ( C ) \pi_\sigma^{-1}\pi\in\operatorname{In}(C) π σ − 1 π ∈ In ( C ) and so π = π σ ( π σ − 1 π ) ∈ π σ In ( C ) \pi= \pi_\sigma(\pi_\sigma^{-1}\pi) \in\pi_\sigma\operatorname{In}(C) π = π σ ( π σ − 1 π ) ∈ π σ In ( C ) . Conversely, for every π ′ ∈ In ( C ) \pi' \in\operatorname{In}(C) π ′ ∈ In ( C ) , σ \sigma σ induces π σ π ′ \pi_\sigma\pi' π σ π ′ as it acts identically to π σ \pi_\sigma π σ on X X X . So σ \sigma σ induces exactly [ π σ ] [\pi_\sigma] [ π σ ] . For an embedding, suppose χ ( σ 1 ) = χ ( σ 2 ) \chi(\sigma_1) = \chi(\sigma_2) χ ( σ 1 ) = χ ( σ 2 ) : then σ 1 \sigma_1 σ 1 and σ 2 \sigma_2 σ 2 both induce some π ∈ Aut ( C ) \pi\in\operatorname{Aut}(C) π ∈ Aut ( C ) , so they must act the same on X X X . The action of G G G on X X X is faithful since X X X is nonempty, so σ 1 = σ 2 \sigma_1 = \sigma_2 σ 1 = σ 2 . □ \square □
This justifies that σ ∈ G \sigma\in G σ ∈ G acts on W ℓ / In ( C ) W^\ell/\operatorname{In}(C) W ℓ / In ( C ) by taking [ w ⃗ ] [\vec{w}] [ w ] to [ π σ w ⃗ ] [\pi_\sigma\vec{w}] [ π σ w ] . If H ≤ G H \le G H ≤ G , we write χ ( H ) = ⋃ σ ∈ H χ ( σ ) ≤ Aut ( C ) \chi(H) = \bigcup_{\sigma\in H}\chi(\sigma) \le\operatorname{Aut}(C) χ ( H ) = ⋃ σ ∈ H χ ( σ ) ≤ Aut ( C ) for the group of automorphisms induced by elements of H H H .
The crucial property of internal automorphisms is that the state of C C C between each layer is symmetric against each internal automorphism, regardless of the input state. Formally, we have the following.
Proposition 4.2. Let G ≤ Sym n G \le\operatorname{Sym}_n G ≤ Sym n and let C C C be a Γ G \Gamma_G Γ G -symmetric output quantum circuit with layers represented by unitaries L 1 , … , L m L_1,\ldots,L_m L 1 , … , L m . Let L ≤ 0 = I L_{\le0} = \mathbb{I} L ≤ 0 = I and L ≤ i = L i L i − 1 ⋯ L 1 L_{\le i} = L_iL_{i-1}\cdots L_1 L ≤ i = L i L i − 1 ⋯ L 1 for each i ∈ [ m ] i \in[m] i ∈ [ m ] . Let
∣ ψ ⟩ ∈ H τ |\psi\rangle\in\mathcal{H}_{\tau} ∣ ψ ⟩ ∈ H τ be any input state: then ∣ ψ i ⟩ = L ≤ i ∣ ψ ⟩ ∣ 0 ⟩ ⊗ a ( C ) |\psi_i\rangle= L_{\leq i}|\psi\rangle|0\rangle^{\otimes a(C)} ∣ ψ i ⟩ = L ≤ i ∣ ψ ⟩ ∣0 ⟩ ⊗ a ( C ) is the state of C C C after any layer 0 ≤ i ≤ m 0 \leq i \leq m 0 ≤ i ≤ m . For every internal automorphism π ∈ In ( C ) \pi\in\operatorname{In}(C) π ∈ In ( C ) , we have U π ∣ ψ i ⟩ = ∣ ψ i ⟩ U_{\pi}|\psi_i\rangle= |\psi_i\rangle U π ∣ ψ i ⟩ = ∣ ψ i ⟩ .
Proof. Since π \pi π is an automorphism of C C C , U π U_{\pi} U π commutes with every layer, and since π \pi π does not move any of the input wires, U π ∣ ψ ⟩ ∣ 0 ⟩ ⊗ a ( C ) = ∣ ψ ⟩ ∣ 0 ⟩ ⊗ a ( C ) U_{\pi}|\psi\rangle|0\rangle^{\otimes a(C)} = |\psi\rangle|0\rangle^{\otimes a(C)} U π ∣ ψ ⟩ ∣0 ⟩ ⊗ a ( C ) = ∣ ψ ⟩ ∣0 ⟩ ⊗ a ( C ) .
We work with equivalence classes of wires [ w ⃗ ] ∈ W ℓ / In ( C ) [\vec{w}] \in W^{\ell}/\operatorname{In}(C) [ w ] ∈ W ℓ / In ( C ) . This formalism has the following useful property:
Lemma 4.3. Let w ⃗ ∈ W ℓ \vec{w} \in W^{\ell} w ∈ W ℓ . Every σ ∈ G \sigma\in G σ ∈ G which stabilizes [ w ⃗ ] [\vec{w}] [ w ] induces some π ∈ Aut ( C ) \pi\in\operatorname{Aut}(C) π ∈ Aut ( C ) which stabilizes w ⃗ \vec{w} w .
Proof. In ( C ) \operatorname{In}(C) In ( C ) acts transitively on [ w ⃗ ] [\vec{w}] [ w ] by definition. So, suppose σ \sigma σ induces some π σ ∈ Aut ( C ) \pi_{\sigma} \in\operatorname{Aut}(C) π σ ∈ Aut ( C ) which maps w ⃗ \vec{w} w to v ⃗ ∈ [ w ⃗ ] \vec{v} \in[\vec{w}] v ∈ [ w ] . There is some π ′ ∈ In ( C ) \pi' \in\operatorname{In}(C) π ′ ∈ In ( C ) mapping v ⃗ \vec{v} v to w ⃗ \vec{w} w , and by Proposition 4.1 , σ \sigma σ also induces π ′ π σ \pi'\pi_{\sigma} π ′ π σ .
Support and support theorem
Our lower bound technique, like that of Dawar and Wilsenach, relies on the notion of support and a support theorem which translates bounds on the size of orbits of circuit elements into bounds on their support size. In our setting, the circuit elements under consideration are equivalence classes of tuples of wires [ w ⃗ ] ∈ W ℓ / In ( C ) [\vec{w}] \in W^{\ell}/\operatorname{In}(C) [ w ] ∈ W ℓ / In ( C ) , so we generalize the corresponding definitions as follows. We identify G G G with Γ G \Gamma_G Γ G through σ ↦ U σ \sigma\mapsto U_{\sigma} σ ↦ U σ .
Definition 4.4. A set of pebbles P ⊆ P P \subseteq\mathcal{P} P ⊆ P supports an orbit [ w ⃗ ] ∈ W ℓ / In ( C ) [\vec{w}] \in W^{\ell}/\operatorname{In}(C) [ w ] ∈ W ℓ / In ( C ) if ⋂ P ≤ Stab G ( [ w ⃗ ] ) \bigcap P \leq\operatorname{Stab}_{G}([\vec{w}]) ⋂ P ≤ Stab G ([ w ]) .
Definition 4.5. Let min-supp ( [ w ⃗ ] ) \operatorname{min\text{-}supp}([\vec{w}]) min - supp ([ w ]) be the size of the smallest set of pebbles P ⊆ P P \subseteq\mathcal{P} P ⊆ P which supports [ w ⃗ ] [\vec{w}] [ w ] . Let
max-supp ℓ ( C ) : = max [ w ⃗ ] ∈ W ℓ / In ( C ) min-supp ( [ w ⃗ ] ) . (11) \operatorname{max\text{-}supp}_{\ell}(C) := \max_{[\vec{w}] \in W^{\ell}/\operatorname{In}(C)} \operatorname{min\text{-}supp}([\vec{w}]). \tag*{(11)} max - supp ℓ ( C ) := [ w ] ∈ W ℓ / In ( C ) max min - supp ([ w ]) . (11)
Definition 4.6. Let
max-orbit ℓ ( C ) : = max [ w ⃗ ] ∈ W ℓ / In ( C ) ∣ Orb Aut ( C ) / In ( C ) ( [ w ⃗ ] ) ∣ . (12) \operatorname{max\text{-}orbit}_{\ell}(C) := \max_{[\vec{w}] \in W^{\ell}/\operatorname{In}(C)} \left|\operatorname{Orb}_{\operatorname{Aut}(C)/\operatorname{In}(C)}([\vec{w}])\right|. \tag*{(12)} max - orbit ℓ ( C ) := [ w ] ∈ W ℓ / In ( C ) max Orb Aut ( C ) / In ( C ) ([ w ]) . (12)
As in Dawar and Wilsenach’s technique [10 ] , our support theorem is based on the following group-theoretic lemma.
Lemma 4.7 [8 Thm. 5.2B] . Suppose that n > 8 n > 8 n > 8 is an integer, and let k k k be an integer such that 1 ≤ k ≤ n / 4 1 \leq k \leq n/4 1 ≤ k ≤ n /4 . Suppose that H ≤ Alt n H \leq\operatorname{Alt}_n H ≤ Alt n has index [ Alt n : H ] < ( n k ) [\operatorname{Alt}_n : H] < \binom{n}{k} [ Alt n : H ] < ( k n ) . There exists some S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] with ∣ S ∣ < k |S| < k ∣ S ∣ < k such that Stab Alt n ( S ) ≤ H \operatorname{Stab}_{\operatorname{Alt}_n}(S) \leq H Stab Alt n ( S ) ≤ H .
Our support theorem is below. It gives an explicitly quantitative rather than asymptotic bound on the parameters defined above, but otherwise closely follows the proof of Dawar and Wilsenach’s support theorem [10 Thm. 4.11] .
Theorem 4.8 (Quantum support theorem). Let ( C n ) n (C_n)_n ( C n ) n be a family of Γ Alt n \Gamma_{\operatorname{Alt}_n} Γ Alt n -symmetric output quantum circuits and let ℓ ∈ Z + \ell\in\mathbb{Z}_{+} ℓ ∈ Z + . For all n > 8 n > 8 n > 8 , if max-orbit ℓ ( C n ) ≤ 2 n / 4 − 1 \operatorname{max\text{-}orbit}_{\ell}(C_n) \leq2^{n/4-1} max - orbit ℓ ( C n ) ≤ 2 n /4 − 1 , then max-supp ℓ ( C n ) ≤ log 2 max-orbit ℓ ( C n ) \operatorname{max\text{-}supp}_{\ell}(C_n) \leq\log_2 \operatorname{max\text{-}orbit}_{\ell}(C_n) max - supp ℓ ( C n ) ≤ log 2 max - orbit ℓ ( C n ) .
Proof. For brevity, write b ( n ) = max-orbit ℓ ( C n ) b(n)=\operatorname{max\text{-}orbit}_{\ell}(\mathcal{C}_n) b ( n ) = max - orbit ℓ ( C n ) . Let k k k be the smallest positive integer such that b ( n ) < ( n k ) b(n)<\binom{n}{k} b ( n ) < ( k n ) : we have ( n k − 1 ) ≤ b ( n ) < ( n k ) \binom{n}{k-1}\le b(n)<\binom{n}{k} ( k − 1 n ) ≤ b ( n ) < ( k n ) . Observe that k ≤ n / 2 k\le n/2 k ≤ n /2 , since otherwise ( n k − 1 ) ≥ ( n k ) \binom{n}{k-1}\ge\binom{n}{k} ( k − 1 n ) ≥ ( k n ) . Since ( n m ) ≥ ( n / m m ) \binom{n}{m}\ge\binom{n/m}{m} ( m n ) ≥ ( m n / m ) whenever 1 ≤ m ≤ n 1\le m\le n 1 ≤ m ≤ n , if k ≥ 2 k\ge2 k ≥ 2 , then
b ( n ) ≥ ( n k − 1 ) ≥ ( n k − 1 ) k − 1 ≥ 2 k − 1 . b(n)\ge\binom{n}{k-1}\ge\left(\frac{n}{k-1}\right)^{k-1}\ge2^{k-1}. b ( n ) ≥ ( k − 1 n ) ≥ ( k − 1 n ) k − 1 ≥ 2 k − 1 .
If k = 1 k=1 k = 1 , we also have b ( n ) ≥ 2 k − 1 = 1 b(n)\ge2^{k-1}=1 b ( n ) ≥ 2 k − 1 = 1 automatically. Hence k ≤ log 2 b ( n ) + 1 k\le\log_2 b(n)+1 k ≤ log 2 b ( n ) + 1 . By the hypothesis, k ≤ n / 4 k\le n/4 k ≤ n /4 .
For every [ w ⃗ ] ∈ W ℓ / In ( C ) [\vec{w}]\in W^\ell/\operatorname{In}(\mathcal{C}) [ w ] ∈ W ℓ / In ( C ) , we have ∣ Orb Aut ( C n ) / In ( C n ) ( [ w ⃗ ] ) ∣ < ( n k ) \left|\operatorname{Orb}_{\operatorname{Aut}(\mathcal{C}_n)/\operatorname{In}(\mathcal{C}_n)}([\vec{w}])\right|<\binom{n}{k} Orb Aut ( C n ) / In ( C n ) ([ w ]) < ( k n ) , and so since Alt n \operatorname{Alt}_n Alt n embeds into Aut ( C n ) / In ( C n ) \operatorname{Aut}(\mathcal{C}_n)/\operatorname{In}(\mathcal{C}_n) Aut ( C n ) / In ( C n ) , ∣ Orb Alt n ( [ w ⃗ ] ) ∣ < ( n k ) \left|\operatorname{Orb}_{\operatorname{Alt}_n}([\vec{w}])\right|<\binom{n}{k} ∣ Orb Alt n ([ w ]) ∣ < ( k n ) . By the orbit–stabilizer theorem, then, [ Alt n : Stab Alt n ( [ w ⃗ ] ) ] < ( n k ) [\operatorname{Alt}_n:\operatorname{Stab}_{\operatorname{Alt}_n}([\vec{w}])]<\binom{n}{k} [ Alt n : Stab Alt n ([ w ])] < ( k n ) , so by Lemma 4.7, there is some S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] with ∣ S ∣ < k |S|<k ∣ S ∣ < k such that Stab Alt n ( S ) ≤ Stab Alt n ( [ w ⃗ ] ) \operatorname{Stab}_{\operatorname{Alt}_n}(S)\le\operatorname{Stab}_{\operatorname{Alt}_n}([\vec{w}]) Stab Alt n ( S ) ≤ Stab Alt n ([ w ]) . Hence the set of pebbles P = { Stab Alt n ( s ) : s ∈ S } ⊆ P Alt n P=\{\operatorname{Stab}_{\operatorname{Alt}_n}(s):s\in S\}\subseteq\mathcal{P}_{\operatorname{Alt}_n} P = { Stab Alt n ( s ) : s ∈ S } ⊆ P Alt n supports [ w ⃗ ] [\vec{w}] [ w ] and has size less than k ≤ log 2 b ( n ) + 1 k\le\log_2 b(n)+1 k ≤ log 2 b ( n ) + 1 . So max-supp ℓ ( C n ) ≤ log 2 b ( n ) \operatorname{max\text{-}supp}_{\ell}(\mathcal{C}_n)\le\log_2 b(n) max - supp ℓ ( C n ) ≤ log 2 b ( n ) .
The ℓ \ell ℓ -part function and partition symmetry
The directional partial trace is formally defined as follows. Fix some total order ≤ \le ≤ on W W W and view H W = ( C 2 ) ⊗ W \mathcal{H}_W=(\mathbb{C}^2)^{\otimes W} H W = ( C 2 ) ⊗ W . For each S ⊆ W S\subseteq W S ⊆ W with ∣ S ∣ = ℓ |S|=\ell ∣ S ∣ = ℓ , we view Tr S \operatorname{Tr}_S Tr S as a function D ( H W ) → D ( ( C 2 ) ⊗ ℓ ) \mathrm{D}(\mathcal{H}_W)\to\mathrm{D}((\mathbb{C}^2)^{\otimes\ell}) D ( H W ) → D (( C 2 ) ⊗ ℓ ) , where for each ρ ∈ D ( H W ) \rho\in\mathrm{D}(\mathcal{H}_W) ρ ∈ D ( H W ) , the qubits of Tr S ( ρ ) \operatorname{Tr}_S(\rho) Tr S ( ρ ) are indexed 1 , … , ℓ 1,\ldots,\ell 1 , … , ℓ and correspond to the qubits of ρ \rho ρ indexed by the wires S S S arranged in ascending order according to ≤ \le ≤ .
Definition 4.9. Let w ⃗ = ( w 1 , … , w ℓ ) ∈ W ℓ \vec{w}=(w_1,\ldots,w_\ell)\in W^\ell w = ( w 1 , … , w ℓ ) ∈ W ℓ and ρ ∈ D ( H W ) \rho\in\mathrm{D}(\mathcal{H}_W) ρ ∈ D ( H W ) . Let π ∈ Sym ℓ \pi\in\operatorname{Sym}_\ell π ∈ Sym ℓ be the unique permutation such that ( w π ( 1 ) , … , w π ( ℓ ) ) (w_{\pi(1)},\ldots,w_{\pi(\ell)}) ( w π ( 1 ) , … , w π ( ℓ ) ) is in ascending order according to ≤ \le ≤ . Let S = { w 1 , … , w ℓ } S=\{w_1,\ldots,w_\ell\} S = { w 1 , … , w ℓ } . The directional partial trace of ρ \rho ρ with respect to w ⃗ \vec{w} w is
DTr w ⃗ ( ρ ) : = U π Tr S ( ρ ) U π † . (13) \operatorname{DTr}_{\vec{w}}(\rho):=U_\pi\operatorname{Tr}_S(\rho)U_\pi^{\dagger}. \tag*{(13)} DTr w ( ρ ) := U π Tr S ( ρ ) U π † . (13)
The i i i th qubit of DTr w ⃗ ( ρ ) \operatorname{DTr}_{\vec{w}}(\rho) DTr w ( ρ ) corresponds to the w i w_i w i qubit of ρ \rho ρ , and in particular does not depend on the total order chosen. Observe that if π ∈ Sym W \pi\in\operatorname{Sym}_W π ∈ Sym W acts on W ℓ W^\ell W ℓ elementwise, then
DTr π w ⃗ ( ρ ) = DTr w ⃗ ( U π † ρ U π ) . (14) \operatorname{DTr}_{\pi\vec{w}}(\rho)=\operatorname{DTr}_{\vec{w}}(U_\pi^\dagger\rho U_\pi). \tag*{(14)} DTr π w ( ρ ) = DTr w ( U π † ρ U π ) . (14)
In our lower bound technique, we look at ℓ \ell ℓ wires of the circuit at a time. This notion is captured via the ℓ \ell ℓ -part function, which is the central piece of data used in our argument.
Definition 4.10. For every density matrix ρ ∈ D ( H W ) \rho\in\mathrm{D}(\mathcal{H}_W) ρ ∈ D ( H W ) and ℓ ∈ Z + \ell\in\mathbb{Z}_+ ℓ ∈ Z + , its ℓ \ell ℓ -part function f ρ : W ℓ → D ( ( C 2 ) ⊗ ℓ ) f_\rho:W^\ell\to\mathrm{D}((\mathbb{C}^2)^{\otimes\ell}) f ρ : W ℓ → D (( C 2 ) ⊗ ℓ ) is defined as
f ρ ( w ⃗ ) = DTr w ⃗ ( ρ ) . f_\rho(\vec{w})=\operatorname{DTr}_{\vec{w}}(\rho). f ρ ( w ) = DTr w ( ρ ) .
For S ⊆ W ℓ S\subseteq W^\ell S ⊆ W ℓ , write f ρ S : S → D ( ( C 2 ) ⊗ ℓ ) f_\rho^S:S\to\mathrm{D}((\mathbb{C}^2)^{\otimes\ell}) f ρ S : S → D (( C 2 ) ⊗ ℓ ) for the restriction of f ρ f_\rho f ρ to the domain S S S .
By equation (4.4), observe that for each π ∈ Sym W \pi\in\operatorname{Sym}_W π ∈ Sym W which setwise fixes S S S ,
f U π † ρ U π S = f ρ S ∘ π . (15) f_{U_\pi^\dagger\rho U_\pi}^S=f_\rho^S\circ\pi. \tag*{(15)} f U π † ρ U π S = f ρ S ∘ π . (15)
Furthermore, Proposition 4.2 implies that if ρ \rho ρ is a pure state occurring between layers in C \mathcal{C} C given a computational-basis input,
f ρ ∘ π = f ρ for all π ∈ In ( C ) . (16) f_\rho\circ\pi=f_\rho\quad\text{for all }\pi\in\operatorname{In}(\mathcal{C}). \tag*{(16)} f ρ ∘ π = f ρ for all π ∈ In ( C ) . (16)
Our indistinguishability argument uses a technical property we call ℓ \ell ℓ -partition symmetry, which broadly states that the reduced state of the circuit on a tuple of wires w ⃗ \vec{w} w after a layer can be determined by the ℓ \ell ℓ -part function of the state before the layer up to a group of symmetries with particularly nice structure. Formally, we have the following. If ( T i ) i (T_i)_i ( T i ) i is a partition of W ℓ W^\ell W ℓ , we denote by ∏ i Sym T i \prod_i \operatorname{Sym}_{T_i} ∏ i Sym T i the subgroup of Sym W ℓ \operatorname{Sym}_{W^\ell} Sym W ℓ whose permutations do not move elements across partition boundaries. We consider Aut ( C ) \operatorname{Aut}(C) Aut ( C ) as a subgroup of Sym W ℓ \operatorname{Sym}_{W^\ell} Sym W ℓ through its elementwise action on W ℓ W^\ell W ℓ .
Definition 4.11. Let C C C be a Γ G \Gamma_G Γ G -symmetric output quantum circuit and let L L L represent one of its layers. L L L has ℓ \ell ℓ -partition symmetry if for every w ⃗ ∈ W ℓ \vec{w} \in W^\ell w ∈ W ℓ , there exists a partition ( T i ) i (T_i)_i ( T i ) i of W ℓ W^\ell W ℓ such that Stab Aut ( C ) ( w ⃗ ) ≤ ∏ i Sym T i \operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) \le\prod_i \operatorname{Sym}_{T_i} Stab Aut ( C ) ( w ) ≤ ∏ i Sym T i and for every ρ 1 , ρ 2 ∈ D ( H W ) \rho_1,\rho_2 \in\mathcal{D}(\mathcal{H}_W) ρ 1 , ρ 2 ∈ D ( H W ) representing pure states with entanglement width at most ℓ \ell ℓ , if f ρ 1 ∘ α = f ρ 2 f_{\rho_1} \circ\alpha= f_{\rho_2} f ρ 1 ∘ α = f ρ 2 for some α ∈ ∏ i Sym T i \alpha\in\prod_i \operatorname{Sym}_{T_i} α ∈ ∏ i Sym T i , then DTr w ⃗ ( L ρ 1 L † ) = DTr w ⃗ ( L ρ 2 L † ) \operatorname{DTr}_{\vec{w}}(L\rho_1L^\dagger) = \operatorname{DTr}_{\vec{w}}(L\rho_2L^\dagger) DTr w ( L ρ 1 L † ) = DTr w ( L ρ 2 L † ) . C C C has ℓ \ell ℓ -partition symmetry if the unitaries representing its layers all do.
In the indistinguishability argument, we use this property to translate an inequality of states on up to ℓ \ell ℓ wires after a layer to an inequality of ℓ \ell ℓ -part functions up to every symmetry α ∈ ∏ i Sym T i \alpha\in\prod_i \operatorname{Sym}_{T_i} α ∈ ∏ i Sym T i before the layer. The remainder of the indistinguishability argument then places pebbles on the support of the orbit [ w ⃗ ′ ] [\vec{w}^{\prime}] [ w ′ ] of a new tuple of wires w ⃗ ′ \vec{w}^{\prime} w ′ in order to restore an explicit inequality of states on those wires. The fact that the inequality of ℓ \ell ℓ -part functions holds up to a large group of symmetries α \alpha α is used to maintain this inequality and the progress made so far no matter which unitary Duplicator chooses.
For the argument to work, it is important that α \alpha α comes from a group with the “partition-symmetric” structure of ∏ i Sym T i \prod_i \operatorname{Sym}_{T_i} ∏ i Sym T i (i.e., the group contains all symmetries respecting the partition ( T i ) i (T_i)_i ( T i ) i ). Our technique therefore applies to circuits for which we can prove ℓ \ell ℓ -partition symmetry. In our case, we take ℓ \ell ℓ equal to the entanglement width η ( C ) \eta(C) η ( C ) of the circuit.
Theorem 4.12. Let G ≤ Sym n G \le\operatorname{Sym}_n G ≤ Sym n . Every Γ G \Gamma_G Γ G -symmetric output quantum circuit C C C using only 1-qubit and 2-qubit gates has η ( C ) \eta(C) η ( C ) -partition symmetry.
Proof. Let η = η ( C ) \eta= \eta(C) η = η ( C ) . Suppose C C C has wires W W W , and observe that η ≤ ∣ W ∣ \eta\le|W| η ≤ ∣ W ∣ . Let w ⃗ ∈ W η \vec{w} \in W^\eta w ∈ W η . Let L \mathcal{L} L be a layer of $C represented by L L L , and suppose it consists of the orbits under Aut ( C ) \operatorname{Aut}(C) Aut ( C ) of the applications of some 1-qubit and 2-qubit unitaries U 1 , … , U k U_1,\ldots,U_k U 1 , … , U k . We define an equivalence relation ≈ \approx ≈ on W W W which expresses that two wires act the same on w ⃗ \vec{w} w in L \mathcal{L} L .
We define ≈ \approx ≈ using a sequence of equivalence relations ( ≈ i ) i (\approx_i)_i ( ≈ i ) i , one for each gate U i U_i U i (where i ∈ [ k ] i \in[k] i ∈ [ k ] ). Let w 1 , w 2 ∈ W w_1,w_2 \in W w 1 , w 2 ∈ W . If U i U_i U i is a 1-qubit gate, suppose it applies to the wires W U i ⊆ W W_{U_i} \subseteq W W U i ⊆ W in L \mathcal{L} L . Let w 1 ≈ i w 2 w_1 \approx_i w_2 w 1 ≈ i w 2 iff w 1 w_1 w 1 and w 2 w_2 w 2 agree on membership in W U i W_{U_i} W U i .
If U i U_i U i is a symmetric 2-qubit gate, then for each w ∈ w ⃗ w \in\vec{w} w ∈ w and each v ∈ W v \in W v ∈ W , let c w ( v ) c_w(v) c w ( v ) be the number of gates U i U_i U i in L \mathcal{L} L on the wires w w w and v v v . Let w 1 ≈ i w 2 w_1 \approx_i w_2 w 1 ≈ i w 2 iff c w ( w 1 ) = c w ( w 2 ) c_w(w_1)=c_w(w_2) c w ( w 1 ) = c w ( w 2 ) for all w ∈ w ⃗ w \in\vec{w} w ∈ w .
If U i U_i U i is an asymmetric 2-qubit gate, then for each w ∈ w ⃗ w \in\vec{w} w ∈ w and v ∈ W v \in W v ∈ W , let c w 1 ( v ) c_w^1(v) c w 1 ( v ) be the number of gates U i U_i U i in L \mathcal{L} L on wires ( v , w ) (v,w) ( v , w ) and let c w 2 ( v ) c_w^2(v) c w 2 ( v ) be the number of such gates on wires ( w , v ) (w,v) ( w , v ) . Let w 1 ≈ i w 2 w_1 \approx_i w_2 w 1 ≈ i w 2 if c w 1 ( w 1 ) = c w 1 ( w 2 ) c_w^1(w_1)=c_w^1(w_2) c w 1 ( w 1 ) = c w 1 ( w 2 ) and c w 2 ( w 1 ) = c w 2 ( w 2 ) c_w^2(w_1)=c_w^2(w_2) c w 2 ( w 1 ) = c w 2 ( w 2 ) for all w ∈ w ⃗ w \in\vec{w} w ∈ w .
Finally, define ≈ \approx ≈ as follows: If w 1 ∈ w ⃗ w_1 \in\vec{w} w 1 ∈ w or w 2 ∈ w ⃗ w_2 \in\vec{w} w 2 ∈ w , then w 1 ≈ w 2 w_1 \approx w_2 w 1 ≈ w 2 iff w 1 = w 2 w_1=w_2 w 1 = w 2 . Otherwise, w 1 ≈ w 2 w_1 \approx w_2 w 1 ≈ w 2 iff w 1 ≈ i w 2 w_1 \approx_i w_2 w 1 ≈ i w 2 for all i ∈ [ k ] i \in[k] i ∈ [ k ] .
Let ( E i ) i (E_i)_i ( E i ) i be the equivalence classes of W W W under ≈ \approx ≈ . Lift ≈ \approx ≈ to an equivalence relation on W η W^\eta W η elementwise: if w ⃗ 1 = ( w 1 , … , w η ) , w ⃗ 2 = ( w 1 ′ , … , w η ′ ) ∈ W η \vec{w}_1=(w_1,\ldots,w_\eta),\vec{w}_2=(w'_1,\ldots,w'_\eta)\in W^\eta w 1 = ( w 1 , … , w η ) , w 2 = ( w 1 ′ , … , w η ′ ) ∈ W η , let w ⃗ 1 ≈ w ⃗ 2 \vec{w}_1\approx\vec{w}_2 w 1 ≈ w 2 iff w i ≈ w i ′ w_i\approx w'_i w i ≈ w i ′ for all i i i . By the construction of ≈ \approx ≈ , every automorphism π ∈ Aut ( C ) \pi\in\operatorname{Aut}(C) π ∈ Aut ( C ) which stabilizes w ⃗ \vec{w} w maps each w ∈ W w \in W w ∈ W to π w ≈ w \pi w\approx w π w ≈ w . Hence, let ( T i ) i (T_i)_i ( T i ) i be the equivalence classes of W η W^\eta W η under ≈ \approx ≈ : then Stab Aut ( C ) ( w ⃗ ) ≤ ∏ i Sym T i \operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) \le\prod_i \operatorname{Sym}_{T_i} Stab Aut ( C ) ( w ) ≤ ∏ i Sym T i .
Next, I make the following claim.
Claim 4.13. Let ρ 1 , ρ 2 ∈ D ( H W ) \rho_1,\rho_2 \in\mathcal{D}(\mathcal{H}_W) ρ 1 , ρ 2 ∈ D ( H W ) represent pure states with entanglement width at most η \eta η . If there is some α ∈ ∏ i Sym T i \alpha\in\prod_i \operatorname{Sym}_{T_i} α ∈ ∏ i Sym T i (acting on W η W^\eta W η ) such that f ρ 1 ∘ α = f ρ 2 f_{\rho_1} \circ\alpha= f_{\rho_2} f ρ 1 ∘ α = f ρ 2 , then there is some β ∈ ∏ i Sym E i \beta\in\prod_i \operatorname{Sym}_{E_i} β ∈ ∏ i Sym E i (acting on W W W ) such that U β ρ 1 U β † = ρ 2 U_\beta\rho_1 U_\beta^\dagger=\rho_2 U β ρ 1 U β † = ρ 2 . That is, I claim that if f ρ 1 f_{\rho_1} f ρ 1 and f ρ 2 f_{\rho_2} f ρ 2 are related by a suitable permutation of the set of tuples W η W^\eta W η , then ρ 1 \rho_1 ρ 1 and ρ 2 \rho_2 ρ 2 are related by a suitable permutation of the wires . This claim gives us η \eta η -partition symmetry as follows: Let ρ 1 , ρ 2 \rho_1,\rho_2 ρ 1 , ρ 2 as above and assume f ρ 1 ∘ α = f ρ 2 f_{\rho_1}\circ\alpha=f_{\rho_2} f ρ 1 ∘ α = f ρ 2 for some α ∈ ∏ i Sym T i \alpha\in\prod_i\operatorname{Sym}_{T_i} α ∈ ∏ i Sym T i : then U β ρ 1 U β † = ρ 2 U_\beta\rho_1U_\beta^\dagger=\rho_2 U β ρ 1 U β † = ρ 2 for some β ∈ ∏ i Sym E i \beta\in\prod_i\operatorname{Sym}_{E_i} β ∈ ∏ i Sym E i . Since all the gates in L \mathcal{L} L commute, divide L \mathcal{L} L into the set of gates L 1 \mathcal{L}_1 L 1 which act on at least one of the wires in w ⃗ \vec{w} w and the set of gates L 2 \mathcal{L}_2 L 2 which do not, and consider the gates in L 2 \mathcal{L}_2 L 2 to come after those in L 1 \mathcal{L}_1 L 1 . Represent these sets of gates by unitaries L 1 L_1 L 1 and L 2 L_2 L 2 respectively. By construction, every β ∈ ∏ i Sym E i \beta\in\prod_i\operatorname{Sym}_{E_i} β ∈ ∏ i Sym E i does not move any w ∈ w ⃗ w\in\vec{w} w ∈ w and is an automorphism of L 1 \mathcal{L}_1 L 1 , so U β U_\beta U β commutes with L 1 L_1 L 1 , and by the no-communication theorem, L 2 L_2 L 2 cannot affect the partial trace to w ⃗ \vec{w} w of the final state. Hence we have
DTr w ⃗ ( L ρ 2 L † ) = DTr w ⃗ ( L 2 L 1 U β ρ 1 U β † L 1 † L 2 † ) = DTr w ⃗ ( U β L 1 ρ 1 L 1 † U β † ) = DTr w ⃗ ( L 1 ρ 1 L 1 † ) = DTr w ⃗ ( L 2 L 1 ρ 1 L 1 † L 2 † ) = DTr w ⃗ ( L ρ 1 L † ) \begin{aligned}
\operatorname{DTr}_{\vec{w}}(L\rho_2L^\dagger)=\operatorname{DTr}_{\vec{w}}(L_2L_1U_\beta\rho_1U_\beta^\dagger L_1^\dagger L_2^\dagger)=\operatorname{DTr}_{\vec{w}}(U_\beta L_1\rho_1L_1^\dagger U_\beta^\dagger)=\operatorname{DTr}_{\vec{w}}(L_1\rho_1L_1^\dagger) \\
&=\operatorname{DTr}_{\vec{w}}(L_2L_1\rho_1L_1^\dagger L_2^\dagger)=\operatorname{DTr}_{\vec{w}}(L\rho_1L^\dagger)
\end{aligned} DTr w ( L ρ 2 L † ) = DTr w ( L 2 L 1 U β ρ 1 U β † L 1 † L 2 † ) = DTr w ( U β L 1 ρ 1 L 1 † U β † ) = DTr w ( L 1 ρ 1 L 1 † ) = DTr w ( L 2 L 1 ρ 1 L 1 † L 2 † ) = DTr w ( L ρ 1 L † )
as required.
Proof of Claim 4.13. Let n = ∣ W ∣ n=|W| n = ∣ W ∣ and let ρ 1 = ∣ ψ ⟩ ⟨ ψ ∣ \rho_1=|\psi\rangle\langle\psi| ρ 1 = ∣ ψ ⟩ ⟨ ψ ∣ and ρ 2 = ∣ ϕ ⟩ ⟨ ϕ ∣ \rho_2=|\phi\rangle\langle\phi| ρ 2 = ∣ ϕ ⟩ ⟨ ϕ ∣ . Then ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ and ∣ ϕ ⟩ |\phi\rangle ∣ ϕ ⟩ have entanglement width at most η \eta η , so let ∣ ψ ⟩ = ∣ ψ 1 ⟩ ⊗ ⋯ ⊗ ∣ ψ r ⟩ |\psi\rangle=|\psi_1\rangle\otimes\cdots\otimes|\psi_r\rangle ∣ ψ ⟩ = ∣ ψ 1 ⟩ ⊗ ⋯ ⊗ ∣ ψ r ⟩ be a decomposition of ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ such that each ∣ ψ i ⟩ |\psi_i\rangle ∣ ψ i ⟩ is defined over a disjoint set of wires S i ⊆ W S_i\subseteq W S i ⊆ W with ∣ S i ∣ ≤ η |S_i|\leq\eta ∣ S i ∣ ≤ η which is maximal in the sense that each ∣ ψ i ⟩ |\psi_i\rangle ∣ ψ i ⟩ is not separable. The sets ( S i ) i (S_i)_i ( S i ) i partition W W W . Let ∣ ϕ ⟩ = ∣ ϕ 1 ⟩ ⊗ ⋯ ⊗ ∣ ϕ r ′ ⟩ |\phi\rangle=|\phi_1\rangle\otimes\cdots\otimes|\phi_{r'}\rangle ∣ ϕ ⟩ = ∣ ϕ 1 ⟩ ⊗ ⋯ ⊗ ∣ ϕ r ′ ⟩ be a maximal decomposition in the same sense. We argue that a condition analogous to that of Hall’s theorem holds.
Suppose that w ⃗ 1 , … , w ⃗ k \vec{w}_1,\ldots,\vec{w}_k w 1 , … , w k are pairwise disjoint c c c -tuples in W c W^c W c for some c ≤ η c\leq\eta c ≤ η such that w ⃗ 1 ≈ ⋯ ≈ w ⃗ k \vec{w}_1\approx\cdots\approx\vec{w}_k w 1 ≈ ⋯ ≈ w k and DTr w ⃗ 1 ( ρ 1 ) = ⋯ = DTr w ⃗ k ( ρ 1 ) = ∣ ξ ⟩ ⟨ ξ ∣ \operatorname{DTr}_{\vec{w}_1}(\rho_1)=\cdots=\operatorname{DTr}_{\vec{w}_k}(\rho_1)=|\xi\rangle\langle\xi| DTr w 1 ( ρ 1 ) = ⋯ = DTr w k ( ρ 1 ) = ∣ ξ ⟩ ⟨ ξ ∣ for some ∣ ξ ⟩ ∈ ( C 2 ) ⊗ c |\xi\rangle\in(\mathbb{C}^2)^{\otimes c} ∣ ξ ⟩ ∈ ( C 2 ) ⊗ c , where ∣ ξ ⟩ |\xi\rangle ∣ ξ ⟩ is not separable. (Then ∣ ξ ⟩ |\xi\rangle ∣ ξ ⟩ is a permutation of one of ∣ ψ 1 ⟩ , … , ∣ ψ r ⟩ |\psi_1\rangle,\ldots,|\psi_r\rangle ∣ ψ 1 ⟩ , … , ∣ ψ r ⟩ .) I claim that there are at least k k k pairwise disjoint c c c -tuples v ⃗ i ∈ W c \vec{v}_i\in W^c v i ∈ W c in the same equivalence class under ≈ \approx ≈ such that DTr v ⃗ i ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ \operatorname{DTr}_{\vec{v}_i}(\rho_2)=|\xi\rangle\langle\xi| DTr v i ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ .
We have c ≤ η c\leq\eta c ≤ η . Let d ≥ 1 d\geq1 d ≥ 1 be the largest integer such that d c ≤ η dc\leq\eta d c ≤ η . If d ≥ k d\geq k d ≥ k , then k c ≤ η kc\leq\eta k c ≤ η , so there is some w ⃗ ∈ W η \vec{w}\in W^\eta w ∈ W η starting with w ⃗ 1 ⊕ ⋯ ⊕ w ⃗ k \vec{w}_1\oplus\cdots\oplus\vec{w}_k w 1 ⊕ ⋯ ⊕ w k , where ⊕ \oplus ⊕ denotes tuple concatenation. Then since f ρ 1 ∘ α = f ρ 2 f_{\rho_1}\circ\alpha=f_{\rho_2} f ρ 1 ∘ α = f ρ 2 , we have f ρ 1 ( w ⃗ ) = f ρ 2 ( α − 1 w ⃗ ) f_{\rho_1}(\vec{w})=f_{\rho_2}(\alpha^{-1}\vec{w}) f ρ 1 ( w ) = f ρ 2 ( α − 1 w ) ; hence DTr w ⃗ ( ρ 1 ) = DTr α − 1 w ⃗ ( ρ 2 ) \operatorname{DTr}_{\vec{w}}(\rho_1)=\operatorname{DTr}_{\alpha^{-1}\vec{w}}(\rho_2) DTr w ( ρ 1 ) = DTr α − 1 w ( ρ 2 ) , and so α − 1 w ⃗ \alpha^{-1}\vec{w} α − 1 w starts with v ⃗ 1 ⊕ ⋯ ⊕ v ⃗ k \vec{v}_1\oplus\cdots\oplus\vec{v}_k v 1 ⊕ ⋯ ⊕ v k where v ⃗ 1 , … , v ⃗ k \vec{v}_1,\ldots,\vec{v}_k v 1 , … , v k are pairwise disjoint c c c -tuples such that DTr v ⃗ 1 ( ρ 2 ) = ⋯ = DTr v ⃗ k ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ \operatorname{DTr}_{\vec{v}_1}(\rho_2)=\cdots=\operatorname{DTr}_{\vec{v}_k}(\rho_2)=|\xi\rangle\langle\xi| DTr v 1 ( ρ 2 ) = ⋯ = DTr v k ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ . Furthermore, since α ∈ ∏ i Sym T i \alpha\in\prod_i\operatorname{Sym}_{T_i} α ∈ ∏ i Sym T i , we have w ⃗ ≈ α − 1 w ⃗ \vec{w}\approx\alpha^{-1}\vec{w} w ≈ α − 1 w , so v ⃗ i ≈ w ⃗ i \vec{v}_i\approx\vec{w}_i v i ≈ w i for all i ∈ [ k ] i\in[k] i ∈ [ k ] . So each v ⃗ i \vec{v}_i v i is in the same equivalence class as w ⃗ 1 , … , w ⃗ k \vec{w}_1,\ldots,\vec{w}_k w 1 , … , w k , and so at least k k k such tuples v ⃗ i \vec{v}_i v i exist.
Otherwise, d < k d<k d < k . Let Aut ( ∣ ξ ⟩ ) : = { π ∈ Sym c : U π ∣ ξ ⟩ = ∣ ξ ⟩ , ( w ⃗ 1 ) π ≈ w ⃗ 1 } \operatorname{Aut}(|\xi\rangle):=\{\pi\in\operatorname{Sym}_c:U_\pi|\xi\rangle=|\xi\rangle,(\vec{w}_1)^\pi\approx\vec{w}_1\} Aut ( ∣ ξ ⟩) := { π ∈ Sym c : U π ∣ ξ ⟩ = ∣ ξ ⟩ , ( w 1 ) π ≈ w 1 } be the group of symmetries of ∣ ξ ⟩ |\xi\rangle ∣ ξ ⟩ with respect to permutations of its c c c qubits (the automorphisms of ∣ ξ ⟩ |\xi\rangle ∣ ξ ⟩ ) which preserve the equivalence class under ≈ \approx ≈ to which w ⃗ 1 , … , w ⃗ k \vec{w}_1,\ldots,\vec{w}_k w 1 , … , w k belong. Here ( a ⃗ ) π (\vec{a})^\pi ( a ) π refers to the tuple obtained by applying the permutation π \pi π to the indices of a ⃗ \vec{a} a : if a ⃗ = ( w 1 , … , w c ) \vec{a}=(w_1,\ldots,w_c) a = ( w 1 , … , w c ) then ( a ⃗ ) π = ( w π − 1 ( 1 ) , … , w π − 1 ( c ) ) . (\vec{a})^\pi=(w_{\pi^{-1}(1)},\ldots,w_{\pi^{-1}(c)}). ( a ) π = ( w π − 1 ( 1 ) , … , w π − 1 ( c ) ) . There are exactly
d ! ( k d ) ∣ Aut ( ∣ ξ ⟩ ) ∣ d ( η − d c ) ! ( n − d c η − d c ) (17) d!\binom{k}{d}|\operatorname{Aut}(|\xi\rangle)|^d(\eta-dc)!\binom{n-dc}{\eta-dc} \tag*{(17)} d ! ( d k ) ∣ Aut ( ∣ ξ ⟩) ∣ d ( η − d c )! ( η − d c n − d c ) (17)
η \eta η -tuples w ⃗ ∈ W η \vec{w}\in W^\eta w ∈ W η which start with ( w ⃗ i 1 ) π 1 ⊕ ⋯ ⊕ ( w ⃗ i d ) π d (\vec{w}_{i_1})^{\pi_1}\oplus\cdots\oplus(\vec{w}_{i_d})^{\pi_d} ( w i 1 ) π 1 ⊕ ⋯ ⊕ ( w i d ) π d for some distinct w ⃗ i 1 , … , w ⃗ i d ∈ { w ⃗ 1 , … , w ⃗ k } \vec{w}_{i_1},\ldots,\vec{w}_{i_d}\in\{\vec{w}_1,\ldots,\vec{w}_k\} w i 1 , … , w i d ∈ { w 1 , … , w k } and some automorphisms π 1 , … , π d ∈ Aut ( ∣ ξ ⟩ ) \pi_1,\ldots,\pi_d\in\operatorname{Aut}(|\xi\rangle) π 1 , … , π d ∈ Aut ( ∣ ξ ⟩) preserving the equivalence class: there are d ! ( k d ) d!\binom{k}{d} d ! ( d k ) ways to choose w ⃗ i 1 , … , w ⃗ i d \vec{w}_{i_1},\ldots,\vec{w}_{i_d} w i 1 , … , w i d from w ⃗ 1 , … , w ⃗ k \vec{w}_1,\ldots,\vec{w}_k w 1 , … , w k , ∣ Aut ( ∣ ξ ⟩ ) ∣ d |\operatorname{Aut}(|\xi\rangle)|^d ∣ Aut ( ∣ ξ ⟩) ∣ d ways to choose π 1 , … , π d \pi_1,\ldots,\pi_d π 1 , … , π d , and ( η − d c ) ! ( n − d c η − d c ) (\eta-dc)!\binom{n-dc}{\eta-dc} ( η − d c )! ( η − d c n − d c ) ways to choose the η − d c \eta-dc η − d c other elements of w ⃗ \vec{w} w . This formula is exact because ( d + 1 ) c > η (d+1)c>\eta ( d + 1 ) c > η , so there are no tuples w ⃗ ∈ W η \vec{w}\in W^\eta w ∈ W η containing d + 1 d+1 d + 1 of the c c c -tuples w ⃗ i \vec{w}_i w i .
Since f ρ 1 = f ρ 2 ∘ α − 1 f_{\rho_1}=f_{\rho_2}\circ\alpha^{-1} f ρ 1 = f ρ 2 ∘ α − 1 , α − 1 \alpha^{-1} α − 1 bijectively maps each of the η \eta η -tuples w ⃗ \vec{w} w to a distinct v ⃗ ∈ W η \vec{v}\in W^\eta v ∈ W η which starts with v ⃗ 1 ⊕ ⋯ ⊕ v ⃗ d \vec{v}_1\oplus\cdots\oplus\vec{v}_d v 1 ⊕ ⋯ ⊕ v d , where v ⃗ 1 , … , v ⃗ d ∈ W c \vec{v}_1,\ldots,\vec{v}_d\in W^c v 1 , … , v d ∈ W c are pairwise disjoint c c c -tuples with DTr v ⃗ 1 ( ρ 2 ) = ⋯ = DTr v ⃗ d ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ \operatorname{DTr}_{\vec{v}_1}(\rho_2)=\cdots=\operatorname{DTr}_{\vec{v}_d}(\rho_2)=|\xi\rangle\langle\xi| DTr v 1 ( ρ 2 ) = ⋯ = DTr v d ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ . As before, since α ∈ ∏ i Sym T i \alpha\in\prod_i\operatorname{Sym}_{T_i} α ∈ ∏ i Sym T i , each v ⃗ i \vec{v}_i v i is in the same equivalence class under ≈ \approx ≈ as w ⃗ 1 , … , w ⃗ k \vec{w}_1,\ldots,\vec{w}_k w 1 , … , w k . Now since ∣ ξ ⟩ |\xi\rangle ∣ ξ ⟩ is a non-separable pure state, if u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 are two such c c c -tuples in W c W^c W c both in the same equivalence class as w ⃗ 1 , … , w ⃗ k \vec{w}_1,\ldots,\vec{w}_k w 1 , … , w k with D T r u ⃗ 1 ( ρ 2 ) = D T r u ⃗ 2 ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ \mathrm{DTr}_{\vec{u}_1}(\rho_2)=\mathrm{DTr}_{\vec{u}_2}(\rho_2)=|\xi\rangle\langle\xi| DTr u 1 ( ρ 2 ) = DTr u 2 ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ , then either u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 are disjoint or u ⃗ 1 = ( u ⃗ 2 ) π \vec{u}_1=(\vec{u}_2)^\pi u 1 = ( u 2 ) π for some automorphism π ∈ Aut ( ∣ ξ ⟩ ) \pi\in\operatorname{Aut}(|\xi\rangle) π ∈ Aut ( ∣ ξ ⟩) . Indeed, suppose u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 are not disjoint, and let S ′ S' S ′ be the set of wires in both u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 . If S ′ S' S ′ does not contain all the wires in u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 (i.e., u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 do not fully overlap), then since D T r u ⃗ 1 ( ρ 2 ) \mathrm{DTr}_{\vec{u}_1}(\rho_2) DTr u 1 ( ρ 2 ) and D T r u ⃗ 2 ( ρ 2 ) \mathrm{DTr}_{\vec{u}_2}(\rho_2) DTr u 2 ( ρ 2 ) are pure states, by Lemma B.3, Tr S ′ ( ρ 2 ) \operatorname{Tr}_{S'}(\rho_2) Tr S ′ ( ρ 2 ) is a pure state, which (by Lemmas B.1 and B.2) violates the non-separability of ∣ ξ ⟩ |\xi\rangle ∣ ξ ⟩ . Hence u ⃗ 1 \vec{u}_1 u 1 and u ⃗ 2 \vec{u}_2 u 2 fully overlap, so since D T r u ⃗ 1 ( ρ 2 ) = D T r u ⃗ 2 ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ \mathrm{DTr}_{\vec{u}_1}(\rho_2)=\mathrm{DTr}_{\vec{u}_2}(\rho_2)=|\xi\rangle\langle\xi| DTr u 1 ( ρ 2 ) = DTr u 2 ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ and u ⃗ 1 ≈ u ⃗ 2 ≈ w ⃗ 1 \vec{u}_1\approx\vec{u}_2\approx\vec{w}_1 u 1 ≈ u 2 ≈ w 1 , we must have u ⃗ 1 = ( u ⃗ 2 ) π \vec{u}_1=(\vec{u}_2)^\pi u 1 = ( u 2 ) π for some π ∈ Aut ( ∣ ξ ⟩ ) \pi\in\operatorname{Aut}(|\xi\rangle) π ∈ Aut ( ∣ ξ ⟩) .
Hence each pair of the c c c -tuples v ⃗ i \vec{v}_i v i are either disjoint or are related by an automorphism. Thus, if there are only at most k − 1 k-1 k − 1 disjoint c c c -tuples v ⃗ i ∈ W c \vec{v}_i\in W^c v i ∈ W c such that D T r v ⃗ i ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ \mathrm{DTr}_{\vec{v}_i}(\rho_2)=|\xi\rangle\langle\xi| DTr v i ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ , then by the same calculation as above, there are only at most
d ! ( k − 1 d ) ⋅ ∣ Aut ( ∣ ξ ⟩ ) ∣ d ⋅ ( η − d c ) ! ( n − d c η − d c ) (18) d!\binom{k-1}{d}\cdot|\operatorname{Aut}(|\xi\rangle)|^d\cdot(\eta-dc)!\binom{n-dc}{\eta-dc} \tag*{(18)} d ! ( d k − 1 ) ⋅ ∣ Aut ( ∣ ξ ⟩) ∣ d ⋅ ( η − d c )! ( η − d c n − d c ) (18)
possible η \eta η -tuples v ⃗ \vec{v} v as defined above. Since the v ⃗ \vec{v} v are mapped bijectively by α \alpha α to the η \eta η -tuples w ⃗ \vec{w} w , whose count is given by (4.7), this is not enough! So there are at least k k k such disjoint c c c -tuples v ⃗ i \vec{v}_i v i in the same equivalence class as w ⃗ 1 , … , w ⃗ k \vec{w}_1,\ldots,\vec{w}_k w 1 , … , w k .
By symmetry, it also holds that if v ⃗ 1 , … , v ⃗ k \vec{v}_1,\ldots,\vec{v}_k v 1 , … , v k is a set of disjoint c c c -tuples in W c W^c W c for some c ≤ η c\leq\eta c ≤ η such that v ⃗ 1 ≈ ⋯ ≈ v ⃗ k \vec{v}_1\approx\cdots\approx\vec{v}_k v 1 ≈ ⋯ ≈ v k and D T r v ⃗ 1 ( ρ 2 ) = ⋯ = D T r v ⃗ k ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ \mathrm{DTr}_{\vec{v}_1}(\rho_2)=\cdots=\mathrm{DTr}_{\vec{v}_k}(\rho_2)=|\xi\rangle\langle\xi| DTr v 1 ( ρ 2 ) = ⋯ = DTr v k ( ρ 2 ) = ∣ ξ ⟩ ⟨ ξ ∣ for some non-separable pure state ∣ ξ ⟩ |\xi\rangle ∣ ξ ⟩ (i.e., a permutation of one of ∣ φ 1 ⟩ , … , ∣ φ r ′ ⟩ |\varphi_1\rangle,\ldots,|\varphi_{r'}\rangle ∣ φ 1 ⟩ , … , ∣ φ r ′ ⟩ ), then there are at least k k k disjoint c c c -tuples w ⃗ i ∈ W c \vec{w}_i\in W^c w i ∈ W c in the same equivalence class under ≈ \approx ≈ as v ⃗ 1 , … , v ⃗ k \vec{v}_1,\ldots,\vec{v}_k v 1 , … , v k such that D T r w ⃗ i ( ρ 1 ) = ∣ ξ ⟩ ⟨ ξ ∣ \mathrm{DTr}_{\vec{w}_i}(\rho_1)=|\xi\rangle\langle\xi| DTr w i ( ρ 1 ) = ∣ ξ ⟩ ⟨ ξ ∣ .
Therefore there is a bijection g : [ r ] → [ r ′ ] g:[r]\to[r'] g : [ r ] → [ r ′ ] (and so r = r ′ r=r' r = r ′ ) between ( ∣ ψ i ⟩ ) i = 1 r (|\psi_i\rangle)_{i=1}^r ( ∣ ψ i ⟩ ) i = 1 r and ( ∣ φ i ⟩ ) i = 1 r ′ (|\varphi_i\rangle)_{i=1}^{r'} ( ∣ φ i ⟩ ) i = 1 r ′ with the following property: For every i ∈ [ r ] i\in[r] i ∈ [ r ] , let w ⃗ i \vec{w}_i w i be an ordering of S i S_i S i , the set of wires underlying ∣ ψ i ⟩ |\psi_i\rangle ∣ ψ i ⟩ . There is an ordering v ⃗ g ( i ) \vec{v}_{g(i)} v g ( i ) of the set of wires underlying ∣ φ g ( i ) ⟩ |\varphi_{g(i)}\rangle ∣ φ g ( i ) ⟩ such that:
(a) The states ∣ ψ i ⟩ |\psi_i\rangle ∣ ψ i ⟩ and ∣ φ g ( i ) ⟩ |\varphi_{g(i)}\rangle ∣ φ g ( i ) ⟩ are equal up to a reordering of the wires of ∣ ψ i ⟩ |\psi_i\rangle ∣ ψ i ⟩ to w ⃗ i \vec{w}_i w i and of ∣ φ g ( i ) ⟩ |\varphi_{g(i)}\rangle ∣ φ g ( i ) ⟩ to v ⃗ g ( i ) \vec{v}_{g(i)} v g ( i ) ; i.e., D T r w ⃗ i ( ρ 1 ) = D T r v ⃗ g ( i ) ( ρ 2 ) \mathrm{DTr}_{\vec{w}_i}(\rho_1)=\mathrm{DTr}_{\vec{v}_{g(i)}}(\rho_2) DTr w i ( ρ 1 ) = DTr v g ( i ) ( ρ 2 ) ; and
(b) w ⃗ i ≈ v ⃗ g ( i ) \vec{w}_i\approx\vec{v}_{g(i)} w i ≈ v g ( i ) .
Let w ⃗ = w ⃗ 1 ⊕ ⋯ ⊕ w ⃗ r \vec{w}=\vec{w}_1\oplus\cdots\oplus\vec{w}_r w = w 1 ⊕ ⋯ ⊕ w r and v ⃗ = v ⃗ g ( 1 ) ⊕ ⋯ ⊕ v ⃗ g ( r ) \vec{v}=\vec{v}_{g(1)}\oplus\cdots\oplus\vec{v}_{g(r)} v = v g ( 1 ) ⊕ ⋯ ⊕ v g ( r ) ; both are orderings of all of W W W . Hence v ⃗ = π w ⃗ \vec{v}=\pi\vec{w} v = π w for some π ∈ Sym W \pi\in\operatorname{Sym}_W π ∈ Sym W . By property (b), w ⃗ ≈ v ⃗ \vec{w}\approx\vec{v} w ≈ v . Let w ⃗ = ( w 1 , … , w n ) \vec{w}=(w_1,\ldots,w_n) w = ( w 1 , … , w n ) and v ⃗ = ( v 1 , … , v n ) \vec{v}=(v_1,\ldots,v_n) v = ( v 1 , … , v n ) : we have v j = π w j v_j=\pi w_j v j = π w j and v j ≈ w j v_j\approx w_j v j ≈ w j for each j ∈ [ n ] j\in[n] j ∈ [ n ] , so since w 1 , … , w n w_1,\ldots,w_n w 1 , … , w n and v 1 , … , v n v_1,\ldots,v_n v 1 , … , v n enumerate W W W , π \pi π maps members of each equivalence class of W W W under ≈ \approx ≈ only to members of the same equivalence class. Hence in fact π ∈ ∏ i Sym E i \pi\in\prod_i\operatorname{Sym}_{E_i} π ∈ ∏ i Sym E i . Finally, by property (a),
D T r w ⃗ ( ρ 1 ) = D T r v ⃗ ( ρ 2 ) = D T r π w ⃗ ( ρ 2 ) = D T r w ⃗ ( U π † ρ 2 U π ) (19) \mathrm{DTr}_{\vec{w}}(\rho_1)=\mathrm{DTr}_{\vec{v}}(\rho_2)=\mathrm{DTr}_{\pi\vec{w}}(\rho_2)=\mathrm{DTr}_{\vec{w}}(U_\pi^\dagger\rho_2U_\pi) \tag*{(19)} DTr w ( ρ 1 ) = DTr v ( ρ 2 ) = DTr π w ( ρ 2 ) = DTr w ( U π † ρ 2 U π ) (19)
where the last equality is by (4.4). So ρ 1 = U π † ρ 2 U π \rho_1=U_\pi^\dagger\rho_2U_\pi ρ 1 = U π † ρ 2 U π .
Indistinguishability proof
We now prove our indistinguishability theorem: if a symmetric quantum circuit C C C has ℓ \ell ℓ -partition symmetry and supports of size at most k k k , then it cannot distinguish inputs on which Duplicator wins the partial trace-based quantum pebble game with 2 k 2k 2 k pebbles. This is a quantum generalization of Theorem 14 [10 ] (Theorem 4.8 in the full version) and our proof strategy largely generalizes theirs.
Given a circuit C C C with max-supp ℓ ( C ) ≤ k \operatorname{max-supp}_{\ell}(C)\leq k max-supp ℓ ( C ) ≤ k , the following lemma shows we can assign a support s p ( [ w ⃗ ] ) sp([\vec{w}]) s p ([ w ]) to each [ w ⃗ ] ∈ W ℓ / In ( C ) [\vec{w}]\in W^\ell/\operatorname{In}(C) [ w ] ∈ W ℓ / In ( C ) in a manner respecting the automorphisms of the circuit. Recall that G G G acts on W ℓ / In ( C ) W^\ell/\operatorname{In}(C) W ℓ / In ( C ) through its embedding into Aut ( C ) / In ( C ) \operatorname{Aut}(C)/\operatorname{In}(C) Aut ( C ) / In ( C ) (Proposition 4.1).
Lemma 5.1. Suppose P ⊆ P G P \subseteq P_G P ⊆ P G supports [ w ⃗ ] ∈ W ℓ / In ( C ) [\vec{w}] \in W^\ell/\operatorname{In}(C) [ w ] ∈ W ℓ / In ( C ) . Then for all σ ∈ G \sigma\in G σ ∈ G , σ P σ − 1 = { σ Γ p σ − 1 : Γ p ∈ P } \sigma P\sigma^{-1}=\{\sigma\Gamma_p\sigma^{-1}:\Gamma_p\in P\} σ P σ − 1 = { σ Γ p σ − 1 : Γ p ∈ P } supports σ [ w ⃗ ] \sigma[\vec{w}] σ [ w ] .
Proof. Observe that ⋂ ( σ P σ − 1 ) = σ ( ⋂ P ) σ − 1 \bigcap(\sigma P\sigma^{-1})=\sigma(\bigcap P)\sigma^{-1} ⋂ ( σ P σ − 1 ) = σ ( ⋂ P ) σ − 1 . That P P P supports [ w ⃗ ] [\vec{w}] [ w ] means ⋂ P ≤ Stab G ( [ w ⃗ ] ) \bigcap P\leq\operatorname{Stab}_G([\vec{w}]) ⋂ P ≤ Stab G ([ w ]) , so σ ( ⋂ P ) σ − 1 ≤ Stab G ( σ [ w ⃗ ] ) \sigma(\bigcap P)\sigma^{-1}\leq\operatorname{Stab}_G(\sigma[\vec{w}]) σ ( ⋂ P ) σ − 1 ≤ Stab G ( σ [ w ]) .
Therefore, to each [ w ⃗ ] ∈ W ℓ / In ( C ) [\vec{w}]\in W^\ell/\operatorname{In}(C) [ w ] ∈ W ℓ / In ( C ) we assign a support s p ( [ w ⃗ ] ) ⊆ P G sp([\vec{w}])\subseteq P_G s p ([ w ]) ⊆ P G such that s p ( σ [ w ⃗ ] ) = σ s p ( [ w ⃗ ] ) σ − 1 sp(\sigma[\vec{w}])=\sigma sp([\vec{w}])\sigma^{-1} s p ( σ [ w ]) = σ s p ([ w ]) σ − 1 . If max-supp ℓ ( C ) ≤ k \operatorname{max\text{-}supp}_{\ell}(C)\leq k max - supp ℓ ( C ) ≤ k , we may take ∣ s p ( [ w ⃗ ] ) ∣ ≤ k |sp([\vec{w}])|\leq k ∣ s p ([ w ]) ∣ ≤ k .
We are now ready to prove the indistinguishability theorem.
Theorem 5.2. Let G ≤ Sym n G\leq\operatorname{Sym}_n G ≤ Sym n with distinct stabilizers. Let C C C be a Γ G \Gamma_G Γ G -symmetric output quantum τ \tau τ -circuit with at least ℓ \ell ℓ wires which has ℓ \ell ℓ -partition symmetry, has η ( C ) ≤ ℓ \eta(C)\leq\ell η ( C ) ≤ ℓ , and has max-supp ℓ ( C ) ≤ k \operatorname{max\text{-}supp}_{\ell}(C)\leq k max - supp ℓ ( C ) ≤ k . Let A , B ∈ fin n [ τ ] A,B\in\operatorname{fin}_n[\tau] A , B ∈ fin n [ τ ] . If Duplicator wins the ( Γ G , P G , 2 k ) (\Gamma_G,P_G,2k) ( Γ G , P G , 2 k ) -ℓ \ell ℓ -PT quantum pebble game on ∣ A ⟩ |A\rangle ∣ A ⟩ and ∣ B ⟩ |B\rangle ∣ B ⟩ , then C [ ∣ A ⟩ ] = C [ ∣ B ⟩ ] C[|A\rangle]=C[|B\rangle] C [ ∣ A ⟩] = C [ ∣ B ⟩] .
Proof. We prove the contrapositive: assume C [ ∣ A ⟩ ] ≠ C [ ∣ B ⟩ ] C[|A\rangle]\ne C[|B\rangle] C [ ∣ A ⟩] = C [ ∣ B ⟩] . We construct a winning Spoiler strategy for the game on ∣ A ⟩ |A\rangle ∣ A ⟩ and ∣ B ⟩ |B\rangle ∣ B ⟩ . Suppose C C C has wires W = X ⊔ A W=X\sqcup A W = X ⊔ A , where X X X are the input wires and A A A are the ancillas. Let the layers of C C C be represented by unitaries L 1 , … , L m L_1,\ldots,L_m L 1 , … , L m , let L ≤ i = L i L i − 1 ⋯ L 1 L_{\leq i}=L_iL_{i-1}\cdots L_1 L ≤ i = L i L i − 1 ⋯ L 1 for i ∈ [ m ] i\in[m] i ∈ [ m ] and let L ≤ 0 = I L_{\leq0}=I L ≤ 0 = I , and for each 0 ≤ i ≤ m 0\leq i\leq m 0 ≤ i ≤ m , let ρ i A = L ≤ i ( ∣ A ⟩ ⟨ A ∣ ⊗ ∣ 0 ⟩ ⟨ 0 ∣ ⊗ A ) L ≤ i † \rho_i^A=L_{\leq i}(|A\rangle\langle A|\otimes|0\rangle\langle0|^{\otimes A})L_{\leq i}^{\dagger} ρ i A = L ≤ i ( ∣ A ⟩ ⟨ A ∣ ⊗ ∣0 ⟩ ⟨ 0 ∣ ⊗ A ) L ≤ i † and ρ i B = L ≤ i ( ∣ B ⟩ ⟨ B ∣ ⊗ ∣ 0 ⟩ ⟨ 0 ∣ ⊗ A ) L ≤ i † \rho_i^B=L_{\leq i}(|B\rangle\langle B|\otimes|0\rangle\langle0|^{\otimes A})L_{\leq i}^{\dagger} ρ i B = L ≤ i ( ∣ B ⟩ ⟨ B ∣ ⊗ ∣0 ⟩ ⟨ 0 ∣ ⊗ A ) L ≤ i † .
For each i i i from m m m to 0 0 0 , Spoiler plays to maintain the invariant that there is some w ⃗ i ∈ W c i \vec{w}_i\in W^{c_i} w i ∈ W c i for some c i ≤ ℓ c_i\leq\ell c i ≤ ℓ such that [ w ⃗ i ] [\vec{w}_i] [ w i ] is supported by the current set of pebbles P P P and for every automorphism π \pi π induced by the game’s current unitary σ ∈ G \sigma\in G σ ∈ G (again identifying G G G with Γ G \Gamma_G Γ G by σ ↦ U σ \sigma\mapsto U_\sigma σ ↦ U σ ), we have DTr w ⃗ i ( ρ i A ) ≠ DTr w ⃗ i ( U π † ρ i B U π ) \operatorname{DTr}_{\vec{w}_i}(\rho_i^A)\ne\operatorname{DTr}_{\vec{w}_i}(U_\pi^\dagger\rho_i^B U_\pi) DTr w i ( ρ i A ) = DTr w i ( U π † ρ i B U π ) .
Then for i = 0 i=0 i = 0 , let S S S be the set of wires in w ⃗ 0 \vec{w}_0 w 0 : we have Tr S ( ρ 0 A ) ≠ Tr S ( U π † ρ 0 B U π ) \operatorname{Tr}_S(\rho_0^A)\ne\operatorname{Tr}_S(U_\pi^\dagger\rho_0^B U_\pi) Tr S ( ρ 0 A ) = Tr S ( U π † ρ 0 B U π ) for all π \pi π induced by σ \sigma σ , where ρ 0 A = ∣ A ⟩ ⟨ A ∣ ⊗ ∣ 0 ⟩ ⟨ 0 ∣ ⊗ A \rho_0^A=|A\rangle\langle A|\otimes|0\rangle\langle0|^{\otimes A} ρ 0 A = ∣ A ⟩ ⟨ A ∣ ⊗ ∣0 ⟩ ⟨ 0 ∣ ⊗ A and ρ 0 B = ∣ B ⟩ ⟨ B ∣ ⊗ ∣ 0 ⟩ ⟨ 0 ∣ ⊗ A \rho_0^B=|B\rangle\langle B|\otimes|0\rangle\langle0|^{\otimes A} ρ 0 B = ∣ B ⟩ ⟨ B ∣ ⊗ ∣0 ⟩ ⟨ 0 ∣ ⊗ A . Since each automorphism permutes the input wires and ancillas separately, if S S S contains only ancillas, then Tr S ( ρ 0 A ) = Tr S ( U π † ρ 0 B U π ) = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ S \operatorname{Tr}_S(\rho_0^A)=\operatorname{Tr}_S(U_\pi^\dagger\rho_0^B U_\pi)=|0\rangle\langle0|^{\otimes S} Tr S ( ρ 0 A ) = Tr S ( U π † ρ 0 B U π ) = ∣0 ⟩ ⟨ 0 ∣ ⊗ S ; but this is not the case, so S S S contains some input wires. Let S X = S ∩ X S_X=S\cap X S X = S ∩ X : then 1 ≤ ∣ S X ∣ ≤ ℓ 1\leq|S_X|\leq\ell 1 ≤ ∣ S X ∣ ≤ ℓ . Furthermore, since P P P supports [ w ⃗ 0 ] [\vec{w}_0] [ w 0 ] and the input wires are not moved by any internal automorphism, S X ⊆ Q P τ S_X\subseteq Q^\tau_P S X ⊆ Q P τ , i.e., ⋂ P \bigcap P ⋂ P pointwise stabilizes S X S_X S X . We have Tr S X ( ∣ A ⟩ ⟨ A ∣ ) ≠ Tr S X ( U σ † ∣ B ⟩ ⟨ B ∣ U σ ) \operatorname{Tr}_{S_X}(|A\rangle\langle A|)\ne\operatorname{Tr}_{S_X}(U_\sigma^\dagger|B\rangle\langle B|U_\sigma) Tr S X ( ∣ A ⟩ ⟨ A ∣ ) = Tr S X ( U σ † ∣ B ⟩ ⟨ B ∣ U σ ) (recall that U σ U_\sigma U σ acts on H n τ \mathcal{H}_n^\tau H n τ ). This is a violation of ℓ \ell ℓ -PT partial isomorphism from ∣ A ⟩ |A\rangle ∣ A ⟩ to ∣ B ⟩ |B\rangle ∣ B ⟩ , so Spoiler wins.
For the base case i = m i=m i = m , recall that the output wire w o u t w_{\mathrm{out}} w out of C C C is not moved by any automorphism, so let c m = 1 c_m=1 c m = 1 and w ⃗ m = ( w o u t ) \vec{w}_m=(w_{\mathrm{out}}) w m = ( w out ) . Then [ w ⃗ m ] = { w ⃗ m } [\vec{w}_m]=\{\vec{w}_m\} [ w m ] = { w m } is supported by the empty set of pebbles. C [ ∣ A ⟩ ] ≠ C [ ∣ B ⟩ ] C[|A\rangle]\ne C[|B\rangle] C [ ∣ A ⟩] = C [ ∣ B ⟩] gives us Tr w ⃗ m ( ρ m A ) ≠ Tr w ⃗ m ( U π † ρ m B U π ) \operatorname{Tr}_{\vec{w}_m}(\rho_m^A)\ne\operatorname{Tr}_{\vec{w}_m}(U_\pi^\dagger\rho_m^B U_\pi) Tr w m ( ρ m A ) = Tr w m ( U π † ρ m B U π ) for all π ∈ Aut ( C ) \pi\in\operatorname{Aut}(C) π ∈ Aut ( C ) .
The inductive step follows from the following claim, analogous to Claim 4.9 in the full version of [10 ] .
Claim 5.3. Suppose we are at layer 0 ≤ i < m 0\leq i<m 0 ≤ i < m and let L = L i + 1 L=L_{i+1} L = L i + 1 , ρ A = ρ i A \rho_A=\rho_i^A ρ A = ρ i A , and ρ B = ρ i B \rho_B=\rho_i^B ρ B = ρ i B . Suppose the current pebbles include P ⊆ P G P\subseteq P_G P ⊆ P G with ∣ P ∣ ≤ k |P|\leq k ∣ P ∣ ≤ k , the current unitary is σ ∈ G \sigma\in G σ ∈ G , and we have w ⃗ = w ⃗ i + 1 ∈ W c \vec{w}=\vec{w}_{i+1}\in W^{c} w = w i + 1 ∈ W c for some c = c i + 1 ≤ ℓ c=c_{i+1}\leq\ell c = c i + 1 ≤ ℓ such that P P P supports [ w ⃗ ] [\vec{w}] [ w ] and for every automorphism π \pi π induced by σ \sigma σ ,
DTr w ⃗ ( L ρ A L † ) ≠ DTr w ⃗ ( U π † L ρ B L † U π ) . (20) \operatorname{DTr}_{\vec{w}}(L\rho_A L^\dagger)\ne\operatorname{DTr}_{\vec{w}}(U_\pi^\dagger L\rho_B L^\dagger U_\pi). \tag*{(20)} DTr w ( L ρ A L † ) = DTr w ( U π † L ρ B L † U π ) . (20) Spoiler can play such that after at most k k k rounds, we are in a position where the pebbles include P ′ ⊆ P G P'\subseteq P_G P ′ ⊆ P G with ∣ P ′ ∣ ≤ k |P'|\leq k ∣ P ′ ∣ ≤ k , the unitary is σ ′ ∈ G \sigma'\in G σ ′ ∈ G , and we have some w ⃗ ′ ∈ W ℓ \vec{w}'\in W^\ell w ′ ∈ W ℓ such that P ′ P' P ′ supports [ w ⃗ ′ ] [\vec{w}'] [ w ′ ] and for every automorphism π ′ \pi' π ′ induced by σ ′ \sigma' σ ′ ,
DTr w ⃗ ′ ( ρ A ) ≠ DTr w ⃗ ′ ( U π ′ † ρ B U π ′ ) . (21) \operatorname{DTr}_{\vec{w}'}(\rho_A)\ne\operatorname{DTr}_{\vec{w}'}(U_{\pi'}^\dagger\rho_B U_{\pi'}). \tag*{(21)} DTr w ′ ( ρ A ) = DTr w ′ ( U π ′ † ρ B U π ′ ) . (21)
Proof. Since C C C has ℓ \ell ℓ -partition symmetry, there is a partition ( T i ) i (T_i)_i ( T i ) i of W ℓ W^\ell W ℓ such that Stab Aut ( C ) ( w ⃗ ) ≤ ∏ i Sym T i \operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) \le\prod_i \operatorname{Sym}_{T_i} Stab Aut ( C ) ( w ) ≤ ∏ i Sym T i and f ρ A ∘ α ≠ f U π † ρ B U π f_{\rho_A} \circ\alpha\ne f_{U_\pi^{\dagger}\rho_B U_\pi} f ρ A ∘ α = f U π † ρ B U π for all α ∈ ∏ i Sym T i \alpha\in\prod_i \operatorname{Sym}_{T_i} α ∈ ∏ i Sym T i and all π \pi π induced by σ \sigma σ . Then χ ( ∩ P ) ∩ Stab Aut ( C ) ( w ⃗ ) ≤ ∏ i Sym T i \chi(\cap P) \cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) \le\prod_i \operatorname{Sym}_{T_i} χ ( ∩ P ) ∩ Stab Aut ( C ) ( w ) ≤ ∏ i Sym T i , so the orbits of W ℓ W^\ell W ℓ under χ ( ∩ P ) ∩ Stab Aut ( C ) ( w ⃗ ) \chi(\cap P) \cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) χ ( ∩ P ) ∩ Stab Aut ( C ) ( w ) form a refinement of ( T i ) (T_i) ( T i ) . Hence there is some such orbit O O O such that
f ρ A O ∘ α ≠ f U π † ρ B U π O (22) f_{\rho_A}^{O} \circ\alpha\ne f_{U_\pi^{\dagger}\rho_B U_\pi}^{O} \tag*{(22)} f ρ A O ∘ α = f U π † ρ B U π O (22)
for all α ∈ Sym O \alpha\in\operatorname{Sym}_{O} α ∈ Sym O and all π \pi π induced by σ \sigma σ .
We now place pebbles. Suppose that in the j j j th round, the pebbles include P j = P ∪ { Γ p 1 , … , Γ p j } P_j = P \cup\{\Gamma_{p_1}, \ldots, \Gamma_{p_j}\} P j = P ∪ { Γ p 1 , … , Γ p j } and the current unitary is σ j \sigma_j σ j . Spoiler plays to maintain the following invariant: there is some w ⃗ j ′ ∈ W ℓ \vec{w}'_j \in W^\ell w j ′ ∈ W ℓ such that Γ p 1 , … , Γ p j ∈ s p ( [ w ⃗ j ′ ] ) \Gamma_{p_1}, \ldots, \Gamma_{p_j} \in sp([\vec{w}'_j]) Γ p 1 , … , Γ p j ∈ s p ([ w j ′ ]) and for its orbit O j = Orb χ ( ∩ P j ) ∩ Stab Aut ( C ) ( w ⃗ ) ( w ⃗ j ′ ) O_j = \operatorname{Orb}_{\chi(\cap P_j)\cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w})}(\vec{w}'_j) O j = Orb χ ( ∩ P j ) ∩ Stab Aut ( C ) ( w ) ( w j ′ ) ,
f ρ A O j ∘ α ≠ f U π j † ρ B U π j O j (23) f_{\rho_A}^{O_j} \circ\alpha\ne f_{U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}}^{O_j} \tag*{(23)} f ρ A O j ∘ α = f U π j † ρ B U π j O j (23)
for all α ∈ Sym O j \alpha\in\operatorname{Sym}_{O_j} α ∈ Sym O j and all π j \pi_j π j induced by σ j \sigma_j σ j . Since ∣ s p ( [ w ⃗ j ′ ] ) ∣ ≤ k |sp([\vec{w}'_j])| \le k ∣ s p ([ w j ′ ]) ∣ ≤ k , after at most k k k rounds, we can take α = id \alpha= \operatorname{id} α = id and apply w ⃗ j ′ \vec{w}'_j w j ′ to get that DTr w ⃗ j ′ ( ρ A ) ≠ DTr w ⃗ j ′ ( U π j † ρ B U π j ) \operatorname{DTr}_{\vec{w}'_j}(\rho_A) \ne\operatorname{DTr}_{\vec{w}'_j}(U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}) DTr w j ′ ( ρ A ) = DTr w j ′ ( U π j † ρ B U π j ) for all π j \pi_j π j induced by σ j \sigma_j σ j with [ w ⃗ j ′ ] [\vec{w}'_j] [ w j ′ ] supported by { Γ p 1 , … , Γ p j } \{\Gamma_{p_1}, \ldots, \Gamma_{p_j}\} { Γ p 1 , … , Γ p j } , which proves the claim.
The case j = 0 j = 0 j = 0 is given above. In round j ≥ 1 j \ge1 j ≥ 1 , Spoiler first picks up some pebble not in the support of w ⃗ \vec{w} w or w ⃗ j − 1 ′ \vec{w}'_{j-1} w j − 1 ′ if necessary. From the invariant,
f ρ A O j − 1 ∘ α ≠ f U π j − 1 † ρ B U π j − 1 O j − 1 (24) f_{\rho_A}^{O_{j-1}} \circ\alpha\ne f_{U_{\pi_{j-1}}^{\dagger}\rho_B U_{\pi_{j-1}}}^{O_{j-1}} \tag*{(24)} f ρ A O j − 1 ∘ α = f U π j − 1 † ρ B U π j − 1 O j − 1 (24)
for all α ∈ Sym O j − 1 \alpha\in\operatorname{Sym}_{O_{j-1}} α ∈ Sym O j − 1 and all π j − 1 \pi_{j-1} π j − 1 induced by σ j − 1 \sigma_{j-1} σ j − 1 . Duplicator chooses some σ ∈ ∩ P j − 1 \sigma\in\cap P_{j-1} σ ∈ ∩ P j − 1 and sets σ j : = σ j − 1 σ \sigma_j := \sigma_{j-1}\sigma σ j := σ j − 1 σ . Observe that every automorphism π j \pi_j π j induced by σ j \sigma_j σ j is of the form π j − 1 π \pi_{j-1}\pi π j − 1 π , where π j − 1 \pi_{j-1} π j − 1 and π \pi π are induced by σ j − 1 \sigma_{j-1} σ j − 1 and σ \sigma σ respectively. By equation (15) ,
f U π j † ρ B U π j = f U π j − 1 † ρ B U π j − 1 ∘ π . (25) f_{U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}} = f_{U_{\pi_{j-1}}^{\dagger}\rho_B U_{\pi_{j-1}}} \circ\pi. \tag*{(25)} f U π j † ρ B U π j = f U π j − 1 † ρ B U π j − 1 ∘ π . (25)
Since P P P supports [ w ⃗ ] [\vec{w}] [ w ] , σ \sigma σ stabilizes [ w ⃗ ] [\vec{w}] [ w ] . Lemma 4.3 states that σ \sigma σ induces some automorphism π ′ \pi' π ′ stabilizing w ⃗ \vec{w} w . By Proposition 4.1, π ′ \pi' π ′ differs from π \pi π only by some internal automorphism, so by equation (15) , in fact
f U π j † ρ B U π j = f U π j − 1 † ρ B U π j − 1 ∘ π ′ . (26) f_{U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}} = f_{U_{\pi_{j-1}}^{\dagger}\rho_B U_{\pi_{j-1}}} \circ\pi'. \tag*{(26)} f U π j † ρ B U π j = f U π j − 1 † ρ B U π j − 1 ∘ π ′ . (26)
Now π ′ ∈ χ ( ∩ P j − 1 ) ∩ Stab Aut ( C ) ( w ⃗ ) \pi' \in\chi(\cap P_{j-1}) \cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) π ′ ∈ χ ( ∩ P j − 1 ) ∩ Stab Aut ( C ) ( w ) and O j − 1 O_{j-1} O j − 1 is the orbit of w ⃗ j − 1 ′ \vec{w}'_{j-1} w j − 1 ′ under this group, so we may restrict both sides of (5.7) to O j − 1 O_{j-1} O j − 1 :
f U π j † ρ B U π j O j − 1 = f U π j − 1 † ρ B U π j − 1 O j − 1 ∘ π ′ (27) f_{U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}}^{O_{j-1}} = f_{U_{\pi_{j-1}}^{\dagger}\rho_B U_{\pi_{j-1}}}^{O_{j-1}} \circ\pi' \tag*{(27)} f U π j † ρ B U π j O j − 1 = f U π j − 1 † ρ B U π j − 1 O j − 1 ∘ π ′ (27)
Combining with (5.5) and observing that π ′ ∈ Sym O j − 1 \pi' \in\operatorname{Sym}_{O_{j-1}} π ′ ∈ Sym O j − 1 , we obtain
f ρ A O j − 1 ∘ α ≠ f U π j † ρ B U π j O j − 1 (28) f_{\rho_A}^{O_{j-1}} \circ\alpha\ne f_{U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}}^{O_{j-1}} \tag*{(28)} f ρ A O j − 1 ∘ α = f U π j † ρ B U π j O j − 1 (28)
for all α ∈ Sym O j − 1 \alpha\in\operatorname{Sym}_{O_{j-1}} α ∈ Sym O j − 1 and all π j \pi_j π j induced by σ j \sigma_j σ j .
Having defused Duplicator’s choice of unitary, we now show how Spoiler can make progress. Let Γ p \Gamma_p Γ p be some pebble in s p ( [ w ⃗ j − 1 ′ ] ) sp([\vec{w}'_{j-1}]) s p ([ w j − 1 ′ ]) which is not yet in P j − 1 P_{j-1} P j − 1 . For each pebble Γ q ∈ P G \Gamma_q \in P_G Γ q ∈ P G which is conjugate to Γ p \Gamma_p Γ p by some π ∈ χ ( ∩ P j − 1 ) ∩ Stab Aut ( C ) ( w ⃗ ) \pi\in\chi(\cap P_{j-1}) \cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) π ∈ χ ( ∩ P j − 1 ) ∩ Stab Aut ( C ) ( w ) , let
W q : = { π w ⃗ j − 1 ′ : π ∈ Stab Aut ( C ) ( w ⃗ ) is induced by some σ ∈ ∩ P j − 1 such that σ Γ p σ − 1 = Γ q } . (29) W_q := \{\pi\vec{w}'_{j-1} : \pi\in\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) \text{ is induced by some } \sigma\in\cap P_{j-1} \text{ such that } \sigma\Gamma_p\sigma^{-1} = \Gamma_q\}. \tag*{(29)} W q := { π w j − 1 ′ : π ∈ Stab Aut ( C ) ( w ) is induced by some σ ∈ ∩ P j − 1 such that σ Γ p σ − 1 = Γ q } . (29)
We make a series of claims about these sets $(W_q)_q: (i) Every v ⃗ ∈ O j − 1 \vec{v} \in O_{j-1} v ∈ O j − 1 appears in the same number of sets W q W_q W q .
(ii) There is some Γ q \Gamma_q Γ q such that f ρ A W q ∘ α ≠ f U π j † ρ B U π j W q f_{\rho_A}^{W_q} \circ\alpha\ne f_{U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}}^{W_q} f ρ A W q ∘ α = f U π j † ρ B U π j W q for all α ∈ Sym W q \alpha\in\operatorname{Sym}_{W_q} α ∈ Sym W q and all π j \pi_j π j induced by σ j \sigma_j σ j .
(iii) For every Γ q \Gamma_q Γ q , we have W q = Orb χ ( Γ q ∩ P j − 1 ) ∩ Stab Aut ( C ) ( w ⃗ ) ( v ⃗ ) W_q = \operatorname{Orb}_{\chi(\Gamma_q \cap P_{j-1}) \cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w})}(\vec{v}) W q = Orb χ ( Γ q ∩ P j − 1 ) ∩ Stab Aut ( C ) ( w ) ( v ) for v ⃗ ∈ W q \vec{v} \in W_q v ∈ W q .
For (i): Let v ⃗ ∈ O j − 1 \vec{v} \in O_{j-1} v ∈ O j − 1 : then v ⃗ = π w ⃗ j − 1 ′ \vec{v} = \pi\vec{w}'_{j-1} v = π w j − 1 ′ for some π ∈ Stab Aut ( C ) ( w ⃗ ) \pi\in\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) π ∈ Stab Aut ( C ) ( w ) induced by some σ ∈ ⋂ P j − 1 \sigma\in\bigcap P_{j-1} σ ∈ ⋂ P j − 1 . The set of Γ q \Gamma_q Γ q such that v ⃗ ∈ W q \vec{v} \in W_q v ∈ W q is given by { σ ′ Γ p σ ′ − 1 : π ′ w ⃗ j − 1 ′ = v ⃗ \{\sigma'\Gamma_p\sigma'^{-1} : \pi'\vec{w}'_{j-1} = \vec{v} { σ ′ Γ p σ ′ − 1 : π ′ w j − 1 ′ = v for some π ′ ∈ Stab Aut ( C ) ( w ⃗ ) \pi' \in\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) π ′ ∈ Stab Aut ( C ) ( w ) induced by σ ′ ∈ ⋂ P j − 1 } \sigma' \in\bigcap P_{j-1}\} σ ′ ∈ ⋂ P j − 1 } . There is a bijection to this set from the fixed set { σ ′ Γ p σ ′ − 1 : π ′ w ⃗ j − 1 ′ = w ⃗ j − 1 ′ \{\sigma'\Gamma_p\sigma'^{-1} : \pi'\vec{w}'_{j-1} = \vec{w}'_{j-1} { σ ′ Γ p σ ′ − 1 : π ′ w j − 1 ′ = w j − 1 ′ for some π ′ ∈ Stab Aut ( C ) ( w ⃗ ) \pi' \in\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) π ′ ∈ Stab Aut ( C ) ( w ) induced by σ ′ ∈ ⋂ P j − 1 } \sigma' \in\bigcap P_{j-1}\} σ ′ ∈ ⋂ P j − 1 } given by conjugating by σ \sigma σ .
For (ii): Suppose there is no such Γ q \Gamma_q Γ q . Then for each Γ q \Gamma_q Γ q there is some α ∈ Sym W q \alpha\in\operatorname{Sym}_{W_q} α ∈ Sym W q such that f ρ A W q ∘ α = f U π j † ρ B U π j W q f_{\rho_A}^{W_q} \circ\alpha= f_{U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}}^{W_q} f ρ A W q ∘ α = f U π j † ρ B U π j W q for some π j \pi_j π j induced by σ j \sigma_j σ j . Fix a particular automorphism π \pi π induced by σ j \sigma_j σ j : then π π j − 1 ∈ In ( C ) \pi\pi_j^{-1} \in\operatorname{In}(C) π π j − 1 ∈ In ( C ) , so applying (4.5) and Lemma 4.3 gives
f U π j † ρ B U π j = f U π † ρ B U π . (30) f_{U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}} = f_{U_{\pi}^{\dagger}\rho_B U_{\pi}}. \tag*{(30)} f U π j † ρ B U π j = f U π † ρ B U π . (30)
Restricting to the domain W q W_q W q , for each Γ q \Gamma_q Γ q , we have f ρ A W q ∘ α = f U π † ρ B U π W q f_{\rho_A}^{W_q} \circ\alpha= f_{U_{\pi}^{\dagger}\rho_B U_{\pi}}^{W_q} f ρ A W q ∘ α = f U π † ρ B U π W q for some α ∈ Sym W q \alpha\in\operatorname{Sym}_{W_q} α ∈ Sym W q . That is, the multisets given by the images of f ρ A W q f_{\rho_A}^{W_q} f ρ A W q and f U π † ρ B U π W q f_{U_{\pi}^{\dagger}\rho_B U_{\pi}}^{W_q} f U π † ρ B U π W q are equal. By claim (i), taking the union of these multisets for all Γ q \Gamma_q Γ q gives a multiset in which the image of each v ⃗ ∈ O j − 1 \vec{v} \in O_{j-1} v ∈ O j − 1 appears the same number of times (say t t t times). That is, the resulting multiset consists of t t t copies of the images of f ρ A O j − 1 f_{\rho_A}^{O_{j-1}} f ρ A O j − 1 and f U π † ρ B U π O j − 1 f_{U_{\pi}^{\dagger}\rho_B U_{\pi}}^{O_{j-1}} f U π † ρ B U π O j − 1 , so these images are equal as multisets. Therefore, f ρ A O j − 1 ∘ α = f U π † ρ B U π O j − 1 f_{\rho_A}^{O_{j-1}} \circ\alpha= f_{U_{\pi}^{\dagger}\rho_B U_{\pi}}^{O_{j-1}} f ρ A O j − 1 ∘ α = f U π † ρ B U π O j − 1 for some α ∈ Sym O j − 1 \alpha\in\operatorname{Sym}_{O_{j-1}} α ∈ Sym O j − 1 , contradicting (5.9).
For (iii): For brevity, let Q = Γ q ∩ ⋂ P j − 1 Q = \Gamma_q \cap\bigcap P_{j-1} Q = Γ q ∩ ⋂ P j − 1 . Let v ⃗ ∈ W q \vec{v} \in W_q v ∈ W q : there is some π ∈ Stab Aut ( C ) ( w ⃗ ) \pi\in\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) π ∈ Stab Aut ( C ) ( w ) induced by some σ ∈ ⋂ P j − 1 \sigma\in\bigcap P_{j-1} σ ∈ ⋂ P j − 1 such that v ⃗ = π w ⃗ j − 1 ′ \vec{v} = \pi\vec{w}'_{j-1} v = π w j − 1 ′ and σ Γ p σ − 1 = Γ q \sigma\Gamma_p\sigma^{-1} = \Gamma_q σ Γ p σ − 1 = Γ q . For every π ′ ∈ χ ( Q ) ∩ Stab Aut ( C ) ( w ⃗ ) \pi' \in\chi(Q) \cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) π ′ ∈ χ ( Q ) ∩ Stab Aut ( C ) ( w ) induced by σ ′ ∈ Q \sigma' \in Q σ ′ ∈ Q , we have ( σ ′ σ ) Γ p ( σ ′ σ ) − 1 = σ ′ Γ q σ ′ − 1 = Γ q (\sigma'\sigma)\Gamma_p(\sigma'\sigma)^{-1} = \sigma'\Gamma_q\sigma'^{-1} = \Gamma_q ( σ ′ σ ) Γ p ( σ ′ σ ) − 1 = σ ′ Γ q σ ′ − 1 = Γ q since σ ′ ∈ Γ q \sigma' \in\Gamma_q σ ′ ∈ Γ q , so since σ ′ σ \sigma'\sigma σ ′ σ induces π ′ π \pi'\pi π ′ π , we have π ′ v ⃗ = π ′ π w ⃗ j − 1 ′ ∈ W q \pi'\vec{v} = \pi'\pi\vec{w}'_{j-1} \in W_q π ′ v = π ′ π w j − 1 ′ ∈ W q . Hence Orb χ ( Q ) ∩ Stab Aut ( C ) ( w ⃗ ) ( v ⃗ ) ⊆ W q \operatorname{Orb}_{\chi(Q)\cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w})}(\vec{v}) \subseteq W_q Orb χ ( Q ) ∩ Stab Aut ( C ) ( w ) ( v ) ⊆ W q . Conversely, for all π ′ ∈ Stab Aut ( C ) ( w ⃗ ) \pi' \in\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) π ′ ∈ Stab Aut ( C ) ( w ) induced by σ ′ ∈ ⋂ P j − 1 \sigma' \in\bigcap P_{j-1} σ ′ ∈ ⋂ P j − 1 such that σ ′ Γ p σ ′ − 1 = Γ q \sigma'\Gamma_p\sigma'^{-1} = \Gamma_q σ ′ Γ p σ ′ − 1 = Γ q (i.e., for every π ′ w ⃗ j − 1 ′ ∈ W q \pi'\vec{w}'_{j-1} \in W_q π ′ w j − 1 ′ ∈ W q ), we have ( σ ′ σ − 1 ) Γ q ( σ ′ σ − 1 ) − 1 = σ ′ Γ p σ ′ − 1 = Γ q (\sigma'\sigma^{-1})\Gamma_q(\sigma'\sigma^{-1})^{-1} = \sigma'\Gamma_p\sigma'^{-1} = \Gamma_q ( σ ′ σ − 1 ) Γ q ( σ ′ σ − 1 ) − 1 = σ ′ Γ p σ ′ − 1 = Γ q . But, since G G G has distinct stabilizers, every pebble is a self-normalizing subgroup; thus we have σ ′ σ − 1 ∈ Γ q \sigma'\sigma^{-1} \in\Gamma_q σ ′ σ − 1 ∈ Γ q and so σ ′ σ − 1 ∈ Q \sigma'\sigma^{-1} \in Q σ ′ σ − 1 ∈ Q . Hence π ′ π − 1 ∈ χ ( Q ) ∩ Stab Aut ( C ) ( w ⃗ ) \pi'\pi^{-1} \in\chi(Q) \cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w}) π ′ π − 1 ∈ χ ( Q ) ∩ Stab Aut ( C ) ( w ) . Furthermore, π ′ π − 1 v ⃗ = π ′ w ⃗ j − 1 ′ \pi'\pi^{-1}\vec{v} = \pi'\vec{w}'_{j-1} π ′ π − 1 v = π ′ w j − 1 ′ , so π ′ w ⃗ j − 1 ′ ∈ Orb χ ( Q ) ∩ Stab Aut ( C ) ( w ⃗ ) ( v ⃗ ) \pi'\vec{w}'_{j-1} \in\operatorname{Orb}_{\chi(Q)\cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w})}(\vec{v}) π ′ w j − 1 ′ ∈ Orb χ ( Q ) ∩ Stab Aut ( C ) ( w ) ( v ) . Hence W q ⊆ Orb χ ( Q ) ∩ Stab Aut ( C ) ( w ⃗ ) ( v ⃗ ) W_q \subseteq\operatorname{Orb}_{\chi(Q)\cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w})}(\vec{v}) W q ⊆ Orb χ ( Q ) ∩ Stab Aut ( C ) ( w ) ( v ) as well.
Thus, by claim (ii), Spoiler places a pebble Γ q \Gamma_q Γ q such that f ρ A W q ∘ α ≠ f U π j † ρ B U π j W q f_{\rho_A}^{W_q} \circ\alpha\ne f_{U_{\pi_j}^{\dagger}\rho_B U_{\pi_j}}^{W_q} f ρ A W q ∘ α = f U π j † ρ B U π j W q for all α ∈ Sym W q \alpha\in\operatorname{Sym}_{W_q} α ∈ Sym W q and all π j \pi_j π j induced by σ j \sigma_j σ j . Let P j : = P j − 1 ∪ { Γ q } P_j := P_{j-1} \cup\{\Gamma_q\} P j := P j − 1 ∪ { Γ q } . Choose any w ⃗ j ′ ∈ W q \vec{w}'_j \in W_q w j ′ ∈ W q : we have w ⃗ j ′ = π w ⃗ j − 1 ′ \vec{w}'_j = \pi\vec{w}'_{j-1} w j ′ = π w j − 1 ′ (so [ w ⃗ j ′ ] = σ [ w ⃗ j − 1 ′ ] [\vec{w}'_j] = \sigma[\vec{w}'_{j-1}] [ w j ′ ] = σ [ w j − 1 ′ ] ) for some π \pi π induced by σ ∈ ⋂ P j − 1 \sigma\in\bigcap P_{j-1} σ ∈ ⋂ P j − 1 with Γ q = σ Γ p σ − 1 \Gamma_q = \sigma\Gamma_p\sigma^{-1} Γ q = σ Γ p σ − 1 , so by our assumption on the assignment of supports, Γ p 1 , … , Γ p j − 1 , Γ q ∈ sp ( w ⃗ j ′ ) \Gamma_{p_1},\ldots,\Gamma_{p_{j-1}},\Gamma_q \in\operatorname{sp}(\vec{w}'_j) Γ p 1 , … , Γ p j − 1 , Γ q ∈ sp ( w j ′ ) . By claim (iii), let O j : = W q = Orb χ ( ⋂ P j ) ∩ Stab Aut ( C ) ( w ⃗ ) ( w ⃗ j ′ ) O_j := W_q = \operatorname{Orb}_{\chi(\bigcap P_j)\cap\operatorname{Stab}_{\operatorname{Aut}(C)}(\vec{w})}(\vec{w}'_j) O j := W q = Orb χ ( ⋂ P j ) ∩ Stab Aut ( C ) ( w ) ( w j ′ ) . This preserves the invariant. □ \square □
Repeatedly applying this claim gives a Spoiler strategy that wins in at most k m km k m rounds. □ \square □
CFI application and parameter calculation
In this section, we define the graph property P CFI Alt \mathcal{P}_{\operatorname{CFI}}^{\operatorname{Alt}} P CFI Alt that is hard for moderate-entanglement symmetric quantum circuits to solve, and prove the corresponding lower bound (Theorem 1.1). We will in fact prove the following stronger result concerning quantum circuits which are symmetric under the action of the alternating group Alt n \operatorname{Alt}_n Alt n , from which Theorem 1.1 immediately follows.
Theorem 6.1. Let f : Z + → Z + f : \mathbb{Z}_{+} \to\mathbb{Z}_{+} f : Z + → Z + be any increasing function with f ( n ) = ω ( log n ) f(n) = \omega(\log n) f ( n ) = ω ( log n ) . There is no family of Γ A l t n \Gamma_{\mathrm{Alt}_{n}} Γ Alt n -symmetric output quantum τ g r a p h \tau_{\mathrm{graph}} τ graph -circuits ( C n ) n (C_n)_n ( C n ) n computing P C F I A l t \mathcal{P}^{\mathrm{Alt}}_{\mathrm{CFI}} P CFI Alt which has size s ( C n ) = 2 o ( f ( n ) ) s(C_n) = 2^{o(f(n))} s ( C n ) = 2 o ( f ( n )) and entanglement width η ( C n ) = O ( n / f ( n ) ) \eta(C_n) = O(n/f(n)) η ( C n ) = O ( n / f ( n )) .
The CFI and Alt-CFI graphs
For a given logic L \mathcal{L} L and structures A \mathcal{A} A and B \mathcal{B} B over the same vocabulary, write A ≡ L B \mathcal{A} \equiv_{\mathcal{L}} \mathcal{B} A ≡ L B to mean that A \mathcal{A} A and B \mathcal{B} B agree on every sentence in L \mathcal{L} L . We follow the notation of Immerman and Lander [13 ] .
Definition 6.2. Let L k \mathcal{L}_k L k denote the fragment of first-order logic consisting of formulas in which the only variables that appear are from the finite set { x 1 , … , x k } \{x_1,\ldots,x_k\} { x 1 , … , x k } .
Definition 6.3. Let C k \mathcal{C}_k C k denote the extension of L k \mathcal{L}_k L k with the following syntax rule: if n ∈ Z ≥ 1 n \in\mathbb{Z}_{\geq1} n ∈ Z ≥ 1 , x ∈ { x 1 , … , x k } x \in\{x_1,\ldots,x_k\} x ∈ { x 1 , … , x k } is a variable, and φ \varphi φ is a formula, then ∃ x ≥ n φ \exists^{\geq n}_x\varphi ∃ x ≥ n φ is a formula.
The semantics are as follows: if A \mathcal{A} A is a structure with domain A A A , φ ( x ) \varphi(x) φ ( x ) is a formula, and n ∈ Z ≥ 1 n \in\mathbb{Z}_{\geq1} n ∈ Z ≥ 1 , then A ⊨ ∃ x ≥ n φ ( x ) \mathcal{A} \models\exists^{\geq n}_x\varphi(x) A ⊨ ∃ x ≥ n φ ( x ) if and only if there are at least n n n distinct elements a ∈ A a \in A a ∈ A such that A ⊨ φ [ a ] \mathcal{A} \models\varphi[a] A ⊨ φ [ a ] .
Cai, Fürer, and Immerman [4 ] constructed a remarkable counterexample showing that FPC, even on τ g r a p h \tau_{\mathrm{graph}} τ graph , does not capture all polynomial-time properties. We present their results but omit the details of the construction. The interested reader may refer to [4 ] .
Theorem 6.4 [4 ] . There exist families of undirected graphs ( G n ) n (G_n)_n ( G n ) n and ( H n ) n (H_n)_n ( H n ) n , n ∈ Z ≥ 1 n \in\mathbb{Z}_{\geq1} n ∈ Z ≥ 1 , called the CFI graphs, with the following properties for each n n n :
G n G_n G n and H n H_n H n have the same number v = O ( n ) v = O(n) v = O ( n ) of vertices, with v ≥ n + 1 v \geq n + 1 v ≥ n + 1 .
G n ≡ C n H n G_n \equiv_{\mathcal{C}_n} H_n G n ≡ C n H n when interpreted as τ g r a p h \tau_{\mathrm{graph}} τ graph -structures.
G n G_n G n is not isomorphic to H n H_n H n .
Furthermore, there is a polynomial-time algorithm which outputs “yes” on every G n G_n G n and “no” on every H n H_n H n .
The “furthermore” part of Theorem 6.4 implies that there is a polynomial-time τ g r a p h \tau_{\mathrm{graph}} τ graph -property, the CFI property P C F I \mathcal{P}_{\mathrm{CFI}} P CFI , such that G n ∈ P C F I G_n \in\mathcal{P}_{\mathrm{CFI}} G n ∈ P CFI but H n ∉ P C F I H_n \notin\mathcal{P}_{\mathrm{CFI}} H n ∈ / P CFI for each n n n .
Definition 6.5. Let A ′ ⊆ A \mathcal{A}' \subseteq\mathcal{A} A ′ ⊆ A and B ′ ⊆ B \mathcal{B}' \subseteq\mathcal{B} B ′ ⊆ B . A bijection f : A ′ → B ′ f : \mathcal{A}' \to\mathcal{B}' f : A ′ → B ′ is a partial isomorphism from A \mathcal{A} A to B \mathcal{B} B if for every relation symbol R i r i ∈ τ R_i^{r_i} \in\tau R i r i ∈ τ and every a 1 , … , a r i ∈ A ′ a_1,\ldots,a_{r_i} \in\mathcal{A}' a 1 , … , a r i ∈ A ′ , we have ( a 1 , … , a r i ) ∈ R i A (a_1,\ldots,a_{r_i}) \in R_i^{\mathcal{A}} ( a 1 , … , a r i ) ∈ R i A if and only if ( f ( a 1 ) , … , f ( a r i ) ) ∈ R i B (f(a_1),\ldots,f(a_{r_i})) \in R_i^{\mathcal{B}} ( f ( a 1 ) , … , f ( a r i )) ∈ R i B .
Let A \mathcal{A} A and B \mathcal{B} B be finite τ \tau τ -structures of the same size n n n , and suppose without loss of generality that they have the domain [ n ] [n] [ n ] . Let G G G be a group acting on [ n ] [n] [ n ] . Without loss of generality, we may take G ≤ Sym n G \leq\operatorname{Sym}_n G ≤ Sym n .
Definition 6.6 [10 ] . The k k k -pebble G G G -bijection game on A \mathcal{A} A and B \mathcal{B} B is played using two sets of k k k pebbles, a 1 , … , a k a_1,\ldots,a_k a 1 , … , a k and b 1 , … , b k b_1,\ldots,b_k b 1 , … , b k . Initially, no pebbles are placed. Each round proceeds as follows:
Spoiler picks up a pair of pebbles ( a i , b i ) (a_i,b_i) ( a i , b i ) .
Duplicator chooses some σ ∈ G \sigma\in G σ ∈ G such that for every pair of pebbles ( a j , b j ) (a_j,b_j) ( a j , b j ) which are placed on the structures, we have σ ( a j ) = b j \sigma(a_j) = b_j σ ( a j ) = b j .
Spoiler places a i a_i a i on some unpebbled element a a a of A \mathcal{A} A and places b i b_i b i on σ ( a i ) \sigma(a_i) σ ( a i ) .
Spoiler wins if the mapping given by the pebbles is not a partial isomorphism. Otherwise, play continues, and Duplicator wins if it has a strategy to play forever.
We abbreviate “k k k -pebble G G G -bijection game” to “( G , k ) (G,k) ( G , k ) -pebble game”. To recover Hella’s bijection game, take G = Sym n G = \operatorname{Sym}_n G = Sym n .
Corollary 6.7. Duplicator wins the k k k -pebble bijection game on A \mathcal{A} A and B \mathcal{B} B if and only if A ≡ C k B \mathcal{A} \equiv_{\mathcal{C}_k} \mathcal{B} A ≡ C k B .
Theorem 6.8 [6 ] . Let ( G n ) n (G_n)_n ( G n ) n and ( H n ) n (H_n)_n ( H n ) n be the families of CFI graphs of Theorem 6.4 , interpreted as τ g r a p h \tau_{\mathrm{graph}} τ graph -structures, and suppose G n G_n G n and H n H_n H n have the same set of vertices V V V . Then Duplicator wins the ( Sym V , n ) (\operatorname{Sym}_V,n) ( Sym V , n ) -pebble game on G n G_n G n and H n H_n H n .
Proof. G n ≡ C n H n G_n \equiv_{\mathcal{C}_n} H_n G n ≡ C n H n by Theorem 6.4 , so Duplicator wins the n n n -pebble bijection game on G n G_n G n and H n H_n H n by Corollary 6.7. Thus Duplicator wins the ( Sym V , n ) (\operatorname{Sym}_V,n) ( Sym V , n ) -pebble game.
It is convenient to instead have families of structures on which Duplicator wins the ( Alt n , k ) (\operatorname{Alt}_n,k) ( Alt n , k ) -pebble game, where Alt n ≤ Sym n \operatorname{Alt}_n \leq\operatorname{Sym}_n Alt n ≤ Sym n is the alternating group consisting of all even permutations of [ n ] [n] [ n ] [8 ] . The following theorem provides a way to translate Duplicator strategies for the ( Sym n , k ) (\operatorname{Sym}_n,k) ( Sym n , k ) -pebble game on graphs to the ( Alt n , k ) (\operatorname{Alt}_n,k) ( Alt n , k ) -pebble game.
Theorem 6.9. Let G G G and H H H be nonisomorphic graphs on the same set of vertices V V V , interpreted as τ g r a p h \tau_{\mathrm{graph}} τ graph -structures, such that Duplicator wins the ( Sym V , k ) (\operatorname{Sym}_V,k) ( Sym V , k ) -pebble game on G G G and H H H . There are nonisomorphic graphs G ′ G' G ′ and H ′ H' H ′ on vertices V ′ V' V ′ with ∣ V ′ ∣ = ∣ V ∣ + k + 2 |V'| = |V| + k + 2 ∣ V ′ ∣ = ∣ V ∣ + k + 2 such that Duplicator wins the ( Alt V ′ , k ) (\operatorname{Alt}_{V'},k) ( Alt V ′ , k ) -pebble game on G ′ G' G ′ and H ′ H' H ′ .
Proof. Add k + 2 k+2 k + 2 isolated vertices to each of G G G and H H H to form G ′ G' G ′ and H ′ H' H ′ . Let I I I be the set of isolated vertices added. We have V ′ = V ∪ I V' = V \cup I V ′ = V ∪ I . In the ( Alt V ′ , k ) (\operatorname{Alt}_{V'},k) ( Alt V ′ , k ) -pebble game on G ′ G' G ′ and H ′ H' H ′ , Duplicator will play only bijections that map vertices in V V V to vertices in V V V and vertices in I I I to vertices in I I I , so no pair of pebbles ( a i , b i ) (a_i,b_i) ( a i , b i ) will ever map a vertex in V V V to a vertex in I I I or vice versa.
Our strategy is as follows. Suppose that in the ( Sym V , k ) (\operatorname{Sym}_V,k) ( Sym V , k ) -pebble game, ignoring the vertices I I I , Duplicator would play σ ∈ Sym V \sigma\in\operatorname{Sym}_V σ ∈ Sym V . Let π ∈ Sym I \pi\in\operatorname{Sym}_I π ∈ Sym I be a bijection on I I I respecting the pebbles placed on I I I , i.e., such that for every pair of pebbles ( a j , b j ) (a_j,b_j) ( a j , b j ) placed on I I I , π ( a j ) = b j \pi(a_j) = b_j π ( a j ) = b j . Since there are only k k k pebbles and ∣ I ∣ = k + 2 |I| = k + 2 ∣ I ∣ = k + 2 , there are at least two distinct isolated vertices i 1 , i 2 ∈ I i_1,i_2 \in I i 1 , i 2 ∈ I which are unpebbled in G ′ G' G ′ . So π ( i 1 i 2 ) \pi(i_1\,i_2) π ( i 1 i 2 ) also respects the pebbles on I I I . Thus, if σ π \sigma\pi σ π , considered by abuse of notation as an element of Sym V ′ \operatorname{Sym}_{V'} Sym V ′ , is an even permutation, Duplicator plays σ π \sigma\pi σ π . If σ π \sigma\pi σ π is odd, then it plays σ π ( i 1 i 2 ) \sigma\pi(i_1\,i_2) σ π ( i 1 i 2 ) , which is even. This strategy simulates the ( Sym V , k ) (\operatorname{Sym}_V,k) ( Sym V , k ) -pebble game strategy on the reduction to V V V and wins since the pebbles on I I I cannot cause a partial isomorphism violation.
We usually have k ≤ ∣ V ∣ k \leq|V| k ≤ ∣ V ∣ since Spoiler always wins if there are more pebbles than domain elements and the structures are nonisomorphic. Then ∣ V ′ ∣ ≤ 2 ∣ V ∣ + 2 |V'| \leq2|V| + 2 ∣ V ′ ∣ ≤ 2∣ V ∣ + 2 and so Theorem 6.9 involves merely a constant factor blowup. It can easily be generalized to arbitrary relational structures. Applying Theorem 6.9 to the CFI graphs, we obtain graphs on which Duplicator wins the ( Alt n , k ) (\operatorname{Alt}_n,k) ( Alt n , k ) -pebble game.
Corollary 6.10. There are families of graphs ( G n ) n (G_n)_n ( G n ) n and ( H n ) n (H_n)_n ( H n ) n , interpreted as τ g r a p h \tau_{\mathrm{graph}} τ graph -structures, where G n G_n G n and H n H_n H n have vertices V V V with ∣ V ∣ = O ( n ) |V| = O(n) ∣ V ∣ = O ( n ) such that each G n G_n G n and H n H_n H n are not isomorphic and Duplicator wins the ( Alt V , k ) (\operatorname{Alt}_V,k) ( Alt V , k ) -pebble game on G n G_n G n and H n H_n H n for some k = Ω ( n ) k = \Omega(n) k = Ω ( n ) . Furthermore, there is a polynomial-time algorithm which outputs “yes” on every G n G_n G n and “no” on every H n H_n H n .
Proof. Apply the transformation of Theorem 6.9 to the CFI graphs of Theorems 6.4 and 6.8 . For the “furthermore” part, the algorithm simply removes the k + 2 k+2 k + 2 isolated vertices and applies the algorithm separating the CFI graphs of Theorem 6.4 .
We call ( G n ) n (G_n)_n ( G n ) n and ( H n ) n (H_n)_n ( H n ) n the Alt-CFI graphs. There is a polynomial-time τ g r a p h \tau_{\mathrm{graph}} τ graph -property, the Alt-CFI property P C F I A l t \mathcal{P}^{\mathrm{Alt}}_{\mathrm{CFI}} P CFI Alt , such that G n ∈ P C F I A l t G_n \in\mathcal{P}^{\mathrm{Alt}}_{\mathrm{CFI}} G n ∈ P CFI Alt and H n ∉ P C F I A l t H_n \notin\mathcal{P}^{\mathrm{Alt}}_{\mathrm{CFI}} H n ∈ / P CFI Alt for each $n.
The classical restriction of the partial trace game
Definition 6.11. A base observable set O \mathcal{O} O for a group Γ ≤ U ( H n τ ) \Gamma\leq\mathrm{U}(\mathcal{H}^{\tau}_{n}) Γ ≤ U ( H n τ ) is a set of observables on H n τ \mathcal{H}^{\tau}_{n} H n τ which is closed under conjugation by Γ \Gamma Γ : for every O ∈ O O \in\mathcal{O} O ∈ O and every U ∈ Γ U \in\Gamma U ∈ Γ , U O U † ∈ O UOU^{\dagger} \in\mathcal{O} U O U † ∈ O .
The classical base observable set for a classical unitary group Γ G \Gamma_{G} Γ G on a Hilbert space H = ( C 2 ) ⊗ m \mathcal{H} = (\mathbb{C}^{2})^{\otimes m} H = ( C 2 ) ⊗ m of m m m qubits is O c l a s = { O i : i ∈ [ m ] } \mathcal{O}_{\mathrm{clas}} = \{O_{i}: i \in[m]\} O clas = { O i : i ∈ [ m ]} , where
O i = ∣ 1 ⟩ i ⟨ 1 ∣ i ⊗ I [ m ] ∖ { i } . O_{i} = |1\rangle_{i}\langle1|_{i} \otimes I_{[m]\setminus\{i\}}. O i = ∣1 ⟩ i ⟨ 1 ∣ i ⊗ I [ m ] ∖ { i } .
The subscripts indicate the qubits each tensor product component acts upon. Each observable O i O_{i} O i applies the projection ∣ 1 ⟩ ⟨ 1 ∣ |1\rangle\langle1| ∣1 ⟩ ⟨ 1∣ on the i i i th qubit and acts trivially on the other qubits.
A set of pebbles P ⊆ P P \subseteq\mathcal{P} P ⊆ P supports an observable O O O if every U ∈ ⋂ P U \in\bigcap P U ∈ ⋂ P commutes with O O O . A unitary U ∈ Γ U \in\Gamma U ∈ Γ is an O \mathcal{O} O -partial isomorphism with respect to P P P from ∣ A ⟩ |A\rangle ∣ A ⟩ to ∣ B ⟩ |B\rangle ∣ B ⟩ if for every base observable O ∈ O O \in\mathcal{O} O ∈ O which is supported by P P P , we have
⟨ A ∣ O ∣ A ⟩ = ⟨ B ∣ U O U † ∣ B ⟩ . \langle A|O|A\rangle= \langle B|UOU^{\dagger}|B\rangle. ⟨ A ∣ O ∣ A ⟩ = ⟨ B ∣ U O U † ∣ B ⟩ .
Definition 6.12. The quantum ( Γ , P , O , k ) (\Gamma,\mathcal{P},\mathcal{O},k) ( Γ , P , O , k ) -pebble game on ∣ A ⟩ |A\rangle ∣ A ⟩ and ∣ B ⟩ |B\rangle ∣ B ⟩ is defined as follows. The state of the game consists of a subset of pebbles P ⊆ P P \subseteq\mathcal{P} P ⊆ P with ∣ P ∣ ≤ k |P| \leq k ∣ P ∣ ≤ k and a unitary U ∈ Γ U \in\Gamma U ∈ Γ . Initially, no pebbles are placed and U = I U = I U = I . Each round proceeds as follows.
Optionally, Spoiler removes a pebble from P P P . If ∣ P ∣ = k |P| = k ∣ P ∣ = k , Spoiler must remove a pebble.
Duplicator chooses a unitary V ∈ ⋂ P V \in\bigcap P V ∈ ⋂ P and sets U : = U V U := UV U := U V .
Spoiler chooses a pebble from P ∖ P \mathcal{P} \setminus P P ∖ P and adds it to P P P .
Spoiler wins if U U U is not an O \mathcal{O} O -partial isomorphism from ∣ A ⟩ |A\rangle ∣ A ⟩ to ∣ B ⟩ |B\rangle ∣ B ⟩ with respect to P P P . Otherwise, play continues, and Duplicator wins if it has a strategy to play forever.
Lemma 6.13. Let Γ G ≤ U ( H n τ ) \Gamma_{G} \leq\mathrm{U}(\mathcal{H}^{\tau}_{n}) Γ G ≤ U ( H n τ ) be a classical unitary group , and let P G \mathcal{P}_{G} P G be its classical pebble set. Suppose P ⊆ P G P \subseteq\mathcal{P}_{G} P ⊆ P G are the classical pebble groups corresponding to the stabilizers of some set P ′ ⊆ [ n ] P^{\prime} \subseteq[n] P ′ ⊆ [ n ] of domain elements. Let A , B \mathcal{A},\mathcal{B} A , B be τ \tau τ -structures. If G = Sym n G = \operatorname{Sym}_{n} G = Sym n or Alt n \operatorname{Alt}_{n} Alt n and ∣ P ∣ ≤ n − 3 |P| \leq n-3 ∣ P ∣ ≤ n − 3 , then U σ ∈ Γ G U_{\sigma} \in\Gamma_{G} U σ ∈ Γ G is an O c l a s \mathcal{O}_{\mathrm{clas}} O clas -partial isomorphism with respect to P P P from ∣ A ⟩ |\mathcal{A}\rangle ∣ A ⟩ to ∣ B ⟩ |\mathcal{B}\rangle ∣ B ⟩ if and only if σ \sigma σ is a partial isomorphism with respect to P ′ P^{\prime} P ′ from A \mathcal{A} A to B \mathcal{B} B .
Proof. Since ∣ P ′ ∣ = ∣ P ∣ ≤ n − 3 |P^{\prime}| = |P| \leq n-3 ∣ P ′ ∣ = ∣ P ∣ ≤ n − 3 and G = Sym n G = \operatorname{Sym}_{n} G = Sym n or Alt n \operatorname{Alt}_{n} Alt n , every domain element j ∈ [ n ] j \in[n] j ∈ [ n ] which is not in P ′ P^{\prime} P ′ is moved by some even permutation σ ∈ Stab G ( P ′ ) \sigma\in\operatorname{Stab}_{G}(P^{\prime}) σ ∈ Stab G ( P ′ ) , namely the cyclic permutation ( j j ′ j ′ ′ ) (j\ j'\ j'') ( j j ′ j ′′ ) between j j j and two other distinct domain elements j ′ , j ′ ′ ∉ P ′ j',j'' \notin P^{\prime} j ′ , j ′′ ∈ / P ′ . So each base observable O ( i , n ⃗ ) ∈ O c l a s O_{(i,\vec{n})} \in\mathcal{O}_{\mathrm{clas}} O ( i , n ) ∈ O clas is supported by P P P if and only if n ⃗ ⊆ P ′ \vec{n} \subseteq P^{\prime} n ⊆ P ′ . For each U σ ∈ Γ G U_{\sigma} \in\Gamma_{G} U σ ∈ Γ G ,
⟨ A ∣ O ( i , n ⃗ ) ∣ A ⟩ = ⟨ B ∣ U σ O ( i , n ⃗ ) U σ † ∣ B ⟩ \langle\mathcal{A}|O_{(i,\vec{n})}|\mathcal{A}\rangle= \langle\mathcal{B}|U_{\sigma}O_{(i,\vec{n})}U_{\sigma}^{\dagger}|\mathcal{B}\rangle ⟨ A ∣ O ( i , n ) ∣ A ⟩ = ⟨ B ∣ U σ O ( i , n ) U σ † ∣ B ⟩ is equivalent to n ⃗ ∈ R i A \vec{n} \in R_{i}^{\mathcal{A}} n ∈ R i A holding just when σ ( n ⃗ ) ∈ R i B \sigma(\vec{n}) \in R_{i}^{\mathcal{B}} σ ( n ) ∈ R i B , so the notions of partial isomorphism are equivalent.
Lemma 6.14. Let Γ G \Gamma_{G} Γ G be a classical unitary group, let P ⊆ P G P \subseteq\mathcal{P}_{G} P ⊆ P G , and let ∣ A ⟩ , ∣ B ⟩ ∈ H n τ |\mathcal{A}\rangle,|\mathcal{B}\rangle\in\mathcal{H}^{\tau}_{n} ∣ A ⟩ , ∣ B ⟩ ∈ H n τ be computational basis states encoding classical structures. U ∈ Γ G U \in\Gamma_{G} U ∈ Γ G is an O c l a s \mathcal{O}_{\mathrm{clas}} O clas -partial isomorphism from ∣ A ⟩ |\mathcal{A}\rangle ∣ A ⟩ to ∣ B ⟩ |\mathcal{B}\rangle ∣ B ⟩ if and only if it is a P T PT P T partial isomorphism from ∣ A ⟩ |\mathcal{A}\rangle ∣ A ⟩ to ∣ B ⟩ |\mathcal{B}\rangle ∣ B ⟩ , both with respect to P P P .
Proof. P P P supports each O ( i , n ⃗ ) = ∣ 1 ⟩ ( i , n ⃗ ) ⟨ 1 ∣ ( i , n ⃗ ) ⊗ I ∈ O c l a s O_{(i,\vec{n})} = |1\rangle_{(i,\vec{n})}\langle1|_{(i,\vec{n})} \otimes I \in O_{\mathrm{clas}} O ( i , n ) = ∣1 ⟩ ( i , n ) ⟨ 1 ∣ ( i , n ) ⊗ I ∈ O clas if and only if qubit ( i , n ⃗ ) (i,\vec{n}) ( i , n ) is not moved by P P P , that is, ( i , n ⃗ ) ∈ Q P T (i,\vec{n}) \in Q^T_P ( i , n ) ∈ Q P T . Since U ∈ Γ G U \in\Gamma_G U ∈ Γ G just permutes the qubits,
Tr Q P T ‾ ( ∣ A ⟩ ⟨ A ∣ ) and Tr Q P T ‾ ( U † ∣ B ⟩ ⟨ B ∣ U ) \operatorname{Tr}_{\overline{Q^T_P}}(|A\rangle\langle A|) \quad\text{and}\quad\operatorname{Tr}_{\overline{Q^T_P}}(U^\dagger|B\rangle\langle B|U) Tr Q P T ( ∣ A ⟩ ⟨ A ∣ ) and Tr Q P T ( U † ∣ B ⟩ ⟨ B ∣ U )
are both computational basis states, so they are equal if and only if
⟨ A ∣ O ( i , n ⃗ ) ∣ A ⟩ = ⟨ B ∣ U O ( i , n ⃗ ) U † ∣ B ⟩ \langle A|O_{(i,\vec{n})}|A\rangle= \langle B|UO_{(i,\vec{n})}U^\dagger|B\rangle ⟨ A ∣ O ( i , n ) ∣ A ⟩ = ⟨ B ∣ U O ( i , n ) U † ∣ B ⟩
for all ( i , n ⃗ ) ∈ Q P T (i,\vec{n}) \in Q^T_P ( i , n ) ∈ Q P T , since O ( i , n ⃗ ) O_{(i,\vec{n})} O ( i , n ) measures qubit ( i , n ⃗ ) (i,\vec{n}) ( i , n ) in the computational basis. □
Corollary 6.15. On classical structures, the ( Γ G , P G , k ) (\Gamma_G,P_G,k) ( Γ G , P G , k ) -PT quantum pebble game is equivalent to the quantum ( Γ G , P G , O c l a s , k ) (\Gamma_G,P_G,O_{\mathrm{clas}},k) ( Γ G , P G , O clas , k ) -pebble game.
We can then show that the PT quantum pebble game also cannot distinguish the CFI graphs.
Proposition 6.16. Let ( G n ) n (G_n)_n ( G n ) n and ( H n ) n (H_n)_n ( H n ) n be the families of CFI graphs of Theorem 6.4 , interpreted as τ g r a p h \tau_{\mathrm{graph}} τ graph -structures, and suppose G n G_n G n and H n H_n H n have the same set of vertices V V V . Let G = Sym V G=\operatorname{Sym}_V G = Sym V . Then for n ≥ 3 n\ge3 n ≥ 3 , Duplicator wins the ( Γ G , P G , k ) (\Gamma_G,P_G,k) ( Γ G , P G , k ) -PT quantum pebble game on G n G_n G n and H n H_n H n for some k = Ω ( n ) k=\Omega(n) k = Ω ( n ) .
Proof. By Theorem 6.8 , Duplicator wins the ( Sym V , n ) (\operatorname{Sym}_V,n) ( Sym V , n ) -pebble game on G n G_n G n and H n H_n H n . Let k = n − 2 k=n-2 k = n − 2 . Reducing the number of pebbles only makes a pebble game easier for Duplicator, so Duplicator also wins the ( Sym V , k ) (\operatorname{Sym}_V,k) ( Sym V , k ) -pebble game on G n G_n G n and H n H_n H n . Since n ≤ ∣ V ∣ − 1 n\le|V|-1 n ≤ ∣ V ∣ − 1 by Theorem 6.4 , we have k ≤ ∣ V ∣ − 3 k\le|V|-3 k ≤ ∣ V ∣ − 3 , so by Lemma 6.13 , O c l a s O_{\mathrm{clas}} O clas -partial isomorphism is equivalent to classical partial isomorphism in this setting with at most k k k pebbles. Thus Duplicator wins the quantum ( Γ G , P G , O c l a s , k ) (\Gamma_G,P_G,O_{\mathrm{clas}},k) ( Γ G , P G , O clas , k ) -pebble game on G n G_n G n and H n H_n H n . By Corollary 6.15 , it also wins the ( Γ G , P G , k ) (\Gamma_G,P_G,k) ( Γ G , P G , k ) -PT quantum pebble game. □
Similarly, by the same proof and Corollary 6.15 :
Proposition 6.17. Let ( G n ) n (G_n)_n ( G n ) n and ( H n ) n (H_n)_n ( H n ) n be the families of Alt-CFI graphs of Corollary 6.10, interpreted as τ g r a p h \tau_{\mathrm{graph}} τ graph -structures, and suppose G n G_n G n and H n H_n H n have the same set of vertices V V V . Let G = Alt V G=\operatorname{Alt}_V G = Alt V . Then for n ≥ 3 n\ge3 n ≥ 3 , Duplicator wins the ( Γ G , P G , k ) (\Gamma_G,P_G,k) ( Γ G , P G , k ) -PT quantum pebble game on G n G_n G n and H n H_n H n for some k = Ω ( n ) k=\Omega(n) k = Ω ( n ) .
Circuit size and entanglement width
The following lemma connects bounds on orbit size to bounds on circuit size and entanglement width. We obtain a tradeoff between these two parameters for a given lower bound on orbit size.
Lemma 6.18. Let G ≤ Sym n G\le\operatorname{Sym}_n G ≤ Sym n . Let ( C n ) n (C_n)_n ( C n ) n be a family of Γ G \Gamma_G Γ G -symmetric output quantum τ \tau τ -circuits over a gateset whose gates act on at most r r r wires, where r r r is constant. For 1 ≤ ℓ ≤ ∣ W n ∣ 1\le\ell\le|W_n| 1 ≤ ℓ ≤ ∣ W n ∣ , where W n W_n W n is the wire set of C n C_n C n , we have
max-orbit ℓ ( C n ) ≤ ( max { r ⋅ s ( C n ) + 1 , ℓ τ ( n ) } ) ℓ . \operatorname{max\text{-}orbit}_{\ell}(C_n) \le\left(\max\{r\cdot s(C_n)+1,\ell_{\tau}(n)\}\right)^{\ell}. max - orbit ℓ ( C n ) ≤ ( max { r ⋅ s ( C n ) + 1 , ℓ τ ( n )} ) ℓ . In particular, for every function f : Z + → Z + f:\mathbb{Z}_{+}\to\mathbb{Z}_{+} f : Z + → Z + with f ( n ) = ω ( log n ) f(n)=\omega(\log n) f ( n ) = ω ( log n ) , if s ( C n ) = 2 o ( f ( n ) ) s(C_n)=2^{o(f(n))} s ( C n ) = 2 o ( f ( n )) , then max-orbit ℓ ( C n ) = 2 o ( ℓ ⋅ f ( n ) ) \operatorname{max\text{-}orbit}_{\ell}(C_n)=2^{o(\ell\cdot f(n))} max - orbit ℓ ( C n ) = 2 o ( ℓ ⋅ f ( n )) .
Proof. Let W n = X n ⊔ A n W_n=X_n\sqcup A_n W n = X n ⊔ A n be the wires of C n C_n C n , where X n X_n X n are the input wires and A n A_n A n are the ancilla wires. Let E n E_n E n be the set of ancilla wires on which no gate acts, excluding the designated output wire, and set R n = A n ∖ E n R_n=A_n\setminus E_n R n = A n ∖ E n . Every circuit automorphism preserves E n E_n E n , and every permutation of
E n E_n E n fixing the other wires is an internal automorphism. In the In ( C ) \operatorname{In}(C) In ( C ) -orbit [ w ⃗ ] [\vec{w}] [ w ] of an ordered tuple w ⃗ \vec{w} w , the positions occupied by wires in E n E_n E n are thus fixed, while the particular unused wires in those positions can be permuted freely. Hence we can remove those positions from w ⃗ \vec{w} w without changing the size of the orbit of [ w ⃗ ] [\vec{w}] [ w ] under Aut ( C ) / In ( C ) \operatorname{Aut}(C)/\operatorname{In}(C) Aut ( C ) / In ( C ) .
Hence, choose a tuple w ⃗ \vec{w} w such that the size of the Aut ( C ) / In ( C ) \operatorname{Aut}(C)/\operatorname{In}(C) Aut ( C ) / In ( C ) -orbit of [ w ⃗ ] [\vec{w}] [ w ] is maximized, and suppose w ⃗ \vec{w} w has a a a positions containing wires in R n R_n R n and b b b positions containing input wires. Then a + b ≤ ℓ a+b\leq\ell a + b ≤ ℓ . We have
max-orbit ℓ ( C n ) ≤ ∣ R n ∣ a ∣ X n ∣ b ≤ max { ∣ R n ∣ , ∣ X n ∣ } ℓ . \operatorname{max\text{-}orbit}_{\ell}(C_n)\leq|R_n|^a|X_n|^b\leq\max\{|R_n|,|X_n|\}^{\ell}. max - orbit ℓ ( C n ) ≤ ∣ R n ∣ a ∣ X n ∣ b ≤ max { ∣ R n ∣ , ∣ X n ∣ } ℓ .
For the vocabulary τ \tau τ , there are ∣ X n ∣ = ℓ τ ( n ) |X_n|=\ell_{\tau}(n) ∣ X n ∣ = ℓ τ ( n ) input wires. At most r ⋅ s ( C n ) r\cdot s(C_n) r ⋅ s ( C n ) nonempty ancilla wires are acted on by gates. Retaining the output wire contributes at most one further wire, so ∣ R n ∣ ≤ r ⋅ s ( C n ) + 1 |R_n|\leq r\cdot s(C_n)+1 ∣ R n ∣ ≤ r ⋅ s ( C n ) + 1 . It follows that
max-orbit ℓ ( C n ) ≤ ( max { r ⋅ s ( C n ) + 1 , ℓ τ ( n ) } ) ℓ . \operatorname{max\text{-}orbit}_{\ell}(C_n)\leq\left(\max\{r\cdot s(C_n)+1,\ell_{\tau}(n)\}\right)^{\ell}. max - orbit ℓ ( C n ) ≤ ( max { r ⋅ s ( C n ) + 1 , ℓ τ ( n )} ) ℓ .
In particular, if s ( C n ) = 2 o ( f ( n ) ) s(C_n)=2^{o(f(n))} s ( C n ) = 2 o ( f ( n )) for f ( n ) = ω ( log n ) f(n)=\omega(\log n) f ( n ) = ω ( log n ) , then max-orbit ℓ ( C n ) = 2 o ( ℓ ⋅ f ( n ) ) \operatorname{max\text{-}orbit}_{\ell}(C_n)=2^{o(\ell\cdot f(n))} max - orbit ℓ ( C n ) = 2 o ( ℓ ⋅ f ( n )) since ℓ τ ( n ) = poly ( n ) = 2 o ( f ( n ) ) \ell_{\tau}(n)=\operatorname{poly}(n)=2^{o(f(n))} ℓ τ ( n ) = poly ( n ) = 2 o ( f ( n )) and r r r is constant.
For graph inputs and gates acting on at most two wires, we obtain the bound
max-orbit ℓ ( C n ) ≤ ( max { 2 s ( C n ) + 1 , n 2 } ) ℓ (31) \operatorname{max\text{-}orbit}_{\ell}(C_n)\leq\left(\max\{2s(C_n)+1,n^2\}\right)^{\ell} \tag*{(31)} max - orbit ℓ ( C n ) ≤ ( max { 2 s ( C n ) + 1 , n 2 } ) ℓ (31)
for 1 ≤ ℓ ≤ ∣ W n ∣ 1\leq\ell\leq|W_n| 1 ≤ ℓ ≤ ∣ W n ∣ . This identifies the circuit-size contribution to the lower-bound argument. The support theorem then relates these orbit sizes to the number of pebbles needed in the indistinguishability theorem.
Theorem 6.19. Let G = Alt n G=\operatorname{Alt}_n G = Alt n . Let ( k n ) n (k_n)_n ( k n ) n and ( ℓ n ) n (\ell_n)_n ( ℓ n ) n be sequences of positive integers such that k n ≤ n k_n\leq n k n ≤ n and k n / ℓ n = ω ( log n ) k_n/\ell_n=\omega(\log n) k n / ℓ n = ω ( log n ) . Suppose that ( A n ) n (\mathcal{A}_n)_n ( A n ) n and ( B n ) n (\mathcal{B}_n)_n ( B n ) n are families of τ \tau τ -structures of order n n n such that for infinitely many n n n , Duplicator wins the ( Γ G , P G , k n ) (\Gamma_G,\mathcal{P}_G,k_n) ( Γ G , P G , k n ) -ℓ n \ell_n ℓ n -PT quantum pebble game on ∣ A n ⟩ |\mathcal{A}_n\rangle ∣ A n ⟩ and ∣ B n ⟩ |\mathcal{B}_n\rangle ∣ B n ⟩ . Let P \mathcal{P} P be any property separating ( A n ) n (\mathcal{A}_n)_n ( A n ) n and ( B n ) n (\mathcal{B}_n)_n ( B n ) n . Then, there is no family of Γ G \Gamma_G Γ G -symmetric quantum τ \tau τ -circuits ( C n ) n (C_n)_n ( C n ) n computing P \mathcal{P} P which, for sufficiently large n n n , has both entanglement width
η ( C n ) ≤ ℓ n \eta(C_n)\leq\ell_n η ( C n ) ≤ ℓ n and size
s ( C n ) ≤ 2 min { k n / 2 , n / 4 − 1 } / ℓ n − 1 − 1 2 . s(C_n)\leq2^{\min\{k_n/2,n/4-1\}/\ell_n-1}-\frac{1}{2}. s ( C n ) ≤ 2 m i n { k n /2 , n /4 − 1 } / ℓ n − 1 − 2 1 .
Proof. Let ( C n ) n (C_n)_n ( C n ) n be a family of such quantum circuits computing P \mathcal{P} P , and suppose η ( C n ) ≤ ℓ n \eta(C_n)\leq\ell_n η ( C n ) ≤ ℓ n . By the partition-symmetry result (Theorem 4.12), each C n C_n C n has η ( C n ) \eta(C_n) η ( C n ) -partition symmetry. The group Alt n \operatorname{Alt}_n Alt n has distinct stabilizers for n ≥ 4 n\geq4 n ≥ 4 . Then by the indistinguishability theorem (Theorem 5.2 ), for n ≥ 4 n\geq4 n ≥ 4 , if max-supp η ( C n ) ( C n ) ≤ k n / 2 \operatorname{max\text{-}supp}_{\eta(C_n)}(C_n)\leq k_n/2 max - supp η ( C n ) ( C n ) ≤ k n /2 and Duplicator wins the ( Γ G , P G , k n ) (\Gamma_G,\mathcal{P}_G,k_n) ( Γ G , P G , k n ) -η ( C n ) \eta(C_n) η ( C n ) -PT quantum pebble game on ∣ A n ⟩ |\mathcal{A}_n\rangle ∣ A n ⟩ and ∣ B n ⟩ |\mathcal{B}_n\rangle ∣ B n ⟩ , then C n [ ∣ A n ⟩ ] = C n [ ∣ B n ⟩ ] C_n[|\mathcal{A}_n\rangle]=C_n[|\mathcal{B}_n\rangle] C n [ ∣ A n ⟩] = C n [ ∣ B n ⟩] , contradicting the assumption that ( C n ) n (C_n)_n ( C n ) n computes P \mathcal{P} P . Hence we must have max-supp η ( C n ) ( C n ) > k n / 2 \operatorname{max\text{-}supp}_{\eta(C_n)}(C_n)>k_n/2 max - supp η ( C n ) ( C n ) > k n /2 for infinitely many n n n .
By the quantum support theorem (Theorem 4.8 ), either max-orbit η ( C n ) ( C n ) > 2 n / 4 − 1 \operatorname{max\text{-}orbit}_{\eta(C_n)}(C_n)>2^{n/4-1} max - orbit η ( C n ) ( C n ) > 2 n /4 − 1 or max-supp η ( C n ) ( C n ) ≤ log 2 max-orbit η ( C n ) ( C n ) \operatorname{max\text{-}supp}_{\eta(C_n)}(C_n)\leq\log_2\operatorname{max\text{-}orbit}_{\eta(C_n)}(C_n) max - supp η ( C n ) ( C n ) ≤ log 2 max - orbit η ( C n ) ( C n ) . It is clear that max-orbit ℓ ( C n ) \operatorname{max\text{-}orbit}_{\ell}(C_n) max - orbit ℓ ( C n ) is non-decreasing with ℓ \ell ℓ . Hence we obtain
max-orbit ℓ n ( C n ) ≥ max-orbit η ( C n ) ( C n ) > 2 min { k n / 2 , n / 4 − 1 } (32) \operatorname{max\text{-}orbit}_{\ell_n}(C_n)\geq\operatorname{max\text{-}orbit}_{\eta(C_n)}(C_n)>2^{\min\{k_n/2,n/4-1\}} \tag*{(32)} max - orbit ℓ n ( C n ) ≥ max - orbit η ( C n ) ( C n ) > 2 m i n { k n /2 , n /4 − 1 } (32)
for infinitely many n n n . Applying Lemma 6.18 with r = 2 r = 2 r = 2 , we get
max { 2 s ( C n ) + 1 , ℓ τ ( n ) } > 2 min { k n / 2 , n / 4 − 1 } / ℓ n . (33) \max\{2s(C_n) + 1, \ell_{\tau}(n)\} > 2^{\min\{k_n/2,n/4-1\}/\ell_n}. \tag*{(33)} max { 2 s ( C n ) + 1 , ℓ τ ( n )} > 2 m i n { k n /2 , n /4 − 1 } / ℓ n . (33)
Since k n / ℓ n = ω ( log n ) k_n/\ell_n = \omega(\log n) k n / ℓ n = ω ( log n ) , the right-hand side of (33) eventually exceeds ℓ τ ( n ) = p o l y ( n ) \ell_{\tau}(n) = poly(n) ℓ τ ( n ) = p o l y ( n ) . Hence we can drop ℓ τ ( n ) \ell_{\tau}(n) ℓ τ ( n ) from the left-hand side, obtaining the bound
s ( C n ) > 2 min { k n / 2 , n / 4 − 1 } / ℓ n − 1 − 1 2 s(C_n) > 2^{\min\{k_n/2,n/4-1\}/\ell_n-1} - \frac{1}{2} s ( C n ) > 2 m i n { k n /2 , n /4 − 1 } / ℓ n − 1 − 2 1
which holds for infinitely many n n n .
Proof of Theorem 6.1 . Write m m m for the construction index of the Alt-CFI pairs in Corollary 6.10, and let N m N_m N m be their actual number of vertices. The original CFI graphs have between m + 1 m + 1 m + 1 and O ( m ) O(m) O ( m ) vertices, and the padding adds only O ( m ) O(m) O ( m ) vertices. Thus N m = Θ ( m ) N_m = \Theta(m) N m = Θ ( m ) and the orders N m N_m N m are unbounded.
By Proposition 6.17 , Duplicator wins the full ( Γ A l t N m , P A l t N m , k N m ) (\Gamma_{\mathrm{Alt}_{N_m}},\mathcal{P}_{\mathrm{Alt}_{N_m}}, k_{N_m}) ( Γ Alt N m , P Alt N m , k N m ) -PT quantum pebble game on these pairs for k N m = Ω ( m ) = Ω ( N m ) k_{N_m} = \Omega(m) = \Omega(N_m) k N m = Ω ( m ) = Ω ( N m ) . It consequently wins the corresponding ℓ \ell ℓ -PT game for every ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 .
Apply Theorem 6.19 to any family of Γ A l t n \Gamma_{\mathrm{Alt}_n} Γ Alt n -symmetric output quantum circuits ( C n ) n (C_n)_n ( C n ) n which separates the CFI pairs at each N m N_m N m . For the conditions of that theorem, let ( ℓ n ) n (\ell_n)_n ( ℓ n ) n be any sequence of integers with ℓ n = O ( n / f ( n ) ) \ell_n = O(n/f(n)) ℓ n = O ( n / f ( n )) , and take k n = Θ ( n ) k_n = \Theta(n) k n = Θ ( n ) where k N m k_{N_m} k N m is as above. Then k n / ℓ n = Ω ( f ( n ) ) = ω ( log n ) k_n/\ell_n = \Omega(f(n)) = \omega(\log n) k n / ℓ n = Ω ( f ( n )) = ω ( log n ) . We obtain that there is no such family of circuits with both entanglement width η ( C n ) = O ( n / f ( n ) ) \eta(C_n) = O(n/f(n)) η ( C n ) = O ( n / f ( n )) and size s ( C n ) = 2 o ( f ( n ) ) s(C_n) = 2^{o(f(n))} s ( C n ) = 2 o ( f ( n )) .
We remark on the constant factors in Theorem 6.1 , Theorem 1.1 , and its corollaries. The quantitative lower bound on the size of symmetric circuits distinguishing the Alt-CFI graphs is determined by the constant c c c such that for large enough n n n , Duplicator wins the ( A l t n , k ) (\mathrm{Alt}_n,k) ( Alt n , k ) -pebble game for some k ≥ c n k \ge cn k ≥ c n , where n n n is the number of vertices. We give a lower bound on c c c .
A calculation by Pikhurko, Veith, and Verbitsky [17 sec. 7.5] shows that on the original CFI graphs, for a large enough number of vertices n ′ n' n ′ , Duplicator wins the ( S y m n ′ , k ) (\mathrm{Sym}_{n'},k) ( Sym n ′ , k ) -pebble game for some k ≥ 0.00465 n ′ k \ge0.00465n' k ≥ 0.00465 n ′ . In particular, Duplicator wins for k = ⌈ 0.00465 n ′ ⌉ k = \lceil0.00465n' \rceil k = ⌈ 0.00465 n ′ ⌉ pebbles. The construction in Corollary 6.10 increases the number of vertices by k + 2 k + 2 k + 2 : hence using this value of k k k , the Alt-CFI graphs have n ≤ 1.00465 n ′ + 3 n \le1.00465n' + 3 n ≤ 1.00465 n ′ + 3 vertices. Hence, with this construction, Duplicator wins the ( A l t n , k ) (\mathrm{Alt}_n,k) ( Alt n , k ) -pebble game on the Alt-CFI graphs for k ≥ 0.00465 1.00465 ( n − 3 ) ≥ 0.00462 n k \ge\frac{0.00465}{1.00465}(n - 3) \ge0.00462n k ≥ 1.00465 0.00465 ( n − 3 ) ≥ 0.00462 n pebbles for large enough n n n , so we obtain a lower bound of c ≥ 0.00462 c \ge0.00462 c ≥ 0.00462 .
Theorem 6.19 then gives the quantitative lower bound
s ( C n ) > 2 0.00231 n / ℓ n − 1 − 1 2 s(C_n) > 2^{0.00231n/\ell_n-1} - \frac{1}{2} s ( C n ) > 2 0.00231 n / ℓ n − 1 − 2 1
on the size of any family of Γ A l t n \Gamma_{\mathrm{Alt}_n} Γ Alt n -symmetric quantum circuits with entanglement width η ( C n ) ≤ ℓ n = o ( n / log n ) \eta(C_n) \le\ell_n = o(n/\log n) η ( C n ) ≤ ℓ n = o ( n / log n ) distinguishing the Alt-CFI graphs; this inequality must be satisfied for infinitely many n n n .
This constant could be improved further, however, by using a more modern variant of the CFI construction: in particular, Schneider and Schweitzer [18 ] show the existence of pairs of graphs on which Duplicator wins the ( S y m n , k ) (\mathrm{Sym}_n,k) ( Sym n , k ) -pebble game for k ≥ 0.0105027 n − o ( n ) k \ge0.0105027n - o(n) k ≥ 0.0105027 n − o ( n ) . (Their argument, however, is nonconstructive.) They study the equivalent notion of Weisfeiler–Leman dimension (WL-dimension): this is the minimum k k k such that the k k k -dimensional Weisfeiler–Leman test can distinguish a graph G G G from any other non-isomorphic graph. It is well-known that Duplicator wins the ( S y m n , k ) (\mathrm{Sym}_n,k) ( Sym n , k ) -pebble game on G G G and H H H if and only if G G G and H H H are not distinguished by the ( k − 1 ) (k - 1) ( k − 1 ) -dimensional Weisfeiler–Leman test [4 ] . See e.g. [15 ] for more on lower bounds on the WL-dimension.
Symmetric simulation of quantum algorithms
We now show that, without restrictions on the entanglement width, it is possible to efficiently simulate every quantum algorithm that computes some graph property. This result can be easily extended to general relational structures, but we focus on graphs for notational simplicity.
The first step is to show that threshold gates can be efficiently computed symmetrically. For a set S S S of h h h control wires and an integer t t t , define Thr S , t ( x ) = 1 { ∑ u ∈ S x u ≥ t } \operatorname{Thr}_{S,t}(x) = \mathbf{1}\{\sum_{u \in S} x_u \ge t\} Thr S , t ( x ) = 1 { ∑ u ∈ S x u ≥ t } . Its reversible implementation flips a separate target bit z ∉ S z \notin S z ∈ / S when Thr S , t ( x ) = 1 \operatorname{Thr}_{S,t}(x) = 1 Thr S , t ( x ) = 1 . This function is clearly Sym S \operatorname{Sym}_S Sym S -symmetric, and we wish to construct a Sym S \operatorname{Sym}_S Sym S -symmetric quantum circuit that efficiently implements it. In order to use our construction in the no-entanglement setting of Theorem 1.5 , we additionally argue that our construction does not generate entanglement on computational-basis inputs.
Lemma 7.1 (Symmetric threshold computation). The map
∣ x ⟩ ∣ z ⟩ ⟼ ∣ x ⟩ ∣ z ⊕ Thr S , t ( x ) ⟩ |x\rangle|z\rangle\longmapsto|x\rangle|z \oplus\operatorname{Thr}_{S,t}(x)\rangle ∣ x ⟩ ∣ z ⟩ ⟼ ∣ x ⟩ ∣ z ⊕ Thr S , t ( x )⟩ has a Sym S \operatorname{Sym}_S Sym S -symmetric implementation using O ( h log h ) O(h \log h) O ( h log h ) one-qubit and two-qubit gates and O ( log h ) O(\log h) O ( log h ) workspace qubits. Furthermore, if the input is in the computational basis, then the state after every gate in this construction is a product state.
Proof. Write w = ∑ u ∈ S x u w = \sum_{u \in S} x_u w = ∑ u ∈ S x u , so that Thr S , t ( x ) = 1 { w ≥ t } \operatorname{Thr}_{S,t}(x) = \mathbf{1}\{w \ge t\} Thr S , t ( x ) = 1 { w ≥ t } . We first design a Sym S \operatorname{Sym}_S Sym S -symmetric quantum circuit that writes the binary expansion of w w w onto m = ⌈ log 2 ( h + 1 ) ⌉ m = \lceil\log_2(h+1) \rceil m = ⌈ log 2 ( h + 1 )⌉ designated ancilla wires. From there, we can decide whether w ≥ t w \ge t w ≥ t in an arbitrary way, as these ancilla wires are dissociated from the symmetries of S S S .
The circuit for obtaining the digits of w w w uses only Hadamard gates H H H and controlled phase gates c R j cR_j c R j , where
R j = ( 1 0 0 e 2 π i / 2 j ) . R_j =
\begin{pmatrix}
1 & 0 \\
0 & e^{2\pi i/2^j}
\end{pmatrix}. R j = ( 1 0 0 e 2 π i / 2 j ) .
First, let c 1 , … , c m c_1,\ldots,c_m c 1 , … , c m be ancillary “counter” qubits starting at ∣ 0 ⟩ |0\rangle ∣0 ⟩ , and apply H H H to each of them to create a uniform superposition. Then, for every u ∈ S u \in S u ∈ S and 1 ≤ j ≤ m 1 \le j \le m 1 ≤ j ≤ m , apply the controlled phase gate c R j cR_j c R j with control qubit u u u and target qubit c j c_j c j . Note that these h m hm hm two-qubit gates commute, even when they share a wire, so they form one layer. This layer is Γ Sym S \Gamma_{\operatorname{Sym}_S} Γ Sym S -symmetric, as any permutation of the qubits indexed by S S S only permutes the gates within this layer.
After these operations, the counter is now
⨂ j = 1 m ∣ 0 ⟩ + e 2 π i w / 2 j ∣ 1 ⟩ 2 = 1 2 m ∑ k = 0 2 m − 1 e 2 π i w k / 2 m ∣ k ⟩ . (34) \bigotimes_{j=1}^{m} \frac{|0\rangle+ e^{2\pi i w/2^j}|1\rangle}{\sqrt{2}}
=
\frac{1}{\sqrt{2^m}}\sum_{k=0}^{2^m-1} e^{2\pi i wk/2^m}|k\rangle. \tag*{(34)} j = 1 ⨂ m 2 ∣0 ⟩ + e 2 π i w / 2 j ∣1 ⟩ = 2 m 1 k = 0 ∑ 2 m − 1 e 2 π i w k / 2 m ∣ k ⟩ . (34)
This is precisely F 2 m ∣ w ⟩ F_{2^m}|w\rangle F 2 m ∣ w ⟩ , where F 2 m F_{2^m} F 2 m is the quantum Fourier transform modulo 2 m 2^m 2 m . By applying its inverse ( F 2 m ) † (F_{2^m})^\dagger ( F 2 m ) † to the counter qubits, we obtain ∣ w ⟩ |w\rangle ∣ w ⟩ . Note that I S ⊗ ( F 2 m ) † I_S \otimes(F_{2^m})^\dagger I S ⊗ ( F 2 m ) † is Γ Sym S \Gamma_{\operatorname{Sym}_S} Γ Sym S -symmetric, as every unitary U π ⊗ I U_\pi\otimes I U π ⊗ I for π ∈ Sym S \pi\in\operatorname{Sym}_S π ∈ Sym S is an automorphism of this circuit.
Finally, one can easily construct a reversible circuit that compares the two m m m -bit integers w , t w,t w , t using O ( m 2 ) O(m^2) O ( m 2 ) Toffoli and NOT gates, and O ( m ) O(m) O ( m ) workspace bits. Since a Toffoli gate can be implemented using five two-qubit gates, this leads to a quantum circuit for deciding whether w ≥ t w \ge t w ≥ t which uses O ( m 2 ) O(m^2) O ( m 2 ) two-qubit gates and O ( m ) O(m) O ( m ) ancillas. Again, as this circuit acts only on the counter ancillas, it is trivially Sym S \operatorname{Sym}_S Sym S -symmetric.
Once this has been done, copy the result using a CNOT to the output wire and undo the whole computation to bring the non-output ancilla qubits back to ∣ 0 ⟩ |0\rangle ∣0 ⟩ . The first part of the result follows.
To argue that the state is maintained in a product state when the input is in the computational basis, we analyze the standard implementations of ( F 2 m ) † (F_{2^m})^\dagger ( F 2 m ) † and the Toffoli gate. First, observe that the control wire of each C R j CR_j C R j gate is in the computational basis when the input is, so no entanglement is produced in the first layer, even between the commuting gates. We use the inverse quantum Fourier transform defined in [16 chap. 5] ; each gate receives its own layer. Observe that when the initial state is of the form in (34) , the control qubits of each two-qubit gate in this construction are in the computational basis: namely, they are the bits of w w w decoded so far. Thus, no entanglement is created.
We use the five-gate Toffoli implementation of [16 Fig. 4.8] , where again each gate is in its own layer. When the input is in the computational basis, so are the control qubits of each two-qubit gate, so no entanglement is created. This yields the second part of the result. □
We can now prove Theorem 1.4 , which shows we can symmetrically simulate any quantum circuit on graph inputs with only a small overhead.
Proof of Theorem 1.4. By first copying the (computational-basis) input several times, running the algorithm on each copy with fresh workspace, and then taking a majority vote on the output qubits, we can assume that the quantum circuits to be simulated are correct with probability at least 0.9. Write r = ⌈ log 2 ( 10 n 2 ) ⌉ r = \lceil\log_2(10n^2) \rceil r = ⌈ log 2 ( 10 n 2 )⌉ and M = 2 r M = 2^r M = 2 r . For each vertex v ∈ [ n ] v \in[n] v ∈ [ n ] , add an r r r -qubit “label” register and apply a Hadamard to each label qubit. These r n rn r n gates form a single layer and prepare the state
1 M n ∑ λ : [ n ] → { 0 , … , M − 1 } ∣ λ ⟩ (35) \frac{1}{\sqrt{M^n}}\sum_{\lambda:[n]\to\{0,\ldots,M-1\}}|\lambda\rangle \tag*{(35)} M n 1 λ : [ n ] → { 0 , … , M − 1 } ∑ ∣ λ ⟩ (35)
on the label registers. We will use these labels to create an ordering of the vertices (in superposition) which does not break the symmetry of the circuit.
First, we describe a classical computation for a fixed label assignment. For each ordered pair ( u , v ) (u,v) ( u , v ) with u ≠ v u \ne v u = v , compute c u , v = 1 { λ ( u ) < λ ( v ) } c_{u,v} = 1\{\lambda(u) < \lambda(v)\} c u , v = 1 { λ ( u ) < λ ( v )} using the same binary comparator for every pair, and set c u , u = 0 c_{u,u} = 0 c u , u = 0 . A binary comparator uses O ( r ) O(r) O ( r ) Boolean gates, and acts symmetrically with respect to the vertices. For every v ∈ [ n ] v \in[n] v ∈ [ n ] and j ∈ [ n ] j \in[n] j ∈ [ n ] , compute the rank indicator
h v , j = 1 { ∑ u ∈ [ n ] c u , v = j − 1 } . h_{v,j}=1\left\{\sum_{u\in[n]}c_{u,v}=j-1\right\}. h v , j = 1 ⎩ ⎨ ⎧ u ∈ [ n ] ∑ c u , v = j − 1 ⎭ ⎬ ⎫ .
If all labels are distinct, then exactly one vertex has each rank j j j . Denote the rank of v v v by θ λ ( v ) \theta_\lambda(v) θ λ ( v ) , so θ λ ∈ Sym n \theta_\lambda\in\operatorname{Sym}_n θ λ ∈ Sym n is a permutation if λ \lambda λ is injective.
For each pair ( i , j ) ∈ [ n ] 2 (i,j)\in[n]^2 ( i , j ) ∈ [ n ] 2 , compute onto a fixed workspace wire
y i , j = ⋁ u , v ∈ [ n ] ( x u , v ∧ h u , i ∧ h v , j ) . y_{i,j}=\bigvee_{u,v\in[n]}\left(x_{u,v}\land h_{u,i}\land h_{v,j}\right). y i , j = u , v ∈ [ n ] ⋁ ( x u , v ∧ h u , i ∧ h v , j ) .
When λ \lambda λ is injective, exactly one pair ( u , v ) (u,v) ( u , v ) contributes to each ( i , j ) (i,j) ( i , j ) , and y = b ( θ λ A ) y=b(\theta_\lambda A) y = b ( θ λ A ) . In this case, these wires contain an isomorphic copy of the input, permuted by θ λ \theta_\lambda θ λ .
The entire classical computation above is symmetric: a permutation σ ∈ Sym n \sigma\in\operatorname{Sym}_n σ ∈ Sym n sends a comparator indexed by ( u , v ) (u,v) ( u , v ) to the one indexed by ( σ ( u ) , σ ( v ) ) (\sigma(u),\sigma(v)) ( σ ( u ) , σ ( v )) , and sends h v , j h_{v,j} h v , j to h σ ( v ) , j h_{\sigma(v),j} h σ ( v ) , j . These rules also specify the action on internal comparator and Boolean clauses. [5 Proposition 1] shows how one can implement a symmetric classical circuit with threshold gates as a symmetric quantum circuit with threshold gates without blowing up its size. Using Lemma 7.1 , we can then implement it as a symmetric quantum circuit using only 1-qubit and 2-qubit gates. Applying it to state (35) , we obtain
1 M n ∑ λ : [ n ] → { 0 , … , M − 1 } ∣ λ ⟩ ∣ b ( θ λ A ) ⟩ . \frac{1}{\sqrt{M^n}}\sum_{\lambda:[n]\to\{0,\ldots,M-1\}}|\lambda\rangle|b(\theta_\lambda A)\rangle. M n 1 λ : [ n ] → { 0 , … , M − 1 } ∑ ∣ λ ⟩ ∣ b ( θ λ A )⟩ .
Run the given quantum algorithm on the second register using fresh workspace. The resulting state can be written as
1 M n ∑ λ : [ n ] → { 0 , … , M − 1 } ∣ λ ⟩ ∣ Φ λ , A ⟩ \frac{1}{\sqrt{M^n}}\sum_{\lambda:[n]\to\{0,\ldots,M-1\}}|\lambda\rangle|\Phi_{\lambda,A}\rangle M n 1 λ : [ n ] → { 0 , … , M − 1 } ∑ ∣ λ ⟩ ∣ Φ λ , A ⟩
where measuring the output qubit of ∣ Φ λ , A ⟩ |\Phi_{\lambda,A}\rangle ∣ Φ λ , A ⟩ gives the correct result with probability at least 0.9 (by assumption). Since this measurement acts trivially on the labels, orthogonality of the ∣ λ ⟩ |\lambda\rangle ∣ λ ⟩ gives the uniform average, so we obtain the correct result with probability 0.9 whenever the function λ \lambda λ is injective. Since the probability that a uniformly chosen λ : [ n ] → { 0 , 1 , … , M − 1 } \lambda:[n]\to\{0,1,\ldots,M-1\} λ : [ n ] → { 0 , 1 , … , M − 1 } is not injective is at most ( n 2 ) 1 M ≤ 1 / 20 \binom{n}{2}\frac{1}{M}\leq1/20 ( 2 n ) M 1 ≤ 1/20 , it follows from the union bound that our symmetric quantum algorithm is correct with probability at least 0.85 > 2 / 3 >2/3 > 2/3 on any input. The theorem follows.
Lemma 7.1 also gives a proof of Theorem 1.5 by showing that symmetric quantum circuits of entanglement width 1 can simulate symmetric classical threshold circuits. A classical threshold circuit on graphs is a directed acyclic graph with an input gate for each potential edge, internal gates computing threshold or NOT functions, and a designated output gate. Such a circuit is symmetric if every permutation of the vertices of the input graph induces a permutation of the input gates that extends to an automorphism of the circuit, preserving the types and thresholds of the internal gates and fixing the output gate. We refer the reader to [5 ] for the precise definitions.
Lemma 7.2 (No-entanglement simulation of classical threshold circuits). Let P \mathcal{P} P be a graph property. Suppose that a polynomial-time uniform family of symmetric classical circuits using threshold and NOT gates computes P \mathcal{P} P . Then P \mathcal{P} P can also be computed by a polynomial-time uniform family of symmetric quantum circuits with entanglement width 1 using only one-qubit and two-qubit gates.
Proof. Given a symmetric classical circuit, use Proposition 1 of [5 ] to convert it to a symmetric reversible circuit. Each threshold gate can be implemented using Lemma 7.1 and each NOT gate by an X gate.
Combining this lemma with Anderson and Dawar’s characterization of FPC (Theorem 2.16) gives Theorem 1.5 .
Acknowledgements
Davi Castro-Silva thanks Anuj Dawar for insightful discussions on the computational power of symmetric quantum circuits. Ryan Dancy is supported by a Clarendon Fund Scholarship from the University of Oxford. Sergii Strelchuk acknowledges support from the Wellcome Leap as part of the Q4Bio Program and the Royal Society University Research Fellowship.
Symmetric implementation of QAOA
Proof of Theorem 1.6. Fix m , n , p ≥ 1 m,n,p\geq1 m , n , p ≥ 1 , a threshold t ∈ { 0 , … , m } t\in\{0,\ldots,m\} t ∈ { 0 , … , m } , and the angle vectors γ , β ∈ R p \gamma,\beta\in\mathbb{R}^p γ , β ∈ R p . For an instance J = ( A , d ) J=(A,d) J = ( A , d ) and an assignment y ∈ { 0 , 1 } n y\in\{0,1\}^n y ∈ { 0 , 1 } n , we define the cost function that corresponds to the number of satisfying equations
c J ( y ) = ∣ { i ∈ [ m ] : ( A y ) i = d i } ∣ . (36) c_J(y)=|\{i\in[m]:(Ay)_i=d_i\}|. \tag*{(36)} c J ( y ) = ∣ { i ∈ [ m ] : ( A y ) i = d i } ∣. (36)
Following Farhi, Goldstone and Gutmann [11 ] , we define the cost and mixing operations by U C ( J ; γ ) ∣ y ⟩ = e − i γ c J ( y ) ∣ y ⟩ U_C(J;\gamma)|y\rangle=e^{-i\gamma c_J(y)}|y\rangle U C ( J ; γ ) ∣ y ⟩ = e − iγ c J ( y ) ∣ y ⟩ and U M ( β ) = ∏ j = 1 n e − i β X y j U_M(\beta)=\prod_{j=1}^{n}e^{-i\beta X_{y_j}} U M ( β ) = ∏ j = 1 n e − i β X y j respectively, where X i X_i X i is the X gate applied to the i i i -th qubit. Starting from ∣ ψ 0 ( J ) ⟩ = ∣ + ⟩ ⊗ n |\psi_0(J)\rangle=|+\rangle^{\otimes n} ∣ ψ 0 ( J )⟩ = ∣ + ⟩ ⊗ n , the states after successive rounds are
∣ ψ ℓ ( J ) ⟩ = U M ( β ℓ ) U C ( J ; γ ℓ ) ∣ ψ ℓ − 1 ( J ) ⟩ , ℓ ∈ [ p ] . (37) |\psi_\ell(J)\rangle=U_M(\beta_\ell)U_C(J;\gamma_\ell)|\psi_{\ell-1}(J)\rangle,\qquad\ell\in[p]. \tag*{(37)} ∣ ψ ℓ ( J )⟩ = U M ( β ℓ ) U C ( J ; γ ℓ ) ∣ ψ ℓ − 1 ( J )⟩ , ℓ ∈ [ p ] . (37)
Let x i j x_{ij} x ij and z i z_i z i be the input wires holding A i j A_{ij} A ij and d i d_i d i . We introduce assignment wires y j y_j y j , product wires w i j w_{ij} w ij , parity wires r i r_i r i , and an output wire w o u t w_{\mathrm{out}} w out , each initialized in ∣ 0 ⟩ |0\rangle ∣0 ⟩ . We call the product and parity wires, together with the counter and comparison wires introduced below, the workspace. All workspace wires are initialized in ∣ 0 ⟩ |0\rangle ∣0 ⟩ . The input, assignment, and output wires are separate from the workspace. Apply a Hadamard gate to every y j y_j y j in one layer to prepare ∣ + ⟩ ⊗ n |+\rangle^{\otimes n} ∣ + ⟩ ⊗ n .
Each Toffoli gate in the construction can be implemented using five two-qubit gates. To see this, define
V = 1 + i 2 I + 1 − i 2 X , (38) V=\frac{1+i}{2}\mathbb{I}+\frac{1-i}{2}X, \tag*{(38)} V = 2 1 + i I + 2 1 − i X , (38)
so that V 2 = X V^2=X V 2 = X . Let C b ( V u ) C_b(V_u) C b ( V u ) denote the application of V V V to target qubit u u u , controlled by qubit b b b . The Toffoli gate with controls a a a , b b b and target u u u is
T o f f o l i a , b → u = C a ( V u ) CNOT a → b C b ( V u † ) CNOT a → b C b ( V u ) (39) \mathrm{Toffoli}_{a,b\to u}=C_a(V_u)\operatorname{CNOT}_{a\to b}C_b(V_u^\dagger)\operatorname{CNOT}_{a\to b}C_b(V_u) \tag*{(39)} Toffoli a , b → u = C a ( V u ) CNOT a → b C b ( V u † ) CNOT a → b C b ( V u ) (39)
This sequence restores the control qubits and, for computational basis values a , b ∈ { 0 , 1 } a,b\in\{0,1\} a , b ∈ { 0 , 1 } , applies
V b − ( a ⊕ b ) + a = V 2 a b = X a b (40) V^{b-(a\oplus b)+a}=V^{2ab}=X^{ab} \tag*{(40)} V b − ( a ⊕ b ) + a = V 2 ab = X ab (40)
to the target. By linearity, it therefore implements the Toffoli gate on arbitrary superpositions.
For every ( i , j ) ∈ [ m ] × [ n ] (i,j)\in[m]\times[n] ( i , j ) ∈ [ m ] × [ n ] , compute w i j = A i j y j w_{ij}=A_{ij}y_j w ij = A ij y j using a Toffoli with controls y j y_j y j , x i j x_{ij} x ij . We apply each step of the above decomposition simultaneously to all pairs ( i , j ) (i,j) ( i , j ) . This gives five commuting layers: gates involving ( x i j , w i j ) (x_{ij},w_{ij}) ( x ij , w ij ) act on disjoint pairs, while the other layers have shared controls y j y_j y j and distinct targets. Every input wire x i j x_{ij} x ij is restored after these five layers.
Next apply all CNOT w i j → r i \operatorname{CNOT}_{w_{ij}\to r_i} CNOT w ij → r i in one commuting layer, followed by all CNOT z i → r i \operatorname{CNOT}_{z_i\to r_i} CNOT z i → r i in another. This computes
r i = d i ⊕ ⨁ j = 1 n A i j y j . (41) r_i=d_i\oplus\bigoplus_{j=1}^{n}A_{ij}y_j. \tag*{(41)} r i = d i ⊕ j = 1 ⨁ n A ij y j . (41)
Thus when equation i i i is satisfied, we have r i = 0 r_i=0 r i = 0 . Now apply
P γ = diag ( e − i γ , 1 ) (42) P_\gamma=\operatorname{diag}(e^{-i\gamma},1) \tag*{(42)} P γ = diag ( e − iγ , 1 ) (42)
to each r i r_i r i in one layer, and then reverse the parity and product computations. For each computational basis state ∣ y ⟩ |y\rangle ∣ y ⟩ of the assignment wires, these operations multiply its amplitude by e − i γ c J ( y ) e^{-i\gamma c_J(y)} e − iγ c J ( y ) and restore all product wires w i j w_{ij} w ij and parity wires r i r_i r i to ∣ 0 ⟩ |0\rangle ∣0 ⟩ . This implements U C ( J ; γ ) U_C(J;\gamma) U C ( J ; γ ) using O ( m n ) O(mn) O ( mn ) gates in 15 commuting layers.
The mixer U M ( β ) U_M(\beta) U M ( β ) is one layer of n n n single-qubit gates. Repeating these operations with angles ( γ ℓ , β ℓ ) (\gamma_\ell,\beta_\ell) ( γ ℓ , β ℓ ) therefore leaves, after round ℓ \ell ℓ , the state
∣ J ⟩ ∣ ψ ℓ ( J ) ⟩ ∣ 0 ⟩ w o u t ∣ 0 ⟩ w o r k s p a c e . (43) |J\rangle|\psi_\ell(J)\rangle|0\rangle_{w_{\mathrm{out}}}|0\rangle_{\mathrm{workspace}}. \tag*{(43)} ∣ J ⟩ ∣ ψ ℓ ( J )⟩ ∣0 ⟩ w out ∣0 ⟩ workspace . (43)
The product and parity wires have returned to ∣ 0 ⟩ |0\rangle ∣0 ⟩ , while the output, counter, and comparison wires have not yet been used. Preparation and all p p p rounds use O ( n + p m n ) O(n+pmn) O ( n + p mn ) gates. Having prepared the QAOA state, we now compute whether the assignment satisfies at least t t t equations and record the result on the output wire. If t = 0 t=0 t = 0 , we apply X X X to the output wire. For 1 ≤ t ≤ m 1\le t\le m 1 ≤ t ≤ m , we first compute the number of satisfied equations.
Computing the number of satisfied equations. Set 1 ≤ t ≤ m 1 \le t \le m 1 ≤ t ≤ m . We now check which equations are satisfied by the assignment. The product and parity wires were restored to ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ after each QAOA round, so we can reuse them. For each i , j i,j i , j , compute A i j y j A_{ij}y_j A ij y j on w i j w_{ij} w ij . Then compute
r i = d i ⊕ ⨁ j = 1 n A i j y j . (44) r_i = d_i \oplus\bigoplus_{j=1}^{n} A_{ij}y_j. \tag*{(44)} r i = d i ⊕ j = 1 ⨁ n A ij y j . (44)
The value of r i r_i r i is 0 when the two sides of the i i i th equation agree, and 1 when they differ. Applying X X X to r i r_i r i reverses these values. Thus this wire now holds
s i = { 1 if the i th equation is satisfied by y , 0 otherwise. (45) s_i =
\begin{cases}
1 & \text{if the } i\text{th equation is satisfied by } y,\\
0 & \text{otherwise.}
\end{cases} \tag*{(45)} s i = { 1 0 if the i th equation is satisfied by y , otherwise. (45)
The number of satisfied equations is c J ( y ) = ∑ i = 1 m s i c_J(y) = \sum_{i=1}^{m} s_i c J ( y ) = ∑ i = 1 m s i . Computing all the values s i s_i s i uses O ( m n ) O(mn) O ( mn ) gates.
We compute the sum by first recording it in the phases of a counter register, then converting those phases into binary digits. This allows all equations to contribute to the counter in a single commuting layer, without choosing an order for them. The counter must represent the integers from 0 to m m m , so we use L = ⌈ log 2 ( m + 1 ) ⌉ L = \lceil\log_2(m+1) \rceil L = ⌈ log 2 ( m + 1 )⌉ wires and set K = 2 L K = 2^L K = 2 L . Introduce counter wires q 0 , … , q L − 1 q_0,\ldots,q_{L-1} q 0 , … , q L − 1 . Apply a Hadamard gate to each wire to change its initial state ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ to ∣ + ⟩ \lvert+\rangle ∣ + ⟩ . For every i ∈ [ m ] i \in[m] i ∈ [ m ] and 0 ≤ j < L 0 \le j < L 0 ≤ j < L , apply
D j = diag ( 1 , 1 , 1 , e 2 π i 2 j / K ) (46) D_j = \operatorname{diag}\left(1,1,1,e^{2\pi i 2^j/K}\right) \tag*{(46)} D j = diag ( 1 , 1 , 1 , e 2 π i 2 j / K ) (46)
to ( r i , q j ) (r_i,q_j) ( r i , q j ) . This gate does nothing when r i r_i r i holds 0. When r i r_i r i holds 1, it multiplies the ∣ 1 ⟩ \lvert1\rangle ∣ 1 ⟩ component of q j q_j q j by e 2 π i 2 j / K e^{2\pi i2^j/K} e 2 π i 2 j / K . Thus each satisfied equation makes the same contribution to the phase of q j q_j q j . All these gates are diagonal, so they commute and form a single layer.
For an assignment y y y satisfying k = c J ( y ) k=c_J(y) k = c J ( y ) equations, these contributions multiply to give
∣ χ k ⟩ = ⨂ j = 0 L − 1 ∣ 0 ⟩ + e 2 π i 2 j k / K ∣ 1 ⟩ 2 . (47) \lvert\chi_k\rangle= \bigotimes_{j=0}^{L-1} \frac{\lvert0\rangle+ e^{2\pi i2^j k/K}\lvert1\rangle}{\sqrt{2}}. \tag*{(47)} ∣ χ k ⟩ = j = 0 ⨂ L − 1 2 ∣ 0 ⟩ + e 2 π i 2 j k / K ∣ 1 ⟩ . (47)
The number k k k is now encoded in the relative phases of the counter qubits. We next convert it into binary, writing
k = ∑ a = 0 L − 1 k a 2 a , (48) k = \sum_{a=0}^{L-1} k_a2^a, \tag*{(48)} k = a = 0 ∑ L − 1 k a 2 a , (48)
where each k a ∈ { 0 , 1 } k_a \in\{0,1\} k a ∈ { 0 , 1 } .
The least significant digit is particularly easy to obtain. Since K = 2 L K=2^L K = 2 L , the state of q L − 1 q_{L-1} q L − 1 is
∣ 0 ⟩ + e π i k ∣ 1 ⟩ 2 = ∣ 0 ⟩ + ( − 1 ) k 0 ∣ 1 ⟩ 2 . (49) \frac{\lvert0\rangle+ e^{\pi i k}\lvert1\rangle}{\sqrt{2}} = \frac{\lvert0\rangle+ (-1)^{k_0}\lvert1\rangle}{\sqrt{2}}. \tag*{(49)} 2 ∣ 0 ⟩ + e π ik ∣ 1 ⟩ = 2 ∣ 0 ⟩ + ( − 1 ) k 0 ∣ 1 ⟩ . (49)
A Hadamard gate maps this state to ∣ k 0 ⟩ \lvert k_0\rangle ∣ k 0 ⟩ . We can then use this qubit as a control to remove the contribution of k 0 k_0 k 0 from the phases of the remaining counter qubits. Repeating this procedure recovers one binary digit at each step.
More precisely, at step a = 0 , … , L − 1 a=0,\ldots,L-1 a = 0 , … , L − 1 , apply a Hadamard gate to q L − 1 − a q_{L-1-a} q L − 1 − a . Then apply
diag ( 1 , 1 , 1 , e − 2 π i 2 j + a / K ) (50) \operatorname{diag}\left(1,1,1,e^{-2\pi i2^{j+a}/K}\right) \tag*{(50)} diag ( 1 , 1 , 1 , e − 2 π i 2 j + a / K ) (50)
to each pair ( q L − 1 − a , q j ) (q_{L-1-a},q_j) ( q L − 1 − a , q j ) with 0 ≤ j < L − 1 − a 0 \le j < L-1-a 0 ≤ j < L − 1 − a . Once q L − 1 − a q_{L-1-a} q L − 1 − a holds k a k_a k a , these gates multiply the ∣ 1 ⟩ |1\rangle ∣1 ⟩ component of each remaining q j q_j q j by e − 2 π i 2 j k a 2 a / K e^{-2\pi i2^j k_a2^a/K} e − 2 π i 2 j k a 2 a / K , cancelling the contribution of the term k a 2 a k_a2^a k a 2 a .
To verify the procedure by induction, suppose that the contributions of k 0 , … , k a − 1 k_0,\ldots,k_{a-1} k 0 , … , k a − 1 have already been removed. The relative phase on q L − 1 − a q_{L-1-a} q L − 1 − a is then
exp ( 2 π i 2 L − 1 − a K ( k − ∑ b < a k b 2 b ) ) = ( − 1 ) k a . (51) \exp\left(\frac{2\pi i2^{L-1-a}}{K}\left(k-\sum_{b<a} k_b2^b\right)\right)=(-1)^{k_a}. \tag*{(51)} exp ( K 2 π i 2 L − 1 − a ( k − b < a ∑ k b 2 b ) ) = ( − 1 ) k a . (51)
Indeed, the expression in parentheses is k a 2 a k_a2^a k a 2 a plus a multiple of 2 a + 1 2^{a+1} 2 a + 1 . The Hadamard gate therefore maps this qubit to ∣ k a ⟩ |k_a\rangle ∣ k a ⟩ , and the subsequent phase gates remove this digit’s contribution from the remaining qubits.
At the end, q L − 1 − a q_{L-1-a} q L − 1 − a holds k a k_a k a for every a a a . The counter therefore stores the number of satisfied equations in binary, with the least significant bit on q L − 1 q_{L-1} q L − 1 . Recording the sum in the phases uses m L mL m L gates, and converting it to binary uses O ( L 2 ) O(L^2) O ( L 2 ) gates, all acting on the counter wires. No measurements are needed: by linearity, the construction also works on a superposition of assignments, associating each assignment ∣ y ⟩ |y\rangle ∣ y ⟩ with the binary representation of c J ( y ) c_J(y) c J ( y ) .
Comparing with the threshold. The counter now stores k = c J ( y ) k=c_J(y) k = c J ( y ) in binary. We now compute whether k ≥ t k\ge t k ≥ t and record the answer on the output wire, without changing the counter. Since t ≥ 1 t\ge1 t ≥ 1 , we can test the equivalent condition k > t − 1 k>t-1 k > t − 1 . We write
t − 1 = ∑ a = 0 L − 1 b a 2 a , (52) t-1=\sum_{a=0}^{L-1}b_a2^a, \tag*{(52)} t − 1 = a = 0 ∑ L − 1 b a 2 a , (52)
where b a ∈ { 0 , 1 } b_a\in\{0,1\} b a ∈ { 0 , 1 } are fixed by the threshold. To compare two binary integers, consider the most significant position at which their digits differ. The larger integer has 1 at that position, and the smaller has 0. Thus k > t − 1 k>t-1 k > t − 1 precisely when there is a position j j j at which k j = 1 k_j=1 k j = 1 and b j = 0 b_j=0 b j = 0 , with all more significant digits equal. For each position j j j with b j = 0 b_j=0 b j = 0 , we therefore compute
e j ( k ) = k j ∧ ⋀ a = j + 1 L − 1 ( k a = b a ) . (53) e_j(k)=k_j\wedge\bigwedge_{a=j+1}^{L-1}(k_a=b_a). \tag*{(53)} e j ( k ) = k j ∧ a = j + 1 ⋀ L − 1 ( k a = b a ) . (53)
It equals 1 when j j j is the most significant position at which the two integers differ and k k k has the larger digit. When j = L − 1 j=L-1 j = L − 1 , there are no more significant digits to check, so e j ( k ) = k j e_j(k)=k_j e j ( k ) = k j .
At most one of these expressions can be 1, since two integers have at most one most significant position at which they differ. When k ≥ t k\ge t k ≥ t , one of these expressions equals 1 and all the others are 0. When k < t k<t k < t , they all equal 0, thus
⨁ j : b j = 0 e j ( k ) = 1 { k ≥ t } . (54) \bigoplus_{j:b_j=0}e_j(k)=\mathbf{1}_{\{k\ge t\}}. \tag*{(54)} j : b j = 0 ⨁ e j ( k ) = 1 { k ≥ t } . (54)
Introduce auxiliary wires for the comparison, which we call the comparison wires. These start in ∣ 0 ⟩ |0\rangle ∣0 ⟩ and are reused to compute the expressions e j ( k ) e_j(k) e j ( k ) one at a time.
Each expression is a conjunction of at most L L L conditions on the counter bits. A condition k a = b a k_a=b_a k a = b a asks for k a = 1 k_a=1 k a = 1 when b a = 1 b_a=1 b a = 1 , and for k a = 0 k_a=0 k a = 0 when b a = 0 b_a=0 b a = 0 . In the latter case, we temporarily apply X X X to the corresponding counter wire, so that every condition can be tested by a control on 1.
A sequence of Toffoli gates computes the conjunction on a comparison wire, using other comparison wires for intermediate results. For a conjunction consisting of a single bit, a CNOT suffices. We use the wire holding e j ( k ) e_j(k) e j ( k ) to control a CNOT onto w o u t w_{\mathrm{out}} w out , then apply the gates that computed the conjunction in reverse order and undo the X X X gates on the counter wires. This restores the counter and returns all comparison wires to ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ , ready for the next value of j j j .
Each expression requires O ( L ) O(L) O ( L ) gates, since every Toffoli uses the five two-qubit gates described above. There are at most L L L expressions, so the comparison uses O ( L 2 ) O(L^2) O ( L 2 ) gates. The output wire starts in ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ and is flipped once for each expression whose value is 1. It therefore records their exclusive OR, which is 1 precisely when k ≥ t k \ge t k ≥ t .
Having recorded the comparison result, we no longer need the counter or the values indicating which equations are satisfied. We undo the operations that computed them, leaving the output wire untouched. All workspace wires return to ∣ 0 ⟩ \lvert0\rangle ∣ 0 ⟩ .
Recall the QAOA state has the form
∣ ψ p ( J ) ⟩ = ∑ y ∈ { 0 , 1 } n a y ∣ y ⟩ , (55) \lvert\psi_p(J)\rangle= \sum_{y\in\{0,1\}^n} a_y\lvert y\rangle, \tag*{(55)} ∣ ψ p ( J )⟩ = y ∈ { 0 , 1 } n ∑ a y ∣ y ⟩ , (55)
and the final state can be succinctly described as
∣ J ⟩ ∑ y ∈ { 0 , 1 } n a y ∣ y ⟩ ∣ 1 { c J ( y ) ≥ t } ⟩ w o u t ∣ 0 ⟩ w o r k s p a c e . (56) \lvert J\rangle\sum_{y\in\{0,1\}^n} a_y\lvert y\rangle\lvert1_{\{c_J(y)\ge t\}}\rangle_{w_{\mathrm{out}}}\lvert0\rangle_{\mathrm{workspace}}. \tag*{(56)} ∣ J ⟩ y ∈ { 0 , 1 } n ∑ a y ∣ y ⟩ ∣ 1 { c J ( y ) ≥ t } ⟩ w out ∣ 0 ⟩ workspace . (56)
Here the indicator is 1 when c J ( y ) ≥ t c_J(y) \ge t c J ( y ) ≥ t and 0 otherwise. Measuring the output wire gives a required acceptance probability
C [ ∣ J ⟩ ] = ∑ y : c J ( y ) ≥ t ∣ a y ∣ 2 . (57) C[\lvert J\rangle] = \sum_{y:c_J(y)\ge t} \lvert a_y\rvert^2. \tag*{(57)} C [∣ J ⟩] = y : c J ( y ) ≥ t ∑ ∣ a y ∣ 2 . (57)
Symmetry. We now verify that relabelling the equations and variables preserves every layer of the circuit. Let ( α , σ ) ∈ S y m m × S y m n (\alpha,\sigma) \in\mathrm{Sym}_m \times\mathrm{Sym}_n ( α , σ ) ∈ Sym m × Sym n , where α \alpha α permutes the equations and σ \sigma σ permutes the variables. We extend this relabelling to the assignment, product, and parity wires:
x i j ↦ x α ( i ) , σ ( j ) , z i ↦ z α ( i ) , w i j ↦ w α ( i ) , σ ( j ) , r i ↦ r α ( i ) , y j ↦ y σ ( j ) . (58) \begin{aligned}
x_{ij} &\mapsto x_{\alpha(i),\sigma(j)}, \quad z_i \mapsto z_{\alpha(i)},\\
w_{ij} &\mapsto w_{\alpha(i),\sigma(j)}, \quad r_i \mapsto r_{\alpha(i)},\\
y_j &\mapsto y_{\sigma(j)}. \tag*{(58)}
\end{aligned} x ij w ij y j ↦ x α ( i ) , σ ( j ) , z i ↦ z α ( i ) , ↦ w α ( i ) , σ ( j ) , r i ↦ r α ( i ) , ↦ y σ ( j ) . (58)
Relabelling the equations and variables does not change the number of satisfied equations or the result of comparing this number with t t t . We extend the wire permutation by mapping each counter wire, each comparison wire, and the output wire w o u t w_{\mathrm{out}} w out to itself. We now check that this choice preserves every circuit layer by considering its successive layers. Each of the five layers used to compute the products A i j y j A_{ij}y_j A ij y j applies the same gate for every pair ( i , j ) (i,j) ( i , j ) . Relabelling these pairs permutes the gates within each layer. The parity computation, cost phases, and X X X gates that mark satisfied equations treat all equations alike. Similarly, the Hadamard preparation and mixing operations apply the same gate to every assignment wire. Each of these layers is therefore preserved.
In the counting layer, each counter wire q j q_j q j interacts with every equation wire r i r_i r i through the same gate D j D_j D j . Permuting the equations only permutes these gates within the layer. The subsequent conversion to binary and comparison with t t t act solely on counter, comparison, and output wires, all of which are fixed. Each gate in these computations is therefore fixed, and we may place these gates in separate layers.
Finally, undoing a computation replaces its layers by their inverses in reverse order. Since the wire permutation preserves each original layer, it also preserves each inverse layer. For t = 0 t=0 t = 0 , the final X X X gate acts on the fixed output wire and is also preserved. Thus every independent permutation of the equations and variables extends to a permutation of all circuit wires that preserves every layer and fixes the output.
Gate count. Preparing the assignment register uses n n n Hadamard gates. Each QAOA round uses O ( m n ) O(mn) O ( mn ) gates for the cost operation and n n n gates for the mixer, giving O ( n + p m n ) O(n+pmn) O ( n + p mn ) gates in total.
For the final threshold test, computing which equations are satisfied uses O ( m n ) O(mn) O ( mn ) gates. Recording their number in the counter phases uses m L mL m L gates, and converting the counter to binary and comparing it with t t t each use O ( L 2 ) O(L^2) O ( L 2 ) gates. Undoing the workspace computations adds at most the same order of cost. The threshold test therefore uses O ( m n + m L + L 2 ) O(mn+mL+L^2) O ( mn + m L + L 2 ) gates. When t = 0 t=0 t = 0 , only the output X X X gate is needed.
For m ≥ 2 m\ge2 m ≥ 2 , we have L = O ( log m ) L=O(\log m) L = O ( log m ) and L 2 = O ( m log m ) L^2=O(m\log m) L 2 = O ( m log m ) . Since p ≥ 1 p\ge1 p ≥ 1 , the total gate count is
s ( C ) = O ( n + p m n + m n + m L + L 2 ) = O ( p m n + m log m ) . (59) s(\mathcal{C})=O(n+pmn+mn+mL+L^2)=O(pmn+m\log m). \tag*{(59)} s ( C ) = O ( n + p mn + mn + m L + L 2 ) = O ( p mn + m log m ) . (59)
For m = 1 m=1 m = 1 , we have L = 1 L=1 L = 1 , so the counter and comparison require only a constant number of gates. Their cost is absorbed by O ( p m n ) O(pmn) O ( p mn ) , giving the same bound. Every gate in the construction acts on at most two qubits.
Additional lemmas
Lemma B.1. Let H = H A ⊗ H B \mathcal{H}=\mathcal{H}_A\otimes\mathcal{H}_B H = H A ⊗ H B be a bipartite Hilbert space. Let ρ ∈ D ( H ) \rho\in\mathrm{D}(\mathcal{H}) ρ ∈ D ( H ) . If Tr B ( ρ ) = ∣ ψ ⟩ ⟨ ψ ∣ \operatorname{Tr}_B(\rho)=|\psi\rangle\langle\psi| Tr B ( ρ ) = ∣ ψ ⟩ ⟨ ψ ∣ is a pure state, then ρ = ∣ ψ ⟩ ⟨ ψ ∣ ⊗ ρ ′ \rho=|\psi\rangle\langle\psi|\otimes\rho' ρ = ∣ ψ ⟩ ⟨ ψ ∣ ⊗ ρ ′ , where ρ ′ = Tr A ( ρ ) \rho'=\operatorname{Tr}_A(\rho) ρ ′ = Tr A ( ρ ) .
Proof. Let { ∣ a i ⟩ } i \{|a_i\rangle\}_i { ∣ a i ⟩ } i and { ∣ b i ⟩ } i \{|b_i\rangle\}_i { ∣ b i ⟩ } i be orthonormal bases for H A \mathcal{H}_A H A and H B \mathcal{H}_B H B respectively, chosen such that ∣ ψ ⟩ = ∣ a 1 ⟩ |\psi\rangle=|a_1\rangle ∣ ψ ⟩ = ∣ a 1 ⟩ . Write ρ = ∑ i p i ∣ ψ i ⟩ ⟨ ψ i ∣ \rho=\sum_i p_i|\psi_i\rangle\langle\psi_i| ρ = ∑ i p i ∣ ψ i ⟩ ⟨ ψ i ∣ for some positive real numbers { p i } i \{p_i\}_i { p i } i with ∑ i p i = 1 \sum_i p_i=1 ∑ i p i = 1 , and further write each ∣ ψ i ⟩ |\psi_i\rangle ∣ ψ i ⟩ as ∣ ψ i ⟩ = ∑ j k α i j k ∣ a j ⟩ ∣ b k ⟩ |\psi_i\rangle=\sum_{jk}\alpha_{ijk}|a_j\rangle|b_k\rangle ∣ ψ i ⟩ = ∑ j k α ij k ∣ a j ⟩ ∣ b k ⟩ for some complex numbers { α i j k } j k \{\alpha_{ijk}\}_{jk} { α ij k } j k where ∑ j k ∣ α i j k ∣ 2 = 1 \sum_{jk}|\alpha_{ijk}|^2=1 ∑ j k ∣ α ij k ∣ 2 = 1 . We obtain
ρ = ∑ i p i ( ∑ j k α i j k ∣ a j ⟩ ∣ b k ⟩ ) ( ∑ j ′ k ′ α i j ′ k ′ ∗ ⟨ a j ′ ∣ ⟨ b k ′ ∣ ) (60) \rho=\sum_i p_i\left(\sum_{jk}\alpha_{ijk}|a_j\rangle|b_k\rangle\right)\left(\sum_{j'k'}\alpha^*_{ij'k'}\langle a_{j'}|\langle b_{k'}|\right) \tag*{(60)} ρ = i ∑ p i j k ∑ α ij k ∣ a j ⟩ ∣ b k ⟩ j ′ k ′ ∑ α i j ′ k ′ ∗ ⟨ a j ′ ∣ ⟨ b k ′ ∣ (60)
= ∑ i , j , k , j ′ , k ′ p i α i j k α i j ′ k ′ ∗ ∣ a j ⟩ ⟨ a j ′ ∣ ⊗ ∣ b k ⟩ ⟨ b k ′ ∣ (61) =\sum_{i,j,k,j',k'}p_i\alpha_{ijk}\alpha^*_{ij'k'}|a_j\rangle\langle a_{j'}|\otimes|b_k\rangle\langle b_{k'}| \tag*{(61)} = i , j , k , j ′ , k ′ ∑ p i α ij k α i j ′ k ′ ∗ ∣ a j ⟩ ⟨ a j ′ ∣ ⊗ ∣ b k ⟩ ⟨ b k ′ ∣ (61)
where α ∗ \alpha^* α ∗ denotes the complex conjugate of α \alpha α . Hence,
Tr B ( ρ ) = ∣ ψ ⟩ ⟨ ψ ∣ = ∑ i , j , j ′ , k p i α i j k α i j ′ k ∗ ∣ a j ⟩ ⟨ a j ′ ∣ . (62) \operatorname{Tr}_B(\rho)=|\psi\rangle\langle\psi|=\sum_{i,j,j',k}p_i\alpha_{ijk}\alpha^*_{ij'k}|a_j\rangle\langle a_{j'}|. \tag*{(62)} Tr B ( ρ ) = ∣ ψ ⟩ ⟨ ψ ∣ = i , j , j ′ , k ∑ p i α ij k α i j ′ k ∗ ∣ a j ⟩ ⟨ a j ′ ∣. (62)
Since we chose ∣ ψ ⟩ = ∣ a 1 ⟩ |\psi\rangle=|a_1\rangle ∣ ψ ⟩ = ∣ a 1 ⟩ , we therefore have
∑ i k p i α i 1 k α i 1 k ∗ = ∑ i k p i ∣ α i 1 k ∣ 2 = 1 (63) \sum_{ik}p_i\alpha_{i1k}\alpha^*_{i1k}=\sum_{ik}p_i|\alpha_{i1k}|^2=1 \tag*{(63)} ik ∑ p i α i 1 k α i 1 k ∗ = ik ∑ p i ∣ α i 1 k ∣ 2 = 1 (63)
and since ∑ i p i = 1 \sum_i p_i=1 ∑ i p i = 1 , we must have ∑ k ∣ α i 1 k ∣ 2 = 1 \sum_k|\alpha_{i1k}|^2=1 ∑ k ∣ α i 1 k ∣ 2 = 1 for each i i i . Since ∑ j k ∣ α i j k ∣ 2 = 1 \sum_{jk}|\alpha_{ijk}|^2=1 ∑ j k ∣ α ij k ∣ 2 = 1 for each i i i , we therefore have α i j k = 0 \alpha_{ijk}=0 α ij k = 0 whenever j ≠ 1 j\ne1 j = 1 . Hence,
ρ = ∑ i , k , k ′ p i α i 1 k α i 1 k ′ ∗ ∣ ψ ⟩ ⟨ ψ ∣ ⊗ ∣ b k ⟩ ⟨ b k ′ ∣ = ∣ ψ ⟩ ⟨ ψ ∣ ⊗ ∑ i , k , k ′ p i α i 1 k α i 1 k ′ ∗ ∣ b k ⟩ ⟨ b k ′ ∣ (64) \rho=\sum_{i,k,k'}p_i\alpha_{i1k}\alpha^*_{i1k'}|\psi\rangle\langle\psi|\otimes|b_k\rangle\langle b_{k'}|=|\psi\rangle\langle\psi|\otimes\sum_{i,k,k'}p_i\alpha_{i1k}\alpha^*_{i1k'}|b_k\rangle\langle b_{k'}| \tag*{(64)} ρ = i , k , k ′ ∑ p i α i 1 k α i 1 k ′ ∗ ∣ ψ ⟩ ⟨ ψ ∣ ⊗ ∣ b k ⟩ ⟨ b k ′ ∣ = ∣ ψ ⟩ ⟨ ψ ∣ ⊗ i , k , k ′ ∑ p i α i 1 k α i 1 k ′ ∗ ∣ b k ⟩ ⟨ b k ′ ∣ (64)
and so ρ = ∣ ψ ⟩ ⟨ ψ ∣ ⊗ Tr A ( ρ ) \rho=|\psi\rangle\langle\psi|\otimes\operatorname{Tr}_A(\rho) ρ = ∣ ψ ⟩ ⟨ ψ ∣ ⊗ Tr A ( ρ ) .
Lemma B.2. Let H = H A ⊗ H B \mathcal{H}=\mathcal{H}_A\otimes\mathcal{H}_B H = H A ⊗ H B be a bipartite Hilbert space. Let ρ 1 ∈ D ( H A ) \rho_1\in\mathrm{D}(\mathcal{H}_A) ρ 1 ∈ D ( H A ) and ρ 2 ∈ D ( H B ) \rho_2\in\mathrm{D}(\mathcal{H}_B) ρ 2 ∈ D ( H B ) . Then ρ 1 ⊗ ρ 2 \rho_1\otimes\rho_2 ρ 1 ⊗ ρ 2 is a pure state if and only if both ρ 1 \rho_1 ρ 1 and ρ 2 \rho_2 ρ 2 are pure states.
Proof. For any density matrix ρ \rho ρ we have Tr ( ρ 2 ) ≤ 1 \operatorname{Tr}(\rho^2) \le1 Tr ( ρ 2 ) ≤ 1 , with equality if and only if ρ \rho ρ is a pure state [16 ] . We have Tr ( ( ρ 1 ⊗ ρ 2 ) 2 ) = Tr ( ρ 1 2 ⊗ ρ 2 2 ) = Tr ( ρ 1 2 ) Tr ( ρ 2 2 ) \operatorname{Tr}((\rho_1 \otimes\rho_2)^2) = \operatorname{Tr}(\rho_1^2 \otimes\rho_2^2) = \operatorname{Tr}(\rho_1^2)\operatorname{Tr}(\rho_2^2) Tr (( ρ 1 ⊗ ρ 2 ) 2 ) = Tr ( ρ 1 2 ⊗ ρ 2 2 ) = Tr ( ρ 1 2 ) Tr ( ρ 2 2 ) , so Tr ( ( ρ 1 ⊗ ρ 2 ) 2 ) = 1 \operatorname{Tr}((\rho_1 \otimes\rho_2)^2) = 1 Tr (( ρ 1 ⊗ ρ 2 ) 2 ) = 1 iff Tr ( ρ 1 2 ) = Tr ( ρ 2 2 ) = 1 \operatorname{Tr}(\rho_1^2) = \operatorname{Tr}(\rho_2^2) = 1 Tr ( ρ 1 2 ) = Tr ( ρ 2 2 ) = 1 .
Lemma B.3. Let H = H A ⊗ H B ⊗ H C \mathcal{H} = \mathcal{H}_A \otimes\mathcal{H}_B \otimes\mathcal{H}_C H = H A ⊗ H B ⊗ H C be a tripartite Hilbert space. Let ρ A B C ∈ D ( H ) \rho^{ABC} \in\mathcal{D}(\mathcal{H}) ρ A B C ∈ D ( H ) . If ρ A B = Tr C ( ρ A B C ) \rho^{AB} = \operatorname{Tr}_C(\rho^{ABC}) ρ A B = Tr C ( ρ A B C ) and ρ A C = Tr B ( ρ A B C ) \rho^{AC} = \operatorname{Tr}_B(\rho^{ABC}) ρ A C = Tr B ( ρ A B C ) are pure states, then ρ A = Tr B C ( ρ A B C ) \rho^A = \operatorname{Tr}_{BC}(\rho^{ABC}) ρ A = Tr B C ( ρ A B C ) is a pure state.
Proof. Let ∣ ψ ⟩ ∈ H ⊗ H D |\psi\rangle\in\mathcal{H} \otimes\mathcal{H}_D ∣ ψ ⟩ ∈ H ⊗ H D be a purification of ρ A B C \rho^{ABC} ρ A B C , i.e. a state ∣ ψ ⟩ |\psi\rangle ∣ ψ ⟩ such that Tr D ( ∣ ψ ⟩ ⟨ ψ ∣ ) = ρ A B C \operatorname{Tr}_D(|\psi\rangle\langle\psi|) = \rho^{ABC} Tr D ( ∣ ψ ⟩ ⟨ ψ ∣ ) = ρ A B C for some Hilbert space H D \mathcal{H}_D H D [16 ] . Since ρ A B \rho^{AB} ρ A B is a pure state, by Lemma B.1 ,
∣ ψ ⟩ ⟨ ψ ∣ = ρ A B ⊗ Tr A B ( ∣ ψ ⟩ ⟨ ψ ∣ ) . (65) |\psi\rangle\langle\psi| = \rho^{AB} \otimes\operatorname{Tr}_{AB}(|\psi\rangle\langle\psi|). \tag*{(65)} ∣ ψ ⟩ ⟨ ψ ∣ = ρ A B ⊗ Tr A B ( ∣ ψ ⟩ ⟨ ψ ∣ ) . (65)
Furthermore, ρ A C = Tr B D ( ∣ ψ ⟩ ⟨ ψ ∣ ) \rho^{AC} = \operatorname{Tr}_{BD}(|\psi\rangle\langle\psi|) ρ A C = Tr B D ( ∣ ψ ⟩ ⟨ ψ ∣ ) , so
ρ A C = Tr B ( ρ A B ) ⊗ Tr D ( Tr A B ( ∣ ψ ⟩ ⟨ ψ ∣ ) ) = ρ A ⊗ Tr A B D ( ∣ ψ ⟩ ⟨ ψ ∣ ) . (66) \rho^{AC} = \operatorname{Tr}_B(\rho^{AB}) \otimes\operatorname{Tr}_D(\operatorname{Tr}_{AB}(|\psi\rangle\langle\psi|)) = \rho^A \otimes\operatorname{Tr}_{ABD}(|\psi\rangle\langle\psi|). \tag*{(66)} ρ A C = Tr B ( ρ A B ) ⊗ Tr D ( Tr A B ( ∣ ψ ⟩ ⟨ ψ ∣ )) = ρ A ⊗ Tr A B D ( ∣ ψ ⟩ ⟨ ψ ∣ ) . (66)
By Lemma B.2 , since ρ A C \rho^{AC} ρ A C is a pure state, ρ A \rho^A ρ A is a pure state.