qiskit-optimization
qiskit-optimization copied to clipboard
qiskit-community
Adding the Max-k-Cut application
Summary
Adding the Max-k-Cut to the application section
Details and comments
Max-k-Cut: Given an undirected graph, find a partition of nodes into at most k subsets such that the total weight of the edges between the k subsets is maximized. To solve this problem, the space-efficient quantum optimization representation (or encoding) for the graph coloring problem proposed in [1] is used.
This work has been done in collaboration between Claudia Zendejas-Morales (@clausia) and Vyron Vasileiadis (@fedonman). This contribution was done under QIntern 2021 (https://qworld.net/qintern-2021/) organized by QWorld, under the supervision of Adam Glos (@adamglos92) and Zoltan Zimboras (@zimboras). We would like to thank Kareem H. El-Safty (@kareem1925) for bringing up the idea of implementing space-efficient Max-k-Cut on qiskit.
[1]: Z. Tabi et al., "Quantum Optimization for the Graph Coloring Problem with Space-Efficient Embedding," 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), 2020, pp. 56-62, doi: 10.1109/QCE49297.2020.00018.
Closes https://github.com/Qiskit/qiskit-optimization/issues/255
Pull Request Test Coverage Report for Build 2265763085
- 79 of 90 (87.78%) changed or added relevant lines in 2 files are covered.
- No unchanged relevant lines lost coverage.
- Overall coverage decreased (-0.02%) to 91.222%
| Changes Missing Coverage | Covered Lines | Changed/Added Lines | % |
|---|---|---|---|
| qiskit_optimization/applications/max_k_cut.py | 78 | 89 | 87.64% |
| <!-- | Total: | 79 | 90 |
| Totals | |
|---|---|
| Change from base Build 2263161952: | -0.02% |
| Covered Lines: | 4292 |
| Relevant Lines: | 4705 |
💛 - Coveralls
@t-imamichi Hi, thanks for asking, I think it's best to close this PR and open another one when the update is ready