Sample Tree

A tree data structure to count circuit and subset selections during protocol sampling.

---

source

draw_tree

 draw_tree (tree, verbose=False, path=None)

Generate and return PNG image of tree

To display the image in command line call .show() on the returned PIL image object.

see Fig. 1 in paper

	Type	Default	Details
tree
verbose	bool	False
path	NoneType	None	File path to save png image to, if None only display image
Returns	PNG image		Image of CountTree

/home/dw/.local/lib/python3.10/site-packages/fastcore/docscrape.py:225: UserWarning: Unknown section Attributes
  else: warn(msg)

---

source

Tree

 Tree (constants, L=None)

Data structure to track sampled Circuits in Protocol

---

source

Variable

 Variable (name, count=0, invariant=False, ff_deterministic=False,
           circuit_id=None, **kwargs)

Representation of a random variable inside Tree

See Appendix C in paper

---

source

Delta

 Delta (name, parent=None, children=None, **kwargs)

Representation of subset cutoff error inside Tree

See Appendix C in paper

---

source

Constant

 Constant (name, count=0, parent=None, const_val=None, **kwargs)

Representation of a constant value inside Tree.

A node in a tree is a uniquely identifiable object containing references to at most one parent and possibly many children. The root node has no parent and leaf nodes have not children.

The Constant class complements the common tree node by a count attribute which represents the number of times a node has been visited during sampling.

See Appendix C in paper

Test creating a 1-level tree.

# Test 1-level tree

constants = {0: {(0,): 0.8, (1,): 0.1, (2,): 0.05}}
tree = Tree(constants)
root = tree.add(name='root', node_type=Variable, count=100, circuit_id=0)
root0 = tree.add(name=(0,), node_type=Constant, parent=root, count=40)
root1 = tree.add(name=(1,), node_type=Constant, parent=root, count=30)
root2 = tree.add(name=(2,), node_type=Constant, parent=root, count=30)
d = tree.add(name='δ', node_type=Delta, parent=root)
none_0 = tree.add(name='None', node_type=Variable, parent=root0, count=40)
none_0.invariant = True
fail_1 = tree.add(name='fail', node_type=Variable, parent=root1, count=20)
none_1 = tree.add(name='None', node_type=Variable, parent=root1, count=10)
none_2 = tree.add(name='None', node_type=Variable, parent=root2, count=25)

tree.marked = set([fail_1])

print(tree)

root (100, 0.00e+00)
├── (0,) (40)
│   └── None (40, 0.00e+00)
├── (1,) (30)
│   ├── fail (20, 7.20e-03)
│   └── None (10, 7.20e-03)
├── (2,) (30)
│   └── None (25, 4.60e-03)
└── δ

Test numerics of 1-level tree.

# Test numerics 1-level tree

test_eq(tree.root_leaf_rate, 20/100)
test_eq(tree.subtree_sum(tree.root, tree.marked), 0.1 * 20/30)

vL = 0.1**2 * fail_1.var + 0.05**2 * none_2.var # vL = vL^up
test_close(tree.var(mode=1), vL, eps=1e-05)
test_close(tree.var(mode=0), vL, eps=1e-05)

Test creation of 2-level tree.

# Test 2-level tree

constants = {0: {(0,): 0.8, (1,): 0.1}, # c0
             1: {(0,): 0.7, (1,): 0.2}, # c1
             2: {(0,): 1.0}}            # c2

tree = Tree(constants)
root = tree.add(name='c0', circuit_id=0, node_type=Variable, count=100)
root0 = tree.add(name=(0,), node_type=Constant, parent=root, count=70)
root1 = tree.add(name=(1,), node_type=Constant, parent=root, count=30)
d1 = tree.add(name='δ', parent=root, node_type=Delta)

c1_0 = tree.add(name='c1', circuit_id=1, node_type=Variable, count=50, parent=root0)
c1_1 = tree.add(name='c1', circuit_id=1, node_type=Variable, count=20, parent=root1)
c2_0 = tree.add(name='c2', circuit_id=2, node_type=Variable, count=20, parent=root0)
c2_1 = tree.add(name='c2', circuit_id=2, node_type=Variable, count=10, parent=root1)

