TreeEncoding (Encodings)

TreeEncoding Module

Namespace: Encodings
Assembly: Encodings.dll

 General tree-based fermion-to-qubit encodings.

 This module implements two approaches:

 (1) Index-set approach (Havlíček et al. arXiv:1701.07072):
     The generic tree → index-set construction below is CAR-valid ONLY for
     rooted STAR trees (one central node adjacent to all others). An
     independent census over all rooted labelled trees finds exactly n of the
     n^(n−1) trees satisfy CAR for n=3..6 — precisely the rooted stars.
     Fenwick, chain, and balanced binary/ternary trees FAIL in general, and
     monotonicity of ancestor indices is neither necessary nor sufficient
     (a star rooted at node 0 passes with ancestor < child; a Fenwick tree
     fails with ancestor > child). This construction is a demonstration of the
     EncodingScheme abstraction, NOT the library's production tree encoder.

 (2) Path-based ternary-tree approach (Bonsai: arXiv:2212.09731,
     Jiang et al.: arXiv:1910.10746):
     Works for ANY ternary tree. Constructs Majorana strings directly
     from root-to-leg paths. Each node has 3 descending links labeled
     X, Y, Z.  Each leg yields a Pauli string by collecting the labels
     along its root-to-leg path. Paired legs give the two Majoranas
     for each fermionic mode. This is what the exported tree encoders
     (ternaryTreeTerms, balancedBinaryTreeTerms, vlasovTreeTerms) use.

 Canonical encodings are provided directly and do NOT rely on the generic
 index-set construction above:
   - Jordan-Wigner:  JordanWigner.fs (and jordanWignerScheme)
   - Bravyi-Kitaev:  BravyiKitaev.fs via a persistent Fenwick tree
   - Balanced ternary tree: O(log₃ n) Pauli weight via the path-based method

Types

Type	Description
EncodingTree	A rooted tree on n nodes. Nodes are indexed 0 .. n-1.
LegId	A "leg" is identified by the node it hangs from and which label slot it uses.
Link	A link descending from a node: either an Edge to a child, or a Leg (no child).
LinkLabel	Label for a link descending from a node.
TreeNode	A node in a rooted tree. Each node represents one qubit/mode.

Functions and values

