WorksPhysics and Astronomy
Distributed Phase Tags: A Locality-Preserving Realification Compiler for Misty-State Quantum Programs
Abstract
Complex amplitudes can be simulated over real Hilbert spaces by adjoining a two-dimensional real/imaginary degree of freedom. In a multipartite program, however, one globally shared phase tag is not a locality-preserving program transformation: every party would have to act on the same auxiliary system. We recast the distributed real simulation of multipartite quantum mechanics as a syntax-directed compiler into a real misty-state intermediate language. For parties we give explicit phase-reference codewords and on local tags and prove that the same real operator on any single tag realizes the logical action of multiplication by . If a complex party-local gate is , its real translation is which acts only on party 's data and local phase tag. We prove an intertwining theorem for arbitrary finite party-local pure-state circuits, exact preservation of computational-basis measurement probabilities, preservation of the run-time interaction graph, and one-rebit-per-party overhead. For the canonical three-party GHZ program, the translation lies entirely inside the ordinary black-and-white misty gate fragment: controlled- replaces the complex phase operation, while the invariant transfers the required branch sign. This yields a short correctness proof for all four promised GHZ inputs and explains the earlier 64-path cancellation calculation at a single logical phase-code boundary. We distinguish this program realification problem from the weaker task of finding any real strategy with the same correlations, and state precisely which parts are known real-Hilbert-space simulation and which parts belong to the misty-language compilation layer developed here.
which acts only on party ’s data and local phase tag. We prove an intertwining theorem for arbitrary finite party-local pure-state circuits, exact preservation of computational-basis measurement probabilities, preservation of the run-time interaction graph, and one-rebit-per-party overhead. For the canonical three-party GHZ program, the translation lies entirely inside the ordinary black-and-white misty gate fragment: controlled- replaces the complex phase operation, while the invariant transfers the required branch sign. This yields a short correctness proof for all four promised GHZ inputs and explains the earlier 64-path cancellation calculation at a single logical phase-code boundary. We distinguish this program realification problem from the weaker task of finding any real strategy with the same correlations, and state precisely which parts are known real-Hilbert-space simulation and which parts belong to the misty-language compilation layer developed here.
Introduction and main results
Quantum programs are normally written over complex Hilbert spaces. A familiar realification replaces a complex vector by its real and imaginary components, encoded in an additional two-level real system. Rudolph and Grover used this idea in the circuit model to show that universal quantum computation can be carried out with real amplitudes [4]; McKague, Mosca and Gisin subsequently gave a multipartite construction that preserves local evolution and measurements by distributing the real/imaginary degree of freedom among the parties [2].
The programming-language issue is more specific. A translation of a distributed program should preserve more than its final input–output statistics. If the source program consists of party-local commands, a target program that makes every party access one globally shared phase ancilla has changed the ownership structure of the program. For a nonlocality protocol such as GHZ, that distinction is especially visible: pre-shared entanglement is allowed, but run-time communication between the separated parties is not.
The misty-state formalism provides a concrete target syntax for asking this question. Rudolph’s black-and-white “mist” represents signed superpositions by collections of tokens and realizes interference by replacement and cancellation [5]. German subsequently formulated a term-rewriting semantics for pure quantum states [1], and Newton–German separated raw amplitude addition from physical normalization and supplied an exact amplitude semantics for finite mist expressions [3]. Rudolph, Newton, and German gave an explicit six-rebit misty-state construction showing that three parties can implement the canonical GHZ X/Y strategy using only real-valued operations [7]. The present paper reorganizes and strengthens that construction as a compiler theorem.
The central distinction. There are two different tasks:
strategy realification: find any real state and observables reproducing a target correlation;
program realification: translate a specified complex state, specified local commands, and specified party decomposition into real syntax while preserving their compositional and locality structure.
The first can be strictly easier. For the GHZ correlation there is a three-rebit graph-state strategy; the six-rebit construction is therefore not a dimension lower bound for the game. Its purpose is that it locally compiles the canonical complex GHZ program.
Main theorem. For parties, introduce one phase tag per party and a two-dimensional logical code space . The code is chosen so that the real matrix
acts identically on the logical phase coordinate regardless of which party’s tag it touches. If is a source operation owned by party , compile it to
We prove that this translation intertwines the complex and real denotations, and therefore extends compositionally to finite party-local circuits.
Theorem 1.1 (Locality-preserving realification, informal form). Let be a finite pure-state circuit in which each command is owned by a single party. Encode the complex state by distributing one phase tag to each party and replace each command by (1). Then the real target circuit has the same computational-basis output distribution as , every translated command acts only on the same party’s data together with that party’s tag, and no run-time edge is added to the party-interaction graph. If the source gates are unitary, the translated gates are real orthogonal gates.
The theorem’s algebraic substrate is the established real-Hilbert-space simulation [4, 2]. Our contribution is the explicit phase-code presentation, its syntax-directed formulation as a misty-program compiler, the ownership theorem, and the gate-level GHZ realization within the ordinary black-and-white fragment.

