[Feature Request] Speed up slice composition

[gwwatkin]

Issue Description

From profiling (#228) it emerged that composing the slices is the slowest part of the compilation, even when simulation is disabled:

         76063897 function calls (64410007 primitive calls) in 63.049 seconds

   Ordered by: cumulative time
   List reduced from 921 to 20 due to restriction <20>

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000   63.049   63.049 ./debug/debug_contract_sk_result.py:37(run_pipeline)
        1    0.016    0.016   62.525   62.525 ./src/lsqecc/patches/lattice_surgery_computation_composer.py:183(make_computation)
     1503    0.008    0.000   43.252    0.029 ./src/lsqecc/patches/lattice_surgery_computation_composer.py:246(__exit__)
     1503    0.131    0.000   42.301    0.028 ./src/lsqecc/patches/lattice_surgery_computation_composer.py:310(newTimeSlice)
9604878/2417   18.211    0.000   42.223    0.017 /usr/lib/python3.10/copy.py:128(deepcopy)
870856/2407    3.811    0.000   42.193    0.018 /usr/lib/python3.10/copy.py:259(_reconstruct)
855175/2404    3.759    0.000   42.152    0.018 /usr/lib/python3.10/copy.py:227(_deepcopy_dict)
314827/3907    0.978    0.000   42.093    0.011 /usr/lib/python3.10/copy.py:201(_deepcopy_list)
     1502    0.010    0.000   18.223    0.012 ./src/lsqecc/patches/lattice_surgery_computation_composer.py:389(addLogicalOperation)
      351    0.008    0.000   18.106    0.052 ./src/lsqecc/patches/lattice_surgery_computation_composer.py:314(multiBodyMeasurePatches)
      351    0.008    0.000   18.096    0.052 ./src/lsqecc/patches/ancilla_region_routing.py:189(compute_ancilla_region_cells)
      351    1.442    0.004   17.187    0.049 ./src/lsqecc/patches/ancilla_region_routing.py:69(make_graph_of_free_cells)
   622331   11.165    0.000   11.165    0.000 ./src/lsqecc/patches/patches.py:175(getPatchOfCell)
   606661    0.273    0.000   11.084    0.000 ./src/lsqecc/patches/patches.py:182(cellIsFree)
   765492    2.520    0.000    6.738    0.000 /usr/lib/python3.10/copy.py:210(_deepcopy_tuple)
   765492    0.792    0.000    4.121    0.000 /usr/lib/python3.10/copy.py:211(<listcomp>)
   213800    0.333    0.000    3.628    0.000 ./venv/lib/python3.10/site-packages/igraph/__init__.py:365(add_edges)
   213800    3.227    0.000    3.227    0.000 {function Graph.add_edges at 0x7f7cd1fdbac0}
  1741706    0.706    0.000    3.063    0.000 /usr/lib/python3.10/copy.py:264(<genexpr>)
 18631138    2.700    0.000    2.702    0.000 {method 'get' of 'dict' objects}

The incriminated copy is this one:

lattice-surgery-compiler/src/lsqecc/patches/lattice_surgery_computation_composer.py

Lines 306 to 308 in 61c5a94

	def newTimeSlice(self):
	self.qubit_patch_slices.append(copy.deepcopy(self.lattice()))
	self.qubit_patch_slices[-1].logical_ops = []

And removing this is tricky because the whole composer is built around editing the last slice in place.

Proposed Solution

Translate and refactor the slice composition in C++. The composer has had a refactoring overdue for some time now.

Using better engineering, leveraging stringer types and const-correctness it should be possible to manage copying better, with flatter data-structures and by avoiding unnecessary copies. It will also be easier to parallelize, which in python has to go through the multiprocessing module