Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add minimum-weight T-join example #61

Open
oscarhiggott opened this issue Mar 31, 2023 · 0 comments
Open

Add minimum-weight T-join example #61

oscarhiggott opened this issue Mar 31, 2023 · 0 comments
Labels
documentation Improvements or additions to documentation enhancement New feature or request

Comments

@oscarhiggott
Copy link
Owner

oscarhiggott commented Mar 31, 2023

The MWPM decoding problem is called a minimum-weight T-join in the graph theory/ combinatorial optimisation literature (the set T is the set of detection events). Therefore pymatching is an implementation of this graph theory problem, which is a subroutine of the Chinese postman problem. It would be good to explain this connection in the readme for potential users interested in combinatorial optimisation but not familiar with QEC jargon (e.g. could add an example function that uses graph theory terminology). Similarly, it might be good to add a C++ method for solving the Chinese postman problem. PyMatching is optimised for the distribution of T-join problems that arise in QEC (where the paths in the solution are typically short), however it will likely be faster than alternative available implementations even for a broader class of more generic problems since it avoids explicitly constructing the complete graph on elements of T (though it would be useful to run benchmarks to make the comparison more concrete).

@oscarhiggott oscarhiggott added documentation Improvements or additions to documentation enhancement New feature or request labels Mar 31, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
documentation Improvements or additions to documentation enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant