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):
     Works correctly ONLY for Fenwick trees (where all ancestors > j).
     Uses Update/Parity/Occupation sets with the generic MajoranaEncoding.

 (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.

 Different tree shapes yield different encodings:
   - Chain (linear tree):   recovers Jordan-Wigner
   - Fenwick tree:          recovers Bravyi-Kitaev
   - Balanced ternary tree: achieves O(log₃ n) Pauli weight (optimal)

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). 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`	Encode using a balanced ternary tree (path-based method). 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 (Fenwick-style index sets). WARNING: Only produces correct encodings for Fenwick trees! 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`