Function or value	Description
`allLegs links` Full Usage: `allLegs links` Parameters: links : `Map<int, Link list>` Returns: `LegId list`	Enumerate all legs in the tree. links : `Map<int, Link list>` Returns: `LegId list`
`balancedBinaryTree n` Full Usage: `balancedBinaryTree n` Parameters: n : `int` Returns: `EncodingTree`	Build a balanced binary tree on n nodes. The root is the middle element; left subtree gets indices 0..mid-1, right subtree gets indices mid+1..n-1. This achieves O(log₂ n) Pauli weight for all operators. n : `int` Returns: `EncodingTree`
`balancedBinaryTreeTerms op j n` Full Usage: `balancedBinaryTreeTerms op j n` Parameters: op : `LadderOperatorUnit` j : `uint32` n : `uint32` Returns: `PauliRegisterSequence`	Encode a ladder operator using a balanced binary tree (also uses the path-based method — binary trees are ternary trees where some nodes have only 2 children). op : `LadderOperatorUnit` j : `uint32` n : `uint32` Returns: `PauliRegisterSequence`
`balancedTernaryTree n` Full Usage: `balancedTernaryTree n` Parameters: n : `int` Returns: `EncodingTree`	Build a balanced ternary tree on n nodes. Each internal node has up to 3 children. The root is the element at position n/2; the three subtrees split the remaining indices into roughly equal thirds. This achieves O(log₃ n) Pauli weight, which is optimal (Jiang et al., arXiv:1910.10746). n : `int` Returns: `EncodingTree`
`computeLinks tree` Full Usage: `computeLinks tree` Parameters: tree : `EncodingTree` Returns: `Map<int, Link list>`	Compute the link labeling for each node in the tree. Each node gets exactly 3 descending links (edges + legs), so the tree must be ternary — at most 3 children per node. Nodes with more than 3 children are not supported and raise ArgumentException. We use "homogeneous localisation" (Bonsai Algorithm 4): - If 2 or 3 children: assign X, Y to edges; Z to leg (or 3rd edge). - If 1 child: assign X to edge; Y, Z to legs. - If 0 children (leaf): X, Y, Z all legs. tree : `EncodingTree` Returns: `Map<int, Link list>`
`encodeWithTernaryTree tree op j n` Full Usage: `encodeWithTernaryTree tree op j n` Parameters: tree : `EncodingTree` op : `LadderOperatorUnit` j : `uint32` n : `uint32` Returns: `PauliRegisterSequence`	Encode a single ladder operator using the path-based ternary tree method. m_{2j} ↔ S_{s_x(u)} (even Majorana) m_{2j+1} ↔ S_{s_y(u)} (odd Majorana) a†_j = ½(m_{2j} − i·m_{2j+1}) = ½(S_x − i·S_y) a_j = ½(m_{2j} + i·m_{2j+1}) = ½(S_x + i·S_y) tree : `EncodingTree` op : `LadderOperatorUnit` j : `uint32` n : `uint32` Returns: `PauliRegisterSequence`
`linearTree n` Full Usage: `linearTree n` Parameters: n : `int` Returns: `EncodingTree`	Build a linear chain tree: 0 — 1 — 2 — … — (n-1) where 0 is the root and each node's only child is the next. This recovers the Jordan-Wigner encoding. n : `int` Returns: `EncodingTree`
`majoranaStringForLeg tree links leg n` Full Usage: `majoranaStringForLeg tree links leg n` Parameters: tree : `EncodingTree` links : `Map<int, Link list>` leg : `LegId` n : `int` Returns: `PauliRegister`	Build the Majorana (Pauli) string for a given leg. Follow the path from root to the leg's node, collecting the Pauli operator at each node along the way, then add the label of the leg itself at the leg's node. tree : `EncodingTree` links : `Map<int, Link list>` leg : `LegId` n : `int` Returns: `PauliRegister`
`pairLegs tree links` Full Usage: `pairLegs tree links` Parameters: tree : `EncodingTree` links : `Map<int, Link list>` Returns: `Map<int, (LegId * LegId)>`	Pair the legs into fermionic modes (Bonsai Algorithm 1 / Section III.3). For each node u: Follow X-link, then keep taking Z-links until a leg → that's s_x(u) Follow Y-link, then keep taking Z-links until a leg → that's s_y(u) Returns: Map from node index to (s_x leg, s_y leg). tree : `EncodingTree` links : `Map<int, Link list>` Returns: `Map<int, (LegId * LegId)>`
`ternaryTreeScheme n` Full Usage: `ternaryTreeScheme n` Parameters: n : `int` Returns: `EncodingScheme`	Index-set EncodingScheme derived from a balanced ternary tree. WARNING: this uses the generic index-set construction, which is CAR-valid ONLY for rooted star trees — a balanced ternary tree is a star only for very small n (e.g. n=4), so this scheme does NOT yield a valid encoding in general. For the correct balanced-ternary encoding use the path-based ternaryTreeTerms. n : `int` Returns: `EncodingScheme`
`ternaryTreeTerms op j n` Full Usage: `ternaryTreeTerms op j n` Parameters: op : `LadderOperatorUnit` j : `uint32` n : `uint32` Returns: `PauliRegisterSequence`	Encode a ladder operator using the ternary tree encoding (correct path-based method from Bonsai / Jiang et al.). op : `LadderOperatorUnit` j : `uint32` n : `uint32` Returns: `PauliRegisterSequence`
`treeAncestors tree j` Full Usage: `treeAncestors tree j` Parameters: tree : `EncodingTree` j : `int` Returns: `int list`	Ancestors of node j (from j toward root, excluding j). tree : `EncodingTree` j : `int` Returns: `int list`
`treeChildren tree j` Full Usage: `treeChildren tree j` Parameters: tree : `EncodingTree` j : `int` Returns: `int list`	Children of node j. tree : `EncodingTree` j : `int` Returns: `int list`
`treeChildrenSet tree j` Full Usage: `treeChildrenSet tree j` Parameters: tree : `EncodingTree` j : `int` Returns: `Set<int>`	Children set F(j): direct children of j. tree : `EncodingTree` j : `int` Returns: `Set<int>`
`treeDescendants tree j` Full Usage: `treeDescendants tree j` Parameters: tree : `EncodingTree` j : `int` Returns: `int list`	All descendants of node j (excluding j), via DFS. tree : `EncodingTree` j : `int` Returns: `int list`
`treeEncodingScheme tree` Full Usage: `treeEncodingScheme tree` Parameters: tree : `EncodingTree` Returns: `EncodingScheme`	Create an EncodingScheme from a tree (Havlíček-style index sets). WARNING: this generic construction is CAR-valid ONLY for rooted STAR trees (verified by census: exactly n of the n^(n−1) rooted labelled trees pass for n=3..6, all rooted stars). Fenwick, chain, and balanced binary/ternary trees produce operators that violate the anticommutation relations. For correct tree encodings use the path-based encoders (ternaryTreeTerms, etc.); for JW/BK/Parity use JordanWigner.fs / BravyiKitaev.fs / parityScheme. tree : `EncodingTree` Returns: `EncodingScheme`
`treeOccupationSet tree j` Full Usage: `treeOccupationSet tree j` Parameters: tree : `EncodingTree` j : `int` Returns: `Set<int>`	Occupation set Occ(j) = {j} ∪ descendants(j). tree : `EncodingTree` j : `int` Returns: `Set<int>`
`treeParitySet tree j` Full Usage: `treeParitySet tree j` Parameters: tree : `EncodingTree` j : `int` Returns: `Set<int>`	Parity set P(j) = R(j) ∪ F(j). tree : `EncodingTree` j : `int` Returns: `Set<int>`
`treeRemainderSet tree j` Full Usage: `treeRemainderSet tree j` Parameters: tree : `EncodingTree` j : `int` Returns: `Set<int>`	The "remainder" set R(j): for each ancestor a of j, collect a's children that have index < j AND are NOT themselves ancestors of j (i.e., not on the path from j to root). tree : `EncodingTree` j : `int` Returns: `Set<int>`
`treeUpdateSet tree j` Full Usage: `treeUpdateSet tree j` Parameters: tree : `EncodingTree` j : `int` Returns: `Set<int>`	Update set U(j): ancestors of j. tree : `EncodingTree` j : `int` Returns: `Set<int>`
`vlasovTree n` Full Usage: `vlasovTree n` Parameters: n : `int` Returns: `EncodingTree`	Build a complete ternary tree with breadth-first (level-order) indexing. Node 0 is the root; children of node j are 3j+1, 3j+2, 3j+3 (when they fall within n). Based on Vlasov, "Clifford algebras, Spin groups and qubit trees", arXiv:1904.09912 (2019), Quanta 11:97-114 (2022). This achieves O(log₃ n) Pauli weight. n : `int` Returns: `EncodingTree`
`vlasovTreeTerms op j n` Full Usage: `vlasovTreeTerms op j n` Parameters: op : `LadderOperatorUnit` j : `uint32` n : `uint32` Returns: `PauliRegisterSequence`	Encode a ladder operator using the Vlasov complete ternary tree. op : `LadderOperatorUnit` j : `uint32` n : `uint32` Returns: `PauliRegisterSequence`