chaeyeunpark / unionfind Goto Github PK

View Code? Open in Web Editor NEW

19.0 2.0 3.0 451 KB

C++ implementation of Union-Find decoder and its Python binding.

License: GNU Lesser General Public License v2.1

Python 12.74% CMake 8.77% C++ 77.25% Makefile 0.80% Shell 0.43%

quantum-error-correction quantum-computing

unionfind's Introduction

UnionFind

Introduction

C++ implementation of the Union-Find decoder arXiv:1709:06218. Python interface is also implemented using pybind11.

Based on a Python implementation by Kai Meinerz.

Under the LGPL lisence.

This repository includes codes for arXiv:2101.07285 which explores a machine learning assisted preprocessing combined with conventional decoders such as minimum-weight perfect matching (MWPM) and the Union-Find decoder.

Installation

Currently, you can install this project by cloning the source code tree and compiling it. To clone the source tree, use git clone as

git clone https://github.com/chaeyeunpark/UnionFind.git && cd UnionFind
git submodule update --init --recursive

Then you can compile the code using

pip install -r requirements.txt
python3 setup.py install

Note that a compiler with some C++20 supports (e.g. GCC version => 10 or Clang++ version => 12) is required. For example, if you are using Ubuntu

apt install -y g++-10
CXX=g++-10 python3 setup.py install

will work.

PyPI support will be available soon.

Basic Usage

from UnionFindPy import Decoder
decoder = Decoder(parity_matrix)
decoder.decode(syndromes) # syndromes is a list of measurment outcomes of each parity operator

For details, check the document and examples directory.

Notes

This repository does not contain an implementation of weighted Union-Find decoder.

Reference

When you cite this repository, please use the following:

@misc{UnionFindCPP,
    author = {Chae-Yeun Park and Kai Meinerz},
    title = {Open-source C++ implementation of the Union-Find decoder},
    year = {2020},
    publisher = {GitHub},
    journal = {GitHub repository},
    doi = {10.5281/zenodo.10044828},
    howpublished = {\url{https://github.com/chaeyeunpark/UnionFind}}
}

unionfind's People

Contributors

Stargazers

Watchers

Forkers

xiangyzhg libi95 lwades

unionfind's Issues

Add benchmark plot

Custom lattice supports for Python

As PyMatching, one may pass a sparse matrix of the parity check matrix to instantiate a decoder for a given lattice.
One may just make C++ lattice class that takes a sparse matrix in csr format.

DecoderFromParity

I am having trouble compiling the decoder because I do not find the ._union_find_py file. Do you know if I am missing some step? I believe I did all the steps correctly.

Thank you in advance

Example of ML assisented decoder

Hi, I had read your arXiv:2101.07285 paper. In readme.md, you mentioned that there is an example with ML combined convention decoder. I didn't find this example. Would you give some links or examples about how to implement it?

Installation error on macOS (both with arm64 and x86_64 conda environments)

When following the installation instruction (with an additional step of conda install cmake), I ran into the following error. Any suggestion on what went wrong? Thanks!

Output (click to expand)

python3 setup.py install
Requirement already satisfied: ninja in /Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages (from -r requirements.txt (line 1)) (1.10.2.3)
Requirement already satisfied: numpy in /Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages (from -r requirements.txt (line 2)) (1.22.0)
Requirement already satisfied: scipy in /Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages (from -r requirements.txt (line 3)) (1.7.3)
running install
running bdist_egg
running egg_info
writing UnionFindPy.egg-info/PKG-INFO
writing dependency_links to UnionFindPy.egg-info/dependency_links.txt
writing requirements to UnionFindPy.egg-info/requires.txt
writing top-level names to UnionFindPy.egg-info/top_level.txt
reading manifest file 'UnionFindPy.egg-info/SOURCES.txt'
adding license file 'LICENSE'
writing manifest file 'UnionFindPy.egg-info/SOURCES.txt'
installing library code to build/bdist.macosx-10.9-x86_64/egg
running install_lib
running build_py
running build_ext
-- The C compiler identification is AppleClang 13.0.0.13000029
-- The CXX compiler identification is AppleClang 13.0.0.13000029
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /Library/Developer/CommandLineTools/usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /Library/Developer/CommandLineTools/usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- union_find version 
-- pybind11 v2.8.1 
-- Found PythonInterp: /Users/honamnguyen/miniconda3/envs/qcircuit64/bin/python3 (found version "3.9.7") 
-- Found PythonLibs: /Users/honamnguyen/miniconda3/envs/qcircuit64/lib/libpython3.9.dylib
-- Performing Test HAS_FLTO
-- Performing Test HAS_FLTO - Success
-- Performing Test HAS_FLTO_THIN
-- Performing Test HAS_FLTO_THIN - Success
-- Configuring done
-- Generating done
-- Build files have been written to: /Users/honamnguyen/miniconda3/UnionFind/build/temp.macosx-10.9-x86_64-3.9
[2/3] Building CXX object UnionFindPy/cpp/CMa.../_union_find_py.dir/binding/UnionFindPy.cpp.
FAILED: UnionFindPy/cpp/CMakeFiles/_union_find_py.dir/binding/UnionFindPy.cpp.o 
/Library/Developer/CommandLineTools/usr/bin/c++ -D_union_find_py_EXPORTS -I/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/externals/robin-map/include -I/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include -I/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/externals -isystem /Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/externals/pybind11/include -isystem /Users/honamnguyen/miniconda3/envs/qcircuit64/include/python3.9 -O3 -DNDEBUG -arch x86_64 -isysroot /Library/Developer/CommandLineTools/SDKs/MacOSX12.1.sdk -fPIC -fvisibility=hidden -flto -std=gnu++2a -MD -MT UnionFindPy/cpp/CMakeFiles/_union_find_py.dir/binding/UnionFindPy.cpp.o -MF UnionFindPy/cpp/CMakeFiles/_union_find_py.dir/binding/UnionFindPy.cpp.o.d -o UnionFindPy/cpp/CMakeFiles/_union_find_py.dir/binding/UnionFindPy.cpp.o -c /Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp
In file included from /Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:18:
In file included from /Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/Decoder.hpp:19:
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/LatticeConcept.hpp:42:9: error: no member named 'convertible_to' in namespace 'std'
        = std::convertible_to<T, std::vector<uint32_t>> || detail::std_array<T>;
          ~~~~~^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/LatticeConcept.hpp:42:24: error: 'T' does not refer to a value
        = std::convertible_to<T, std::vector<uint32_t>> || detail::std_array<T>;
                              ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/LatticeConcept.hpp:40:19: note: declared here
template<typename T>
                  ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/LatticeConcept.hpp:52:8: error: expected concept name with optional arguments
                } -> std::convertible_to<uint32_t>;
                     ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/LatticeConcept.hpp:55:8: error: expected concept name with optional arguments
                } -> std::convertible_to<uint32_t>;
                     ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/LatticeConcept.hpp:58:8: error: expected concept name with optional arguments
                } -> vertex_connections_result;
                     ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/LatticeConcept.hpp:61:8: error: expected concept name with optional arguments
                } -> std::convertible_to<uint32_t>;
                     ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/LatticeConcept.hpp:64:8: error: expected concept name with optional arguments
                } -> std::convertible_to<uint32_t>;
                     ^
