Max-independent set and the quantum alternating operator ansatz
Open accessAbstract
The maximum-independent set (MIS) problem of graph theory using the quantum alternating operator ansatz is studied. We perform simulations on the Rigetti Forest simulator for the square ring, [Formula: see text], and [Formula: see text] graphs and analyze the dependence of the algorithm on the depth of the circuit and initial states. The probability distribution of observation of the feasible states representing maximum-independent sets is observed to be asymmetric for the MIS problem, which is unlike the Max-Cut problem where the probability distribution of feasible states is symmetric. For asymmetric graphs, it is shown that the algorithm clearly favors the independent set with the larger number of elements even for finite circuit depth. We also compare the approximation ratios for the algorithm when we choose different initial states for the square ring graph and show that it is dependent on the choice of the initial state.
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The Maximum Independent Set problem has been tackled with the Quantum Alternating Operator Ansatz.
“The Maximum Independent Set problem has been tackled with the Quantum Alternating Operator Ansatz [119].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [119]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Cites
Reducibility among Combinatorial Problems
Karp, R. M. (1972) · Complexity of Computer Computations · doi:10.1007/978-1-4684-2001-2_9 · Cited by 11,511 · see citing works
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830 · see citing works
A variational eigenvalue solver on a photonic quantum processor
Peruzzo, A., McClean, J., Shadbolt, P., Yung, M.-H., Zhou, X.-Q., Love, P. J., Aspuru-Guzik, A., & O’Brien, J. L. (2014) · Nature Communications · doi:10.1038/ncomms5213 · Cited by 4,552 · see citing works
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653 · see citing works
Quantum optimization using variational algorithms on near-term quantum devices
Moll, N., Barkoutsos, P., Bishop, L. S., Chow, J. M., Cross, A., Egger, D. J., Filipp, S., Fuhrer, A., Gambetta, J. M., Ganzhorn, M., et al. (2018) · Quantum Science and Technology · doi:10.1088/2058-9565/aab822 · Cited by 744 · see citing works
Bazgan, C., Escoffier, B., & Paschos, V. T. (2005) · Theoretical Computer Science · doi:10.1016/j.tcs.2005.03.007 · Cited by 57 · see citing works
Flagged first, then by citations
Research works printed but not linked: 12
- [1]J. Preskill, Quantum 2, 79 (2018)
- [2]E. Farhi, J. Goldstone, and S. Gutmann, (2014), arXiv:1411.4028. · arXiv
- [3]A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O Brien, Nature Communications 5, 4213 (2014).
- [4]N. Moll, P. Barkoutsos, L. S. Bishop, J. M. Chow, A. Cross, D. J. Egger, S. Filipp, A. Fuhrer, J. M. Gambetta, M. Ganzhorn, A. Kandala, A. Mezzacapo, P. Muller, W. Riess, G. Salis, J. Smolin, I. Tavernelli, and K. Temme, Quantum Science and Technology 3, 030503 (2018).
- [5]E. Farhi and A. W. Harrow, (2016), arXiv:1602.07674 · arXiv
- [6]S. Hadfield, Z. Wang, B. O Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, arXiv:1709.03489. · arXiv
- [7]H Pichler, ST Wang, L Zhou, S Choi, MD Lukin arXiv preprint arXiv:1808.10816 · arXiv
- [10]Bazgan, C., Escoffier, B., AND Paschos, V. T. Theoretical Computer Science 339, 2-3 (2005), 272-292
- [11]Papadimitriou, C. H., and Yannakis, M. Journal of Computer and System Sciences 43 (1991), 425-440.
- [12]B. Chandra, M.M. Halldorsson, in Proc. 10th Annual SIAM-ACM Symposium on Discrete Algorithms (SODA), Baltimore, MD, 1999, pp. 169-176.
- [13]E. Farhi, J. Goldstone, and S. Gutmann, arXiv:1411.4028, 2014. · arXiv
- [14]E. Farhi and A. W. Harrow, arXiv:1602.07674, 2016. https://grove-docs.readthedocs.io/en/latest/qaoa.html http://docs.rigetti.com/en/stable/ http://docs.rigetti.com/en/stable/ · arXiv
Cited by
Sorted by citations
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 1,726 · see citing works
Quantum variational optimization: The role of entanglement and problem hardness
Díez-Valle, P., Porras, D., & García-Ripoll, J. J. (2021) · Physical Review A · doi:10.1103/physreva.104.062426 · Cited by 47 · see citing works
Lower bounds on circuit depth of the quantum approximate optimization algorithm
Herrman, R., Ostrowski, J., Humble, T. S., & Siopsis, G. (2021) · Quantum Information Processing · doi:10.1007/s11128-021-03001-7 · Cited by 35 · see citing works
Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study
Gemeinhardt, F., Garmendia, A., Wimmer, M., Weder, B., & Leymann, F. (2024) · ACM Computing Surveys · doi:10.1145/3620668 · Cited by 22 · see citing works
“The Maximum Independent Set problem has been tackled with the Quantum Alternating Operator Ansatz [119].”
Method
- Authors
- Saleem, Z. H.
- Affiliations
- Argonne National Laboratory (US)
- Corresponding author
- Saleem, Zain Hamid
- ORCID
- Saleem, Zain Hamid
- Venue
- International Journal of Quantum Information
- Publisher
- World Scientific Pub Co Pte Ltd
- Published
- 2020-06
- Volume
- 18
- Issue
- 04
- Pages
- 2050011
- ISSN
- 0219-7499 (ISSN-L)
- 1793-6918
- OpenAlex
- W3015675400
- Cited by
- 28
- References
- 6
- Citations by year
- 2025: 6 · 2024: 6 · 2023: 6 · 2022: 4 · 2021: 5 · 2020: 1
- FWCI
- 1.57
- Type
- journal article
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- International Journal of Quantum Information (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) (submittedVersion)
- arXiv (Cornell University)
- Funders
- U.S. Department of Energy, Office of Science (DE-AC02-06CH11357)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
- Keywords
- maximum independent set, Quantum Alternating Operator Ansatz, quantum annealing, circuit depth, sensitivity to initial conditions, approximation ratio
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