c1_0_0 = tree.add(name=(0,), node_type=Constant, parent=c1_0, count=40)
c1_0_1 = tree.add(name=(1,), node_type=Constant, parent=c1_0, count=10)
d2 = tree.add(name='δ', node_type=Delta, parent=c1_0)

c1_1_0 = tree.add(name=(0,), node_type=Constant, parent=c1_1, count=15)
c1_1_1 = tree.add(name=(1,), node_type=Constant, parent=c1_1, count=5)
d3 = tree.add(name='δ', node_type=Delta, parent=c1_1)

c2_0_0 = tree.add(name=(0,), node_type=Constant, parent=c2_0, count=20)
d4 = tree.add(name='δ', node_type=Delta, parent=c2_0)
c2_1_0 = tree.add(name=(0,), node_type=Constant, parent=c2_1, count=10)
d5 = tree.add(name='δ', node_type=Delta, parent=c2_1)

none_c1_0_0 = tree.add(name='None', node_type=Variable, parent=c1_0_0, count=40)
none_c1_0_0.invariant = True
none_c1_0_1 = tree.add(name='None', node_type=Variable, parent=c1_0_1, count=5)
fail_c1_0_1 = tree.add(name='fail', node_type=Variable, parent=c1_0_1, count=5)
none_c1_1_0 = tree.add(name='None', node_type=Variable, parent=c1_1_0, count=15)
none_c1_1_1 = tree.add(name='None', node_type=Variable, parent=c1_1_1, count=3)
fail_c1_1_1 = tree.add(name='fail', node_type=Variable, parent=c1_1_1, count=2)

none_c2_0_0 = tree.add(name='None', node_type=Variable, parent=c2_0_0, count=20)
none_c2_0_0.invariant = True
fail_c2_1_0 = tree.add(name='fail', node_type=Variable, parent=c2_1_0, count=10)

tree.marked = set([fail_c1_0_1, fail_c1_1_1, fail_c2_1_0])

print(tree)

c0 (100, 0.00e+00)
├── (0,) (70)
│   ├── c1 (50, 2.88e-03)
│   │   ├── (0,) (40)
│   │   │   └── None (40, 0.00e+00)
│   │   ├── (1,) (10)
│   │   │   ├── None (5, 2.27e-02)
│   │   │   └── fail (5, 2.27e-02)
│   │   └── δ
│   └── c2 (20, 2.88e-03)
│       ├── (0,) (20)
│       │   └── None (20, 0.00e+00)
│       └── δ
├── (1,) (30)
│   ├── c1 (20, 7.20e-03)
│   │   ├── (0,) (15)
│   │   │   └── None (15, 9.77e-04)
│   │   ├── (1,) (5)
│   │   │   ├── None (3, 4.03e-02)
│   │   │   └── fail (2, 4.03e-02)
│   │   └── δ
│   └── c2 (10, 7.20e-03)
│       ├── (0,) (10)
│       │   └── fail (10, 2.07e-03)
│       └── δ
└── δ

A0 = 0.8
A1 = 0.1
B0 = 0.7
B1 = 0.2
C0 = 1

test_close(tree.path_prod(tree.root, fail_c1_0_1), A0*50/70*B1*5/10)
test_close(tree.path_prod(tree.root, fail_c1_1_1), A1*20/30*B1*2/5)
test_close(tree.path_prod(tree.root, fail_c2_1_0), A1*10/30*1)

test_close(tree.path_prod(tree.root, d1), 1 - A0 - A1)
test_close(tree.path_prod(tree.root, d2), A0*50/70*(1-B0-B1))
test_close(tree.path_prod(tree.root, d3), A1*20/30*(1-B0-B1))
test_close(tree.path_prod(tree.root, d4), 0)
test_close(tree.path_prod(tree.root, d5), 0)

v1 = A0**2 * B1**2 * ((c1_0.var + (50/70)**2)*(fail_c1_0_1.var + (5/10)**2) - (50/70)**2 * (5/10)**2)
test_close(tree.path_var(fail_c1_0_1), v1)

v2 = A0**2 * (1-B0-B1)**2 * c1_0.var
test_close(tree.path_var(d2), v2)

Test numerics of 2-level tree.

# Test numerics 2-level tree
test_eq(tree.root_leaf_rate, 5/100 + 2/100 + 10/100)

