Algebra-of-Boxes-code

Associated Manuscript

This GitHub page is associated to the following manuscript

• Manuscript: 📃 Algebra of Nonlocal Boxes and the Collapse of Communication Complexity
• Authors: 👤 Pierre Botteron, 👤 Anne Broadbent, 👤 Reda Chhaibi, 👤 Ion Nechita, and 👤 Clément Pellegrini.

Content

./
|__ nonlocal-boxes/: Core of package. 
|  |-- `__init__.py`: Init file.
|  |-- `evaluate.py`: Package of the function to evaluate, using PyTorch.
|  |-- `utils.py`: Package of the constants, using PyTorch.
|  |-- `Vectorization-of-the-code.pdf`: Explanations of the vectorization.
|__ ipynb/: Contains Python notebooks which demonstrate how the code works.
|-- `README.md`: This file.

Details of the Python notebooks (folder ipynb/):

File name	Description	Link with the manuscript
Coordinates_extremal_NS_boxes.ipynb	Drawing the 24 extremal boxes of $\mathcal{NS}$ in terms of $2$ games.	Figures 11 and 8
Draw-new-collapsing-boxes.ipynb	Drawing new collapsing boxes using Algorithm 4.	Figure 10
Draw-Orbit.ipynb	Drawing the Orbit of a box $\mathtt{P}$ in some slices.	Figures 7 and 8, Appendix A
Histograms.ipynb	Drawing the histograms of the ouputs of Algorithms 2 and 3.	Figure 9
Multiplication-Table.ipynb	Computing the multiplication table given some boxes and a wiring.	Figure 4, Eq. (18), Appendix C
Test_if_W_is_collapsing.ipynb	Given a wiring $\mathsf{W}$ and a triangle of boxes, test if the wiring collapses the triangle.	Proof of Thm. 41

Installation of the Package

1. Create new virtual environment .venv_boxes:

$ python3 -m venv .venv_boxes

2. If needed:

$ sudo apt install python3-venv

3. Activate virtual environment:

$ source .venv_boxes/bin/activate

4. Upgrade pip, wheel and setuptools

$ pip install --upgrade pip
$ pip install --upgrade setuptools
$ pip install wheel

5. Install the non_local_boxes package.

$ python setup.py develop

6. (Optional) In order to use Jupyter with this virtual environment .venv_boxes (see https://janakiev.com/blog/jupyter-virtual-envs/ for details):

$ pip install ipykernel
$ python -m ipykernel install --user --name=.venv_boxes

Configuration

There is a variable nb_columns in non_local_boxes/evaluate.py that can be set depending on the algo that is running:

• for optimisation codes, set it to a large number, e.g. 1000;
• for evaluation codes, set it to 1. The bigger that number is, the more precise is the optimisation but the longer is the run time.

Reference

@article{Botteron2024algebraofnonlocal,
  doi = {10.22331/q-2024-07-10-1402},
  url = {https://doi.org/10.22331/q-2024-07-10-1402},
  title = {Algebra of {N}onlocal {B}oxes and the {C}ollapse of {C}ommunication {C}omplexity},
  author = {Botteron, Pierre and Broadbent, Anne and Chhaibi, Reda and Nechita, Ion and Pellegrini, Cl{\'{e}}ment},
  journal = {{Quantum}},
  issn = {2521-327X},
  volume = {8},
  pages = {1402},
  month = jul,
  year = {2024}
}