In file included from /Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:18:
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/Decoder.hpp:36:10: error: unknown type name 'LatticeConcept'
template<LatticeConcept Lattice> class Decoder
         ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/Decoder.hpp:43:8: error: unknown type name 'Lattice'
        const Lattice lattice_;
              ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:40:52: error: template argument for non-type template parameter must be an expression
        using UnionFindFromParity = UnionFindCPP::Decoder<UnionFindCPP::LatticeFromParity>;
                                                          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/include/Decoder.hpp:36:25: note: template parameter is declared here
template<LatticeConcept Lattice> class Decoder
                        ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:41:13: error: use of undeclared identifier 'UnionFindFromParity'
        py::class_<UnionFindFromParity>(m, "DecoderFromParity")
                   ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:57:12: error: use of undeclared identifier 'UnionFindFromParity'
                                return UnionFindFromParity(static_cast<uint32_t>(num_parities),
                                       ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:42:8: error: no matching function for call to 'init'
                .def(py::init(
                     ^~~~~~~~
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/externals/pybind11/include/pybind11/pybind11.h:1657:5: note: candidate template ignored: substitution failure [with Func = (lambda at /Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:43:4)]
Ret init(Func &&f) { return {std::forward<Func>(f)}; }
    ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/externals/pybind11/include/pybind11/pybind11.h:1650:68: note: candidate function template not viable: requires 0 arguments, but 1 was provided
template <typename... Args> detail::initimpl::constructor<Args...> init() { return {}; }
                                                                   ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/externals/pybind11/include/pybind11/pybind11.h:1662:5: note: candidate function template not viable: requires 2 arguments, but 1 was provided
Ret init(CFunc &&c, AFunc &&a) {
    ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:82:12: error: use of undeclared identifier 'UnionFindFromParity'
                                return UnionFindFromParity(static_cast<uint32_t>(num_parities),
                                       ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:62:8: error: no matching function for call to 'init'
                .def(py::init(
                     ^~~~~~~~
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/externals/pybind11/include/pybind11/pybind11.h:1657:5: note: candidate template ignored: substitution failure [with Func = (lambda at /Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:63:4)]
Ret init(Func &&f) { return {std::forward<Func>(f)}; }
    ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/externals/pybind11/include/pybind11/pybind11.h:1650:68: note: candidate function template not viable: requires 0 arguments, but 1 was provided
template <typename... Args> detail::initimpl::constructor<Args...> init() { return {}; }
                                                                   ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/externals/pybind11/include/pybind11/pybind11.h:1662:5: note: candidate function template not viable: requires 2 arguments, but 1 was provided
Ret init(CFunc &&c, AFunc &&a) {
    ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:88:18: error: use of undeclared identifier 'UnionFindFromParity'
                .def("clear", &UnionFindFromParity::clear, "Clear decoder's internal data")
                               ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:89:40: error: use of undeclared identifier 'UnionFindFromParity'
                .def_property_readonly("num_edges", &UnionFindFromParity::num_edges,
                                                     ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:92:21: error: use of undeclared identifier 'UnionFindFromParity'
                        "num_vertices", &UnionFindFromParity::num_vertices,
                                         ^
/Users/honamnguyen/miniconda3/UnionFind/UnionFindPy/cpp/binding/UnionFindPy.cpp:96:7: error: unknown type name 'UnionFindFromParity'
                        [](UnionFindFromParity& decoder,
                           ^
19 errors generated.
ninja: build stopped: subcommand failed.
Traceback (most recent call last):
  File "/Users/honamnguyen/miniconda3/UnionFind/setup.py", line 130, in <module>
    setup(classifiers=classifiers, **(info))
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages/setuptools/__init__.py", line 153, in setup
    return distutils.core.setup(**attrs)
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/core.py", line 148, in setup
    dist.run_commands()
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/dist.py", line 966, in run_commands
    self.run_command(cmd)
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/dist.py", line 985, in run_command
    cmd_obj.run()
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages/setuptools/command/install.py", line 67, in run
    self.do_egg_install()
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages/setuptools/command/install.py", line 109, in do_egg_install
    self.run_command('bdist_egg')
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/cmd.py", line 313, in run_command
    self.distribution.run_command(command)
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/dist.py", line 985, in run_command
    cmd_obj.run()
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages/setuptools/command/bdist_egg.py", line 164, in run
    cmd = self.call_command('install_lib', warn_dir=0)
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages/setuptools/command/bdist_egg.py", line 150, in call_command
    self.run_command(cmdname)
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/cmd.py", line 313, in run_command
    self.distribution.run_command(command)
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/dist.py", line 985, in run_command
    cmd_obj.run()
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages/setuptools/command/install_lib.py", line 11, in run
    self.build()
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/command/install_lib.py", line 107, in build
    self.run_command('build_ext')
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/cmd.py", line 313, in run_command
    self.distribution.run_command(command)
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/dist.py", line 985, in run_command
    cmd_obj.run()
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/site-packages/setuptools/command/build_ext.py", line 79, in run
    _build_ext.run(self)
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/command/build_ext.py", line 340, in run
    self.build_extensions()
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/command/build_ext.py", line 449, in build_extensions
    self._build_extensions_serial()
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/distutils/command/build_ext.py", line 474, in _build_extensions_serial
    self.build_extension(ext)
  File "/Users/honamnguyen/miniconda3/UnionFind/setup.py", line 78, in build_extension
    subprocess.check_call(
  File "/Users/honamnguyen/miniconda3/envs/qcircuit64/lib/python3.9/subprocess.py", line 373, in check_call
    raise CalledProcessError(retcode, cmd)
subprocess.CalledProcessError: Command '['cmake', '--build', '.']' returned non-zero exit status 1.

Thanks!

Recommend Projects

React

A declarative, efficient, and flexible JavaScript library for building user interfaces.
Vue.js

🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript

TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
TensorFlow

An Open Source Machine Learning Framework for Everyone
Django

The Web framework for perfectionists with deadlines.
Laravel

A PHP framework for web artisans
D3

Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

javascript

JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
web

Some thing interesting about web. New door for the world.
server

A server is a program made to process requests and deliver data to clients.
Machine learning

Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Visualization

Some thing interesting about visualization, use data art
Game

Some thing interesting about game, make everyone happy.

Recommend Org

Facebook

We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft

Open source projects and samples from Microsoft.
Google

Google ❤️ Open Source for everyone.
Alibaba

Alibaba Open Source for everyone
D3

Data-Driven Documents codes.
Tencent

China tencent open source team.