Quantum approximate algorithm for NP optimization problems with constraints
Open accessAbstract
The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA or QAA, one needs to find a way to encode problem constraints into the scheme. In this paper, we formalize different constraint types to linear equalities, linear inequalities, and arbitrary form. Based on this, we propose constraint-encoding schemes well-fitting into the QAOA framework for solving NP combinatorial optimization problems. The implemented algorithms demonstrate the effectiveness and efficiency of the proposed scheme by the testing results of varied instances of some well-known NP optimization problems. We argue that our work leads to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to combinatorial problems with various types of constraints.
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?
Ansatz adaptations can occur as a byproduct, as in the Quantum Alternating Operator Ansatz where the primary goal is to find a mixing Hamiltonian that ensures staying in the feasible subspace.
“Besides the mentioned ansatz search, as the driving force behind ansatz adaptation, there is also the possibility of having these adaptations as a byproduct, like it happens, e.g., within the Quantum Alternating Operator Ansatz where the primary goal is to find a mixing Hamiltonian that ensures to stay in the feasible subspace [11, 58, 95, 112, 116, 117, 120, 127].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [117]
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
Quantum principal component analysis
Lloyd, S., Mohseni, M., & Rebentrost, P. (2014) · Nature Physics · doi:10.1038/nphys3029 · Cited by 1,385 · see citing works
Adiabatic quantum state generation and statistical zero knowledge
Aharonov, D., & Ta-Shma, A. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780546 · Cited by 322 · see citing works
Flagged first, then by citations
Research works printed but not linked: 16
- [1][1] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 , 2014. - · arXiv
- [2][2] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, Joshua Lapan, Andrew Lundgren, and Daniel Preda. A quantum adiabatic evolution algorithm applied to random instances of an np-complete problem. Science , 292(5516):472-475, 2001. -
- [3][3] Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics , 90(1):015002, 2018. -
- [4][4] Brian Hall. Lie groups, Lie algebras, and representations: an elementary introduction , volume 222. Springer, 2015. -
- [6][6] Itay Hen and Federico M Spedalieri. Quantum annealing for constrained optimization. Physical Review Applied , 5(3):034007, 2016. -
- [7][7] Itay Hen and Marcelo S Sarandy. Driver hamiltonians for constrained optimization in quantum annealing. Physical Review A , 93(6):062312, 2016. -
- [8][8] Stuart Hadfield, Zhihui Wang, Eleanor G Rieffel, Bryan O'Gorman, Davide Venturelli, and Rupak Biswas. Qantum approximate optimization with hard and soft constraints. In Proceedings of the Second International Workshop on Post Moores Era Supercomputing , pages 15-21. ACM, 2017. -
- [9][9] Stuart Hadfield, Zhihui Wang, Bryan O'Gorman, Eleanor G Rieffel, Davide Venturelli, and Rupak Biswas. From the quantum approximate optimization algorithm to a quantum alternating operator ansatz. arXiv preprint arXiv:1709.03489 , 2017. - · arXiv
- [10][10] Stuart Hadfield. Quantum algorithms for scientific computing and approximate optimization. arXiv preprint arXiv:1805.03265 , 2018. - · arXiv
- [11][11] Samuel Marsh and Jingbo Wang. A quantum walk assisted approximate algorithm for bounded np optimisation problems. Quantum Information Processing , 18(3):61, 2019. -
- [12][12] Juraj Hromkoviˇ c. Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics . Springer Science & Business Media, 2013. -
- [13][13] Andrew Macgregor Childs. Quantum information processing in continuous time . PhD thesis, Massachusetts Institute of Technology, 2004. -
- [16][16] Richard M Karp. Reducibility among combinatorial problems. In Complexity of computer computations , pages 85-103. Springer, 1972. -
- [18][18] Shelby Kimmel, Cedric Yen-Yu Lin, Guang Hao Low, Maris Ozols, and Theodore J Yoder. Hamiltonian simulation with optimal sample complexity. npj Quantum Information , 3(1):13, 2017. -
- [19][19] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin. Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices. arXiv preprint arXiv:1812.01041 , 2018. - · arXiv
- [20][20] AT Rezakhani, W-J Kuo, A Hamma, DA Lidar, and P Zanardi. Quantum adiabatic brachistochrone. Physical review letters , 103(8):080502, 2009.
Cited by
Sorted by citations
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
“Objective Function [10], [78], [86] Ansatz [11, 36, 48, 58, 82, 86, 88, 89, 95–97], [112], [116], [117, 120, 127, 131, 151], [152, 153, 155] Parameter Optimization [51], [75], [76, 99], [141], [143], [146] Measurement [122], [125] Grover-search [52], [118] Other gate-based approaches [15], [16],…”
Background
- Authors
- Ruan, Y., Marsh, S., Xue, X., Li, X., Liu, Z., & Wang, J.
- Affiliations
- Anhui University of Technology (CN)
- The University of Western Australia (AU)
- Southeast University (CN)
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2020
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2002.00943
- OpenAlex
- W3005066064
- Cited by
- 9
- References
- 2
- Citations by year
- 2024: 1 · 2023: 4 · 2022: 1 · 2021: 1 · 2020: 2
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- UWA Profiles and Research Repository (University of Western Australia) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Natural Science Foundation of Anhui Province (61802002, 1708085MF162)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- quantum approximate optimization algorithm, adiabatic quantum computation, combinatorial optimization, constraint encoding, NP optimization problems, linear inequalities, approximate solutions, quantum annealing
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
