WorksPhysics and Astronomy
Fixed Points as Programs: Finite Symmetry and One-Shot State-Gate Duality in the Misty-State Calculus
Abstract
The same quantum object can support several logically distinct descriptions: it can be an eigenstate of an operator, a fixed point of an action, a nonstabilizer resource, or a state consumed by a gate-injection protocol. We make these relations precise in the misty-state calculus. The semantic core is a normalized superposition constructor . For any finite unitary group , whenever the orbit sum is nonzero, the normalized orbit cloud is fixed by every element of ; the involutive specialization is therefore a certified fixed-point constructor. Applied to and , it gives the nested misty state , the Hadamard eigenstate. This state is not a Pauli stabilizer state; it is an H-type magic state and is Clifford-equivalent to . We then prove an exact one-shot state-gate duality. Writing and , the state can be consumed by a Clifford controlled- injection circuit to apply either or to arbitrary data. Whenever is free, feed-forward makes the implementation deterministic. At , is Clifford, so one copy of implements one exact use of the non-Clifford gate ; conversely one use of prepares from . We formulate this as a pair of sound semantic certificates, and , and separate the resulting finite symmetrization mechanism from the genuinely recursive fixed-point role of the combinator, while identifying the exact -combinator sharing pattern in . The result is a small, auditable semantics in which invariance and consumable program resources coexist without being conflated.
Introduction and main results
A recurring pattern across quantum information and programming-language semantics is that an operation acts on an object while some structure survives. The equations look deceptively similar. An eigenvector satisfies ; a projective quantum state is fixed when ; a stabilizer state is fixed by a family of Pauli operators; a fixed-point combinator constructs a solution of ; an attractor is a fixed object approached dynamically. These notions are related, but identifying them would erase exactly the distinctions that make them useful.

Figure 1. One state supports two different certificates. The upper route is an equation in state semantics; the lower route is an operational statement about a processor that consumes the state.
The misty-state language gives a compact setting in which the distinctions can be made explicit. Rudolph’s original black-and-white formalism represents basis states by tokens and superpositions by clouds, with interference realized by symbolic cancellation [6]. German recast the language as a term-rewriting semantics and introduced irreducible nested states with fixed-point behavior [3]. Newton and German subsequently separated raw amplitude addition from physical normalization and supplied an exact, falsifiable semantics for finite mist expressions [5]. The present paper develops the fixed-point and resource-program consequences of that semantic separation.
The starting object is the nested state
Its significance is twofold. First, it is an exact fixed point of Hadamard. Second, it is a nonstabilizer state that can be consumed to apply a non-Clifford rotation to arbitrary data. The phrase “state as program” is therefore not used metaphorically here: we give a concrete processor architecture and prove its induced channel.
Main results. The paper establishes four claims.
A finite orbit cloud is an exact fixed-point constructor. The involution case gives a particularly small certified constructor and places the nested Hadamard state inside a general symmetry principle.
The state in (1) is simultaneously a Hadamard fixed point and an H-type magic state, while not being a Pauli stabilizer state. This provides a precise example of why eigenstate, stabilizer state, and magic state must not be conflated.
A one-parameter injection identity converts into the gate on arbitrary data. If is free, the conversion is deterministic. At , the correction is Clifford, giving an exact one-shot equivalence between one copy of and one invocation of relative to Clifford processing.
The fixed-point constructor has the exact sharing pattern of the S combinator, but it is finite orbit symmetrization rather than recursive self-application. The Y combinator supplies the genuinely recursive equation . We encode this distinction by separate semantic certificates for invariance and resource-program behavior.
The underlying ingredients—group averaging, Clifford magic states, and gate injection—are established ideas in their respective subjects [2, 4]. The contribution here is their exact organization inside the misty-state syntax: normalized nesting becomes a certified invariance constructor, while the same denotation becomes a first-class consumable program resource. We state claim boundaries explicitly in § 9.
Semantic core of the misty-state calculus
We use only the finite pure-state fragment needed for the results. Let and denote the computational basis tokens,
For signed finite clouds,
Normalization is an explicit semantic operation
This scope discipline matters. For example,
are not equivalent: the first normalizes a raw amplitude sum proportional to , whereas the second first converts the inner cloud into a unit state.
Normalized combination
For nonzero vectors , define
The operation is symmetric and equivariant under every unitary :
The equality follows because unitaries preserve norms. On the real great-circle family
we have the midpoint law
Indeed, the usual sum-to-product identities give
and the prefactor is positive on the declared interval.
The Hadamard state
Since
Eq. (5) gives
Direct multiplication shows
The same fact will reappear below as a consequence of finite symmetrization rather than a special trigonometric identity.
Finite symmetry as a fixed-point constructor
The fixed-point mechanism extends beyond Hadamard and beyond involutions. Let a finite group act unitarily on a Hilbert space through .
Definition 3.1 (Orbit cloud). For with nonzero orbit sum, define
Theorem 3.2 (Finite-orbit invariance). For every ,
Thus the orbit cloud is a certified common fixed point of the group action whenever the orbit sum is nonzero.
Proof. Left multiplication permutes the elements of :
The vector is therefore unchanged before normalization, and hence after normalization.
For an involution , the group is and
is a fixed point whenever .
Corollary 3.3 (Involution constructor). If and , then
Proof. Using Eq. (4), symmetry of , and ,