Figure 1. Compiler architecture. The nonlocal phase code is prepared once; every dynamic command remains local to its source owner.
GHZ corollary. For three parties the logical phase-zero codeword is
The identity for is exactly the sign needed when two players execute the source branch. It turns the initial data state into , after which three Hadamards expose the required even parity. For the all- input no acts and the final parity is odd. The long path expansion in the original derivation is therefore the concrete normal-form trace of one logical sign-transfer invariant.
Misty syntax and real denotational semantics
We use only a small fragment of the misty notation and make its denotation explicit. Write and for white and black basis tokens,
For the finite fragment needed here,
Juxtaposition is an ordered tensor product; braces collect amplitudes; the minus sign negates an amplitude; and gates extend linearly:
Thus a pair cancels exactly. Braces denote raw amplitude addition; normalization is a separate operation. This convention is essential: it prevents nested punctuation from being mistaken for physical normalization and agrees with the certified amplitude semantics of [3].
The black-and-white gate fragment
The Hadamard (PETE) action is
The real phase operator is
Controlled- can be synthesized from controlled- and controlled-; controlled- is obtained by conjugating CNOT by Hadamards on the target. Hence the GHZ target program uses only real gates naturally expressible in the ordinary misty circuit language.
A semantic real-linear intermediate language
For the general compiler theorem we allow finite real matrices as target primitives. This is a semantic intermediate language, not a claim that every real matrix is primitive in Rudolph’s original gate vocabulary. The distinction matters: the general theorem establishes a compositional semantics, while the GHZ case additionally admits a gate-level decomposition into the elementary black-and-white operations above.
A source command is a complex matrix acting on one party’s local data space. Relative to the computational basis write uniquely
The target compiler will replace the scalar complex structure by the logical real operator encoded in the phase tags.
The distributed phase-reference code
The three-tag state used in the original GHZ derivation is the member of a simple family. Let , let be its Hamming weight, and write for the corresponding phase-tag basis vector.
Definition 3.1 (Distributed phase code). For , define
The supports are disjoint and each contains basis states, so the codewords are orthonormal. They are invariant under permutation of the parties.
For let mean on phase tag and identity on every other tag.
Lemma 3.2 (Local complex-structure lemma). For every party ,
Consequently the restriction of every to is the same logical matrix , and for distinct

