BPOTF Decoder

Belief Propagation Ordered Tanner Forest decoder
Report Bug · Request Feature

Table of Contents

1. About The Project
2. Getting Started
   • Prerequisites
   • Installation
3. Usage
4. Roadmap
5. Contributing
6. License
7. Contact
8. Acknowledgments
9. Attribution

About The Project

This project implements a new decodig method for quantum low density parity check codes which we have named Belief Propagation Ordered Tanner Forest (BPOTF). The method is based on an slighlty modified Kruskal's algorithm to find the spanning forest associated to the columns of a PCM with highest a posteriori probability coming from running belief propagation and it uses the Disjoint-Set data structure for the implementation.

(back to top)

Getting Started

This section explains which are the prerequites, how to compile and use the Python module created from this project.

Prerequisites

The project has the following dependecies, which some of them are handled by pip/CMake installation processes and do not need to be accounted for. The dependencies are:

• C++20
• Pybind11 (automatic download)
• Cmake (pip installation supports it)
• LDPC (part of its source code is embedded in the module)
• BeliefMatching (automatic handling with pip)
• Stim (automatic handling with pip)
• SciPy (automatic handling with pip)

Installation

Below are the explanations on how to compile the python module to use the BPOTF decoder. It is highly recommended to use the pip option, while for developing use pip's editable mode and then the CMake option.

NOTE: the installation instructions are presented for linux systems, but some may also work for other kind of OS.

CMake

The steps to compile the python importable BPOTF module using this method are explained below.

1. Clone the git repository and navigate to the directory.

   git clone https://github.com/Ademartio/BPOTF.git
   cd BPOTF

2. Create a new build folder and navigate to it.

   mkdir build
   cd build

3. Configure the Cmake project and build the python importable module.

   cmake ..
   make

When using this method alone, to be able to use the module it must be copied to the virtual environment or import the location of the module directly from the python script.

Pip

To compile the python importable module using pip, the only requisite is to have a C++20 compatible compiler and a pip 10+. Currently, Debian based systems and Windows 10 systems with MSVC 17 have been tested with this option. To compile it using this method, the steps indicated below can be followed:

1. Clone the git repository and navigate to the directory.

   git clone https://github.com/Ademartio/BPOTF.git
   cd BPOTF

2. (Optional) It is recommended to create a virtual environment to install python packages local to the project.

   python3 -m venv .venv
   source .venv/bin/activate # linux
   .venv\Scripts\activate # Windows

3. Execute the following command:

   pip install . # Normal install
   pip install -e . # Editable mode

(back to top)

Usage

Simple usage of the module, import it just like another python module and use the offered OBPOTF object to initialize and decode the error. A minimal example of its initialization could be the following:

# Assuming the module is placed in the compilation output folder 'module'
from module import BPOTF
import numpy as np

_bpotf = BPOTF.OBPOTF(pcm.astype(np.uint8), p)

# ...
# Generate errors/syndrome or whatever
# ...

_bpotf.decode(syndrome.astype(np.int32))

(back to top)

Roadmap

• Add a License to the repo.
• Add CSC support.
• Add Pip supported installation method.
• Add function to calculate an sparsified detector error model and transfer matrix.
• Add function to map soft information from detector error model to sparsified detector matrix.
• Add BP+BP decoding protocol for circuit-level noise.
• Add OTF function against LLRs (using logarithmic probabilities)
• Try to optimize BP decoder

See the open issues for a full list of proposed features (and known issues).

(back to top)

Contributing

Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.

If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!

1. Fork the Project
2. Create your Feature Branch (git checkout -b feature/AmazingFeature)
3. Commit your Changes (git commit -m 'Add some AmazingFeature')
4. Push to the Branch (git push origin feature/AmazingFeature)
5. Open a Pull Request

(back to top)

License

Distributed under the MIT License. See LICENSE for more information.

(back to top)

Contact

• Antonio de Martì - @ton_demarti - [email protected]
• Josu Etxezarreta - @katutxakur - [email protected]
• Imanol Etxezarreta @ima96.bsky.social - [email protected]
• Joschka Roffe - @quantumgizmos - [email protected]

Project Link: https://github.com/Ademartio/BPOTF

(back to top)

Acknowledgments

Thanks to the following amazing projects and webs for the help, tools and information! Do not forget to visit and star/like their work also!

• Pybind11
• LDPC python library - Joschka Roffe
• Beliefmatching package - Oscar Higgott
• Stim
• SciPy
• Best-README-Template - Othneil Drew

(back to top)

Attribution

When using the OTF post-processing decoding algorithm or the two stage BP decoder please cite our paper:

@article{bpotf_2024,
    author = "{deMarti iOlius}, Antonio and {Etxezarreta Martinez}, Imanol and Roffe, Joschka and {Etxezarreta Martinez}, Josu",
    title = "{An almost-linear time decoding algorithm for quantum LDPC codes under circuit-level noise}",
    journal = {arXiv},
    pages = {2409.01440},
    archivePrefix = "arXiv",
    primaryClass = "quant-ph",
    month = sep,
    year = {2024},
    url ={https://arxiv.org/abs/2409.01440}
}