pL = A0 * 50/70 * 0.2 * 5/10 + A1 * (20/30 * B1 * 2/5 + 10/30 * C0 * 1)
pL_up = 1 - A0 - A1 + A0*(50/70)*(1-B0-B1*5/10) + A1*(20/30)*(1-B0-B1*(3/5)) + A1*10/30*C0*1

test_eq(tree.subtree_sum(tree.root, tree.marked), pL)

v14 = (c1_0.var + (50/70)**2)*(fail_c1_0_1.var + (5/10)**2) - (50/70)**2 * (5/10)**2
v27 = (c1_1.var + (20/30)**2)*(fail_c1_1_1.var + (2/5)**2) - (20/30)**2 * (2/5)**2
v2bar8 = (c2_1.var + (10/30)**2) * (fail_c2_1_0.var + (1)**2) - (10/30)**2 * (1)**2
vL = A0**2*B1**2*v14 + A1**2*B1**2*v27 + A1**2*C0**2*v2bar8 - 2*A1*A1*B1*C0*(2/5)*(1)*c1_1.var
vL += A1**2 * B0**2 * ((c1_1.var + c1_1.rate**2) * none_c1_1_0.var) # non-fail path contributions

test_close(tree.var(mode=1), vL)

Simple (real) tree example

constants = {'ENC': {(0,): 0.977251, (1,): 0.0224993}, # c0
             'meas': {(0,): 0.993021, (1,): 0.0069581}, # c1
             'Z2': {(0,): 0.994015, (1,): 0.00597006}
            } # corresp. p_max = 1e-3
M0 = constants['ENC'][(0,)]
L = 2

tree = Tree(constants, L=L)
root = tree.add(name='ENC', circuit_id='ENC', node_type=Variable, count=1)
root1 = tree.add(name=(1,), node_type=Constant, parent=root, count=1)

root1enc = tree.add(name='meas', circuit_id='meas', node_type=Variable, parent=root1, count=1)
root1enc0 = tree.add(name=(0,), node_type=Constant, parent=root1enc, count=1)
root1enc0 = tree.add(name="None", node_type=Variable, parent=root1enc0, count=1)
root1enc0.invariant = True

root1encd = tree.add(name='δ', node_type=Delta, parent=root1enc)

root1meas = tree.add(name='Z2', circuit_id='Z2', node_type=Variable, parent=root1, count=0)
root1meas0 = tree.add(name=(0,), node_type=Constant, parent=root1meas, count=0)

root1measd = tree.add(name='δ', node_type=Delta, parent=root1meas)

print(tree)

ENC (1, 0.00e+00)
└── (1,) (1)
    ├── meas (1, 6.25e-02)
    │   ├── (0,) (1)
    │   │   └── None (1, 0.00e+00)
    │   └── δ
    └── Z2 (0, 6.25e-02)
        ├── (0,) (0)
        └── δ

delta = constants['ENC'][(1,)] * (1 - constants['meas'][(0,)])
test_close(tree.delta, delta)

# 10 samples test

constants = {'ENC': {(0,): 0.977251, (1,): 0.0224993}, # c0
             'meas': {(0,): 0.993021, (1,): 0.0069581}, # c1
             'Z2': {(0,): 0.994015, (1,): 0.00597006}
            } # corresp. p_max = 1e-3

M0 = constants['ENC'][(0,)]
L = 2

tree = Tree(constants, L=L)
root = tree.add(name='ENC', circuit_id='ENC', node_type=Variable, count=10)
root1 = tree.add(name=(1,), node_type=Constant, parent=root, count=1)
root0 = tree.add(name=(0,), node_type=Constant, parent=root, count=9)
rootd = tree.add(name='δ', node_type=Delta, parent=root)


root0meas = tree.add(name='meas', circuit_id='meas', node_type=Variable, parent=root0, count=9)
root0meas0 = tree.add(name=(0,), node_type=Constant, parent=root0meas, count=9)
root0meas0None = tree.add(name="None", node_type=Variable, parent=root0meas0, count=9)
root0meas0None.invariant = True

root0meas1 = tree.add(name=(1,), node_type=Constant, parent=root0meas, count=0)
root0measd = tree.add(name='δ', node_type=Delta, parent=root0meas)


root1enc = tree.add(name='meas', circuit_id='meas', node_type=Variable, parent=root1, count=1)
root1enc0 = tree.add(name=(0,), node_type=Constant, parent=root1enc, count=1)
root1enc0 = tree.add(name="None", node_type=Variable, parent=root1enc0, count=1)
root1enc0.invariant = True