Figure 2. Finite orbit symmetrization as a fixed-point constructor. The theorem is purely algebraic; no recursive limit or dynamical convergence is involved.
The exceptional condition is essential: if , the orbit sum vanishes and normalization is undefined. In operator language the unnormalized two-element orbit sum is , where is the projector onto the eigenspace. Thus the constructor is not an attractor process; it is a finite algebraic projection followed by normalization.
Taking and gives
so Eq. (7) is a special case of Theorem 3.3.
The Hadamard fixed point as a magic resource
The state is a useful test of conceptual boundaries because three classifications intersect.
Eigenstate but not Pauli stabilizer state
Equation (7) makes a eigenstate of the Clifford gate . This does not make it a stabilizer state in the usual qubit Pauli-stabilizer sense. A pure one-qubit Pauli stabilizer state has Bloch vector on one of the coordinate axes. From (6),
which is not a coordinate-axis vector. Thus is a fixed point of a Clifford action while remaining nonstabilizer.
This distinction is central to magic-state computation. Bravyi and Kitaev identify pure nonstabilizer states in special directions as magic resources which, combined with Clifford processing, enable universal quantum computation [2].
Clifford equivalence to the phase magic state
Let
Then
Proposition 4.1 (H-type/phase-type equivalence). The misty Hadamard state is Clifford-equivalent to :
Proof. Writing and ,
The leading phase is physically irrelevant.
| Notion | Defining statement | Status of |
| Eigenstate | Yes: | |
| Projective fixed point | Yes | |
| Pauli stabilizer state | for a maximal Pauli subgroup | No |
| Magic state | nonstabilizer resource for free Clifford processing | Yes |
| Attractor | neighboring states converge under dynamics | Not implied by |
| Program resource | a processor consumes the state to realize a channel | Yes, for below |
Table 1. Closely related notions remain logically distinct.
Hence the fixed-point state discovered syntactically in the misty calculus lies on a standard one-qubit magic-state orbit. The mathematical facts are established; the new semantic point is that the same misty term can carry an invariance certificate and a program-resource certificate simultaneously.
Exact state-to-gate compilation by injection
We now make the “state as program” statement operational. Define the real matrix
For , let
The target state of the paper is and the target gate is
Let denote controlled- with the helper qubit as control and the data register as target:
This is a Clifford operation: with the same control and target, , since the control-1 block is . The remaining ingredients below—Hadamard, computational-basis measurement, and conditional Clifford correction in the case—are likewise free in the stabilizer model.
Theorem 5.1 (Injection identity). For every data state ,
Each measurement outcome on the helper occurs with probability . If is available as a free correction, one copy of implements deterministically on arbitrary data.
Proof. From (12), with , . Controlled- gives
Applying Hadamard to the helper yields
Since , and , proving (13). Both branch operators are unitary and have prefactor , so the outcomes are equiprobable. On outcome 1, applying gives .
At the Hadamard magic angle,
which is Clifford. Thus the entire processor outside the consumed state is Clifford.
One-shot resource duality and universality
The injection theorem gives one direction of a conversion. The reverse direction is immediate from the definition:
To avoid a misleading claim that a state and a reusable gate are literally identical resources, we formulate a one-shot relation.
Definition 6.1 (One-shot free conversion). Fix a class of free operations containing state preparation of , Clifford unitaries, computational-basis measurement, and classical feed-forward. We write when one use or one copy of resource , together with operations in , realizes one use or one copy of .
Theorem 6.2 (One-shot state–gate duality). Let and . Relative to Clifford processing,
More explicitly, one invocation of prepares one copy of from , and one copy of implements one invocation of on arbitrary data.
Proof. The conversion is (15). The conversion is Theorem 5.1 together with the Clifford correction (14).
This is the precise sense in which the state and gate are interchangeable resources. It is an operational equivalence in a declared processor model, not an identification of Hilbert-space vectors with operators.
Universality consequence
The gate is a real single-qubit rotation that does not preserve the computational basis and is non-Clifford. Shi proved that CNOT together with any suitable real one-qubit gate of this kind yields universal quantum computation over real amplitudes, apart from the explicitly characterized exceptional cases [7]. Consequently a real Clifford processor supplied with copies of can inject and thereby reach universal real quantum computation in the usual approximation sense.
There is also a direct bridge to the conventional Clifford+ picture. Put . Since and ,
Thus access to together with the full Clifford group is equivalent, up to global phase and Clifford conjugation, to access to . The familiar Clifford+ universality therefore appears in the same processor model.
Corollary 6.3 (Magic misty resource). A supply of the nested misty state promotes the declared Clifford injection processor to a universal quantum resource: it gives universal real computation using the real gate fragment, and, with the full Clifford group, recovers Clifford+ universality through (17).
The corollary does not assert that the misty notation is a new route to the established universality of magic-state computation. Its point is representational: a nested source-language value discovered as a fixed point is simultaneously a consumable program resource.
A programming-language semantics for dual-role values
The two roles of can be stated as semantic certificates rather than informal labels. Let denote the state semantics of a closed misty term .
Definition 7.1 (Invariance certificate). A judgment
is sound when
Definition 7.2 (Program-resource certificate). A judgment
is sound when the declared injection processor , after consuming one copy of and applying its allowed feed-forward, realizes the unitary channel
on arbitrary input states, including inputs entangled with an external reference.
Because Theorem 5.1 proves equality at the operator level branch by branch, the program-resource certificate is stable under extension by an untouched reference system.
Theorem 7.3 (Dual-role soundness). For
we have both
where is the controlled- processor of Figure 3 with Clifford feed-forward.
Figure 3. State-to-gate injection. Outcome 0 applies directly; outcome 1 applies and is repaired by . For the correction is Clifford.