Figure 2. Logical complex structure from local real actions. Every party has a different physical tag but the same logical action of multiplication by .
Proof. On a computational basis state, (2) gives
Suppose first that is even. If , flipping bit increases the weight by one and leaves the coefficient unchanged. If , the weight decreases by one and the extra factor from is exactly the sign needed to obtain . This proves . The odd-weight calculation is the same with the signs reversed, giving . Applying the first identity and then the second yields (6).
For the definition becomes
which is exactly the phase-reference pair used in the compressed GHZ proof.
A locality-preserving realification compiler
We now state the general semantic translation. Fix a computational basis of the source data Hilbert space . Regard as the corresponding real coordinate space. Every source state has a unique decomposition
Definition 4.1 (Distributed encoding). The -party realification map is
Since the phase codewords are orthonormal,
so is an isometry of real inner-product spaces.
Suppose a source command is owned by party . The compiler emits
with identity on all other data and phase registers.
Theorem 4.2 (Intertwining / compiler soundness). For every source state and every party-local complex linear command ,
If is unitary, then is a real orthogonal operator.
Proof. Using Theorem 3.2,
which is exactly the real and imaginary decomposition of . For the second statement, implies
Using and , direct multiplication gives .
Corollary 4.3 (Finite-circuit compositionality). Let be a finite sequence of party-local source commands and let . Then
for every source state .
Proof. Induct on the command sequence using Theorem 4.2.
Measurement preservation
Let project onto a computational-basis outcome of the data registers. Since and are orthonormal,
Thus computational-basis measurement probabilities are preserved exactly. Combined with Theorem 4.3, this proves output-distribution preservation for the circuit language considered here.
Locality and overhead
The source command acts only on party ’s data. The target command (10) acts only on the same data plus tag . Therefore no command acquires access to another party’s register. The phase code is pre-shared entanglement prepared before the run, so the dynamic party-interaction graph is unchanged.
Theorem 4.4 (Ownership and interaction-graph preservation). For an -party source program consisting of party-local commands and final computational-basis measurements, the compiler adds exactly one two-level real phase tag per party and adds no run-time communication edge. The target local dimension is doubled at each party, and the compiled program has exactly the same computational-basis output distribution as the source.
Remark 4.5 (What is known and what is being formalized). The existence of locality-preserving real simulations is established in [2]. Theorems 4.2 and 4.4 should therefore be read as the semantic correctness theorem of the present compiler presentation: it identifies the source command, target command, ownership discipline and explicit phase-code invariant needed to expose that simulation as a misty-language transformation. We do not claim the underlying real-Hilbert-space embedding as new.
The GHZ program as an exact gate-level case study
We now specialize to three parties, where the target program remains inside the elementary black-and-white gate fragment rather than merely the real-linear intermediate language.
Let
The referee supplies
With the convention of the original misty derivation, the required output parity is odd for 000 and even for the other three promised inputs.
For , party applies and measures in the computational basis. For , the complex source program applies
then and measures. This realizes the basis up to an exchange of the two classical labels; promised inputs contain zero or two questions, so the label exchange does not change parity.
Since and , (10) gives the compiled gate
namely controlled- from the data token to the local phase tag.
Proposition 5.1 (GHZ sign transfer). Start the target program in . If no party executes the compiled branch, the data state remains . If exactly two distinct parties execute it, then
In both cases the phase code finishes unentangled from the data.
Proof. On the branch neither controlled- fires. On the branch both fire, and (6) supplies a factor on . That factor cancels the source minus sign:
The final Hadamards expose the parity directly:
The first support is exactly the odd-weight strings; the second is exactly the even-weight strings.

Figure 3. The GHZ branch. The 64-path cancellation of the original derivation is compressed to one logical sign-transfer identity.
Theorem 5.2 (GHZ correctness and locality). For every promised input , the compiled real misty program wins with probability one. Its output distribution agrees with the complex source program; the phase tags finish in independently of the observed data; and every dynamic operation remains local to one party.
Proof. For , no controlled- is used and (16) gives odd parity with probability one. Each other promised input contains exactly two 1s; Theorem 5.1 changes to and (17) gives even parity with probability one. Every allowed output has amplitude and probability . Locality follows from (14) and Table 1.
| Input | Complex source branch | Real misty target branch | Target owner |
| 0 | ; measure | ; measure | |
| 1 | ; ; measure | ; ; measure |
Table 1. Local translation for the GHZ fragment. Commands are written in execution order.
Rewrite-level realization and exact verification
The Hilbert-space proof above is deliberately short, but the construction remains a misty-state rewrite rather than merely a matrix simulation. This section identifies the exact rewrite obligations and relates them to the longer black-and-white expansion.
Local gate identities
The only nontrivial target operation for the GHZ branch is controlled-. On basis tokens its action is
The control- cases do nothing; the control- cases apply to the phase token. Because , each case reduces using only NOT, controlled-NOT, Hadamard-conjugated controlled-Z, sign propagation and cancellation.
From 64 paths to one invariant
In the original explicit derivation [7], the initial data mist has two components and the phase-code mist has four, producing eight six-token components before local boxes are expanded. The Hadamard branches then generate 64 paths. For the all- input, terms pair so that even-parity outputs cancel; for an input with two questions, the controlled- action changes the pairing and odd-parity outputs cancel.
The invariant proof performs the same cancellation one level earlier. Instead of tracking all paths separately, it proves once that the phase-code action on the branch is whenever exactly two controls fire. Linearity then gives Theorem 5.1, after which the ordinary Hadamard identities (16)–(17) determine the support. The two proofs are therefore consistent descriptions at different abstraction levels rather than competing derivations.

