quantum-maxcut
A quantum algorithm for the maximum cut problem in arbitrary graphs. Implementation using Qiskit.
Science Score: 57.0%
This score indicates how likely this project is to be science-related based on various indicators:
-
✓CITATION.cff file
Found CITATION.cff file -
✓codemeta.json file
Found codemeta.json file -
✓.zenodo.json file
Found .zenodo.json file -
✓DOI references
Found 6 DOI reference(s) in README -
○Academic publication links
-
○Academic email domains
-
○Institutional organization owner
-
○JOSS paper metadata
-
○Scientific vocabulary similarity
Low similarity (8.9%) to scientific vocabulary
Keywords
Repository
A quantum algorithm for the maximum cut problem in arbitrary graphs. Implementation using Qiskit.
Basic Info
Statistics
- Stars: 3
- Watchers: 1
- Forks: 0
- Open Issues: 0
- Releases: 2
Topics
Metadata Files
README.md
Quantum maxcut
Quantum algorithms for the maximum cut problem in arbitrary graphs.
Status
This project consists of two notebooks. Both are complete.
How to use the notebooks:
- Input a list of edges into the code body at the indicated position.
- Hit "Run" to execute the algorithm and print the output.
Note: If you run the Python version, you will get a dictionary of results as output.
Note:
You may need to adjust the variable t in the CNOT gate. It is currently set to the highest possible value indicating that we expect the highest possible cut. So, if your output is not producing two spikes (= a maxcut was found), t should be decreased and the code executed again. Repeat this procedure till the maxcut is found.
You may also need to adjust the variable R used for calculating the number of algorithm iterations. It is currently set to 2 as we expect a single max-cut. If you expect there might be more than one, try setting this value to 2 * expectednumberof_maxcuts.
Acknowledgement
The code of quantummaxcutalgorithm.ipynb is based on the theory described in [1].
The code of quantummaxcutalgorithm_optimized.ipynb is based on the theory described in [2].
The code was written by Renata Wong (https://renatawong.github.io/).
This work benefited greatly from discussions with Prof. Weng-Long Chang (National Kaohsiung University of Science and Technology) and Yu-Hao Chen (National Taiwan University). All remaining deficiencies are my own.
References
[1] W-L. Chang, R. Wong, W-Y. Chung, Y-H. Chen, J-C. Chen, and A.V. Vasilakos, Quantum speedup for the maximum cut problem, CTHPC 2023 (https://sites.google.com/view/cthpc2023), May 25-26, 2023, Taiwan. DOI: https://doi.org/10.48550/arXiv.2305.16644
[2] W-L. Chang, R. Wong, Y-H. Chen, W-Y. Chung, J-C. Chen, and A.V. Vasilakos, Bioinspired Quantum Oracle Circuits for Biomolecular Solutions of the Maximum Cut Problem. TechRxiv. December 07, 2023. DOI: [https://doi.org/10.36227/techrxiv.24736389]
Owner
- Name: Renata Wong
- Login: renatawong
- Kind: user
- Location: Poland / Taiwan
- Company: National Center for Theoretical Sciences, Taipei, Taiwan, R.O.C.
- Website: https://www.linkedin.com/in/renata-wong/
- Repositories: 4
- Profile: https://github.com/renatawong
Researcher in Quantum Information Science. IBM Certified Associate Developer (Quantum Computing). IBM Qiskit Advocate.
Citation (CITATION.cff)
cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: Wong
given-names: Renata
orcid: https://orcid.org/0000-0001-5468-0716
title: "Quantum maximum cut algorithm"
version: 2.0.0
doi: 10.5281/zenodo.7790804
date-released: 2023-04-02
url: "https://github.com/github/renatawong"
GitHub Events
Total
- Watch event: 1
Last Year
- Watch event: 1