TernaryTree

class TernaryTree(spec)

Bases: object

A ternary tree defining a fermion-to-qubit encoding.

A ternary tree on \(N\) nodes encodes \(N\) fermionic modes onto \(N\) qubits. Each node is a qubit carrying three downward links, labelled X, Y and Z. A link either descends to a child node (an edge) or terminates (a leg). Each leg’s upward path to the root spells a Pauli string: crossing the link labelled \(P\) that descends from node \(u\) contributes \(P\) on qubit \(u\), with the identity everywhere else.

Every tree of this shape yields a valid encoding, so the constructor accepts an arbitrary one. The familiar encodings are particular shapes:

Encoding	Construction	Pauli weight
Jordan-Wigner	TernaryTree.chain(n, "Z")	\(n\)
Parity	TernaryTree.chain(n, "X")	\(n\)
Balanced [1]	TernaryTree.breadth_first(n, 3)	\(\lceil \log_3(2n+1) \rceil\), optimal
Binary-branching	TernaryTree.breadth_first(n, 2, "ZXY")	\(\lfloor \log_2 n \rfloor + 1\)

Those two conveniences cover the uniform families only, which is why the constructor also takes an arbitrary tree: a parent-and-label specification, one entry per node, giving that node’s parent and the label of the link descending to it (None for the root). The trees that motivate the framework need it – the Bonsai algorithm [2] grows a spanning tree of a device’s coupling graph, so its branching follows that connectivity and is neither a chain nor uniform.

Not every encoding in the family has a convenience constructor: Bravyi-Kitaev, for instance, is a tree that is not uniform, so it is built by computing its specification. The mappers guide works that case through as an example.

Usage

>>> from qiskit_fermions.mappers import TernaryTree
>>> tree = TernaryTree.breadth_first(4, 3)
>>> tree.num_nodes, tree.num_legs, tree.max_weight
(4, 9, 2)

The balanced tree’s weight grows logarithmically where Jordan-Wigner’s grows linearly:

>>> TernaryTree.chain(13, "Z").max_weight
13
>>> TernaryTree.breadth_first(13, 3).max_weight
3

An arbitrary tree is given as one (parent, label) pair per node, with None for the root:

>>> tree = TernaryTree([None, (0, "X"), (0, "Y"), (1, "Z")])
>>> tree.num_nodes, tree.num_legs
(4, 9)

[1]

Z. Jiang, A. Kalev, W. Mruczkiewicz and H. Neven, Optimal fermion-to-qubit mapping via ternary trees with applications to reduced quantum states learning, Quantum 4, 276 (2020), arXiv:1910.10746.

[2]

A. Miller, Z. Zimborás, S. Knecht, S. Maniscalco and G. García-Pérez, Bonsai algorithm: grow your own fermion-to-qubit mappings, PRX Quantum 4, 030314 (2023), arXiv:2212.09731.

Attributes

max_weight

The largest Pauli weight of any single Majorana operator this tree generates.

A fermionic creation or annihilation operator is a sum of two Majorana operators, so its image may reach twice this.

num_legs

The number of legs, always 2 * num_nodes + 1.

This holds for every shape: a node with fewer children has more legs, not fewer strings. Of these, 2 * num_nodes pair into the Majorana operators and one is left over, carrying the total fermionic parity.

num_nodes

The number of nodes, which is both the number of modes and the number of qubits.

root

The root node.

Methods

static breadth_first(num_nodes, branching, order='XYZ')

Build a tree by attaching up to branching children to each node in turn.

branching=3 gives the balanced tree, whose Pauli weight \(\lceil \log_3(2n+1) \rceil\) is optimal over all fermion-to-qubit mappings.

Parameters:

• num_nodes – the number of modes, and hence qubits.

• branching – how many children to attach per node, at most 3.

• order – the labels to attach children along, as a 3-character string. Changing it changes which Pauli strings the encoding produces, though not their weight.

Raises:

ValueError – if num_nodes is zero, branching exceeds 3, order is not 3 Pauli labels, or its first branching labels are not distinct.

Note

branching=2 gives a binary-branching tree of weight \(\lfloor \log_2 n \rfloor + 1\). That matches the Bravyi-Kitaev weight but is not that encoding, except when num_nodes is a power of two: Bravyi-Kitaev’s tree is the irregular partial-sum shape. See TernaryTree for how to build it.

static chain(num_nodes, label)

Build a linear chain descending along label.

label="Z" is the Jordan-Wigner encoding and label="X" the parity encoding; both have Pauli weight num_nodes.

Parameters:

• num_nodes – the number of modes, and hence qubits.

• label – the link the chain descends along.

Raises:

ValueError – if num_nodes is zero or label is not a Pauli label.

children(node)

Return the children of node, as a {label: child} mapping over its edges.

Links that terminate in a leg are omitted.

leg_paths()

Return the Pauli string of every leg, as (qubit, label) pairs ordered leaf-to-root.

>>> from qiskit_fermions.mappers import TernaryTree
>>> TernaryTree.chain(2, "Z").leg_paths()
[[(0, 'X')], [(0, 'Y')], [(1, 'X'), (0, 'Z')], [(1, 'Y'), (0, 'Z')], [(1, 'Z'), (0, 'Z')]]

The qubits within a path are not sorted: they follow the tree’s depth rather than the node numbering. Use TernaryTreeEncoding.majorana_image() for the sorted form the mapped observables use.