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\)

TernaryTree.chain() and TernaryTree.breadth_first() 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)

Two trees compare equal when they have the same shape, labels and node numbering, however they were built, which is what lets a set or dictionary deduplicate the candidates a tree search produces. A chain, for instance, is just TernaryTree.breadth_first() with a branching of one, and only the first label of its order matters:

>>> chain = TernaryTree.chain(3, "Z")
>>> chain == TernaryTree.breadth_first(3, 1, "ZXY")
True
>>> chain == TernaryTree.breadth_first(3, 1, "ZYX")
True
>>> len({chain, TernaryTree.breadth_first(3, 1, "ZXY"), TernaryTree.chain(3, "X")})
2

A tree is what a search produces and what defines an encoding, so it is the thing worth carrying between processes, and it can be pickled:

>>> import pickle
>>> tree = TernaryTree.breadth_first(4, 3)
>>> pickle.loads(pickle.dumps(tree)) == tree
True

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

No Pauli term of a fermionic creation or annihilation operator is heavier than this, since it is a sum of two Majorana operators. The two terms generally act on different qubits, though, so the operator as a whole can be supported on more.

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.

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, for any order: Bravyi-Kitaev’s tree is the irregular partial-sum shape. See the mappers guide for how to build it.

Parameters:

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

• branching – how many children to attach per node, from 1 to 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 is not between 1 and 3, order is not 3 Pauli labels, or its first branching labels are not distinct.

• OverflowError – if num_nodes is negative or does not fit in 32 bits.

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.

This is only a convenience: it is breadth_first() with branching=1, where order needs just the one label.

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.

• OverflowError – if num_nodes is negative or does not fit in 32 bits.

children(node)

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

Links that terminate in a leg are omitted.

>>> from qiskit_fermions.mappers import TernaryTree
>>> TernaryTree.breadth_first(4, 3).children(0)
{'X': 1, 'Y': 2, 'Z': 3}

Raises:

ValueError – if node is out of range.

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.