Trees and Fenwick Trees

Why trees?

The Z-chain in Jordan-Wigner grows linearly because it uses a linear data structure. The key insight behind better encodings: use a tree to share parity information, cutting depth to $O(\log n)$.

Fenwick Trees (Binary Indexed Trees)

The Bravyi-Kitaev encoding is built on a Fenwick tree. FockMap provides a purely functional, immutable implementation:

open System.Numerics
open Encodings
open Encodings.TreeEncoding
open Encodings.MajoranaEncoding
open Encodings.JordanWigner
open Encodings.BravyiKitaev
open Encodings.Hamiltonian
let occupations = [| 1; 0; 1; 1; 0; 1; 0; 1 |]
let tree = FenwickTree.ofArray (^^^) 0 occupations

// Prefix query: XOR of elements 0..3
FenwickTree.prefixQuery tree 3

// Point query: just element 5
FenwickTree.pointQuery tree 5

// Immutable update (returns a new tree):
let tree' = FenwickTree.update tree 2 0

The Fenwick structure defines the BK index sets:

FenwickTree.updateSet 8 3        // U(3) — which qubits to update
FenwickTree.paritySet 3          // P(3) — parity contributors
FenwickTree.occupationSet 3      // Occ(3) — occupation encoding
FenwickTree.remainderSet 3       // R(3) = P(3) \ Occ(3)

Encoding trees: choose your shape

FockMap generalises beyond Fenwick trees to arbitrary ternary tree shapes (the path-based encoder supports at most three children per node):

let linear  = linearTree 8            // Chain → recovers Jordan-Wigner
let binary  = balancedBinaryTree 8     // Balanced binary → O(log₂ n)
let ternary = balancedTernaryTree 8    // Balanced ternary → O(log₃ n)
let vlasov  = vlasovTree 8            // Complete ternary (Vlasov) → O(log₃ n)

Walk any tree:

let binTree = balancedBinaryTree 8
treeAncestors binTree 5      // path from node 5 toward root
treeDescendants binTree 1    // all descendants
treeChildren binTree 1       // direct children only

Two frameworks for tree-based encoding

Framework 1 — Index sets (rooted star trees only):

⚠️ The generic treeEncodingScheme construction is CAR-valid only for rooted star trees. A census over all rooted labelled trees finds exactly n of the n^(n−1) trees satisfy the anticommutation relations for n = 3..6 — precisely the stars. Fenwick, chain, and balanced binary/ternary trees do not satisfy CAR under this construction. The call below runs and returns Pauli strings, but for balancedBinaryTree 8 (a non-star) those operators are not a valid encoding — it is shown only to illustrate the API surface. For valid tree encodings use Framework 2 (path-based) below, and for JW/BK/Parity use jordanWignerTerms / bravyiKitaevTerms / parityTerms.

// Valid index-set encoding: use one of the canonical schemes. For a general
// tree topology, prefer the path-based Framework 2 below.
let scheme = jordanWignerScheme
encodeOperator scheme Raise 2u 8u

Framework 2 — Path-based ternary tree (any ternary tree):

Constructs Pauli strings directly from root-to-leg paths using X/Y/Z link labels. This is the approach from Jiang et al. and the Bonsai paper:

let terTree = balancedTernaryTree 8
let links = computeLinks terTree       // assign X/Y/Z labels
let legs  = allLegs links              // enumerate all legs
let pairs = pairLegs terTree links     // pair legs per mode

// Full encoding in one call:
let result = encodeWithTernaryTree terTree Raise 2u 8u

The Vlasov tree: a different ternary shape

The balanced ternary tree (balancedTernaryTree) uses midpoint-split indexing: the root is in the middle, and children are spread across three roughly equal partitions. The Vlasov tree (vlasovTree) uses level-order (breadth-first) indexing instead: node 0 is the root, and children of node $j$ are $3j+1, 3j+2, 3j+3$.

This is based on Vlasov’s Clifford-algebraic construction (arXiv:1904.09912), where Clifford algebra generators are defined recursively on a complete ternary tree.

Both achieve $O(\log_3 n)$ weight, but they distribute weight differently across modes:

let n = 8u
printfn "%-5s  %-8s  %-8s" "Mode" "TerTree" "Vlasov"
for j in 0u .. n-1u do
    let weight (encode : EncoderFn) =
        let terms = (encode Raise j n).DistributeCoefficient
        terms.SummandTerms
        |> Array.map (fun t ->
            t.Signature |> Seq.filter (fun c -> c <> 'I') |> Seq.length)
        |> Array.max
    printfn "%-5d  %-8d  %-8d" j (weight ternaryTreeTerms) (weight vlasovTreeTerms)

Output:

Mode   TerTree   Vlasov
    3         3
    3         3
    3         3
    3         2       ← Vlasov wins here
    2         3       ← Balanced ternary wins here
    3         3
    3         3
    3         3

The tree shape matters: different qubit assignments put different modes at different depths, so the “best” tree depends on which modes appear most frequently in your Hamiltonian.

Comparing tree shapes on H₂

Both ternary tree shapes produce valid H₂ Hamiltonians with identical eigenspectra but different Pauli structure:

// A minimal H₂/STO-3G coefficient factory (4 spin-orbitals).
// See Chapter 10 for the full integral set and Chapter 13 for loading FCIDUMP files.
let lookup =
    let fcidump = """
 &FCI NORB=   2,NELEC= 2,MS2=0,
  ORBSYM=1,1,
  ISYM=1,
 &END
 0.6747559268144484    1    1    1    1
 0.6637114013508132    1    1    2    2
 0.1812104620151968    2    1    2    1
 0.6637114013508132    2    2    1    1
 0.697651504490461     2    2    2    2
 -1.253309786645977    1    1  0  0
 -0.4750688487721783   2    2  0  0
 0.7151043390810812  0  0  0  0
"""
    let (factory, _core, _nso) = Fcidump.parseToSpinOrbitalFactory fcidump
    factory

let hamEncoders = [
    ("Jordan-Wigner",    jordanWignerTerms)
    ("Bravyi-Kitaev",    bravyiKitaevTerms)
    ("Balanced Ternary", ternaryTreeTerms)
    ("Vlasov Tree",      vlasovTreeTerms)
]

for (name, encoder) in hamEncoders do
    let ham = (computeHamiltonianWith encoder lookup 4u).DistributeCoefficient
    let terms = ham.SummandTerms |> Array.filter (fun t -> Complex.Abs t.Coefficient > 1e-10)
    let weights = terms |> Array.map (fun t ->
        t.Signature |> Seq.filter (fun c -> c <> 'I') |> Seq.length)
    printfn "%-20s  Terms: %d  MaxWt: %d  AvgWt: %.2f"
        name terms.Length (Array.max weights) (Array.averageBy float weights)

Jordan-Wigner         Terms: 15  MaxWt: 4  AvgWt: 2.13
Bravyi-Kitaev         Terms: 15  MaxWt: 4  AvgWt: 2.40
Balanced Ternary      Terms: 15  MaxWt: 4  AvgWt: 2.40
Vlasov Tree           Terms: 15  MaxWt: 4  AvgWt: 2.40

For H₂ (4 qubits), both tree encodings match each other (and Bravyi–Kitaev) in term count and average weight. The differences grow with system size — at $n = 64$, different tree shapes can differ by 30–40% in total CNOT cost, making tree selection a first-order optimization concern.

Try it yourself: See Lab 10: Vlasov Tree for the full comparison script with tree structure printouts, per-mode weight tables, and H₂ Hamiltonian analysis.

Next: Building a Real Hamiltonian — the complete end-to-end pipeline