Figure 4. The conceptual neighborhood. Solid arrows mark precise implications or constructions used here; dashed links indicate comparisons that require additional hypotheses and must not be read as equivalences.
Proof. The first judgment is Theorem 3.3 with and . The second is Theorem 5.1 and Eq. (14).
The judgments classify different semantic facts. is extensional state invariance; is an operational statement about what an external processor does when the state is supplied and consumed. A richer language could track both as refinement/effect information without collapsing them into one type.
Combinators, recursion, and the boundary of the analogy
The fixed-point constructor has an exact syntactic relation to the combinator. In curried combinatory logic,
If a binary constructor is treated as and a unary operation as , then
Thus the misty constructor has an -shaped sharing pattern: the same argument is supplied both directly and through .
The semantic fixed-point property, however, does not come from the defining equation of . It comes from the algebraic hypotheses , symmetry of , and equivariance (4). This is precisely why and should not be conflated.
A fixed-point combinator satisfies
so is a general mechanism for obtaining a recursive fixed point of in a calculus where such self-application is meaningful [1]. Denotational semantics often interprets recursive definitions through least fixed points of continuous operators on ordered domains [9]. Neither construction is the same as finite group averaging.
The distinction can be summarized as follows.
is a finite algebraic symmetrizer. It constructs a fixed state because a finite orbit is averaged.
exposes the sharing/data-flow pattern of that expression.
is a recursive fixed-point constructor whose defining equation is itself self-referential.
An attractor is a dynamical notion: nearby states converge under iteration or continuous-time evolution. A unitary eigenstate need not be attracting; in particular causes generic states to oscillate rather than converge.
This separation is not cosmetic. It prevents the common but incorrect inference that a quantum eigenstate, a stabilizer state, a recursive fixed point, and an attractor are merely different names for the same mathematical object. What they share is an invariance schema; the mechanisms that establish or exploit the invariance are different.
Scope, prior work, and claim boundaries
The results sit at the intersection of several mature subjects, so the claim boundary is part of the theorem architecture.
Misty-state semantics. Rudolph introduced the black-and-white misty-state representation as an accessible rewriting language for quantum computation [6]. German’s 2026 work explicitly developed irreducible/fixed-point misty states and used them in a term-rewriting semantics [3]. Newton and German supplied the explicit normalization discipline used here [5]. We do not claim to introduce the misty notation, the nested Hadamard state, or the basic idea of fixed points in that notation.
Magic states and gate injection. Magic-state computation and the sufficiency of nonstabilizer ancillary states with Clifford processing are established by Bravyi and Kitaev and related gate-teleportation work [2, 4]. We do not claim the discovery of magic-state injection or of H-type magic states. The contribution is the exact processor theorem Theorem 5.1 stated in the real misty representation and its use to formalize a dual-role misty term.
Universality. The universality statement relies on established real-gate universality results, in particular Shi’s characterization of real single-qubit gates that promote classical/restricted gate sets to universality [7]. Our corollary simply transfers that result through the exact state-to-gate injection.
Fixed points and combinators. The equations for and , and the use of fixed points in denotational semantics, are classical programming-language theory [1, 9]. The paper does not identify those constructions with quantum eigenstates. Instead, it isolates one exact syntactic sharing identity (19) and one exact semantic contrast: finite orbit symmetrization versus recursive fixed-point construction.
What is new in the present synthesis. Within the declared misty-state fragment, the main contribution is a single auditable chain:
The fixed-point and program roles are carried by the same denotation but certified by different semantic judgments. This makes the “programs are data” analogy precise at one nontrivial quantum resource interface without asserting a universal state–gate correspondence.
Conclusion and next theorem frontier
The nested misty term
is a compact example of how one quantum object can legitimately inhabit several mathematical roles without those roles becoming synonymous. As a state it is the Hadamard eigenvector. As the two-element orbit cloud of under , it is a certified fixed point generated by finite symmetrization. As a nonstabilizer H-type state, it is a magic resource. As an input to the controlled- processor, it is consumed to implement the non-Clifford gate on arbitrary data. Conversely, one invocation of prepares the state. The exact operational statement is therefore the one-shot resource duality
The programming-language lesson is equally specific. The term can carry both an invariance certificate and a program-resource certificate ; these are distinct judgments about the same denotation. The constructor has an exact -combinator sharing pattern, but its fixed-point property comes from finite symmetry, not from recursion. remains the genuinely recursive mechanism. This separation turns a suggestive analogy into a small semantic discipline.
The next theorem frontier is to generalize the program-resource certificate from the single H-type resource to a typed family of dyadic mist terms, where the syntax records both the target gate and the adaptive correction structure. Such an extension should preserve the central discipline of the present paper: every claimed program interpretation must be backed by an exact channel identity, and every invariance claim by an explicit semantic certificate.
Acknowledgments
We thank Prof. Terry Rudolph for helpful conversations about this work.
References
- [1]H. P. Barendregt. The Lambda Calculus: Its Syntax and Semantics, 2nd ed. North-Holland, 1984.
- [2]S. Bravyi and A. Kitaev. Universal quantum computation with ideal Clifford gates and noisy ancillas. Physical Review A 71, 022316 (2005). doi:10.1103/PhysRevA.71.022316.DOI
- [3]D.-A. German. A term-rewriting semantics for pure quantum states. arXiv:2607.06584 (2026).arxiv.org/abs/2607.06584
- [4]D. Gottesman and I. L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature 402, 390–393 (1999).DOI
- [5]T. Newton and D.-A. German. Certified misty-state rewriting: A question-and-answer guide. arXiv:2608.10024 (2026).arxiv.org/abs/2608.10024
- [6]T. Rudolph. Q Is for Quantum. Terence Rudolph, 2017.
- [7]Y. Shi. Both Toffoli and Controlled-NOT need little help to do universal quantum computation. Quantum Information and Computation 3(1), 84–92 (2003); arXiv:quant-ph/0205115.DOI
- [9]G. Winskel. The Formal Semantics of Programming Languages: An Introduction. MIT Press, 1993.DOI
