---
title: TernaryTree (latest version)
description: API reference for qiskit_fermions.mappers.TernaryTree in the latest version of qiskit-fermions
source: https://quantum.cloud.ibm.com/docs/en/api/qiskit-fermions/mappers-ternary-tree
---

# TernaryTree

*class* `TernaryTree(spec)`

Bases: [`object`](https://docs.python.org/3/builtins/functions.html#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\]](#id3) | `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()`](#qiskit_fermions.mappers.TernaryTree.chain "qiskit_fermions.mappers.TernaryTree.chain") and [`TernaryTree.breadth_first()`](#qiskit_fermions.mappers.TernaryTree.breadth_first "qiskit_fermions.mappers.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\]](#id4) 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](/docs/addons/qiskit-fermions/guides/mappers#bravyi-kitaev-by-hand) works that case through as an example.

## Usage

```pycon
>>> 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:

```pycon
>>> 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:

```pycon
>>> 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()`](#qiskit_fermions.mappers.TernaryTree.breadth_first "qiskit_fermions.mappers.TernaryTree.breadth_first") with a branching of one, and only the first label of its `order` matters:

```pycon
>>> 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:

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

\[[1](#id1)]

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](https://arxiv.org/abs/1910.10746).

\[[2](#id2)]

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](https://arxiv.org/abs/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

### breadth\_first

*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](/docs/addons/qiskit-fermions/guides/mappers#bravyi-kitaev-by-hand) 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**](https://docs.python.org/3/builtins/exceptions.html#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**](https://docs.python.org/3/builtins/exceptions.html#OverflowError) – if `num_nodes` is negative or does not fit in 32 bits.

### chain

*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()`](#qiskit_fermions.mappers.TernaryTree.breadth_first "qiskit_fermions.mappers.TernaryTree.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**](https://docs.python.org/3/builtins/exceptions.html#ValueError) – if `num_nodes` is zero or `label` is not a Pauli label.
- [**OverflowError**](https://docs.python.org/3/builtins/exceptions.html#OverflowError) – if `num_nodes` is negative or does not fit in 32 bits.

### children

`children(node)`

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

Links that terminate in a leg are omitted.

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

**Raises**

[**ValueError**](https://docs.python.org/3/builtins/exceptions.html#ValueError) – if `node` is out of range.

### leg\_paths

`leg_paths()`

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

```pycon
>>> 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()`](/docs/api/qiskit-fermions/mappers-ternary-tree-encoding#majorana_image "qiskit_fermions.mappers.TernaryTreeEncoding.majorana_image") for the sorted form the mapped observables use.