Introduction
The paradigm of a simple unstable theory is the theory of the random graph [26 , 17 ] . A first-order theory, a set of axioms in a formal language, is simple, in the sense of Shelah, when no formula has the tree property, a branching pattern of consistent and inconsistent conditions that we describe later in this Introduction; the theory of the random graph is unstable because its edge relation has the independence property: for any finitely many vertices and any choice among them, some vertex is adjacent to the chosen ones and to none of the others. The random graph has two modes of presentation: as the Rado graph, it is the Fraïssé limit of the finite graphs, that is, the countable graph, unique up to isomorphism, that contains every finite graph as an induced subgraph and in which every isomorphism between finite induced subgraphs extends to an automorphism [Fra54, Rad64]; as a random object, it is the graph to which a random network of couplings on countably many sites, in which each pair of sites is coupled independently with probability one half, is isomorphic with probability one [15 ] . Quantum error correction, the protection of quantum information against noise, rests on a structure of its own. In a stabilizer code, errors are detected by measuring checks, which are Pauli strings: tensor products of factors on the individual qubits, or two-level quantum systems, each factor being the identity, a bit flip, a phase flip or, up to a phase, their product. The checks of a code commute, and the code stores quantum information in their common eigenspace for the eigenvalue 1. It suffices to correct errors that are themselves Pauli strings, since a code that corrects a set of errors corrects every linear combination of them (see [18 ] ).
To make this precise, let F 2 \mathbb{F}_2 F 2 n n n C 2 \mathbb{C}^2 C 2 X X X Z Z Z n n n n n n X x k Z z k X^{x_k}Z^{z_k} X x k Z z k k = 1 , … , n k=1,\ldots,n k = 1 , … , n x k , z k ∈ F 2 x_k,z_k \in\mathbb{F}_2 x k , z k ∈ F 2 ± 1 \pm1 ± 1 ± i \pm i ± i ( x , z ) ∈ F 2 2 n (x,z) \in\mathbb{F}_2^{2n} ( x , z ) ∈ F 2 2 n x = ( x 1 , … , x n ) x=(x_1,\ldots,x_n) x = ( x 1 , … , x n ) z = ( z 1 , … , z n ) z=(z_1,\ldots,z_n) z = ( z 1 , … , z n ) ω \omega ω F 2 2 n \mathbb{F}_2^{2n} F 2 2 n ω ( ( x , z ) , ( x ′ , z ′ ) ) = x ⋅ z ′ + z ⋅ x ′ \omega((x,z),(x',z'))=x\cdot z'+z\cdot x' ω (( x , z ) , ( x ′ , z ′ )) = x ⋅ z ′ + z ⋅ x ′ x , z , x ′ , z ′ ∈ F 2 n x,z,x',z' \in\mathbb{F}_2^{n} x , z , x ′ , z ′ ∈ F 2 n x ⋅ z ′ = ∑ k = 1 n x k z k ′ x\cdot z'=\sum_{k=1}^{n}x_kz'_k x ⋅ z ′ = ∑ k = 1 n x k z k ′ F 2 2 n \mathbb{F}_2^{2n} F 2 2 n n n n ω \omega ω g g g g g g e e e n n n e e e g g g ω ( g , e ) \omega(g,e) ω ( g , e ) e e e g 1 , … , g m g_1,\ldots,g_m g 1 , … , g m m m m g 1 , … , g m g_1,\ldots,g_m g 1 , … , g m
On countably many qubits, the labels of the Pauli strings that act nontrivially on only finitely many qubits form a vector space over F 2 \mathbb{F}_2 F 2 ω \omega ω § 3 we show that, with this form, the Pauli group is the Fraïssé limit of the finite alternating spaces over F 2 \mathbb{F}_2 F 2 F 2 \mathbb{F}_2 F 2 Fact 2.2 ). The Pauli group is thus the quantum counterpart of the random graph, and in this paper we study the two paradigms side by side.
In Section § 4 we give a dictionary between model theory and quantum error correction, and we prove the three results on which it rests. The checks of a stabilizer code generate its stabilizer group; an error is undetectable when it commutes with every check, and an undetectable error is a logical error when it alters the encoded information, that is, when it lies outside the stabilizer group. Clifford unitaries, the unitary operators that map Pauli strings to Pauli strings under conjugation, up to phases, implement the homogeneity of the Pauli group: every isomorphism between finite-dimensional substructures of the Pauli group extends to an automorphism induced by a Clifford unitary on finitely many qubits, and every stabilizer code has an encoding circuit made of Clifford gates. The type of an error over a set of Pauli strings records which elements of the set anticommute with it and how, if at all, it is a product of them. An extension of such a type to a larger set forks over the original set when it confines the error to one of infinitely many alternatives that the original type cannot tell apart. Forking recognizes the logical errors: an undetectable error is a logical error exactly when its type over the stabilizer group and a set of logical operators, which generate the undetectable errors modulo the stabilizer group, forks over the stabilizer group. The Kim–Pillay independence theorem becomes a rule for syndromes: if two sets of checks are independent over a common set, then any two syndromes, each realized by some error on its own set of checks, that agree on the common set are realized by a single error. Here two sets of checks are independent over a common set when a Pauli string that is, up to a phase, both a product of checks of the first set and the common set and a product of checks of the second set and the common set is already, up to a phase, a product of checks of the common set. As first-order structures the two paradigms are alike: both are Fraïssé limits, and both have simple unstable theories. We show that the bipartite observables that they define, which we introduce in the next two paragraphs, tell them apart.
This paper is the third of a series on bipartite observables. A bipartite observable is a bounded self-adjoint operator on the tensor product of the Hilbert spaces of two systems, one prepared by Alice and the other probed by Bob. A preparation of Alice, a state of her system, averages the observable to an operator on Bob’s space. These operators and the identity generate the probe algebra, the smallest algebra of operators on Bob’s space that contains them and is closed under adjoints and under limits in the operator norm. A probe of Bob is a state of the probe algebra, that is, a positive linear functional on it with value 1 1 1 [13 ] we studied stability in the sense of Shelah: an observable is stable when its expectation, for independently prepared systems, does not depend on which of the two systems is idealized first. A system is idealized when its state is replaced by the limit, along a nonprincipal ultrafilter on the natural numbers, of a sequence of its states given by density operators, the positive operators of trace one. This limit assigns to each bounded operator on the space of the system the ultralimit of its expectations in the states of the sequence, that is, the unique complex number that these expectations approximate, to within any prescribed error, on a set of indices belonging to the ultrafilter. In the second paper [14 ] we called a sequence of Alice’s preparations independent when there are real numbers α < β \alpha< \beta α < β α \alpha α β \beta β k ≥ 2 k \ge2 k ≥ 2 k k k
In § 5 we define the observables of the two paradigms. Both are diagonal observables: the Hilbert spaces of Alice and Bob have orthonormal bases indexed by countable sets of labels, and the observable reports whether a relation holds between Alice’s label and Bob’s. In the Rado observable, Alice and Bob each hold a site of the network, that is, a vertex of the Rado graph, and the observable reports whether the two sites are coupled; in the Pauli observable, Alice holds a check and Bob an error, and the observable reports whether the two anticommute. A mixed preparation of Alice, a density operator on her space, enters a diagonal observable only through its diagonal, a probability measure on her labels; a single mixed preparation can therefore spread its weight over arbitrarily many labels, and its response is affine in the mixture. We call the point masses at single labels her pure preparations. Bob’s probes differ in the two observables, as we establish in Lemma 5.5 and Proposition 5.4: for the Rado observable they are the Radon probability measures on the space of all sets of vertices, with the product topology, that is, the random sets of neighbors, and for the Pauli observable they are the Pauli channels, the probability laws of random Pauli errors of arbitrary support, the support of an error being the set of qubits on which it acts nontrivially. The pure probes are the point masses among the probes, and we identify each of them with the point at which it is concentrated. Every set of vertices is thus a pure probe of the Rado observable; we express this by saying that the pure responses of this observable, the responses of pure preparations, are freely independent. The pure probes of the Pauli observable, its idealized errors, are the Pauli strings of arbitrary support. The syndrome sector of a syndrome with respect to finitely many checks is the set of idealized errors with that syndrome. The depolarizing noise of rate p p p 0 < p ≤ 1 0 < p \le1 0 < p ≤ 1 1 − p 1-p 1 − p p / 3 p/3 p /3
The real-valued theory of an observable is the theory of the structure formed by its mixed preparations, its probes and its response, in Keisler’s real-valued logic [21 ] , whose formulas take real values. A formula has the tree property of the second kind when, for some integer k ≥ 2 k \ge2 k ≥ 2 k k k k k k α < β \alpha< \beta α < β β \beta β k k k α \alpha α § 6 that the real-valued theory of every diagonal observable with the independence property, and in particular of the Rado observable and of the Pauli observable, has the tree property of the second kind: the difference between the responses to the uniform mixtures on a half of a finite set of labels and on the complementary half reaches its maximum, 1, at a probe exactly when the probe answers 1 on the first half and 0 on the second, and the differences given by two halves that meet in a quarter of the set are never both greater than 1 / 2 1/2 1/2 ( μ k ) k ∈ N (\mu_k)_{k\in\mathbb{N}} ( μ k ) k ∈ N ( ν k ) k ∈ N (\nu_k)_{k\in\mathbb{N}} ( ν k ) k ∈ N μ k \mu_k μ k ν k \nu_k ν k § 7 and § 8 we show that, for the Pauli observable, the tree property of the second kind is witnessed by an array of actual preparations, while, for the Rado observable, every array that witnesses it for a quantifier-free formula contains idealized preparations. Finally, in § 9 we compare mixing in our sense with the affine logic of Ben Yaacov, Ibarlucía and Tsankov, in which a mixture of structures is a direct integral, and we close with open questions in § 10 .
Theorem 1.1 (Main results). (A) The Rado graph and the symplectic space of countably infinite dimension over F 2 \mathbb{F}_2 F 2 (Theorems 3.1 and 3.3 ).
(B) Let n n n n n n S S S L L L S S S n n n n n n S ∪ L S\cup L S ∪ L S S S S S S (Theorem 4.5 and Proposition 4.7 ). Every isomorphism between finite-dimensional substructures of the Pauli group extends to an automorphism induced by a Clifford unitary on finitely many qubits, and every stabilizer code has an encoding circuit made of Clifford gates (Theorem 4.3 and Corollary 4.4 ). The independence theorem becomes the gluing of syndromes: if two sets of checks are independent over a common set, then any two syndromes, each realized by some error on its own set of checks, that agree on the common set are realized by a single error (Proposition 4.8 ). The probes of the Pauli observable are the Pauli channels, and the depolarizing noise of every positive rate on countably many qubits is concentrated on the Pauli strings of infinite support, which are idealized errors and not actual ones (Proposition 5.4).
(C) For every diagonal observable whose pure responses, the responses of single labels, have the independence property, and in particular for the Rado observable and the Pauli observable, the real-valued theory of the observable has the tree property of the second kind, for the formula that is the difference of two responses. Since the independence property of a diagonal observable passes to its pure responses, it follows that a diagonal observable whose real-valued theory is simple is NIP (Theorem 6.1 ).
(D) For the Pauli observable, the indicator of the syndrome sector of every nonzero syndrome of finitely many linearly independent checks is, on pure probes, the difference of the responses of two uniform mixtures of checks, and the response itself has the tree property of the second kind, witnessed by actual preparations: for blocks of checks that are linearly independent all together, the conditions that a given check is the first of its block to fire, that is, to anticommute with the unknown error, form the rows of a witnessing array; in the bit-flip repetition code, whose checks compare neighboring qubits of a chain, the first check to fire marks the first domain wall of a bit flip, the first boundary between flipped and unflipped qubits (Proposition 7.1, Theorem 7.2 and Example 7.4 ).
(E) For the Rado observable, and more generally for every diagonal observable with freely independent pure responses, that is, one in which every pattern of answers to Alice’s labels is a pure probe, such as the observable of the random bipartite graph, the Fraïssé limit of the finite bipartite graphs with the two sides as two sorts, the conditions on a probe given by instances of a quantifier-free formula with actual mixtures as parameters are compatible along every sequence: no such sequence is uniformly k k k k ≥ 2 k\geq2 k ≥ 2 (Theorems 8.1 and 8.3 , and Corollary 8.2 ).
The difference between (D) and (E) lies in the probes. For the Pauli observable we show in Proposition 5.4 that the pure probes are the Pauli strings of arbitrary support, which form a compact group in the product topology. Alice’s pure responses are then, up to an affine change, the characters of this group, that is, its continuous homomorphisms into the multiplicative group { ± 1 } \{\pm1\} { ± 1 } [18 ] , although it requires the checks only to be linearly independent, not to commute. With it, a single mixture of checks can single out the first check of a block to fire, that is, to anticommute with a given error: for linearly independent checks g 0 , g 1 , … g_0, g_1, \ldots g 0 , g 1 , … j ∈ N j \in\mathbb{N} j ∈ N g j g_j g j g j g_j g j Theorem 8.1 , a gliding hump argument, which passes to a subsequence whose weights lie, up to small errors, on a common finite set and on pairwise disjoint finite blocks, shows that no sequence of conditions given by affine combinations of responses of actual mixtures, with a common bound on the sum of the absolute values of the constant term and the coefficients, is uniformly k k k k ≥ 2 k \ge2 k ≥ 2 Theorem 8.3 ). For the observable of the paradigm, the Rado graph, every array of mixtures that witnesses the tree property of the second kind for a quantifier-free formula therefore contains idealized preparations; for the observable of its quantum counterpart, the Pauli group, the linear relations among the labels, which make the syndrome bit of a product of checks the sum of their syndrome bits, allow actual preparations to witness the same property.
Simple theories and the Kim–Pillay theorem
In this section we recall the tree property, whose absence defines simple theories, together with its two variants, and the Kim–Pillay theorem, which characterizes simple theories by an independence relation; in Section 3 we use this theorem to prove that the theories of both paradigms, the Rado graph and the Pauli group, are simple.
To fix the setting, we work in a monster model M \mathbb{M} M T T T tp ( a / C ) \operatorname{tp}(a/C) tp ( a / C ) a a a C C C C C C a a a B B B D D D B D BD B D B ∪ D B \cup D B ∪ D a a a a B aB a B B B B s ∈ N < N s \in\mathbb{N}^{<\mathbb{N}} s ∈ N < N j ∈ N j \in\mathbb{N} j ∈ N s ⌢ j s^\frown j s ⌢ j j j j s s s η ∈ N N \eta\in\mathbb{N}^{\mathbb{N}} η ∈ N N n ∈ N n \in\mathbb{N} n ∈ N η ↾ n \eta\mathord{\upharpoonright} n η ↾ n n n n η \eta η
Definition 2.1. Let φ ( x , y ) \varphi(x,y) φ ( x , y ) x x x y y y
(1) For an integer k ≥ 2 k \ge2 k ≥ 2 ( b j ) j ∈ N (b_j)_{j\in\mathbb{N}} ( b j ) j ∈ N M \mathbb{M} M y y y k k k φ \varphi φ j 1 < ⋯ < j k j_1 < \cdots< j_k j 1 < ⋯ < j k N \mathbb{N} N x x x φ ( x , b j 1 ) ∧ ⋯ ∧ φ ( x , b j k ) \varphi(x,b_{j_1}) \land\cdots\land\varphi(x,b_{j_k}) φ ( x , b j 1 ) ∧ ⋯ ∧ φ ( x , b j k )
(2) The formula φ \varphi φ k ≥ 2 k \ge2 k ≥ 2 ( b s ) s ∈ N < N (b_s)_{s\in\mathbb{N}^{<\mathbb{N}}} ( b s ) s ∈ N < N η ∈ N N \eta\in\mathbb{N}^{\mathbb{N}} η ∈ N N { φ ( x , b η ↾ n ) : n ∈ N } \{\varphi(x,b_{\eta\upharpoonright n}) : n \in\mathbb{N}\} { φ ( x , b η ↾ n ) : n ∈ N } s s s ( b s ⌢ j ) j ∈ N (b_{s^\frown j})_{j\in\mathbb{N}} ( b s ⌢ j ) j ∈ N k k k φ \varphi φ
(3) The formula φ \varphi φ ( b s ) s ∈ N < N (b_s)_{s\in\mathbb{N}^{<\mathbb{N}}} ( b s ) s ∈ N < N η ∈ N N \eta\in\mathbb{N}^{\mathbb{N}} η ∈ N N { φ ( x , b η ↾ n ) : n ∈ N } \{\varphi(x,b_{\eta\upharpoonright n}) : n \in\mathbb{N}\} { φ ( x , b η ↾ n ) : n ∈ N } s , t ∈ N < N s,t \in\mathbb{N}^{<\mathbb{N}} s , t ∈ N < N { φ ( x , b s ) , φ ( x , b t ) } \{\varphi(x,b_s),\varphi(x,b_t)\} { φ ( x , b s ) , φ ( x , b t )}
(4) The formula φ \varphi φ T P 2 \mathrm{TP}_2 TP 2 k ≥ 2 k \ge2 k ≥ 2 ( b i j ) i , j ∈ N (b_{ij})_{i,j\in\mathbb{N}} ( b ij ) i , j ∈ N ( b i j ) j ∈ N (b_{ij})_{j\in\mathbb{N}} ( b ij ) j ∈ N k k k φ \varphi φ f : N → N f:\mathbb{N}\to\mathbb{N} f : N → N { φ ( x , b i f ( i ) ) : i ∈ N } \{\varphi(x,b_{if(i)}) : i \in\mathbb{N}\} { φ ( x , b i f ( i ) ) : i ∈ N }
(5) The theory T T T
Recall that the theory T T T φ ( x , y ) \varphi(x,y) φ ( x , y ) a i a_i a i b i b_i b i i ∈ N i \in\mathbb{N} i ∈ N i , j ∈ N i,j \in\mathbb{N} i , j ∈ N φ ( a i , b j ) \varphi(a_i,b_j) φ ( a i , b j ) i < j i<j i < j φ ( x , y ) \varphi(x,y) φ ( x , y ) b i b_i b i i ∈ N i \in\mathbb{N} i ∈ N N \mathbb{N} N { i ∈ N : φ ( a , b i ) holds } \{i \in\mathbb{N} : \varphi(a,b_i)\text{ holds}\} { i ∈ N : φ ( a , b i ) holds } a a a T P 2 \mathrm{TP}_2 TP 2 [27 Theorem III.7.11] ). A simple theory is stable if and only if it is NIP (see [26 , 17 ] ), so a simple unstable theory has the independence property. To prove simplicity we do not build trees; instead, we exhibit an independence relation directly and show that it is nonforking independence, which we now recall. For a formula φ ( x , y ) \varphi(x,y) φ ( x , y ) b b b M \mathbb{M} M y y y φ ( x , b ) \varphi(x,b) φ ( x , b ) C C C k ≥ 2 k \ge2 k ≥ 2 ( b j ) j ∈ N (b_j)_{j\in\mathbb{N}} ( b j ) j ∈ N b 0 = b b_0=b b 0 = b k k k φ \varphi φ C C C C C C C C C C C C C C C A ⊥ C B A \mathrel{\perp_C} B A ⊥ C B A A A B B B C C C a a a A A A tp ( a / B C ) \operatorname{tp}(a/BC) tp ( a / B C ) C C C Fact 2.2 ), every relation with the properties listed there coincides with nonforking independence.
Fact 2.2 (Kim and Pillay). Let ⊥ \mathrel{\perp} ⊥ M \mathbb{M} M A ⊥ C B A \mathrel{\perp_C} B A ⊥ C B
(i) invariance under automorphisms of M \mathbb{M} M
(ii) symmetry: the relation A ⊥ C B A \mathrel{\perp_C} B A ⊥ C B B ⊥ C A B \mathrel{\perp_C} A B ⊥ C A
(iii) monotonicity and transitivity: the relation A ⊥ C B D A \mathrel{\perp_C} BD A ⊥ C B D A ⊥ C B A \mathrel{\perp_C} B A ⊥ C B A ⊥ C B D A \mathrel{\perp_{CB}} D A ⊥ C B D
(iv) finite character: the relation A ⊥ C B A \mathrel{\perp_C} B A ⊥ C B a ⊥ C b a \mathrel{\perp_C} b a ⊥ C b a a a A A A b b b
(v) local character: for every finite tuple a a a and every set B B B there is B 0 ⊆ B B_0 \subseteq B B 0 ⊆ B with ∣ B 0 ∣ ≤ ∣ T ∣ \lvert B_0\rvert\leq\lvert T\rvert ∣ B 0 ∣ ≤ ∣ T ∣ and a ⊥ B 0 B a \mathrel{\perp}_{B_0} B a ⊥ B 0 B where ∣ T ∣ \lvert T\rvert ∣ T ∣ is the number of formulas of the language of T T T
(vi) extension: for every tuple a a a and all sets C ⊆ B C \subseteq B C ⊆ B there is a ′ a' a ′ with tp ( a ′ / C ) = tp ( a / C ) \operatorname{tp}(a'/C) = \operatorname{tp}(a/C) tp ( a ′ / C ) = tp ( a / C ) and a ′ ⊥ C B a' \mathrel{\perp}_{C} B a ′ ⊥ C B
(vii) independence theorem over models: if M M M is a small elementary substructure of M \mathfrak{M} M B ⊥ M D B \mathrel{\perp}_{M} D B ⊥ M D a 1 ⊥ M B a_1 \mathrel{\perp}_{M} B a 1 ⊥ M B a 2 ⊥ M D a_2 \mathrel{\perp}_{M} D a 2 ⊥ M D and tp ( a 1 / M ) = tp ( a 2 / M ) \operatorname{tp}(a_1/M) = \operatorname{tp}(a_2/M) tp ( a 1 / M ) = tp ( a 2 / M ) then there is a a a with tp ( a / M B ) = tp ( a 1 / M B ) \operatorname{tp}(a/MB) = \operatorname{tp}(a_1/MB) tp ( a / M B ) = tp ( a 1 / M B ) tp ( a / M D ) = tp ( a 2 / M D ) \operatorname{tp}(a/MD) = \operatorname{tp}(a_2/MD) tp ( a / M D ) = tp ( a 2 / M D ) and a ⊥ M B D a \mathrel{\perp}_{M} BD a ⊥ M B D
Then the theory T T T ⊥ \mathrel{\perp} ⊥ [23 Theorem 4.2] ).
The two paradigms
Here we prove Theorem 1.1 (A): the Rado graph and the Pauli group on countably many qubits, taken modulo phases and with anticommutation as its relation, have simple unstable theories. In the subsections below we show that both are Fraïssé limits whose theories eliminate quantifiers, and that in both the independence relation of the Kim–Pillay theorem (see Fact 2.2 ) is read off from algebraic closure, which adds to a set the elements that lie in finite sets definable with parameters from it, and which takes each set to itself in the graph and to its linear span in the Pauli group.
The Rado graph
The class of finite graphs has the amalgamation property, since two graphs that share an induced subgraph can be glued along it without new edges. Its Fraïssé limit is the Rado graph ( Γ , E ) (\Gamma, E) ( Γ , E ) Γ \Gamma Γ E E E extension property : for all finite disjoint sets Γ 1 \Gamma_1 Γ 1 Γ 0 \Gamma_0 Γ 0 Γ 1 ∪ Γ 0 \Gamma_1 \cup\Gamma_0 Γ 1 ∪ Γ 0 Γ 1 \Gamma_1 Γ 1 Γ 0 \Gamma_0 Γ 0 ( Γ , E ) (\Gamma, E) ( Γ , E ) ℵ 0 \aleph_0 ℵ 0 D D D D D D M \mathfrak{M} M ( Γ , E ) (\Gamma, E) ( Γ , E ) Γ 1 \Gamma_1 Γ 1 Γ 0 \Gamma_0 Γ 0
The relation E ( x , y ) E(x,y) E ( x , y ) n n n a 1 , … , a n a_1,\ldots,a_n a 1 , … , a n 1 , … , n 1,\ldots,n 1 , … , n a i a_i a i i i i
Theorem 3.1. The theory of the Rado graph is simple, and, for small sets A A A B B B and C C C of vertices of the monster model M \mathfrak{M} M of this theory, nonforking independence A ⊥ C B A \mathrel{\perp}_{C} B A ⊥ C B holds if and only if A ∩ B ⊆ C A \cap B \subseteq C A ∩ B ⊆ C
Proof. We verify the hypotheses of Fact 2.2 for the relation A ⊥ C B A \mathrel{\perp}_{C} B A ⊥ C B A ∩ B ⊆ C A \cap B \subseteq C A ∩ B ⊆ C M \mathfrak{M} M A ∩ B ⊆ C A \cap B \subseteq C A ∩ B ⊆ C A ∩ D ⊆ C ∪ B A \cap D \subseteq C \cup B A ∩ D ⊆ C ∪ B A ∩ ( B ∪ D ) A \cap(B \cup D) A ∩ ( B ∪ D ) C C C a a a B B B B 0 = B ∩ a ⊆ B B_0 = B \cap a \subseteq B B 0 = B ∩ a ⊆ B a ⊥ B 0 B a \mathrel{\perp}_{B_0} B a ⊥ B 0 B
For extension, let a a a C ⊆ B C \subseteq B C ⊆ B a = ( c , a 0 ) a = (c,a_0) a = ( c , a 0 ) c c c a a a C C C a 0 a_0 a 0 C C C a 0 a_0 a 0 C C C M \mathfrak{M} M B ∖ C B \setminus C B ∖ C a 0 ′ a'_0 a 0 ′ B B B C C C a ′ = ( c , a 0 ′ ) a'=(c,a'_0) a ′ = ( c , a 0 ′ ) a ′ ∩ B ⊆ C a'\cap B\subseteq C a ′ ∩ B ⊆ C
For the independence theorem, let M M M B B B D D D a 1 a_1 a 1 a 2 a_2 a 2 tp ( a 1 / M ) = tp ( a 2 / M ) \operatorname{tp}(a_1/M)=\operatorname{tp}(a_2/M) tp ( a 1 / M ) = tp ( a 2 / M ) M M M a ℓ = ( m , a ℓ ′ ) a_\ell=(m,a'_\ell) a ℓ = ( m , a ℓ ′ ) ℓ = 1 , 2 \ell=1,2 ℓ = 1 , 2 m m m a ℓ ′ a'_\ell a ℓ ′ M M M a 1 ⊥ ⊥ M B a_1\mathrel{\perp\!\!\!\perp}_M B a 1 ⊥ ⊥ M B a 2 ⊥ ⊥ M D a_2\mathrel{\perp\!\!\!\perp}_M D a 2 ⊥ ⊥ M D a 1 ′ a'_1 a 1 ′ B B B a 2 ′ a'_2 a 2 ′ D D D x x x M ∪ B ∪ D M\cup B\cup D M ∪ B ∪ D M M M a 1 ′ a'_1 a 1 ′ a 2 ′ a'_2 a 2 ′ B ∖ M B\setminus M B ∖ M a 1 ′ a'_1 a 1 ′ D ∖ M D\setminus M D ∖ M a 2 ′ a'_2 a 2 ′ B ∩ D ⊆ M B\cap D\subseteq M B ∩ D ⊆ M M M M x x x a = ( m , x ) a=(m,x) a = ( m , x )
Pauli strings
The Hilbert space of a qubit is C 2 \mathbb{C}^2 C 2
X = ( 0 1 1 0 ) , Z = ( 1 0 0 − 1 ) , X Z = − Z X . X=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad Z=\begin{pmatrix}1&0\\0&-1\end{pmatrix},\qquad XZ=-ZX. X = ( 0 1 1 0 ) , Z = ( 1 0 0 − 1 ) , X Z = − Z X . For a positive integer n n n n n n X x 1 Z z 1 ⊗ ⋯ ⊗ X x n Z z n X^{x_1}Z^{z_1}\otimes\cdots\otimes X^{x_n}Z^{z_n} X x 1 Z z 1 ⊗ ⋯ ⊗ X x n Z z n x k x_k x k z k z_k z k F 2 \mathbb{F}_2 F 2 k = 1 , … , n k=1,\ldots,n k = 1 , … , n ( x , z ) ∈ F 2 2 n (x,z)\in\mathbb{F}_2^{2n} ( x , z ) ∈ F 2 2 n x = ( x 1 , … , x n ) x=(x_1,\ldots,x_n) x = ( x 1 , … , x n ) z = ( z 1 , … , z n ) z=(z_1,\ldots,z_n) z = ( z 1 , … , z n ) v = ( x , z ) v=(x,z) v = ( x , z ) P v P_v P v i N ( v ) X x 1 Z z 1 ⊗ ⋯ ⊗ X x n Z z n i^{N(v)}X^{x_1}Z^{z_1}\otimes\cdots\otimes X^{x_n}Z^{z_n} i N ( v ) X x 1 Z z 1 ⊗ ⋯ ⊗ X x n Z z n N ( v ) N(v) N ( v ) k k k x k = z k = 1 x_k=z_k=1 x k = z k = 1 P v 2 = I P_v^2=I P v 2 = I I I I ( 1 , 1 ) (1,1) ( 1 , 1 ) P ( 1 , 1 ) = i X Z = Y P_{(1,1)}=iXZ=Y P ( 1 , 1 ) = i X Z = Y
P ( x , z ) P ( x ′ , z ′ ) = ( − 1 ) ω ( ( x , z ) , ( x ′ , z ′ ) ) P ( x ′ , z ′ ) P ( x , z ) , ω ( ( x , z ) , ( x ′ , z ′ ) ) = x ⋅ z ′ + z ⋅ x ′ , P_{(x,z)}P_{(x',z')}=(-1)^{\omega((x,z),(x',z'))}P_{(x',z')}P_{(x,z)},\qquad\omega((x,z),(x',z'))=x\cdot z'+z\cdot x', P ( x , z ) P ( x ′ , z ′ ) = ( − 1 ) ω (( x , z ) , ( x ′ , z ′ )) P ( x ′ , z ′ ) P ( x , z ) , ω (( x , z ) , ( x ′ , z ′ )) = x ⋅ z ′ + z ⋅ x ′ , where x ⋅ z ′ = ∑ k = 1 n x k z k ′ x\cdot z'=\sum_{k=1}^{n}x_kz'_k x ⋅ z ′ = ∑ k = 1 n x k z k ′ F 2 \mathbb{F}_2 F 2 ω \omega ω F 2 2 n \mathbb{F}_2^{2n} F 2 2 n syndrome of an error e e e g 1 , … , g m g_1,\ldots,g_m g 1 , … , g m m m m ( ω ( g 1 , e ) , … , ω ( g m , e ) ) (\omega(g_1,e),\ldots,\omega(g_m,e)) ( ω ( g 1 , e ) , … , ω ( g m , e )) V V V ⨁ k ∈ N F 2 2 \bigoplus_{k\in\mathbb{N}}\mathbb{F}_2^2 ⨁ k ∈ N F 2 2
The Pauli group as a Fraïssé limit
In the language with + + + ω ( x , y ) = 1 \omega(x,y)=1 ω ( x , y ) = 1 F 2 \mathbb{F}_2 F 2 F 2 \mathbb{F}_2 F 2 F 2 \mathbb{F}_2 F 2 W 0 ⊆ W 1 W_0\subseteq W_1 W 0 ⊆ W 1 W 0 ⊆ W 2 W_0\subseteq W_2 W 0 ⊆ W 2 W 1 = W 0 ⊕ W 1 ′ W_1=W_0\oplus W'_1 W 1 = W 0 ⊕ W 1 ′ W 2 = W 0 ⊕ W 2 ′ W_2=W_0\oplus W'_2 W 2 = W 0 ⊕ W 2 ′ W 0 ⊕ W 1 ′ ⊕ W 2 ′ W_0\oplus W'_1\oplus W'_2 W 0 ⊕ W 1 ′ ⊕ W 2 ′ W 1 W_1 W 1 W 1 ′ × W 2 ′ W'_1\times W'_2 W 1 ′ × W 2 ′ W 2 ′ × W 1 ′ W'_2\times W'_1 W 2 ′ × W 1 ′ [2 ] every isometry between subspaces of a finite nondegenerate alternating space extends to an isometry of the whole space. A back-and-forth argument along symplectic bases therefore shows that ( V , ω ) (V,\omega) ( V , ω ) F 2 \mathbb{F}_2 F 2 ℵ 0 \aleph_0 ℵ 0 a a a D D D a a a span ( D ) \operatorname{span}(D) span ( D ) ω \omega ω span ( a D ) \operatorname{span}(aD) span ( a D )
Lemma 3.2. Let n n n a 1 , … , a n ∈ V a_1,\ldots,a_n \in V a 1 , … , a n ∈ V ε 1 , … , ε n ∈ F 2 \varepsilon_1,\ldots,\varepsilon_n \in\mathbb{F}_2 ε 1 , … , ε n ∈ F 2 b ∈ V b \in V b ∈ V ω ( a i , b ) = ε i \omega(a_i,b)=\varepsilon_i ω ( a i , b ) = ε i i = 1 , … , n i=1,\ldots,n i = 1 , … , n
Proof. The vectors a i a_i a i W W W X X X Z Z Z m m m m m m W W W ω ( a i , ⋅ ) \omega(a_i,\mathord{\cdot}) ω ( a i , ⋅ ) W W W b ↦ ( ω ( a i , b ) ) i ≤ n b \mapsto(\omega(a_i,b))_{i\leq n} b ↦ ( ω ( a i , b ) ) i ≤ n W W W F 2 n \mathbb{F}_2^n F 2 n
By Lemma 3.2 and compactness, the formula ω ( x , y ) = 1 \omega(x,y)=1 ω ( x , y ) = 1 ( V , ω ) (V,\omega) ( V , ω ) D D D M \mathbb{M} M ( V , ω ) (V,\omega) ( V , ω ) n n n D ⊕ span ( x 1 , … , x n ) D\oplus\operatorname{span}(x_1,\ldots,x_n) D ⊕ span ( x 1 , … , x n ) D D D n n n D D D M \mathbb{M} M f f f D D D b ∈ M b\in\mathbb{M} b ∈ M ω ( ⋅ , b ) = f \omega(\mathord{\cdot},b)=f ω ( ⋅ , b ) = f D D D
Theorem 3.3. The theory of ( V , ω ) (V,\omega) ( V , ω ) A A A B B B C C C M \mathbb{M} M A ⊥ ⊥ C B A\mathrel{\perp\!\!\!\perp}_{C}B A ⊥ ⊥ C B span ( A C ) ∩ span ( B C ) = span ( C ) \operatorname{span}(AC)\cap\operatorname{span}(BC)=\operatorname{span}(C) span ( A C ) ∩ span ( B C ) = span ( C )
Proof. The proof follows that of Theorem 3.1 , with linear spans in place of the sets themselves: the first five axioms are linear algebra, and extension and the independence theorem come from the freedom to prescribe the form on a complement. We verify the hypotheses of Fact 2.2 for the relation A ⊥ ⊥ C B A\mathrel{\perp\!\!\!\perp}_{C}B A ⊥ ⊥ C B span ( A C ) ∩ span ( B C ) = span ( C ) \operatorname{span}(AC)\cap\operatorname{span}(BC)=\operatorname{span}(C) span ( A C ) ∩ span ( B C ) = span ( C ) span ( A C ) ∩ span ( B C ) \operatorname{span}(AC)\cap\operatorname{span}(BC) span ( A C ) ∩ span ( B C ) span ( C ) \operatorname{span}(C) span ( C ) A A A B B B C C C
For monotonicity and transitivity, put Q 1 = span ( A C ) Q_1=\operatorname{span}(AC) Q 1 = span ( A C ) Q 2 = span ( B C ) Q_2=\operatorname{span}(BC) Q 2 = span ( B C ) Q 3 = span ( B C D ) Q_3=\operatorname{span}(BCD) Q 3 = span ( B C D ) Q 0 = span ( C ) Q_0=\operatorname{span}(C) Q 0 = span ( C ) Q 2 ⊆ Q 3 Q_2\subseteq Q_3 Q 2 ⊆ Q 3 span ( A B C ) = Q 1 + Q 2 \operatorname{span}(ABC)=Q_1+Q_2 span ( A B C ) = Q 1 + Q 2 Q 1 ∩ Q 3 = Q 0 Q_1\cap Q_3=Q_0 Q 1 ∩ Q 3 = Q 0 Q 1 ∩ Q 2 = Q 0 Q_1\cap Q_2=Q_0 Q 1 ∩ Q 2 = Q 0 ( Q 1 + Q 2 ) ∩ Q 3 = Q 2 (Q_1+Q_2)\cap Q_3=Q_2 ( Q 1 + Q 2 ) ∩ Q 3 = Q 2 Q 1 ∩ Q 3 = Q 0 Q_1\cap Q_3=Q_0 Q 1 ∩ Q 3 = Q 0 Q 2 ⊆ Q 3 Q_2\subseteq Q_3 Q 2 ⊆ Q 3 Q 1 ∩ Q 2 Q_1\cap Q_2 Q 1 ∩ Q 2 Q 0 Q_0 Q 0 u 1 + u 2 ∈ Q 3 u_1+u_2\in Q_3 u 1 + u 2 ∈ Q 3 u 1 ∈ Q 1 u_1\in Q_1 u 1 ∈ Q 1 u 2 ∈ Q 2 u_2\in Q_2 u 2 ∈ Q 2 u 1 u_1 u 1 Q 3 Q_3 Q 3 Q 1 ∩ Q 3 = Q 0 ⊆ Q 2 Q_1\cap Q_3=Q_0\subseteq Q_2 Q 1 ∩ Q 3 = Q 0 ⊆ Q 2 Q 2 Q_2 Q 2 u ∈ Q 1 ∩ Q 3 u\in Q_1\cap Q_3 u ∈ Q 1 ∩ Q 3 ( Q 1 + Q 2 ) ∩ Q 3 = Q 2 (Q_1+Q_2)\cap Q_3=Q_2 ( Q 1 + Q 2 ) ∩ Q 3 = Q 2 Q 1 ∩ Q 2 = Q 0 Q_1\cap Q_2=Q_0 Q 1 ∩ Q 2 = Q 0
Local character follows from finite dimension. Given a finite tuple a a a B B B span ( a ) ∩ span ( B ) \operatorname{span}(a)\cap\operatorname{span}(B) span ( a ) ∩ span ( B ) span ( B 0 ) \operatorname{span}(B_0) span ( B 0 ) B 0 ⊆ B B_0\subseteq B B 0 ⊆ B u + w ∈ span ( B ) u+w\in\operatorname{span}(B) u + w ∈ span ( B ) u ∈ span ( a ) u\in\operatorname{span}(a) u ∈ span ( a ) w ∈ span ( B 0 ) w\in\operatorname{span}(B_0) w ∈ span ( B 0 ) u u u span ( a ) ∩ span ( B ) ⊆ span ( B 0 ) \operatorname{span}(a)\cap\operatorname{span}(B)\subseteq\operatorname{span}(B_0) span ( a ) ∩ span ( B ) ⊆ span ( B 0 ) span ( a B 0 ) ∩ span ( B ) = span ( B 0 ) \operatorname{span}(aB_0)\cap\operatorname{span}(B)=\operatorname{span}(B_0) span ( a B 0 ) ∩ span ( B ) = span ( B 0 ) a ⊥ ⊥ B 0 B a\mathrel{\perp\!\!\!\perp}_{B_0}B a ⊥ ⊥ B 0 B
For extension, let a a a C ⊆ B C\subseteq B C ⊆ B a a a span ( C ) \operatorname{span}(C) span ( C ) a a a span ( C ) \operatorname{span}(C) span ( C ) B ′ B' B ′ span ( C ) \operatorname{span}(C) span ( C ) span ( B C ) \operatorname{span}(BC) span ( B C ) x x x a a a span ( B C ) ⊕ span ( x ) \operatorname{span}(BC)\oplus\operatorname{span}(x) span ( B C ) ⊕ span ( x ) x x x ω \omega ω tp ( a / C ) \operatorname{tp}(a/C) tp ( a / C ) span ( x C ) \operatorname{span}(xC) span ( x C ) B ′ B' B ′ span ( B C ) \operatorname{span}(BC) span ( B C ) a ′ a' a ′ a a a C C C span ( B C ) \operatorname{span}(BC) span ( B C ) span ( a ′ C ) ∩ span ( B C ) = span ( C ) \operatorname{span}(a'C)\cap\operatorname{span}(BC)=\operatorname{span}(C) span ( a ′ C ) ∩ span ( B C ) = span ( C ) a ′ ⊥ ⊥ C B a'\mathrel{\perp\!\!\!\perp}_{C}B a ′ ⊥ ⊥ C B
The independence theorem reduces to a gluing of functionals. Let M M M B B B D D D a 1 a_1 a 1 a 2 a_2 a 2 Fact 2.2 (vii). As in the proof of extension, we may assume that a 1 a_1 a 1 M M M a 2 a_2 a 2 a 1 ⊥ ⊥ M B a_1\mathrel{\perp\!\!\!\perp}_{M}B a 1 ⊥ ⊥ M B a 2 ⊥ ⊥ M D a_2\mathrel{\perp\!\!\!\perp}_{M}D a 2 ⊥ ⊥ M D a 1 a_1 a 1 span ( M B ) \operatorname{span}(MB) span ( M B ) a 2 a_2 a 2 span ( M D ) \operatorname{span}(MD) span ( M D ) n n n
of a 1 a_1 a 1 a 2 a_2 a 2 ℓ = 1 , 2 \ell= 1, 2 ℓ = 1 , 2 k = 1 , … , n k = 1, \ldots, n k = 1 , … , n a ℓ , k a_{\ell,k} a ℓ , k k k k a ℓ a_\ell a ℓ k k k ω ( a 1 , k , ⋅ ) \omega(a_{1,k}, \mathord\cdot) ω ( a 1 , k , ⋅ ) span ( M B ) \operatorname{span}(MB) span ( M B ) ω ( a 2 , k , ⋅ ) \omega(a_{2,k}, \mathord\cdot) ω ( a 2 , k , ⋅ ) span ( M D ) \operatorname{span}(MD) span ( M D ) M M M tp ( a 1 / M ) = tp ( a 2 / M ) \operatorname{tp}(a_1/M) = \operatorname{tp}(a_2/M) tp ( a 1 / M ) = tp ( a 2 / M ) B ⊥ M D B \mathrel{\perp_M} D B ⊥ M D span ( M B ) ∩ span ( M D ) = M \operatorname{span}(MB) \cap\operatorname{span}(MD) = M span ( M B ) ∩ span ( M D ) = M span ( M B D ) \operatorname{span}(MBD) span ( M B D ) span ( M B D ) \operatorname{span}(MBD) span ( M B D ) a a a span ( M B D ) \operatorname{span}(MBD) span ( M B D ) ω \omega ω a a a tp ( a 1 / M ) \operatorname{tp}(a_1/M) tp ( a 1 / M ) a a a M B MB M B a 1 a_1 a 1 M D MD M D a 2 a_2 a 2 a ⊥ M B D a \mathrel{\perp_M} BD a ⊥ M B D □ \square □
In both structures, then, nonforking independence is the independence given by algebraic closure: for small sets A A A B B B C C C A ⊥ C B A \mathrel{\perp_C} B A ⊥ C B A C AC A C B C BC B C C C C
Remark 3.4. The proof of Theorem 3.3 applies over every finite field F q \mathbb{F}_q F q q q q Fact 2.2 goes through with the values ω ( x , x ) \omega(x,x) ω ( x , x ) ω ( x , ⋅ ) \omega(x,\mathord\cdot) ω ( x , ⋅ ) ω ( ⋅ , x ) \omega(\mathord\cdot,x) ω ( ⋅ , x )
Stabilizer codes as a structure: a dictionary
Three notions of model theory, namely Fraïssé limits, forking and the independence theorem, are already at work in quantum error correction under other names, and in this section we identify them. After a brief account of stabilizer codes, in each of the three subsections that follow it we state a theorem, prove it, and interpret it twice: once for the physicist, who knows stabilizer codes but not model theory, and once for the logician, who knows model theory but not stabilizer codes. A single example runs through the section: the Laflamme–Miquel–Paz–Zurek five-qubit code [24 ] , the smallest code that corrects an arbitrary error on one qubit, which Bennett, DiVincenzo, Smolin and Wootters [3 ] found independently. The dictionary is summarized in Table 1 .
Table 1. The Pauli group as a structure: the dictionary of Sections 4, 5 and 7.
Stabilizer codes in brief
We recall what the logician needs (see [18 ] ). For a positive integer n n n stabilizer group on n n n G \mathcal{G} G − I -I − I 1 1 1 code space ; if G \mathcal{G} G n − k n-k n − k k k k 0 ≤ k ≤ n 0 \leq k \leq n 0 ≤ k ≤ n 2 k 2^k 2 k k k k G \mathcal{G} G S ⊆ F 2 2 n S \subseteq\mathbb{F}_2^{2n} S ⊆ F 2 2 n ω \omega ω e e e g 1 , … , g n − k g_1,\ldots,g_{n-k} g 1 , … , g n − k G \mathcal{G} G syndrome ( ω ( g 1 , e ) , … , ω ( g n − k , e ) ) (\omega(g_1,e),\ldots,\omega(g_{n-k},e)) ( ω ( g 1 , e ) , … , ω ( g n − k , e )) G \mathcal{G} G logical error otherwise. On labels, the errors with zero syndrome form the centralizer S ⊥ = { e ∈ F 2 2 n : ω ( s , e ) = 0 for all s ∈ S } S^\perp= \{e \in\mathbb{F}_2^{2n} : \omega(s,e) = 0 \text{ for all } s \in S\} S ⊥ = { e ∈ F 2 2 n : ω ( s , e ) = 0 for all s ∈ S } S S S 2 n − ( n − k ) = n + k 2n - (n-k) = n+k 2 n − ( n − k ) = n + k L L L logical operators is a set of 2 k 2k 2 k S ⊥ = S ⊕ span ( L ) S^\perp= S \oplus\operatorname{span}(L) S ⊥ = S ⊕ span ( L ) ω ( ℓ , e ) \omega(\ell,e) ω ( ℓ , e ) ℓ ∈ L \ell\in L ℓ ∈ L S ⊥ S^\perp S ⊥ k ≥ 1 k \geq1 k ≥ 1 Clifford unitary is a unitary operator U U U U U U F 2 2 n \mathbb{F}_2^{2n} F 2 2 n ω \omega ω
Example 4.1. The five-qubit code has the stabilizer generators
g 1 = X Z Z X I , g 2 = I X Z Z X , g 3 = X I X Z Z , g 4 = Z X I X Z , g_1 = XZZXI,\qquad g_2 = IXZZX,\qquad g_3 = XIXZZ,\qquad g_4 = ZXIXZ, g 1 = X Z Z X I , g 2 = I X Z Z X , g 3 = X I X Z Z , g 4 = Z X I X Z , where each word stands for the tensor product of its letters (thus X Z Z X I XZZXI X Z Z X I X ⊗ Z ⊗ Z ⊗ X ⊗ I X \otimes Z \otimes Z \otimes X \otimes I X ⊗ Z ⊗ Z ⊗ X ⊗ I X X X Z Z Z Y = i X Z Y = iXZ Y = i X Z § 3 and the identity I I I C 2 \mathbb{C}^2 C 2 X ‾ = X X X X X \overline{X} = XXXXX X = X X X X X Z ‾ = Z Z Z Z Z \overline{Z} = ZZZZZ Z = Z Z Z Z Z X X X Y Y Y Z Z Z X I I I I XIIII X I I I I ( 0 , 0 , 0 , 1 ) (0,0,0,1) ( 0 , 0 , 0 , 1 ) I I Z I I IIZII I I Z I I ( 0 , 0 , 1 , 0 ) (0,0,1,0) ( 0 , 0 , 1 , 0 )
3; after Proposition 4.7 we exhibit a logical error that acts on exactly three qubits, which shows that the distance is exactly 3.
Fraïssé limits and Clifford circuits
In Proposition 4.2 and Theorem 4.3 below, we show that every finite piece of commutation structure occurs among Pauli strings, and that every symmetry between finite pieces is implemented by a Clifford circuit, a product of elementary Clifford unitaries on one or two qubits that serve as the gates of a quantum computer; every Clifford unitary is such a product, up to a phase (see [18 , 12 ] ).
Proposition 4.2. Let d d d Θ \Theta Θ d × d d \times d d × d F 2 \mathbb{F}_2 F 2 P 1 , … , P d P_1,\ldots,P_d P 1 , … , P d d d d i , j ∈ { 1 , … , d } i,j \in\{1,\ldots,d\} i , j ∈ { 1 , … , d } P i P_i P i P j P_j P j Θ i j = 1 \Theta_{ij}=1 Θ ij = 1
Proof. The matrix Θ \Theta Θ F 2 d \mathbb{F}_2^d F 2 d W 0 W_0 W 0 W W W W 0 W_0 W 0 W W W r r r 2 r = dim W 2r=\dim W 2 r = dim W r r r X X X Z Z Z r r r W 0 W_0 W 0 X X X dim W 0 \dim W_0 dim W 0 F 2 d \mathbb{F}_2^d F 2 d r + dim W 0 ≤ d r+\dim W_0\le d r + dim W 0 ≤ d
Theorem 4.3. Let n n n W W W W ′ W' W ′ F 2 2 n \mathbb{F}_2^{2n} F 2 2 n f : W → W ′ f: W \to W' f : W → W ′ ω ( f ( v ) , f ( w ) ) = ω ( v , w ) \omega(f(v),f(w))=\omega(v,w) ω ( f ( v ) , f ( w )) = ω ( v , w ) v , w ∈ W v,w \in W v , w ∈ W U U U n n n U P v U ∗ = ± P f ( v ) UP_vU^*=\pm P_{f(v)} U P v U ∗ = ± P f ( v ) v ∈ W v \in W v ∈ W P v P_v P v v v v § 3 ). If, moreover, the subspace W W W v 1 , … , v m v_1,\ldots,v_m v 1 , … , v m W W W U U U U P v i U ∗ = P f ( v i ) UP_{v_i}U^*=P_{f(v_i)} U P v i U ∗ = P f ( v i ) i ≤ m i\le m i ≤ m
Proof. By Witt’s theorem, the map f f f τ \tau τ F 2 2 n \mathbb{F}_2^{2n} F 2 2 n ω \omega ω τ \tau τ [11 , 12 ] ; let U U U U P v U ∗ UP_vU^* U P v U ∗ I I I ε i ∈ { ± 1 } \varepsilon_i \in\{\pm1\} ε i ∈ { ± 1 } U P v i U ∗ = ε i P f ( v i ) UP_{v_i}U^*=\varepsilon_iP_{f(v_i)} U P v i U ∗ = ε i P f ( v i ) f ( v i ) f(v_i) f ( v i ) b ∈ F 2 2 n b \in\mathbb{F}_2^{2n} b ∈ F 2 2 n ( − 1 ) ω ( f ( v i ) , b ) = ε i (-1)^{\omega(f(v_i),b)}=\varepsilon_i ( − 1 ) ω ( f ( v i ) , b ) = ε i i i i P b P_b P b P f ( v i ) P_{f(v_i)} P f ( v i ) ( − 1 ) ω ( f ( v i ) , b ) (-1)^{\omega(f(v_i),b)} ( − 1 ) ω ( f ( v i ) , b ) P b U P_bU P b U
Corollary 4.4. Let n n n n n n k k k 0 ≤ k ≤ n 0\le k\le n 0 ≤ k ≤ n k k k n n n Z 1 , … , Z n − k Z_1,\ldots,Z_{n-k} Z 1 , … , Z n − k Z i Z_i Z i i i i
Proof. Let G \mathcal{G} G G ′ \mathcal{G}' G ′ m m m g 1 , … , g m g_1,\ldots,g_m g 1 , … , g m g 1 ′ , … , g m ′ g'_1,\ldots,g'_m g 1 ′ , … , g m ′ G \mathcal{G} G G ′ \mathcal{G}' G ′ v i v_i v i v i ′ v'_i v i ′ i = 1 , … , m i=1,\ldots,m i = 1 , … , m v i ↦ v i ′ v_i\mapsto v'_i v i ↦ v i ′ ω \omega ω U 0 U_0 U 0 U 0 P v i U 0 ∗ = P v i ′ U_0P_{v_i}U_0^*=P_{v'_i} U 0 P v i U 0 ∗ = P v i ′ i i i I I I − I -I − I I I I − I -I − I g i = ε i P v i g_i=\varepsilon_iP_{v_i} g i = ε i P v i g i ′ = ε i ′ P v i ′ g'_i=\varepsilon'_iP_{v'_i} g i ′ = ε i ′ P v i ′ ε i , ε i ′ ∈ { ± 1 } \varepsilon_i,\varepsilon'_i\in\{\pm1\} ε i , ε i ′ ∈ { ± 1 } b ∈ F 2 2 n b\in\mathbb{F}_2^{2n} b ∈ F 2 2 n
( − 1 ) ω ( v i , b ) = ε i ε i ′ for all i , and the Clifford unitary U = P b U 0 satisfies U g i U ∗ = g i ′ for all i , (-1)^{\omega(v_i,b)} = \varepsilon_i\varepsilon'_i \text{ for all } i, \text{ and the Clifford unitary } U = P_bU_0 \text{ satisfies } Ug_iU^* = g'_i \text{ for all } i, ( − 1 ) ω ( v i , b ) = ε i ε i ′ for all i , and the Clifford unitary U = P b U 0 satisfies U g i U ∗ = g i ′ for all i , whence U G U ∗ = G ′ UGU^* = G' U G U ∗ = G ′
On countably many qubits, every finite-dimensional subspace of V V V n n n n n n Theorem 4.3 there, and extending by the identity on the remaining qubits, shows that every isometry between finite-dimensional subspaces of ( V , ω ) (V,\omega) ( V , ω ) ( V , ω ) (V,\omega) ( V , ω )
For the physicist or operator theorist. A Fraïssé limit is a countable structure whose finite configurations are, up to isomorphism, exactly those of a given kind and in which every symmetry between two finite configurations extends to a symmetry of the whole structure; any two such structures are isomorphic. By Proposition 4.2 , every finite pattern of commutation relations occurs among Pauli strings, and by Theorem 4.3 , every symmetry between finite pieces extends to a global one, implemented by a Clifford circuit. The Pauli group on countably many qubits is therefore the Fraïssé limit of the finite alternating spaces over F 2 \mathbb{F}_2 F 2 Corollary 4.4 , the five-qubit code is the image of the trivial code with generators Z 1 Z_1 Z 1 Z 2 Z_2 Z 2 Z 3 Z_3 Z 3 Z 4 Z_4 Z 4
For the logician. The structure ( V , ω ) (V,\omega) ( V , ω ) § 3 is the Pauli group modulo phases, and, for each positive integer n n n n n n ( F 2 2 n , ω ) (\mathbb{F}_2^{2n},\omega) ( F 2 2 n , ω ) § 3 came from Witt’s theorem and a back-and-forth argument, is implemented by Clifford circuits. On labels, a stabilizer code becomes an isotropic subspace, which determines it up to the signs of its generators, and Corollary 4.4 follows from ultrahomogeneity for isotropic subspaces, with the signs of the generators as additional data handled by Lemma 3.2 .
Forking and logical errors
In a simple theory, an extension of the type of an element forks when, in the sense recalled in § 2 and explained after Proposition 4.7 , it confines the element to one of infinitely many alternatives that the original type cannot tell apart. The next theorem computes forking for the Pauli group, using the description of nonforking independence in Theorem 3.3 .
Theorem 4.5. Let e e e M \mathbb{M} M ( V , ω ) (V,\omega) ( V , ω ) D ⊆ B D \subseteq B D ⊆ B M \mathbb{M} M tp ( e / B ) \operatorname{tp}(e/B) tp ( e / B ) D D D e ∈ span ( B ) ∖ span ( D ) e \in\operatorname{span}(B)\setminus\operatorname{span}(D) e ∈ span ( B ) ∖ span ( D )
Proof. By Theorem 3.3 , the type tp ( e / B ) \operatorname{tp}(e/B) tp ( e / B ) D D D span ( e D ) ∩ span ( B ) = span ( D ) \operatorname{span}(eD) \cap\operatorname{span}(B) = \operatorname{span}(D) span ( eD ) ∩ span ( B ) = span ( D ) e ∈ span ( D ) e \in\operatorname{span}(D) e ∈ span ( D ) span ( e D ) \operatorname{span}(eD) span ( eD ) span ( D ) \operatorname{span}(D) span ( D ) e D eD eD span ( D ) ⊕ { 0 , e } \operatorname{span}(D)\oplus\{0,e\} span ( D ) ⊕ { 0 , e } e + d e+d e + d d ∈ span ( D ) d \in\operatorname{span}(D) d ∈ span ( D ) span ( B ) \operatorname{span}(B) span ( B ) e ∈ span ( B ) e \in\operatorname{span}(B) e ∈ span ( B )
By Theorem 4.5 , commutation data never fork: the type of an element e e e M \mathbb{M} M B B B ω ( b , e ) \omega(b,e) ω ( b , e ) b ∈ B b \in B b ∈ B e e e D D D B B B D D D e e e B B B e e e B B B
Corollary 4.6. Let n n n F 2 2 n \mathbb{F}_{2}^{2n} F 2 2 n V V V n n n G \mathcal{G} G n n n S S S e ∈ F 2 2 n e \in\mathbb{F}_{2}^{2n} e ∈ F 2 2 n tp ( e / S ) \operatorname{tp}(e/S) tp ( e / S ) ∅ \emptyset ∅ e e e S S S G \mathcal{G} G F 2 2 n \mathbb{F}_{2}^{2n} F 2 2 n S S S ∅ \emptyset ∅
Proof. Apply Theorem 4.5 with D = ∅ D = \emptyset D = ∅ B = S B = S B = S S S S S S S span ( ∅ ) = { 0 } \operatorname{span}(\emptyset) = \{0\} span ( ∅ ) = { 0 } S S S
In Proposition 4.7 below, we show that the stabilizer group alone does not tell logical errors apart, because they all have the same type over its set of labels, and that the logical operators, once known, characterize them by forking.
Proposition 4.7. Let n n n F 2 2 n \mathbb{F}_{2}^{2n} F 2 2 n V V V G \mathcal{G} G n n n S S S L L L e ∈ F 2 2 n e \in\mathbb{F}_{2}^{2n} e ∈ F 2 2 n
(a) the label e e e tp ( e / S ∪ L ) \operatorname{tp}(e/S \cup L) tp ( e / S ∪ L ) S S S
(b) all logical errors have the same type over S S S ∅ \emptyset ∅
Proof. (a) Since the syndrome of e e e e e e S ⊥ = span ( S ∪ L ) S^\perp= \operatorname{span}(S \cup L) S ⊥ = span ( S ∪ L ) D = S D = S D = S B = S ∪ L B = S \cup L B = S ∪ L tp ( e / S ∪ L ) \operatorname{tp}(e/S \cup L) tp ( e / S ∪ L ) S S S e ∈ span ( S ∪ L ) ∖ S = S ⊥ ∖ S e \in\operatorname{span}(S \cup L) \setminus S = S^\perp\setminus S e ∈ span ( S ∪ L ) ∖ S = S ⊥ ∖ S
(b) Suppose that the label e e e e ∈ S ⊥ ∖ S e \in S^\perp\setminus S e ∈ S ⊥ ∖ S e e e S S S e e e S S S e ∉ S e \notin S e ∈ / S ω \omega ω span ( e S ) \operatorname{span}(eS) span ( e S ) ω \omega ω S S S ω ( e , e ) \omega(e,e) ω ( e , e ) ω \omega ω ω ( s , e ) \omega(s,e) ω ( s , e ) s ∈ S s \in S s ∈ S e e e S ⊥ S^\perp S ⊥ S S S e e e S S S S S S S S S ∅ \emptyset ∅
In the five-qubit code, the errors g 1 g 2 = X Y I Y X g_1g_2 = XYIYX g 1 g 2 = X Y I Y X X ˉ = X X X X X \bar{X} = XXXXX X ˉ = X X X X X S S S S S S ∅ \emptyset ∅ ∅ \emptyset ∅ X ˉ g 1 = I Y Y I X \bar{X}_{g_1} = IY Y I X X ˉ g 1 = I Y Y I X L = { X ˉ , Z ˉ } L = \{\bar{X},\bar{Z}\} L = { X ˉ , Z ˉ } X ˉ \bar{X} X ˉ Z ˉ \bar{Z} Z ˉ X ˉ g 1 \bar{X}_{g_1} X ˉ g 1 S S S S ∪ L S \cup L S ∪ L span ( S ∪ L ) \operatorname{span}(S \cup L) span ( S ∪ L ) S S S
For the physicist or operator theorist. Forking is the model-theoretic notion of an observation that singles out one of infinitely many alternatives that the data known in advance cannot tell apart and of which, for some fixed integer k ≥ 2 k \ge2 k ≥ 2 k k k φ ( x , b ) \varphi(x,b) φ ( x , b ) x x x D D D k ≥ 2 k \ge2 k ≥ 2 b b b ( b j ) j ∈ N (b_j)_{j \in\mathbb{N}} ( b j ) j ∈ N D D D k k k φ \varphi φ k k k φ ( x , b j ) \varphi(x,b_j) φ ( x , b j ) Definition 2.1 ). A sequence is indiscernible over D D D D D D D D D B B B B B B B B B Theorem 4.5 , this type forks over a subset D D D B B B B B B D D D S S S Corollary 4.6 ): the type over S S S S S S Proposition 4.7 : the stabilizer group alone sees all logical errors alike, and each logical error is pinned down as soon as a set L L L S ∪ L S \cup L S ∪ L S S S
For the logician. The theory of ( V , ω ) (V,\omega) ( V , ω ) Theorem 4.5 its forking is the dependence of this pregeometry: the type of a single element over a set forks over a subset exactly when the element is algebraic over the set but not over the subset. Thus the theory has SU-rank one, as does the theory of the Rado graph (see Theorem 3.1 ), with linear span in place of equality. In finite dimension, the information carried by a syndrome is measured by counting: if n n n m m m s 1 , … , s m s_1,\ldots,s_m s 1 , … , s m F 2 2 n \mathbb{F}_2^{2n} F 2 2 n σ ∈ F 2 m \sigma\in\mathbb{F}_2^m σ ∈ F 2 m 2 2 n − m 2^{2n-m} 2 2 n − m e e e ω ( s i , e ) = σ i \omega(s_i,e)=\sigma_i ω ( s i , e ) = σ i i i i e ↦ ( ω ( s i , e ) ) i ≤ m e \mapsto(\omega(s_i,e))_{i \le m} e ↦ ( ω ( s i , e ) ) i ≤ m S S S S S S S S S Proposition 4.7 they share one type over S S S L L L S ∪ L S \cup L S ∪ L ( V , ω ) (V,\omega) ( V , ω ) span ( S ∪ L ) \operatorname{span}(S \cup L) span ( S ∪ L ) S S S
The independence theorem and the gluing of syndromes
The Kim–Pillay independence theorem says that two nonforking extensions of a type over a model, to sets that are independent over the model, have a common nonforking extension. In the Pauli group it becomes a statement about syndromes.
Proposition 4.8. Let n n n C C C B B B D D D F 2 2 n \mathbb{F}_2^{2n} F 2 2 n span ( B C ) ∩ span ( D C ) = span ( C ) \operatorname{span}(BC) \cap\operatorname{span}(DC) = \operatorname{span}(C) span ( B C ) ∩ span ( D C ) = span ( C ) ξ 1 \xi_1 ξ 1 ξ 2 \xi_2 ξ 2 span ( B C ) \operatorname{span}(BC) span ( B C ) span ( D C ) \operatorname{span}(DC) span ( D C ) span ( C ) \operatorname{span}(C) span ( C ) e ∈ F 2 2 n e \in\mathbb{F}_2^{2n} e ∈ F 2 2 n ω ( s , e ) = ξ 1 ( s ) \omega(s,e)=\xi_1(s) ω ( s , e ) = ξ 1 ( s ) s ∈ span ( B C ) s \in\operatorname{span}(BC) s ∈ span ( B C ) ω ( s , e ) = ξ 2 ( s ) \omega(s,e)=\xi_2(s) ω ( s , e ) = ξ 2 ( s ) s ∈ span ( D C ) s \in\operatorname{span}(DC) s ∈ span ( D C )
Proof. Since ξ 1 \xi_1 ξ 1 ξ 2 \xi_2 ξ 2 ξ \xi ξ span ( B C ) + span ( D C ) \operatorname{span}(BC)+\operatorname{span}(DC) span ( B C ) + span ( D C ) ξ \xi ξ F 2 2 n \mathbb{F}_2^{2n} F 2 2 n ω \omega ω F 2 2 n \mathbb{F}_2^{2n} F 2 2 n ω ( ⋅ , e ) \omega(\cdot,e) ω ( ⋅ , e ) e e e
In the five-qubit code, take C = ∅ C = \varnothing C = ∅ B = { g 1 , g 2 } B = \{g_1,g_2\} B = { g 1 , g 2 } D = { g 3 , g 4 } D = \{g_3,g_4\} D = { g 3 , g 4 } B B B D D D 0 0 0 g 1 , g 2 g_1,g_2 g 1 , g 2 g 3 , g 4 g_3,g_4 g 3 , g 4 Example 4.1 , every nonzero syndrome is realized even by an error on a single qubit, for instance the syndrome ( 1 , 0 ∣ 1 , 1 ) (1,0 \mid1,1) ( 1 , 0 ∣ 1 , 1 ) Y I I I I YIIII Y I I I I D D D { g 1 g 2 } \{g_1g_2\} { g 1 g 2 } g 1 g 2 g_1g_2 g 1 g 2 g 1 g_1 g 1 g 2 g_2 g 2
For the physicist or operator theorist. The independence theorem is the rule that lets partial information be combined: two sets of checks that are independent over a common set constrain each other only on that set: two syndromes prescribed separately on them are realized by a single error as soon as they agree on the common set. The point of the Kim–Pillay theorem is that this gluing rule, together with the other properties of Fact 2.2, characterizes the simple theories [23 ] . In § 6 we show that the rule has no counterpart once preparations are mixed, for instance in the Pauli observable of § 5 , in which Alice holds a check and Bob’s probe is a random error: for two halves of a finite set of linearly independent checks that meet in a quarter of the set, the condition that the error anticommutes almost surely with every check of one half and commutes almost surely with every other check of the set and the same condition for the other half are each consistent but cannot hold together; infinitely many such conditions produce the tree property of the second kind.
For the logician. The statement of Proposition 4.8 is the counterpart, in finite dimension and over the span of an arbitrary set rather than over a model, of the independence theorem verified in the proof of Theorem 3.3: the whole argument is the gluing of two functionals whose domains, the spans of two sets of checks together with a common set, meet only in the span of the common set. Its physical content is that the syndrome bits of an error with respect to a set of checks are the values of a linear functional on the span of the checks, and the consistency of prescribed syndromes is therefore a matter of linear algebra on that span; the surjectivity of the syndrome map of linearly independent checks is Lemma 3.2.
Observables, mixtures and dividing
We now transport the tree properties of Definition 2.1 to the responses of an observable, as we transported the independence property in the second paper of this series [14 ] , and introduce the observables of the two paradigms. Their probes, we find, are of different kinds (see Proposition 5.4 and Lemma 5.5): the probes of the Pauli observable are the Pauli channels, and its pure probes are the Pauli strings of arbitrary support; the pure probes of the Rado observable are all sets of neighbors.
Diagonal observables
Let A A A B B B φ : A × B → { 0 , 1 } \varphi\colon A \times B \to\{0,1\} φ : A × B → { 0 , 1 } diagonal observable of φ \varphi φ
C φ = ∑ a ∈ A , b ∈ B φ ( a , b ) ∣ a ⟩ ⟨ a ∣ ⊗ ∣ b ⟩ ⟨ b ∣ on ℓ 2 ( A ) ⊗ ℓ 2 ( B ) . C_\varphi= \sum_{a\in A,b\in B} \varphi(a,b)\lvert a\rangle\langle a\rvert\otimes\lvert b\rangle\langle b\rvert\quad\text{on } \ell^2(A) \otimes\ell^2(B). C φ = a ∈ A , b ∈ B ∑ φ ( a , b ) ∣ a ⟩ ⟨ a ∣ ⊗ ∣ b ⟩ ⟨ b ∣ on ℓ 2 ( A ) ⊗ ℓ 2 ( B ) . Here ∣ a ⟩ ⟨ a ∣ \lvert a\rangle\langle a\rvert ∣ a ⟩ ⟨ a ∣ ∣ b ⟩ ⟨ b ∣ \lvert b\rangle\langle b\rvert ∣ b ⟩ ⟨ b ∣ ℓ 2 ( A ) \ell^2(A) ℓ 2 ( A ) ℓ 2 ( B ) \ell^2(B) ℓ 2 ( B ) a a a b b b a a a b b b φ ( a , b ) \varphi(a,b) φ ( a , b ) ρ \rho ρ ℓ 2 ( A ) \ell^2(A) ℓ 2 ( A ) μ \mu μ A A A mixture of her labels: the preparation draws a a a μ \mu μ C φ C_\varphi C φ ρ \rho ρ
b ↦ ∑ a ∈ A μ ( a ) φ ( a , b ) . b \mapsto\sum_{a\in A}\mu(a)\varphi(a,b). b ↦ a ∈ A ∑ μ ( a ) φ ( a , b ) . The probe algebra of the second paper is the unital C ∗ C^* C ∗ C ∗ C^* C ∗ B B B b ↦ φ ( a , b ) b\mapsto\varphi(a,b) b ↦ φ ( a , b ) a ∈ A a\in A a ∈ A 1 1 1 ∗ ^* ∗ K φ K_\varphi K φ φ ( ⋅ , b ) \varphi(\cdot,b) φ ( ⋅ , b ) b ∈ B b\in B b ∈ B { 0 , 1 } A \{0,1\}^{A} { 0 , 1 } A
Lemma 5.1. Let A A A B B B φ : A × B → { 0 , 1 } \varphi:A\times B\to\{0,1\} φ : A × B → { 0 , 1 } C φ C_\varphi C φ C ( K φ ) C(K_\varphi) C ( K φ ) K φ K_\varphi K φ φ ( ⋅ , b ) \varphi(\cdot,b) φ ( ⋅ , b ) b ∈ B b\in B b ∈ B { 0 , 1 } A \{0,1\}^{A} { 0 , 1 } A P ( K φ ) \mathcal{P}(K_\varphi) P ( K φ ) K φ K_\varphi K φ ∗ ^* ∗ μ \mu μ A A A
r μ ( ν ) = ∫ K φ ∑ a ∈ A μ ( a ) λ ( a ) d ν ( λ ) ( ν ∈ P ( K φ ) ) . r_\mu(\nu)=\int_{K_\varphi}\sum_{a\in A}\mu(a)\lambda(a)\,d\nu(\lambda)\qquad(\nu\in\mathcal{P}(K_\varphi)). r μ ( ν ) = ∫ K φ a ∈ A ∑ μ ( a ) λ ( a ) d ν ( λ ) ( ν ∈ P ( K φ )) . Proof. The unital C ∗ C^* C ∗ { b : φ ( a , b ) = 1 } \{b:\varphi(a,b)=1\} { b : φ ( a , b ) = 1 } B B B b ↦ φ ( ⋅ , b ) b\mapsto\varphi(\cdot,b) b ↦ φ ( ⋅ , b ) K φ K_\varphi K φ C ( K φ ) C(K_\varphi) C ( K φ ) r μ r_\mu r μ ν \nu ν μ \mu μ
The pure probes are the point masses δ λ \delta_\lambda δ λ λ ∈ K φ \lambda\in K_\varphi λ ∈ K φ λ \lambda λ idealized label of Bob, recording which of Alice’s labels it answers with 1 1 1 φ ( ⋅ , b ) \varphi(\cdot,b) φ ( ⋅ , b ) b ∈ B b\in B b ∈ B K φ K_\varphi K φ b b b r μ ( b ) r_\mu(b) r μ ( b ) φ ( ⋅ , b ) \varphi(\cdot,b) φ ( ⋅ , b )
5.2. The structure of an observable. To speak of the theory of an observable, we regard it as a structure of real-valued logic. For a diagonal observable C φ C_\varphi C φ S φ \mathcal{S}_\varphi S φ A A A P ( K φ ) \mathcal{P}(K_\varphi) P ( K φ ) R ( μ , ν ) = r μ ( ν ) R(\mu,\nu)=r_\mu(\nu) R ( μ , ν ) = r μ ( ν ) [ 0 , 1 ] [0,1] [ 0 , 1 ] [21 ] , in which no metric is given a priori; in an ultrapower, two elements of the same sort are identified when every atomic formula takes the same value at them, whatever the elements in its other places. We say that C φ C_\varphi C φ simple if the real-valued theory of S φ \mathcal{S}_\varphi S φ [4 ] . In an elementary extension of S φ \mathcal{S}_\varphi S φ S φ \mathcal{S}_\varphi S φ ℵ 1 \aleph_1 ℵ 1 S φ \mathcal{S}_{\varphi} S φ
Dividing for families of functions
The responses of an observable form a family of real functions on the probe space, and in the second paper we defined the independence property for such a family: a sequence in the family is independent when, for some reals α < β \alpha< \beta α < β α \alpha α β \beta β S φ \mathcal{S}_{\varphi} S φ
Definition 5.2. Let Y Y Y R \mathcal{R} R Y Y Y
For an integer k ≥ 2 k \ge2 k ≥ 2 ( r j ) j ∈ N (r_j)_{j\in\mathbb{N}} ( r j ) j ∈ N R \mathcal{R} R uniformly k k k if there are reals α < β \alpha< \beta α < β r j r_j r j ≥ β \ge\beta ≥ β Y Y Y j 1 < ⋯ < j k j_1 < \cdots< j_k j 1 < ⋯ < j k y ∈ Y y \in Y y ∈ Y r j ℓ ( y ) > α r_{j_\ell}(y) > \alpha r j ℓ ( y ) > α ℓ = 1 , … , k \ell= 1,\ldots,k ℓ = 1 , … , k
The family R \mathcal{R} R tree property of the second kind (TP2 _2 2 k ≥ 2 k \ge2 k ≥ 2 α < β \alpha< \beta α < β ( r i j ) i , j ∈ N (r_{ij})_{i,j\in\mathbb{N}} ( r ij ) i , j ∈ N R \mathcal{R} R k k k α \alpha α β \beta β f : N → N f:\mathbb{N}\to\mathbb{N} f : N → N n ∈ N n\in\mathbb{N} n ∈ N y ∈ Y y\in Y y ∈ Y r i f ( i ) ( y ) ≥ β r_{if(i)}(y)\ge\beta r i f ( i ) ( y ) ≥ β i < n i<n i < n
The tree property of Definition 2.1 , its variant of the first kind, and TP2 _2 2 k k k k ≥ 2 k \ge2 k ≥ 2 k k k k ≥ 2 k \ge2 k ≥ 2 k k k α \alpha α β \beta β [4 ] .
The Pauli observable
The Pauli observable is the diagonal observable of the symplectic form ω \omega ω V × V V \times V V × V V V V § 3 ): Alice and Bob each hold a Pauli label, and the observable reports whether the two Pauli strings anticommute. We call Alice’s label the check and Bob’s label the error; the observable then reports one syndrome bit. For a mixture μ \mu μ e e e μ \mu μ e e e Lemma 3.2 , which provides an error with any prescribed syndrome with respect to finitely many linearly independent checks, the observable has the independence property already on pure preparations.
Lemma 5.3. For the Pauli observable, the space K ω K_\omega K ω V ∗ V^* V ∗ V → F 2 V \to\mathbb{F}_2 V → F 2
Proof. Each ω ( ⋅ , e ) \omega(\cdot,e) ω ( ⋅ , e ) { 0 , 1 } V \{0,1\}^{V} { 0 , 1 } V λ \lambda λ λ \lambda λ Lemma 3.2 gives e e e ω ( ⋅ , e ) \omega(\cdot,e) ω ( ⋅ , e )
The functionals of V ∗ V^* V ∗ V ^ = ∏ k ∈ N F 2 2 \widehat{V}=\prod_{k\in\mathbb{N}}\mathbb{F}_2^2 V = ∏ k ∈ N F 2 2 V V V a ∈ V a \in V a ∈ V u ∈ V ^ u \in\widehat{V} u ∈ V ω ( a , u ) \omega(a,u) ω ( a , u ) § 3 , which is a finite sum because a a a p p p 0 < p ≤ 1 0 < p \le1 0 < p ≤ 1 ν p \nu_p ν p depolarizing noise of rate p p p V ^ \widehat{V} V ( 0 , 0 ) (0,0) ( 0 , 0 ) 1 − p 1-p 1 − p ( 1 , 0 ) (1,0) ( 1 , 0 ) ( 0 , 1 ) (0,1) ( 0 , 1 ) ( 1 , 1 ) (1,1) ( 1 , 1 ) p / 3 p/3 p /3 Pauli channel on countably many qubits is a Radon probability measure on V ^ \widehat{V} V
Proposition 5.4. Let V ^ \widehat{V} V 0 < p ≤ 1 0 < p \le1 0 < p ≤ 1 ν p \nu_p ν p p p p
(a) the map u ↦ ω ( ⋅ , u ) u \mapsto\omega(\mathord{\cdot},u) u ↦ ω ( ⋅ , u ) V ^ \widehat{V} V V ∗ V^* V ∗ V V V
(b) the probes of the Pauli observable are the Pauli channels on countably many qubits, and the response of a mixture μ \mu μ ν \nu ν μ \mu μ ν \nu ν
(c) the depolarizing noise ν p \nu_p ν p a ∈ V a \in V a ∈ V w w w
r δ a ( ν p ) = 1 2 ( 1 − ( 1 − 4 p 3 ) w ) . r_{\delta_a}(\nu_p)=\frac{1}{2}\left(1-\left(1-\frac{4p}{3}\right)^w\right). r δ a ( ν p ) = 2 1 ( 1 − ( 1 − 3 4 p ) w ) . Proof. (a) The map is a homomorphism. Write X k X_k X k Z k Z_k Z k X X X Z Z Z k k k ω ( X k , u ) \omega(X_k,u) ω ( X k , u ) ω ( Z k , u ) \omega(Z_k,u) ω ( Z k , u ) u u u k k k λ ∈ V ∗ \lambda\in V^* λ ∈ V ∗ u = ( x , z ) u=(x,z) u = ( x , z ) z k = λ ( X k ) z_k=\lambda(X_k) z k = λ ( X k ) x k = λ ( Z k ) x_k=\lambda(Z_k) x k = λ ( Z k ) k k k λ \lambda λ ω ( ⋅ , u ) \omega(\mathord{\cdot},u) ω ( ⋅ , u ) { X k , Z k : k ∈ N } \{X_k,Z_k:k\in\mathbb{N}\} { X k , Z k : k ∈ N } V V V ω ( a , u ) \omega(a,u) ω ( a , u ) u u u
(b) By Lemma 5.1 , Lemma 5.3 and (a), the probes are the Radon probability measures on V ^ \widehat{V} V r μ ( ν ) = ∫ ∑ a μ ( a ) ω ( a , u ) d ν ( u ) r_\mu(\nu)=\int\sum_a \mu(a)\omega(a,u)\,d\nu(u) r μ ( ν ) = ∫ ∑ a μ ( a ) ω ( a , u ) d ν ( u )
(c) Under ν p \nu_p ν p k k k p p p w w w a a a 2 p / 3 2p/3 2 p /3 w w w 1 2 ( 1 − ( 1 − 4 p 3 ) w ) \frac{1}{2}\left(1-\left(1-\frac{4p}{3}\right)^w\right) 2 1 ( 1 − ( 1 − 3 4 p ) w )
In what follows we identify V ∗ V^* V ∗ V ^ \widehat{V} V idealized errors . By Proposition 5.4(c), the depolarizing noise ν p \nu_p ν p p p p ν p \nu_p ν p w w w w w w 1 2 \frac{1}{2} 2 1 w w w a ∈ V a \in V a ∈ V χ a \chi_a χ a V ∗ V^* V ∗ χ a ( λ ) = ( − 1 ) λ ( a ) \chi_a(\lambda)=(-1)^{\lambda(a)} χ a ( λ ) = ( − 1 ) λ ( a ) V ∗ V^* V ∗ { ± 1 } \{\pm1\} { ± 1 } r δ a r_{\delta_a} r δ a a a a λ ( a ) = ( 1 − χ a ( λ ) ) / 2 \lambda(a)=(1-\chi_a(\lambda))/2 λ ( a ) = ( 1 − χ a ( λ )) /2 λ \lambda λ
5.5. The Rado observable. The Rado observable is the diagonal observable of the edge relation E E E Γ × Γ \Gamma\times\Gamma Γ × Γ ( Γ , E ) (\Gamma,E) ( Γ , E ) § 3 : Alice and Bob each hold a site of a random network of couplings, and the observable reports whether the two sites are coupled. By the extension property of the Rado graph, which provides a vertex adjacent to every vertex of a finite set and to none of another finite set disjoint from it, the observable has the independence property already on pure preparations. We say that the diagonal observable C φ C_{\varphi} C φ φ : A × B → { 0 , 1 } \varphi:A \times B \to\{0,1\} φ : A × B → { 0 , 1 } freely independent pure responses when K φ = { 0 , 1 } A K_{\varphi} = \{0,1\}^{A} K φ = { 0 , 1 } A
Lemma 5.5. For the Rado observable, the space K E K_{E} K E { 0 , 1 } Γ \{0,1\}^{\Gamma} { 0 , 1 } Γ
Proof. A basic open subset of { 0 , 1 } Γ \{0,1\}^{\Gamma} { 0 , 1 } Γ Γ 1 \Gamma_{1} Γ 1 Γ 0 \Gamma_{0} Γ 0 Γ 1 ∪ Γ 0 \Gamma_{1} \cup\Gamma_{0} Γ 1 ∪ Γ 0 Lemma 5.3 , the space K ω K_{\omega} K ω V ∗ V^{*} V ∗ { 0 , 1 } V \{0,1\}^{V} { 0 , 1 } V
The pure probes of the Rado observable are arbitrary sets of neighbors, that is, arbitrary subsets of Γ \Gamma Γ μ \mu μ ν \nu ν μ \mu μ ν \nu ν ν \nu ν ν { λ : λ ( a ) = 1 } \nu\{\lambda:\lambda(a)=1\} ν { λ : λ ( a ) = 1 } a ∈ Γ a \in\Gamma a ∈ Γ § 7 and § 8 we show what this difference does to the tree property.
The theory of mixed preparations has the tree property of the second kind
This section is devoted to Theorem 1.1 (C), and its idea is a comparison of two averages. Consider a finite set of Alice’s labels and a half of it. The difference between the response to the uniform mixture on the half and the response to the uniform mixture on the complementary half reaches its maximum, 1, at a probe exactly when the probe answers 1 on the first half and 0 on the second. The differences given by two halves that meet in a quarter of the set cannot both be nearly maximal, while the independence property of the pure responses supplies a pure probe with any prescribed answers on finitely many disjoint finite sets of labels. These three facts, established in the proof of Theorem 6.1 , together give the tree.
Theorem 6.1 (Mixed preparations and the tree property of the second kind). Let C φ C_{\varphi} C φ φ : A × B → { 0 , 1 } \varphi:A \times B \to\{0,1\} φ : A × B → { 0 , 1 } A A A B B B a 0 , a 1 , … a_{0},a_{1},\ldots a 0 , a 1 , … A A A N 1 , N 0 ⊆ N N_{1},N_{0} \subseteq\mathbb{N} N 1 , N 0 ⊆ N b ∈ B b \in B b ∈ B φ ( a n , b ) = 1 \varphi(a_{n},b)=1 φ ( a n , b ) = 1 n ∈ N 1 n \in N_{1} n ∈ N 1 φ ( a n , b ) = 0 \varphi(a_{n},b)=0 φ ( a n , b ) = 0 n ∈ N 0 n \in N_{0} n ∈ N 0
ψ ( x ; y 1 , y 2 ) = R ( y 1 , x ) − R ( y 2 , x ) , \psi(x;y_{1},y_{2}) = R(y_{1},x) - R(y_{2},x), ψ ( x ; y 1 , y 2 ) = R ( y 1 , x ) − R ( y 2 , x ) , in which the predicate R R R x x x y 1 , y 2 y_{1},y_{2} y 1 , y 2 S φ \mathcal{S}_{\varphi} S φ k = 2 k=2 k = 2 α = 1 / 2 \alpha=1/2 α = 1/2 β = 1 \beta=1 β = 1 k k k α \alpha α β \beta β ψ \psi ψ N 1 \mathbb{N}_{1} N 1 S φ \mathcal{S}_{\varphi} S φ
Proof. We first build finite arrays in S φ S_\varphi S φ
Let N ≥ 1 N \ge1 N ≥ 1 t t t 2 t > N 2^t > N 2 t > N 2 t N 2^tN 2 t N a n a_n a n N N N J 0 , … , J N − 1 J_0,\ldots,J_{N-1} J 0 , … , J N − 1 2 t 2^t 2 t F 2 t \mathbb{F}_2^t F 2 t w 0 , … , w N − 1 w_0,\ldots,w_{N-1} w 0 , … , w N − 1 F 2 t \mathbb{F}_2^t F 2 t i , j < N i,j<N i , j < N H i j ⊆ J i H_{ij}\subseteq J_i H ij ⊆ J i v ∈ F 2 t v\in\mathbb{F}_2^t v ∈ F 2 t w j ⋅ v = 1 w_j\cdot v=1 w j ⋅ v = 1 w j ⋅ v w_j\cdot v w j ⋅ v F 2 \mathbb{F}_2 F 2 H i j H_{ij} H ij 2 t − 1 2^{t-1} 2 t − 1 j ≠ j ′ j\ne j' j = j ′ H i j ∩ H i j ′ H_{ij}\cap H_{ij'} H ij ∩ H i j ′ 2 t − 2 2^{t-2} 2 t − 2 w j w_j w j w j ′ w_{j'} w j ′ μ i j + \mu^+_{ij} μ ij + μ i j − \mu^-_{ij} μ ij − H i j H_{ij} H ij J i ∖ H i j J_i\setminus H_{ij} J i ∖ H ij
For a probe ν \nu ν π a ( ν ) = ν { λ : λ ( a ) = 1 } ∈ [ 0 , 1 ] \pi_a(\nu)=\nu\{\lambda:\lambda(a)=1\}\in[0,1] π a ( ν ) = ν { λ : λ ( a ) = 1 } ∈ [ 0 , 1 ] a a a Lemma 5.1 , the response is then R ( μ , ν ) = ∑ a μ ( a ) π a ( ν ) R(\mu,\nu)=\sum_a\mu(a)\pi_a(\nu) R ( μ , ν ) = ∑ a μ ( a ) π a ( ν ) m = 2 t m=2^t m = 2 t
ψ ( ν ; μ i j + , μ i j − ) = 2 m ( ∑ a ∈ H i j π a ( ν ) − ∑ a ∈ J i ∖ H i j π a ( ν ) ) ≤ 1. \psi(\nu;\mu^+_{ij},\mu^-_{ij})=\frac{2}{m}\left(\sum_{a\in H_{ij}}\pi_a(\nu)-\sum_{a\in J_i\setminus H_{ij}}\pi_a(\nu)\right)\le1. ψ ( ν ; μ ij + , μ ij − ) = m 2 a ∈ H ij ∑ π a ( ν ) − a ∈ J i ∖ H ij ∑ π a ( ν ) ≤ 1. For j ≠ j ′ j\ne j' j = j ′
4 m ( ∑ a ∈ H i j ∩ H i j ′ π a ( ν ) − ∑ a ∈ J i ∖ ( H i j ∪ H i j ′ ) π a ( ν ) ) ≤ 4 m ⋅ m 4 = 1 , \frac{4}{m}\left(\sum_{a\in H_{ij}\cap H_{ij'}}\pi_a(\nu)-\sum_{a\in J_i\setminus(H_{ij}\cup H_{ij'})}\pi_a(\nu)\right)\le\frac{4}{m}\cdot\frac{m}{4}=1, m 4 a ∈ H ij ∩ H i j ′ ∑ π a ( ν ) − a ∈ J i ∖ ( H ij ∪ H i j ′ ) ∑ π a ( ν ) ≤ m 4 ⋅ 4 m = 1 , so the two values are never both greater than 1 / 2 1/2 1/2 f f f { 0 , … , N − 1 } \{0,\ldots,N-1\} { 0 , … , N − 1 } ⋃ i H i f ( i ) \bigcup_i H_{if(i)} ⋃ i H i f ( i ) ⋃ i ( J i ∖ H i f ( i ) ) \bigcup_i(J_i\setminus H_{if(i)}) ⋃ i ( J i ∖ H i f ( i ) ) b b b φ ( ⋅ , b ) \varphi(\cdot,b) φ ( ⋅ , b ) ψ ( ⋅ ; μ i f ( i ) + , μ i f ( i ) − ) \psi(\cdot;\mu^+_{if(i)},\mu^-_{if(i)}) ψ ( ⋅ ; μ i f ( i ) + , μ i f ( i ) − ) i < N i<N i < N
Thus, for every N N N S φ S_\varphi S φ 2 N 2 2N^2 2 N 2 y i j ± y^\pm_{ij} y ij ± i , j < N i,j<N i , j < N f f f { 0 , … , N − 1 } \{0,\ldots,N-1\} { 0 , … , N − 1 } sup x min i < N ψ ( x ; y i f ( i ) + , y i f ( i ) − ) \sup_x\min_{i<N}\psi(x;y^+_{if(i)},y^-_{if(i)}) sup x min i < N ψ ( x ; y i f ( i ) + , y i f ( i ) − ) i < N i<N i < N j , j ′ < N j,j'<N j , j ′ < N sup x min ( ψ ( x ; y i j + , y i j − ) , ψ ( x ; y i j ′ + , y i j ′ − ) ) \sup_x\min(\psi(x;y^+_{ij},y^-_{ij}),\psi(x;y^+_{ij'},y^-_{ij'})) sup x min ( ψ ( x ; y ij + , y ij − ) , ψ ( x ; y i j ′ + , y i j ′ − )) 1 / 2 1/2 1/2 N N N N N N ℵ 1 \aleph_1 ℵ 1 S φ S_\varphi S φ ( y i j ± ) i , j ∈ N (y^\pm_{ij})_{i,j\in\mathbb{N}} ( y ij ± ) i , j ∈ N N N N [4 ] .
It remains to be shown that every simple diagonal observable is NIP. The hypothesis of the theorem is the independence property of the pure responses, in the form used in the second paper: actual labels are dense in K φ K_\varphi K φ a n a_n a n K φ K_\varphi K φ λ ↦ λ ( a n ) \lambda\mapsto\lambda(a_n) λ ↦ λ ( a n ) K φ K_\varphi K φ K φ K_\varphi K φ C ( K φ ) C(K_\varphi) C ( K φ ) 1 1 1 C ( K φ ) C(K_\varphi) C ( K φ ) S φ \mathcal{S}_{\varphi} S φ
The array that witnesses the tree property of the second kind in the proof of Theorem 6.1 lies in an ℵ 1 \aleph_{1} ℵ 1 S φ \mathcal{S}_{\varphi} S φ
The Pauli observable: syndrome sectors and the first check to fire
We turn to Theorem 1.1 (D): for the Pauli observable, actual preparations witness the tree property of the second kind. The tool is the expression of the projector onto the states of a given syndrome as an average over the group generated by the checks; we first state it for responses, as a formula for the indicator of a syndrome sector, the set of idealized errors with a given syndrome. The idea of the theorem is then to let a single mixture ask a question about many checks at once. Given a block, a sequence of linearly independent checks, let Alice draw a Pauli string uniformly from the coset of one of its checks modulo the span of the checks before it. In the proof of Theorem 7.2 we show that if the earlier checks are silent on Bob’s error, that is, commute with it, and the chosen check fires, that is, anticommutes with it, then every string in the coset anticommutes with the error, and that if one of the earlier checks fires, exactly half of the strings do. Two different checks of a block cannot both be the first to fire, and the syndromes with respect to several blocks can be prescribed separately when all their checks together are linearly independent (see Lemma 3.2 ).
Syndrome sectors
Let d d d g 1 , … , g d g_{1},\ldots,g_{d} g 1 , … , g d V V V G G G σ ∈ F 2 d \sigma\in\mathbb{F}_{2}^{d} σ ∈ F 2 d σ \sigma σ G G G σ ( g i ) = σ i \sigma(g_{i})=\sigma_{i} σ ( g i ) = σ i Σ σ = { λ ∈ V ∗ : λ ( g i ) = σ i for i ≤ d } \Sigma_{\sigma}=\{\lambda\in V^{*}:\lambda(g_{i})=\sigma_{i}\text{ for }i\le d\} Σ σ = { λ ∈ V ∗ : λ ( g i ) = σ i for i ≤ d } σ \sigma σ syndrome sector . For s ∈ G s\in G s ∈ G r s r_{s} r s r δ s r_{\delta_{s}} r δ s s s s χ s \chi_{s} χ s V ∗ V^{*} V ∗ χ s ( λ ) = ( − 1 ) λ ( s ) \chi_{s}(\lambda)=(-1)^{\lambda(s)} χ s ( λ ) = ( − 1 ) λ ( s )
Proposition 7.1. Let d d d g 1 , … , g d ∈ V g_{1},\ldots,g_{d}\in V g 1 , … , g d ∈ V G G G σ ∈ F 2 d \sigma\in\mathbb{F}_{2}^{d} σ ∈ F 2 d G G G σ ( g i ) = σ i \sigma(g_{i})=\sigma_{i} σ ( g i ) = σ i i ≤ d i\le d i ≤ d Σ σ \Sigma_{\sigma} Σ σ λ ∈ V ∗ \lambda\in V^{*} λ ∈ V ∗
1 Σ σ ( λ ) = 2 − d ∑ s ∈ G ( − 1 ) σ ( s ) χ s ( λ ) = 2 − d ∑ s ∈ G ( − 1 ) σ ( s ) − 2 1 − d ∑ s ∈ G ( − 1 ) σ ( s ) r s ( λ ) . \mathbf{1}_{\Sigma_{\sigma}}(\lambda)=2^{-d}\sum_{s\in G}(-1)^{\sigma(s)}\chi_{s}(\lambda)=2^{-d}\sum_{s\in G}(-1)^{\sigma(s)}-2^{1-d}\sum_{s\in G}(-1)^{\sigma(s)}r_{s}(\lambda). 1 Σ σ ( λ ) = 2 − d s ∈ G ∑ ( − 1 ) σ ( s ) χ s ( λ ) = 2 − d s ∈ G ∑ ( − 1 ) σ ( s ) − 2 1 − d s ∈ G ∑ ( − 1 ) σ ( s ) r s ( λ ) . Consequently, if σ ≠ 0 \sigma\ne0 σ = 0 1 Σ σ = r μ σ 1 − r μ σ 0 \mathbf{1}_{\Sigma_{\sigma}}=r_{\mu_{\sigma}^{1}}-r_{\mu_{\sigma}^{0}} 1 Σ σ = r μ σ 1 − r μ σ 0 μ σ 1 \mu_{\sigma}^{1} μ σ 1 μ σ 0 \mu_{\sigma}^{0} μ σ 0 { s ∈ G : σ ( s ) = 1 } \{s\in G:\sigma(s)=1\} { s ∈ G : σ ( s ) = 1 } { s ∈ G : σ ( s ) = 0 } \{s\in G:\sigma(s)=0\} { s ∈ G : σ ( s ) = 0 } 1 Σ 0 = 1 − 2 r μ G \mathbf{1}_{\Sigma_{0}}=1-2r_{\mu_{G}} 1 Σ 0 = 1 − 2 r μ G μ G \mu_{G} μ G G G G ν \nu ν ν \nu ν σ \sigma σ r μ σ 1 ( ν ) − r μ σ 0 ( ν ) r_{\mu_{\sigma}^{1}}(\nu)-r_{\mu_{\sigma}^{0}}(\nu) r μ σ 1 ( ν ) − r μ σ 0 ( ν ) σ ≠ 0 \sigma\ne0 σ = 0 1 − 2 r μ G ( ν ) 1-2r_{\mu_{G}}(\nu) 1 − 2 r μ G ( ν ) σ = 0 \sigma=0 σ = 0
Proof. The map s ↦ ( − 1 ) σ ( s ) χ s ( λ ) = ( − 1 ) ( σ + λ ) ( s ) s\mapsto(-1)^{\sigma(s)}\chi_{s}(\lambda)=(-1)^{(\sigma+\lambda)(s)} s ↦ ( − 1 ) σ ( s ) χ s ( λ ) = ( − 1 ) ( σ + λ ) ( s ) G G G G G G 2 d 2^{d} 2 d σ + λ \sigma+\lambda σ + λ G G G λ ∈ Σ σ \lambda\in\Sigma_{\sigma} λ ∈ Σ σ 0 0 0 G G G 1 1 1 G G G χ s = 1 − 2 r s \chi_{s}=1-2r_{s} χ s = 1 − 2 r s σ ≠ 0 \sigma\ne0 σ = 0 σ \sigma σ 2 d − 1 2^{d-1} 2 d − 1 σ \sigma σ r μ σ 1 − r μ σ 0 r_{\mu_{\sigma}^{1}}-r_{\mu_{\sigma}^{0}} r μ σ 1 − r μ σ 0 σ = 0 \sigma=0 σ = 0 2 d 2^{d} 2 d ν \nu ν
When the checks commute pairwise and carry signs, the operator 2 − d ∑ s ∈ G ( − 1 ) σ ( s ) g s 2^{-d}\sum_{s\in G}(-1)^{\sigma(s)}g_s 2 − d ∑ s ∈ G ( − 1 ) σ ( s ) g s g s g_s g s s s s σ \sigma σ [18 ] , and the probability of the outcome σ \sigma σ ν \nu ν 1 + 2 = 3 1+2=3 1 + 2 = 3 d d d
The first check to fire
The next theorem arranges the syndrome sectors of the initial segments of blocks of checks in an array that witnesses the tree property of the second kind.
Theorem 7.2 (The first check to fire). Let ( g i m ) i , m ∈ N (g_{im})_{i,m\in\mathbb{N}} ( g im ) i , m ∈ N V V V W i j = span ( g i m : m < j ) W_{ij}=\operatorname{span}(g_{im}:m<j) W ij = span ( g im : m < j ) i , j ∈ N i,j\in\mathbb{N} i , j ∈ N μ i j \mu_{ij} μ ij g i j + W i j g_{ij}+W_{ij} g ij + W ij
(a) for every f : N → N f:\mathbb{N}\to\mathbb{N} f : N → N n ∈ N n\in\mathbb{N} n ∈ N e ∈ V e\in V e ∈ V r μ i f ( i ) ( e ) = 1 r_{\mu_{if(i)}}(e)=1 r μ i f ( i ) ( e ) = 1 i < n i<n i < n λ ∈ V ∗ \lambda\in V^* λ ∈ V ∗ r μ i f ( i ) ( λ ) = 1 r_{\mu_{if(i)}}(\lambda)=1 r μ i f ( i ) ( λ ) = 1 i i i
(b) for every i i i j ≠ j ′ j\ne j' j = j ′ ν ∈ P ( V ∗ ) \nu\in\mathcal{P}(V^*) ν ∈ P ( V ∗ ) min ( r μ i j ( ν ) , r μ i j ′ ( ν ) ) ≤ 2 / 3 \min(r_{\mu_{ij}}(\nu),r_{\mu_{ij'}}(\nu))\le2/3 min ( r μ ij ( ν ) , r μ i j ′ ( ν )) ≤ 2/3 2 / 3 2/3 2/3
Consequently, the family of responses of Alice has the tree property of the second kind in the sense of Definition 5.2, with k = 2 k=2 k = 2 α = 2 / 3 \alpha=2/3 α = 2/3 β = 1 \beta=1 β = 1
Proof. We first compute the response of μ i j \mu_{ij} μ ij λ ∈ V ∗ \lambda\in V^* λ ∈ V ∗ λ \lambda λ W i j W_{ij} W ij λ \lambda λ 1 1 1 g i j + W i j g_{ij}+W_{ij} g ij + W ij F 2 \mathbb{F}_2 F 2 g i j g_{ij} g ij λ \lambda λ W i j W_{ij} W ij λ \lambda λ λ ( g i j ) \lambda(g_{ij}) λ ( g ij )
r μ i j ( λ ) = { 1 if λ ( g i m ) = 0 for m < j and λ ( g i j ) = 1 , 1 / 2 if λ ( g i m ) = 1 for some m < j , 0 otherwise. (1) r_{\mu_{ij}}(\lambda)=
\begin{cases}
1 & \text{if }\lambda(g_{im})=0\text{ for }m<j\text{ and }\lambda(g_{ij})=1,\\
1/2 & \text{if }\lambda(g_{im})=1\text{ for some }m<j,\\
0 & \text{otherwise.}
\end{cases} \tag*{(1)} r μ ij ( λ ) = ⎩ ⎨ ⎧ 1 1/2 0 if λ ( g im ) = 0 for m < j and λ ( g ij ) = 1 , if λ ( g im ) = 1 for some m < j , otherwise. (1) In words, the response is $1$ exactly when g i j g_{ij} g ij ( g i m ) m ∈ N (g_{im})_{m\in\mathbb{N}} ( g im ) m ∈ N i i i 1 1 1
(a) Let f f f n n n λ ( g i m ) = 0 \lambda(g_{im})=0 λ ( g im ) = 0 m < f ( i ) m<f(i) m < f ( i ) λ ( g i f ( i ) ) = 1 \lambda(g_{if(i)})=1 λ ( g i f ( i ) ) = 1 i < n i<n i < n Lemma 3.2 gives an error e e e ω ( ⋅ , e ) \omega(\mathord{\cdot},e) ω ( ⋅ , e ) r μ i f ( i ) ( e ) r_{\mu_{if(i)}}(e) r μ i f ( i ) ( e ) 1 1 1 i < n i<n i < n i i i V ∗ V^* V ∗ g i m g_{im} g im λ \lambda λ
(b) By symmetry, we may assume that j < j ′ j<j' j < j ′ ( r μ i j ( λ ) , r μ i j ′ ( λ ) ) (r_{\mu_{ij}}(\lambda),r_{\mu_{ij'}}(\lambda)) ( r μ ij ( λ ) , r μ i j ′ ( λ ))
( 1 , 1 / 2 ) , ( 1 / 2 , 1 / 2 ) , ( 0 , 1 / 2 ) , ( 0 , 1 ) , ( 0 , 0 ) . (1,1/2),\qquad(1/2,1/2),\qquad(0,1/2),\qquad(0,1),\qquad(0,0). ( 1 , 1/2 ) , ( 1/2 , 1/2 ) , ( 0 , 1/2 ) , ( 0 , 1 ) , ( 0 , 0 ) . Indeed, if the first check of block i i i g i 0 , … , g i j ′ g_{i0},\ldots,g_{ij'} g i 0 , … , g i j ′ m m m ( 1 / 2 , 1 / 2 ) (1/2,1/2) ( 1/2 , 1/2 ) m < j m<j m < j ( 1 , 1 / 2 ) (1,1/2) ( 1 , 1/2 ) m = j m=j m = j ( 0 , 1 / 2 ) (0,1/2) ( 0 , 1/2 ) j < m < j ′ j<m<j' j < m < j ′ ( 0 , 1 ) (0,1) ( 0 , 1 ) m = j ′ m=j' m = j ′ ( 0 , 0 ) (0,0) ( 0 , 0 ) ν \nu ν 2 / 3 2/3 2/3 2 3 ( 1 2 , 1 2 ) + 1 3 ( 0 , 1 ) = ( 2 3 , 2 3 ) \frac{2}{3}(\frac{1}{2},\frac{1}{2})+\frac{1}{3}(0,1)=(\frac{2}{3},\frac{2}{3}) 3 2 ( 2 1 , 2 1 ) + 3 1 ( 0 , 1 ) = ( 3 2 , 3 2 ) 2 3 λ 1 + 1 3 λ 2 \frac{2}{3}\lambda_1+\frac{1}{3}\lambda_2 3 2 λ 1 + 3 1 λ 2 λ 1 \lambda_1 λ 1 λ 2 \lambda_2 λ 2 g i j g_{ij} g ij g i j ′ g_{ij'} g i j ′ i i i ( r μ i j ) (r_{\mu_{ij}}) ( r μ ij ) k = 2 k=2 k = 2 α = 2 / 3 \alpha=2/3 α = 2/3 β = 1 \beta=1 β = 1
Example 7.4. Index the qubits by pairs ( i , m ) ∈ N 2 (i,m)\in\mathbb{N}^2 ( i , m ) ∈ N 2 i ∈ N i\in\mathbb{N} i ∈ N ( i , m ) (i,m) ( i , m ) m ∈ N m\in\mathbb{N} m ∈ N i i i g i m = Z i , m Z i , m + 1 g_{im}=Z_{i,m}Z_{i,m+1} g im = Z i , m Z i , m + 1 m m m m + 1 m+1 m + 1 i i i X i , m X_{i,m} X i , m Z i , m Z_{i,m} Z i , m ( i , m ) (i,m) ( i , m ) e = ∏ i , m X i , m x i , m e=\prod_{i,m}X_{i,m}^{x_{i,m}} e = ∏ i , m X i , m x i , m x i , m ∈ F 2 x_{i,m}\in\mathbb{F}_2 x i , m ∈ F 2 ω ( g i m , e ) = x i , m + x i , m + 1 \omega(g_{im},e)=x_{i,m}+x_{i,m+1} ω ( g im , e ) = x i , m + x i , m + 1 m m m m + 1 m+1 m + 1 i i i e e e e e e μ i j \mu_{ij} μ ij g i j g_{ij} g ij g i 0 , … , g i , j − 1 g_{i0},\ldots,g_{i,j-1} g i 0 , … , g i , j − 1 e e e i i i j j j j + 1 j+1 j + 1 i i i V ^ ∖ V V^{\hat{}}\setminus V V ^ ∖ V
By Theorem 6.1 , the real-valued theory of the structure S ω S_\omega S ω ( V , ω ) (V,\omega) ( V , ω ) Theorem 7.2 the tree property of the second kind is witnessed by actual preparations, for the atomic formula, the response itself, rather than for the difference of two responses.
The Rado observable: marginals and idealized preparations
In this section we prove Theorem 1.1 (E), which concerns the Rado observable. By Theorem 6.1 , the real-valued theory of the structure of its mixed preparations and probes has the tree property of the second kind, as that of the Pauli observable does. In Theorem 8.1 , Corollary 8.2 and Theorem 8.3 we show that every array that witnesses this property for a quantifier-free formula contains idealized preparations, because the conditions that actual mixtures impose on the marginals of a probe, the probabilities with which it declares the individual vertices neighbors, are compatible on disjoint finite sets of vertices. After Corollary 8.2 we note that the same holds for the random bipartite graph, the Fraïssé limit of the finite bipartite graphs with the two sides as two sorts, which has exactly the shape of a bipartite observable: Alice’s labels form one side, and Bob’s the other.
Affine combinations of responses
Consider a diagonal observable with freely independent pure responses, that is, one for which every pattern λ ∈ { 0 , 1 } A \lambda\in\{0,1\}^{A} λ ∈ { 0 , 1 } A A A A ν \nu ν π a ( ν ) = ν { λ : λ ( a ) = 1 } \pi_a(\nu)=\nu\{\lambda:\lambda(a)=1\} π a ( ν ) = ν { λ : λ ( a ) = 1 } a ∈ A a\in A a ∈ A [ 0 , 1 ] A [0,1]^{A} [ 0 , 1 ] A
h c , γ ( ν ) = γ + ∑ a ∈ A c ( a ) π a ( ν ) , γ ∈ R , c ∈ ℓ 1 ( A ) , h_{c,\gamma}(\nu)=\gamma+\sum_{a\in A}c(a)\pi_a(\nu),\qquad\gamma\in\mathbb{R},\ c\in\ell^1(A), h c , γ ( ν ) = γ + a ∈ A ∑ c ( a ) π a ( ν ) , γ ∈ R , c ∈ ℓ 1 ( A ) , and its supremum over the probe space is γ + ∑ a c ( a ) + \gamma+\sum_a c(a)^+ γ + ∑ a c ( a ) + λ = 1 { c > 0 } \lambda=1_{\{c>0\}} λ = 1 { c > 0 } Theorem 8.1 below we show, by a gliding hump, that a sequence of such functions along which ∣ γ ∣ + ∥ c ∥ 1 |\gamma|+\|c\|_1 ∣ γ ∣ + ∥ c ∥ 1 k k k k k k
Theorem 8.1 (Compatibility of affine conditions). Let C φ C_\varphi C φ φ : A × B → { 0 , 1 } \varphi:A\times B\to\{0,1\} φ : A × B → { 0 , 1 } A A A B B B κ ≥ 1 \kappa\ge1 κ ≥ 1 R κ \mathcal{R}_\kappa R κ γ + ∑ i < n c i μ i \gamma+\sum_{i<n}c_i\mu_i γ + ∑ i < n c i μ i P ( { 0 , 1 } A ) \mathcal{P}(\{0,1\}^{A}) P ({ 0 , 1 } A ) { 0 , 1 } A \{0,1\}^{A} { 0 , 1 } A n ∈ N n\in\mathbb{N} n ∈ N μ i \mu_i μ i γ \gamma γ c i c_i c i ∣ γ ∣ + ∑ i ∣ c i ∣ ≤ κ |\gamma|+\sum_i|c_i|\le\kappa ∣ γ ∣ + ∑ i ∣ c i ∣ ≤ κ R κ \mathcal{R}_\kappa R κ k k k k ≥ 2 k\ge2 k ≥ 2 R κ \mathcal{R}_\kappa R κ
Proof. Let ( h j ) j ∈ N (h_j)_{j\in\mathbb{N}} ( h j ) j ∈ N R κ \mathcal{R}_\kappa R κ α < β \alpha<\beta α < β h j h_j h j ≥ β \ge\beta ≥ β k ≥ 2 k\ge2 k ≥ 2 j 1 < ⋯ < j k j_1<\cdots<j_k j 1 < ⋯ < j k λ \lambda λ h j ℓ ( δ λ ) > α h_{j_\ell}(\delta_\lambda)>\alpha h j ℓ ( δ λ ) > α ℓ = 1 , … , k \ell=1,\ldots,k ℓ = 1 , … , k
Write h j = γ j + ∑ i c j , i r μ j , i h_j=\gamma_j+\sum_i c_{j,i}r_{\mu_{j,i}} h j = γ j + ∑ i c j , i r μ j , i c j , i c_{j,i} c j , i μ j , i \mu_{j,i} μ j , i h j = h c j , γ j h_j=h_{c_j,\gamma_j} h j = h c j , γ j c j = ∑ i c j , i μ j , i c_j=\sum_i c_{j,i}\mu_{j,i} c j = ∑ i c j , i μ j , i ∥ c j ∥ 1 ≤ κ \|c_j\|_1\le\kappa ∥ c j ∥ 1 ≤ κ A A A ( c j ) (c_j) ( c j ) A A A c c c ∥ c ∥ 1 ≤ κ \|c\|_1\le\kappa ∥ c ∥ 1 ≤ κ η = ( β − α ) / 5 \eta=(\beta-\alpha)/5 η = ( β − α ) /5 F ⊆ A F \subseteq A F ⊆ A ∥ c ↾ ( A ∖ F ) ∥ 1 < η \lVert c \upharpoonright(A \setminus F)\rVert_1 < \eta ∥ c ↾ ( A ∖ F ) ∥ 1 < η F 0 = F F_0 = F F 0 = F j 1 < ⋯ < j k j_1 < \cdots< j_k j 1 < ⋯ < j k F 0 ⊆ F 1 ⊆ ⋯ ⊆ F k F_0 \subseteq F_1 \subseteq\cdots\subseteq F_k F 0 ⊆ F 1 ⊆ ⋯ ⊆ F k
∥ ( c j ℓ − c ) ↾ F ℓ − 1 ∥ 1 < η and ∥ c j ℓ ↾ ( A ∖ F ℓ ) ∥ 1 < η ; \lVert(c_{j_\ell} - c) \upharpoonright F_{\ell-1}\rVert_1 < \eta
\quad\text{and}\quad
\lVert c_{j_\ell} \upharpoonright(A \setminus F_\ell)\rVert_1 < \eta; ∥( c j ℓ − c ) ↾ F ℓ − 1 ∥ 1 < η and ∥ c j ℓ ↾ ( A ∖ F ℓ ) ∥ 1 < η ; the first condition holds for all large indices by pointwise convergence, and the second for a large enough finite set. Define λ ∈ { 0 , 1 } A \lambda\in\{0,1\}^A λ ∈ { 0 , 1 } A λ ( a ) = 1 \lambda(a) = 1 λ ( a ) = 1 a ∈ F a \in F a ∈ F c ( a ) > 0 c(a) > 0 c ( a ) > 0 a ∈ F ℓ ∖ F ℓ − 1 a \in F_\ell\setminus F_{\ell-1} a ∈ F ℓ ∖ F ℓ − 1 c j ℓ ( a ) > 0 c_{j_\ell}(a) > 0 c j ℓ ( a ) > 0 ℓ ≤ k \ell\le k ℓ ≤ k
Let ℓ ≤ k \ell\le k ℓ ≤ k λ \lambda λ h j ℓ h_{j_\ell} h j ℓ
sup h j ℓ − h j ℓ ( δ λ ) = ∑ λ ( a ) = 0 c j ℓ ( a ) + + ∑ λ ( a ) = 1 c j ℓ ( a ) − , \sup h_{j_\ell} - h_{j_\ell}(\delta_\lambda)
=
\sum_{\lambda(a)=0} c_{j_\ell}(a)^+
+
\sum_{\lambda(a)=1} c_{j_\ell}(a)^-, sup h j ℓ − h j ℓ ( δ λ ) = λ ( a ) = 0 ∑ c j ℓ ( a ) + + λ ( a ) = 1 ∑ c j ℓ ( a ) − , and we bound its contribution on four disjoint pieces of A A A F ℓ ∖ F ℓ − 1 F_\ell\setminus F_{\ell-1} F ℓ ∖ F ℓ − 1 λ \lambda λ c j ℓ c_{j_\ell} c j ℓ F F F c c c c j ℓ c_{j_\ell} c j ℓ c c c ∣ c j ℓ ( a ) − c ( a ) ∣ \lvert c_{j_\ell}(a) - c(a)\rvert ∣ c j ℓ ( a ) − c ( a )∣ η \eta η F ℓ − 1 ∖ F F_{\ell-1} \setminus F F ℓ − 1 ∖ F ∥ c j ℓ ↾ ( F ℓ − 1 ∖ F ) ∥ 1 ≤ ∥ ( c j ℓ − c ) ↾ F ℓ − 1 ∥ 1 + ∥ c ↾ ( A ∖ F ) ∥ 1 < 2 η \lVert c_{j_\ell} \upharpoonright(F_{\ell-1} \setminus F)\rVert_1 \le\lVert(c_{j_\ell} - c) \upharpoonright F_{\ell-1}\rVert_1 + \lVert c \upharpoonright(A \setminus F)\rVert_1 < 2\eta ∥ c j ℓ ↾ ( F ℓ − 1 ∖ F ) ∥ 1 ≤ ∥( c j ℓ − c ) ↾ F ℓ − 1 ∥ 1 + ∥ c ↾ ( A ∖ F ) ∥ 1 < 2 η A ∖ F ℓ A \setminus F_\ell A ∖ F ℓ η \eta η h j ℓ ( δ λ ) > sup h j ℓ − 4 η ≥ β − 4 η > α h_{j_\ell}(\delta_\lambda) > \sup h_{j_\ell} - 4\eta\ge\beta- 4\eta> \alpha h j ℓ ( δ λ ) > sup h j ℓ − 4 η ≥ β − 4 η > α
Corollary 8.2. Let n ∈ N n \in\mathbb{N} n ∈ N γ \gamma γ c i c_i c i i < n i < n i < n γ + ∑ i < n c i R ( y i , x ) \gamma+ \sum_{i<n} c_iR(y_i,x) γ + ∑ i < n c i R ( y i , x ) R R R y i y_i y i x x x S E S_E S E
Proof. By Lemma 5.5, the Rado observable has freely independent pure responses. With actual preparations as parameters, the instances of the formula lie in the family R κ \mathcal{R}_\kappa R κ Theorem 8.1 for every κ > 0 \kappa> 0 κ > 0 κ ≥ ∣ γ ∣ + ∑ i < n ∣ c i ∣ \kappa\ge|\gamma| + \sum_{i<n} |c_i| κ ≥ ∣ γ ∣ + ∑ i < n ∣ c i ∣ Theorem 6.1 . □
The finite arrays in the proof of Theorem 6.1 are made of actual preparations, and their rows have any prescribed finite length; by Theorem 8.1 , the rows cannot be made infinite in S E S_E S E ℵ 1 \aleph_1 ℵ 1
Quantifier-free formulas
In Theorem 8.1 the conditions on a probe are given by affine combinations of responses. In the real-valued logic of the second paper, a quantifier-free formula in a variable x x x [ 0 , 1 ] [0,1] [ 0 , 1 ] Theorem 8.1 for these formulas. Its proof uses the same gliding hump, with one change: a continuous function of responses is no longer maximized by reading off signs (we show this after the proof), so instead of building the probe from signs we glue maximizers of the individual instances on disjoint blocks of labels.
Theorem 8.3 (Compatibility of quantifier-free conditions). Let C φ C_{\varphi} C φ φ : A × B → { 0 , 1 } \varphi:A \times B \to\{0,1\} φ : A × B → { 0 , 1 } A A A B B B n ≥ 1 n \ge1 n ≥ 1 u : [ 0 , 1 ] n → R u:[0,1]^n \to\mathbb{R} u : [ 0 , 1 ] n → R R u \mathcal{R}_u R u
h ( ν ) = u ( r μ 1 ( ν ) , … , r μ n ( ν ) ) ( ν ∈ P ( { 0 , 1 } A ) ) . h(\nu)=u\left(r_{\mu_1}(\nu),\ldots,r_{\mu_n}(\nu)\right) \qquad\left(\nu\in\mathcal{P}\left(\{0,1\}^{A}\right)\right). h ( ν ) = u ( r μ 1 ( ν ) , … , r μ n ( ν ) ) ( ν ∈ P ( { 0 , 1 } A ) ) . where μ 1 , … , μ n \mu_1,\ldots,\mu_n μ 1 , … , μ n R u \mathcal{R}_u R u k k k k ≥ 2 k \ge2 k ≥ 2 u ( R ( y 1 , x ) , … , R ( y n , x ) ) u(R(y_1,x),\ldots,R(y_n,x)) u ( R ( y 1 , x ) , … , R ( y n , x )) R R R x x x y 1 , … , y n y_1,\ldots,y_n y 1 , … , y n
Proof. For ν ∈ P ( { 0 , 1 } A ) \nu\in\mathcal{P}(\{0,1\}^{A}) ν ∈ P ({ 0 , 1 } A ) π ( ν ) ∈ [ 0 , 1 ] A \pi(\nu) \in[0,1]^A π ( ν ) ∈ [ 0 , 1 ] A ( π a ( ν ) ) a ∈ A (\pi_a(\nu))_{a\in A} ( π a ( ν ) ) a ∈ A Theorem 8.1 . Every h ∈ R u h \in\mathcal{R}_u h ∈ R u h ( ν ) = H ( π ( ν ) ) h(\nu)=H(\pi(\nu)) h ( ν ) = H ( π ( ν ))
H ( q ) = u ( ⟨ μ 1 , q ⟩ , … , ⟨ μ n , q ⟩ ) , ⟨ μ , q ⟩ = ∑ a ∈ A μ ( a ) q a , H(q)=u\left(\langle\mu_1,q\rangle,\ldots,\langle\mu_n,q\rangle\right), \qquad\langle\mu,q\rangle=\sum_{a\in A}\mu(a)q_a, H ( q ) = u ( ⟨ μ 1 , q ⟩ , … , ⟨ μ n , q ⟩ ) , ⟨ μ , q ⟩ = a ∈ A ∑ μ ( a ) q a , and every q ∈ [ 0 , 1 ] A q \in[0,1]^A q ∈ [ 0 , 1 ] A [ 0 , 1 ] A [0,1]^A [ 0 , 1 ] A
Let ( h j ) j ∈ N (h_j)_{j\in\mathbb{N}} ( h j ) j ∈ N R u \mathcal{R}_u R u μ j , 1 , … , μ j , n \mu_{j,1},\ldots,\mu_{j,n} μ j , 1 , … , μ j , n H j H_j H j α < β \alpha< \beta α < β h j h_j h j ≥ β \ge\beta ≥ β k ≥ 2 k \ge2 k ≥ 2 j 1 < ⋯ < j k j_1 < \cdots< j_k j 1 < ⋯ < j k q ∈ [ 0 , 1 ] A q \in[0,1]^A q ∈ [ 0 , 1 ] A H j ℓ ( q ) > α H_{j_\ell}(q)>\alpha H j ℓ ( q ) > α ℓ = 1 , … , k \ell=1,\ldots,k ℓ = 1 , … , k u u u θ > 0 \theta>0 θ > 0 ∣ u ( s ) − u ( t ) ∣ < β − α |u(s)-u(t)|<\beta-\alpha ∣ u ( s ) − u ( t ) ∣ < β − α max i ∣ s i − t i ∣ < θ \max_i|s_i-t_i|<\theta max i ∣ s i − t i ∣ < θ j j j q ( j ) ∈ [ 0 , 1 ] A q^{(j)}\in[0,1]^A q ( j ) ∈ [ 0 , 1 ] A H j ( q ( j ) ) ≥ β H_j(q^{(j)})\ge\beta H j ( q ( j ) ) ≥ β A A A j j j μ j , i → μ i \mu_{j,i}\to\mu_i μ j , i → μ i A A A i ≤ n i\le n i ≤ n q ( j ) → q ∞ q^{(j)}\to q^\infty q ( j ) → q ∞ [ 0 , 1 ] A [0,1]^A [ 0 , 1 ] A μ i \mu_i μ i 1 1 1 η = θ / 5 \eta=\theta/5 η = θ /5 F ⊆ A F\subseteq A F ⊆ A μ i ( A ∖ F ) < η \mu_i(A\setminus F)<\eta μ i ( A ∖ F ) < η i ≤ n i\le n i ≤ n
Put F 0 = F F_0=F F 0 = F j 1 < ⋯ < j k j_1<\cdots<j_k j 1 < ⋯ < j k F 0 ⊆ F 1 ⊆ ⋯ ⊆ F k F_0\subseteq F_1\subseteq\cdots\subseteq F_k F 0 ⊆ F 1 ⊆ ⋯ ⊆ F k i ≤ n i\le n i ≤ n
∑ a ∈ F ℓ − 1 ∣ μ j ℓ , i ( a ) − μ i ( a ) ∣ < η , ∑ a ∈ F ∣ q a ( j ℓ ) − q a ∞ ∣ < η , μ j ℓ , i ( A ∖ F ℓ ) < η . \sum_{a\in F_{\ell-1}}\left|\mu_{j_\ell,i}(a)-\mu_i(a)\right|<\eta,\qquad
\sum_{a\in F}\left|q_a^{(j_\ell)}-q_a^\infty\right|<\eta,\qquad
\mu_{j_\ell,i}(A\setminus F_\ell)<\eta. a ∈ F ℓ − 1 ∑ ∣ μ j ℓ , i ( a ) − μ i ( a ) ∣ < η , a ∈ F ∑ q a ( j ℓ ) − q a ∞ < η , μ j ℓ , i ( A ∖ F ℓ ) < η . The first two conditions hold for all large indices, by convergence on the finite sets F ℓ − 1 F_{\ell-1} F ℓ − 1 F F F F ℓ F_\ell F ℓ q ∈ [ 0 , 1 ] A q\in[0,1]^A q ∈ [ 0 , 1 ] A q a = q a ∞ q_a=q_a^\infty q a = q a ∞ a ∈ F a\in F a ∈ F q a = q a ( j ℓ ) q_a=q_a^{(j_\ell)} q a = q a ( j ℓ ) a ∈ F ℓ ∖ F ℓ − 1 a\in F_\ell\setminus F_{\ell-1} a ∈ F ℓ ∖ F ℓ − 1 ℓ ≤ k \ell\le k ℓ ≤ k q a = 0 q_a=0 q a = 0 a ∉ F k a\notin F_k a ∈ / F k
Let ℓ ≤ k \ell\le k ℓ ≤ k i ≤ n i\le n i ≤ n ⟨ μ j ℓ , i , q ⟩ \langle\mu_{j_\ell,i},q\rangle ⟨ μ j ℓ , i , q ⟩ ⟨ μ j ℓ , i , q ( j ℓ ) ⟩ \langle\mu_{j_\ell,i},q^{(j_\ell)}\rangle ⟨ μ j ℓ , i , q ( j ℓ ) ⟩ A A A Theorem 8.1 ; on each piece the two vectors differ by at most 1 1 1 F ℓ ∖ F ℓ − 1 F_\ell\setminus F_{\ell-1} F ℓ ∖ F ℓ − 1 F F F ∑ a ∈ F ∣ q a ∞ − q a ( j ℓ ) ∣ < η \sum_{a\in F}|q_a^\infty-q_a^{(j_\ell)}|<\eta ∑ a ∈ F ∣ q a ∞ − q a ( j ℓ ) ∣ < η μ j ℓ , i ( a ) ≤ 1 \mu_{j_\ell,i}(a)\le1 μ j ℓ , i ( a ) ≤ 1 F ℓ − 1 ∖ F F_{\ell-1}\setminus F F ℓ − 1 ∖ F μ j ℓ , i ( F ℓ − 1 ∖ F ) ≤ ∑ a ∈ F ℓ − 1 ∣ μ j ℓ , i ( a ) − μ i ( a ) ∣ + μ i ( A ∖ F ) < 2 η \mu_{j_\ell,i}(F_{\ell-1}\setminus F)\le\sum_{a\in F_{\ell-1}}|\mu_{j_\ell,i}(a)-\mu_i(a)|+\mu_i(A\setminus F)<2\eta μ j ℓ , i ( F ℓ − 1 ∖ F ) ≤ ∑ a ∈ F ℓ − 1 ∣ μ j ℓ , i ( a ) − μ i ( a ) ∣ + μ i ( A ∖ F ) < 2 η A ∖ F ℓ A\setminus F_\ell A ∖ F ℓ μ j ℓ , i ( A ∖ F ℓ ) < η \mu_{j_\ell,i}(A\setminus F_\ell)<\eta μ j ℓ , i ( A ∖ F ℓ ) < η ∣ ⟨ μ j ℓ , i , q ⟩ − ⟨ μ j ℓ , i , q ( j ℓ ) ⟩ ∣ < 4 η < θ |\langle\mu_{j_\ell,i},q\rangle-\langle\mu_{j_\ell,i},q^{(j_\ell)}\rangle|<4\eta<\theta ∣ ⟨ μ j ℓ , i , q ⟩ − ⟨ μ j ℓ , i , q ( j ℓ ) ⟩ ∣ < 4 η < θ i ≤ n i\le n i ≤ n θ \theta θ H j ℓ ( q ) > H j ℓ ( q ( j ℓ ) ) − ( β − α ) ≥ α H_{j_\ell}(q)>H_{j_\ell}(q^{(j_\ell)})-(\beta-\alpha)\ge\alpha H j ℓ ( q ) > H j ℓ ( q ( j ℓ ) ) − ( β − α ) ≥ α □ \square □
For affine combinations, the proof of Theorem 8.1 yields slightly more: there the common witness can be taken pure. For an arbitrary connective u u u q q q Theorem 8.3 , and it cannot always be taken pure: for n = 1 n=1 n = 1 μ = δ a \mu=\delta_a μ = δ a a ∈ A a\in A a ∈ A u ( t ) = 1 − ∣ 2 t − 1 ∣ u(t)=1-|2t-1| u ( t ) = 1 − ∣2 t − 1∣ 1 1 1 ν \nu ν π a ( ν ) = 1 / 2 \pi_a(\nu)=1/2 π a ( ν ) = 1/2
The difference between the two paradigms lies entirely in the probe space: on the Cantor cube { 0 , 1 } Γ \{0,1\}^{\Gamma} { 0 , 1 } Γ V ∗ V^{*} V ∗
Affine logic and correlated preparations
Finally, we place the results in affine logic, in the form developed by Ben Yaacov, Ibarlucía and Tsankov [BYIT24], whose connectives are the affine maps and in which a mixture of structures is a direct integral. Formula values in a direct integral are integrals of formula values, which is the rule by which a response is computed on a mixed preparation. In this logic the type spaces are compact convex sets, and a structure is extremal when it realizes only extreme types, the extreme points of these sets. Ben Yaacov, Ibarlucía and Tsankov [BYIT24] showed that every model of an affine theory is an affine elementary substructure of a direct integral of extremal models. An affine theory is simplicial when its type spaces are Choquet simplices, that is, sets in which every point is the barycenter of exactly one probability measure that is maximal in the Choquet order; when the set is metrizable, the maximal measures are those concentrated on its extreme points. The same authors also showed that every model of a simplicial theory is such a direct integral, uniquely.
Ben Yaacov and Ibarlucía [BYI26] proved that an affine formula stable in almost every member of a measurable field of structures is stable in its direct integral, and that an affine theory is stable exactly when its extremal models are stable. Their definition of stability of a formula in a structure is the double limit condition of the first paper of this series [13 ] : for every two sequences of elements, one in each variable of the formula, the two iterated limits of its values agree whenever both exist. Mixing in the sense of this paper behaves differently with respect to simplicity: the first-order theories of the Pauli group and of the Rado graph are simple, whereas, by Theorem 6.1 , the real-valued theories of their observables have the tree property of the second kind.
The direct integral allows the elements in the two variables of a formula to depend on the same random parameter. For observables this means that Alice and Bob share randomness: they prepare a separable state, a mixture of product states, rather than a single product state. Keisler’s randomizations [20 BY13] are of this kind: their elements are random elements of a structure, that is, measurable maps from a common probability space into it. The preparations in Theorem 6.1 , by contrast, are product preparations.
Questions
Question 10.1. Which diagonal observables with the independence property have the tree property of the second kind witnessed by actual preparations? For the diagonal observable C φ C_{\varphi} C φ φ : A × B → { 0 , 1 } \varphi:A \times B \to\{0,1\} φ : A × B → { 0 , 1 } A A A B B B Theorem 7.2 and Theorem 8.1 suggest a criterion in terms of the linear span of its responses in the space C ( K φ ) C(K_{\varphi}) C ( K φ ) K φ K_{\varphi} K φ
Question 10.2. By Remark 7.3 , the proof of Theorem 7.2 adapts to qudits of prime dimension. For continuous variables, that is, for systems such as a particle on a line, whose position and momentum take real values, the commutation phase of a translation by a distance x x x ℏ k \hbar k ℏ k ℏ \hbar ℏ k k k e i k x e^{ikx} e ik x cos k x \cos kx cos k x 8 n 8^n 8 n n ∈ N n \in\mathbb{N} n ∈ N
Question 10.3. In first-order model theory, a simple theory without the independence property is stable. Is an observable stable when its real-valued theory is simple? By Theorem 6.1 , every simple diagonal observable is NIP, so for diagonal observables the question is whether those of the second paper that are NIP but unstable, such as the comparison of photon numbers, which asks whether Bob’s system has more photons than Alice’s, have a tree property once preparations are mixed.
Question 10.4. Does Theorem 6.1 hold for every observable whose responses have the independence property, not only for diagonal ones? The proof uses the values 0 and 1 of pure responses; for general observables they are replaced by two distinct levels, and the averages must be controlled with a gap.
Question 10.5. Is there an analogue of the Kim–Pillay theorem for affine logic, characterizing simple affine theories by an independence relation on extremal types?
Simple theories were introduced by Shelah [26 ] in 1980, together with the tree properties of the first and second kind; the motivating example was the theory of the countable random graph (see [26 , 17 ] ). Kim [Kim98] proved in 1998 that forking is symmetric in simple theories, and Kim and Pillay [23 ] proved the independence theorem and the characterization of simplicity by an independence relation in 1997. Ben Yaacov [4 ] extended the theory in 2003 to compact abstract theories, a framework that contains the continuous logic of metric structures. The Rado graph was described by Ackermann [1 ] in 1937 and by Rado [25 ] in 1964; by a theorem of Erdős and Rényi [15 ] from 1963, it is the almost sure isomorphism type of the random graph on countably many vertices. Fraïssé [Fra54] introduced his limits in 1954, and Witt’s theorem on isometries of forms is in Artin’s Geometric Algebra [2 ] . Vector spaces of countably infinite dimension over finite fields with a nondegenerate alternating form, such as the Pauli group, are among the Cherlin–Hrushovski smoothly approximable structures [9 ] . Granger [19 ] studied vector spaces with a generic bilinear form over an arbitrary field in his thesis of 1999 and showed that, over an infinite field carried as a second sort, the theory is not simple; Chernikov and Ramsey [10 ] proved in 2016 that over an algebraically closed field it is N S O P 1 NSOP_1 N S O P 1 1 1 1 [18 ] and to Calderbank, Rains, Shor and Sloane [11 ] ; the expression of the projector onto the states of a given syndrome as an average over the stabilizer group, behind Proposition 7.1, is standard in Gottesman’s stabilizer formalism. Keisler [20 ] introduced randomizations in 1999; Ben Yaacov and Keisler [BYK09] treated them as metric structures, and Ben Yaacov [BY13] proved in 2013 that the Keisler randomization of a theory with the independence property has T P 2 TP_2 T P 2 [13 , 14 ] .
Declarations
Competing interests. The authors have no competing interests to declare.
Data availability. No data were generated or analyzed in this work.
References
Department of Mathematics, The University of Texas at San Antonio, One UTSA Circle, San Antonio, TX 78249, USA Email address: Eduardo.Duenez@utsa.edu
Department of Mathematics, The University of Texas at San Antonio, One UTSA Circle, San Antonio, TX 78249, USA Email address: jose.iovino@utsa.edu