root1encd = tree.add(name='δ', node_type=Delta, parent=root1enc)

root1meas = tree.add(name='Z2', circuit_id='Z2', node_type=Variable, parent=root1, count=0)
root1meas0 = tree.add(name=(0,), node_type=Constant, parent=root1meas, count=0)

root1measd = tree.add(name='δ', node_type=Delta, parent=root1meas)

print(tree)

ENC (10, 0.00e+00)
├── (1,) (1)
│   ├── meas (1, 6.25e-02)
│   │   ├── (0,) (1)
│   │   │   └── None (1, 0.00e+00)
│   │   └── δ
│   └── Z2 (0, 6.25e-02)
│       ├── (0,) (0)
│       └── δ
├── (0,) (9)
│   └── meas (9, 2.50e-03)
│       ├── (0,) (9)
│       │   └── None (9, 0.00e+00)
│       ├── (1,) (0)
│       └── δ
└── δ

Another example

constants = {'ENC': {(0,): 0.977251, (1,): 0.0224993}, # c0
             'meas': {(0,): 0.993021, (1,): 0.0069581}, # c1
            } # corresp. p_max = 1e-3

tree = Tree(constants, L=2)
root = tree.add(name='ENC', circuit_id='ENC', node_type=Variable, count=2)
root0 = tree.add(name=(0,), node_type=Constant, parent=root, count=1)
root1 = tree.add(name=(1,), node_type=Constant, parent=root, count=1)
d = tree.add(name='δ', node_type=Delta, parent=root)

root1enc = tree.add(name='ENC', circuit_id='ENC', node_type=Variable, parent=root1, count=0)
root1enc0 = tree.add(name=(0,), node_type=Constant, parent=root1enc, count=0)
root1encd = tree.add(name='δ', node_type=Delta, parent=root1enc)

root1meas = tree.add(name='meas', circuit_id='meas', node_type=Variable, parent=root1, count=1)
root1meas0 = tree.add(name=(0,), node_type=Constant, parent=root1meas, count=1)
root1meas0none = tree.add(name='None', node_type=Variable, parent=root1meas0, count=1)
root1meas0none.invariant = True # Set leaf node to inv (FT PATH!)
root1measd = tree.add(name='δ', node_type=Delta, parent=root1meas)


root0meas = tree.add(name='meas', circuit_id='meas', node_type=Variable, parent=root0, count=1)
root0meas0 = tree.add(name=(0,), node_type=Constant, parent=root0meas, count=1)
root0meas1 = tree.add(name=(1,), node_type=Constant, parent=root0meas, count=0)

root0meas0none = tree.add(name='None', node_type=Variable, parent=root0meas0, count=1)
root0meas0none.invariant = True # Set leaf node to inv
root0measd = tree.add(name='δ', node_type=Delta, parent=root0meas)

print(tree)

ENC (2, 0.00e+00)
├── (0,) (1)
│   └── meas (1, 6.25e-02)
│       ├── (0,) (1)
│       │   └── None (1, 0.00e+00)
│       ├── (1,) (0)
│       └── δ
├── (1,) (1)
│   ├── ENC (0, 6.25e-02)
│   │   ├── (0,) (0)
│   │   └── δ
│   └── meas (1, 6.25e-02)
│       ├── (0,) (1)
│       │   └── None (1, 0.00e+00)
│       └── δ
└── δ

d1 = 1 - constants['ENC'][(0,)] - constants['ENC'][(1,)]
d2 = constants['ENC'][(0,)] * (1 - constants['meas'][(0,)] - constants['meas'][(1,)])
d3 = constants['ENC'][(1,)] * (1 - constants['meas'][(0,)])
delta = d1 + d2 + d3
test_close(tree.delta, delta)

M0 = constants['ENC'][(0,)] # smallest possible A0.
test_close(tree.constants[tree.M0_index[0]][tree.M0_index[1]], M0)

L = 2
V1 = 6.25e-02

VLup = constants['ENC'][(1,)]**2 * (1 - constants['meas'][(0,)] - L * (1 - M0))**2 * V1
test_close(np.sqrt(VLup), np.sqrt(tree.var(mode=0)))