Modeling Linear Inequality Constraints in Quadratic Binary Optimization for Variational Quantum Eigensolver
Open accessAbstract
This paper introduces the use of tailored variational forms for variational quantum eigensolver that have properties of representing certain constraints on the search domain of a linear constrained quadratic binary optimization problem solution. Four constraints that usually appear in several optimization problems are modeled. The main advantage of the proposed methodology is that the number of parameters on the variational form remain constant and depend on the number of variables that appear on the constraints. Moreover, this variational form always produces feasible solutions for the represented constraints differing from penalization techniques commonly used to translate constrained problems into unconstrained one. The methodology is implemented in a real quantum computer for two known optimization problems: the Facility Location Problem and the Set Packing Problem. The results obtained for this two problems with VQE using 2-Local variational form and a general QAOA implementation are compared, and indicate that less quantum gates and parameters were used, leading to a faster convergence.
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 [112]
The Conclusion (p. 9) says the paper’s tailored variational forms explore only feasible solutions, supporting the general idea of adapting an ansatz to stay within a feasible search space. But the paper does not describe the Quantum Alternating Operator Ansatz or a mixing Hamiltonian as the means of doing so; its Applications section (p. 6) instead treats QAOA as a comparison method that uses constraint penalties. (LLM, conf=0.84)
Experimental — accuracy not yet measuredVariational forms for VQE have been proposed to ensure that the search is limited to domains of feasible solutions.
“Similarly, and in analogy to the Quantum Alternating Operator Ansatz for QAOA, variational forms for VQE have been proposed to ensure that the search is limited to domains of feasible solutions [112].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [112]
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
Adam: A Method for Stochastic Optimization
Kingma, D. P., & Ba, J. (2014) · arXiv · doi:10.48550/arxiv.1412.6980 · Cited by 98,946 · see citing works
A Simplex Method for Function Minimization
Nelder, J. A., & Mead, R. (1965) · The Computer Journal · doi:10.1093/comjnl/7.4.308 · Cited by 28,905 · 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 · cited 2× · see citing works
“Some of these heuristics are the Variational Quantum Eigensolver (VQE) [2, 3] and its special form called Quantum Approximation Algorithm (QAOA)[4].”
BackgroundMethodHardware-efficient variational quantum eigensolver for small molecules and quantum magnets
Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J. M., & Gambetta, J. M. (2017) · Nature · doi:10.1038/nature23879 · Cited by 2,982 · see citing works
Ising formulations of many NP problems
Lucas, A. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00005 · Cited by 2,512 · see citing works
Barren plateaus in quantum neural network training landscapes
McClean, J. R., Boixo, S., Smelyanskiy, V. N., Babbush, R., & Neven, H. (2018) · Nature Communications · doi:10.1038/s41467-018-07090-4 · Cited by 2,329 · see citing works
Multivariate stochastic approximation using a simultaneous perturbation gradient approximation
Spall, J. C. (1992) · IEEE Transactions on Automatic Control · doi:10.1109/9.119632 · Cited by 2,283 · see citing works
The theory of variational hybrid quantum-classical algorithms
McClean, J. R., Romero, J., Babbush, R., & Aspuru-Guzik, A. (2016) · New Journal of Physics · doi:10.1088/1367-2630/18/2/023023 · Cited by 2,227 · see citing works
Powell, M. J. D. (1994) · Advances in Optimization and Numerical Analysis · doi:10.1007/978-94-015-8330-5_4 · Cited by 1,369 · see citing works
An adaptive variational algorithm for exact molecular simulations on a quantum computer
Grimsley, H. R., Economou, S. E., Barnes, E., & Mayhall, N. J. (2019) · Nature Communications · doi:10.1038/s41467-019-10988-2 · Cited by 1,033 · see citing works
Sim, S., Johnson, P. D., & Aspuru‐Guzik, A. (2019) · Advanced Quantum Technologies · doi:10.1002/qute.201900070 · Cited by 972 · 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
Multiple criteria facility location problems: A survey
Farahani, R. Z., SteadieSeifi, M., & Asgari, N. (2009) · Applied Mathematical Modelling · doi:10.1016/j.apm.2009.10.005 · Cited by 663 · see citing works
Generalized Unitary Coupled Cluster Wave functions for Quantum Computation
Lee, J., Huggins, W. J., Head-Gordon, M., & Whaley, K. B. (2019) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.8b01004 · Cited by 432 · see citing works
Barkoutsos, P. K., Gonthier, J. F., Sokolov, I., Moll, N., Salis, G., Fuhrer, A., Ganzhorn, M., Egger, D. J., Troyer, M., Mezzacapo, A., et al. (2018) · Physical Review A · doi:10.1103/physreva.98.022322 · Cited by 363 · see citing works
Fischer, C. F. (1987) · Computer Physics Communications · doi:10.1016/0010-4655(87)90053-1 · Cited by 316 · see citing works
Minimal universal two-qubit controlled-NOT-based circuits
Shende, V. V., Markov, I. L., & Bullock, S. S. (2004) · Physical Review A · doi:10.1103/physreva.69.062321 · Cited by 288 · see citing works
A Tutorial on Formulating and Using QUBO ModelsPreprint
Glover, F., Kochenberger, G. A., & Du, Y. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.11538 · Cited by 273 · see citing works
Sequential minimal optimization for quantum-classical hybrid algorithms
Nakanishi, K. M., Fujii, K., & Todo, S. (2020) · Physical Review Research · doi:10.1103/physrevresearch.2.043158 · Cited by 221 · see citing works
Classical signature of quantum annealing
Smolin, J. A., & Smith, G. (2014) · Frontiers in Physics · doi:10.3389/fphy.2014.00052 · Cited by 79 · see citing works
Using models to improve optimizers for variational quantum algorithms
Sung, K. J., Yao, J., Harrigan, M. P., Rubin, N. C., Jiang, Z., Lin, L., Babbush, R., & McClean, J. R. (2020) · Quantum Science and Technology · doi:10.1088/2058-9565/abb6d9 · Cited by 78 · see citing works
Solving Quantum Ground-State Problems with Nuclear Magnetic Resonance
Li, Z., Yung, M.-H., Chen, H., Lu, D., Whitfield, J. D., Peng, X., Aspuru-Guzik, A., & Du, J. (2011) · Scientific Reports · doi:10.1038/srep00088 · Cited by 63 · cited 1× · see citing works
“Some of these heuristics are the Variational Quantum Eigensolver (VQE) [2, 3] and its special form called Quantum Approximation Algorithm (QAOA)[4].”
MethodAn Efficient Quantum Circuits Optimizing Scheme Compared with QISKit (Short Paper)
Zhang, X., Xiang, H., & Xiang, T. (2019) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-030-12981-1_32 · Cited by 14 · see citing works
Problem-specific Entangler Circuits of the VQE Algorithm for Optimization ProblemsPreprint
Matsuo, A. (2020) · arXiv (Cornell University) · Cited by 2 · see citing works
Flagged first, then by citations
1 of the 25 references couldn’t be matched to a known paper.
Research works printed but not linked: 4
- [1][1] Marcos Arenales, Vinícius Armentano, Reinaldo Morabito, and Horácio Yanasse. Pesquisa operacional . Elsevier Brasil, 2007. ISBN 978-85-352-5193-7. -
- [3][3] Yu-Hong Dai and Klaus Schittkowski. A sequential quadratic programming algorithm with non-monotone line search. Pacific Journal of Optimization , 4:335-351, 05 2008. -
- [6][6] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm, 2014. Preprint at https://arxiv.org/abs/1411.4028. - · arXiv
- [21][21] Duc Manh Nguyen, Hoai An Le Thi, and Tao Pham Dinh. Solving the multidimensional assignment problem by a crossentropy method. J. Comb. Optim. , 27(4): 808-823, May 2014. ISSN 1382-6905. DOI: 10.1007/s10878-012-9554-z. - · DOI
Cited by
Sorted by citations
Layer VQE: A Variational Approach for Combinatorial Optimization on Noisy Quantum Computers
Liu, X., Angone, A., Shaydulin, R., Safro, I., Alexeev, Y., & Cincio, L. (2022) · IEEE Transactions on Quantum Engineering · doi:10.1109/tqe.2021.3140190 · Cited by 78 · 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
Díez-Valle, P., Luis-Hita, J., Hernández-Santana, S., Martínez-García, F., Díaz-Fernández, Á., Andrés, E., García‐Ripoll, J. J., Sánchez-Martínez, E., & Porras, D. (2023) · Quantum Science and Technology · doi:10.1088/2058-9565/ace474 · Cited by 15 · see citing works
Matsuo, A., Suzuki, Y., Hamamura, I., & Yamashita, S. (2023) · IEICE Transactions on Information and Systems · doi:10.1587/transinf.2023edp7071 · Cited by 14 · see citing works
Inductive Construction of Variational Quantum Circuit for Constrained Combinatorial Optimization
Nakada, H., Tanahashi, K., & Tanaka, S. (2025) · IEEE Access · doi:10.1109/access.2025.3563960 · Cited by 4 · see citing works
A Quantum Approach for Stochastic Constrained Binary Optimization
Gupta, S., & Kekatos, V. (2023) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp49357.2023.10097179 · Cited by 4 · see citing works
- Authors
- Quinones, M. P., & Junqueira, C.
- ORCID
- Junqueira, Catarina
- Venue
- arXiv
- Publisher
- arXiv
- Published
- 2020
- ISSN
- 2331-8422 (ISSN-L)
- arXiv
- 2007.13245
- OpenAlex
- W3110215513
- Cited by
- 6
- References
- 25
- Citations by year
- 2025: 1 · 2023: 4 · 2022: 1
- Type
- posted content
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Metaheuristic Optimization Algorithms Research
- Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
- Keywords
- variational quantum eigensolver, linear inequality constraints, variational formulation, constraint modeling, feasible solutions, penalty method, facility location, set packing problem, quantum approximate optimization algorithm, quantum optimization
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