Figure 4. Two different realification goals. The six-rebit construction addresses the stronger structure-preserving problem, not minimal dimension for the GHZ correlation.
Executable checker boundary
A small exact checker for this fragment requires no floating point arithmetic. Terms can be represented as maps from basis strings to coefficients in , with rules for tensor product, signed union, , , , CNOT and cancellation. The four GHZ inputs then normalize to the supports in (16)–(17). Such a checker would mechanize the case-study proof; it is not required for the algebraic correctness theorem and is left as an artifact-level extension rather than being silently assumed here.
Preservation, overhead, and claim boundaries
A strong statement of what is preserved is as important as the correctness proof itself.
What the compiler preserves
For the source language of § 4, the translation preserves:
denotation under encoding: ;
computational-basis probabilities: by (12);
party ownership: every command remains owned by the same party;
dynamic interaction graph: no new run-time communication edge is introduced;
asymptotic local overhead: exactly one two-level phase tag is added per party.
The phase tags may be initially entangled across parties. This is pre-shared static resource, not run-time communication.
What the compiler does not prove
The construction does not prove that two rebits per player are necessary to win GHZ, nor that the chosen phase code is dimension-optimal among all strategies reproducing the same correlation. Indeed, the triangle graph state
is a real three-qubit state. It is stabilized by , and , whose product is ; measuring for one input label and for the other reproduces the same odd/even parity pattern. This is a strategy realification. It does not preserve the specified GHZ source circuit with its phase operations.
Scope of the general compiler theorem
The proof in § 4 covers finite pure-state circuits of party-local complex linear maps followed by computational-basis measurements. Extending the syntax to arbitrary instruments, mixed states, classical control and recursive programs requires the corresponding density-operator or completely-positive semantics. Nothing in the present theorem establishes such a full language automatically.
Likewise, the semantic real-linear target admits the matrices and as primitives. The GHZ fragment is stronger in a different sense: its translation is explicitly synthesized in the ordinary black-and-white gate vocabulary. A general gate-synthesis theorem for arbitrary translated is a separate compilation problem.
Related work and novelty boundary
Real quantum computation. Real-amplitude simulation predates the present misty language. Rudolph and Grover gave a circuit-model translation using a two-level real/imaginary ancilla and a universal two-rebit gate [4]. McKague, Mosca and Gisin developed a multipartite real simulation in which local evolution and measurements remain local [2]. The distributed phase code used here is an explicit presentation of that logical complex structure. We therefore do not claim that representing complex quantum mechanics over a real Hilbert space, or distributing the complex structure across parties, is new.
Misty-state semantics. Rudolph’s notation was introduced as an elementary black-and-white route to quantum reasoning [5]. German’s term-rewriting work treats mist expressions as a formal semantic object rather than merely a picture [1]. Newton–German give an explicit amplitude semantics, normalization discipline and exact finite equality machinery [3]. The present work uses that semantic separation to formulate the distributed real simulation as a source-to-target program transformation.
Quantum programming languages. Denotational semantics for quantum programming has a long history; Selinger’s language and superoperator semantics are a foundational example [6]. Our language fragment is intentionally much smaller. The goal is not to compete with full quantum languages or graphical calculi, but to make one concrete compilation issue—distributed complex phase in a real rewriting syntax—fully inspectable.
Claimed contribution. The result to attribute to this paper is therefore the following package: an explicit -party phase-code invariant in misty notation; a syntax-directed party-local compiler rule ; a direct denotational, measurement and ownership proof for the stated finite circuit language; and a gate-level GHZ realization whose correctness collapses to the two-tag sign lemma. The paper’s contribution is the program-semantics organization and proof interface, built on known real-Hilbert-space simulation.
Conclusions and next formalization steps
The black-and-white GHZ construction is most informative when read as a compiler rather than as an alternative hand calculation of a known nonlocal game. The phase-reference state supplies one logical complex structure through several physically local real actions. Once that invariant is isolated, the six-token calculation becomes a special case of a simple rule: replace each source occurrence of in a party-owned operation by that party’s local action on a distributed phase tag.
For the finite pure-state language considered here, this translation is compositional, probability preserving and locality preserving. The GHZ case adds an unusually transparent gate-level witness: two local actions return the phase code to itself with a minus sign, which flips the relative GHZ branch phase and determines the parity after the final Hadamards. The proof therefore explains the detailed cancellation pattern without requiring the cancellation table to carry the logical burden.
Three extensions now have clear, separable proof obligations. First, a typed density-operator language could extend the compiler to general measurements, classical feed-forward and mixed states. Second, a verified rewrite engine could mechanize normalization of the compiled mist terms and serve as an executable certificate layer. Third, one can ask a genuine minimality question: under explicit requirements of compositionality, party-decomposition preservation and uniform compilation of arbitrary local complex operators, is one local two-dimensional phase system per party necessary? That is a compiler lower-bound problem and should not be conflated with the much weaker question of how many rebits are needed to reproduce one correlation.
The main conceptual conclusion is correspondingly precise: complex phase is not removed by the real misty semantics; it is reified as distributed local program state. The resulting code makes the scalar action of locally available to every party without introducing run-time communication, turning a pedagogical black-and-white calculation into a small, auditable example of locality-preserving quantum compilation.
Acknowledgments
The authors thank Prof. Terry Rudolph for several illuminating conversations that helped crystallize and refine some of the ideas developed in this paper.
Explicit three-party phase-code check
For completeness, start from
Applying gives
after accounting for on the term; this is . The same result follows for and by permutation symmetry. Applying any second with gives . This is the compact algebraic identity that the original four-component phase mist verified term by term.
Relation to the original path expansion
The original six-ball derivation [7] is retained as an independent low-level validation. Before the final Hadamards, the eight products of the two GHZ data components with the four phase-code components evolve through the local boxes. For , expansion under three Hadamards yields 64 paths whose even-parity contributions cancel in pairs. For , or , exactly two controlled- operations alter the relative sign on the data component; the pairing reverses and odd-parity contributions cancel. Theorem 5.1 factors this calculation through the logical code space: the 64 individual paths are the distributive expansion of the single identity followed by (16) or (17).
All computational algorithms, proof-search procedures, and certificate criteria were developed by the author(s). Large Language Models (LLMs) such as ChatGPT and Claude were utilized strictly as computational assistants for debugging code and cross-checking routines. No mathematical claims rely on LLM outputs; all results are grounded exclusively in independently reproducible, rigorously verified certificates (exact, symbolic, rational, interval, exhaustive, or controlled high-precision).
References
- [1]Dan-Adrian German. A term-rewriting semantics for pure quantum states. arXiv:2607.06584, 2026.arxiv.org/abs/2607.06584
- [2]Matthew McKague, Michele Mosca, and Nicolas Gisin. Simulating quantum systems using real Hilbert spaces. Physical Review Letters, 102:020505, 2009. doi:10.1103/PhysRevLett.102.020505.DOI
- [3]Tony Newton and Dan-Adrian German. Certified misty-state rewriting: A question-and-answer guide. arXiv:2608.10024, 2026.arxiv.org/abs/2608.10024
- [4]Terry Rudolph and Lov Grover. A 2 rebit gate universal for quantum computing. arXiv:quant-ph/0210187, 2002.DOI
- [5]Terry Rudolph. Q Is for Quantum. Terence Rudolph, 2017.
- [6]Peter Selinger. Towards a quantum programming language. Mathematical Structures in Computer Science, 14(4):527–586, 2004.DOI
- [7]Terry Rudolph, Tony Newton, and Dan-Adrian German. The GHZ game in black and white. arXiv:2610.14411, 2026.arxiv.org/abs/2610.14411