tqec.templates.subtemplates.get_spatially_distinct_subtemplates#

get_spatially_distinct_subtemplates(instantiation: ndarray[Any, dtype[int64]], manhattan_radius: int = 1, avoid_zero_plaquettes: bool = True) → UniqueSubTemplates[source]#

Returns a representation of all the distinct sub-templates of the provided manhattan radius.

Note

This function will likely be inefficient for large templates (i.e., large values of k) or for large Manhattan radiuses, both in terms of memory used and computation time.

Right now, with

  • n the width of the provided instantiation array,

  • m the height of the provided instantiation array,

  • r the provided Manhattan radius,

it takes of the order of n*m*(2*r+1)² memory and has to sort an array of n*m elements of size (2*r+1)² in lexicographic order so require, in the worst case, O(n*m*log(n*m)*(2*r+1)²) runtime.

Subclasses are invited to reimplement that method using a specialized algorithm (or hard-coded values) to speed things up.

Some timings obtained on an AMD Ryzen 9 5950X:

` k = 10 ---------------------------------------------------------------------- radius   =         0 |         1 |         2 |         3 |         4 time (s) =  0.000776 |  0.000992 |   0.00151 |   0.00227 |   0.00321 ---------------------------------------------------------------------- k = 20 ---------------------------------------------------------------------- radius   =         0 |         1 |         2 |         3 |         4 time (s) =   0.00202 |   0.00356 |   0.00672 |    0.0116 |    0.0173 ---------------------------------------------------------------------- k = 40 ---------------------------------------------------------------------- radius   =         0 |         1 |         2 |         3 |         4 time (s) =   0.00778 |    0.0156 |    0.0326 |    0.0574 |    0.0889 ---------------------------------------------------------------------- k = 80 ---------------------------------------------------------------------- radius   =         0 |         1 |         2 |         3 |         4 time (s) =    0.0318 |    0.0706 |     0.147 |      0.27 |     0.426 ---------------------------------------------------------------------- k = 160 ---------------------------------------------------------------------- radius   =         0 |         1 |         2 |         3 |         4 time (s) =     0.139 |     0.309 |     0.651 |      1.25 |      1.98 ---------------------------------------------------------------------- `

Parameters:

  • instantiation – a 2-dimensional array representing the instantiated template on which sub-templates should be computed.

  • manhattan_radius – radius of the considered ball using the Manhattan distance. Only squares with sides of 2*manhattan_radius+1 plaquettes will be considered.

  • avoid_zero_plaquettes – True if sub-templates with an empty plaquette (i.e., 0 value in the instantiation of the Template instance) at its center should be ignored. Default to True.

Returns:

a representation of all the sub-templates found.