Efficient Encoding of the Weighted MAX $$k$$-CUT on a Quantum Computer Using QAOA
Open accessAbstract
The weighted MAX$$k$$k-CUT problem consists of finding a k-partition of a given weighted undirected graph G(V, E), such that the sum of the weights of the crossing edges is maximized. The problem is of particular interest as it has a multitude of practical applications. We present a formulation of the weighted MAX$$k$$k-CUT suitable for running the quantum approximate optimization algorithm (QAOA) on noisy intermediate scale quantum (NISQ) devices to get approximate solutions. The new formulation uses a binary encoding that requires only$$|V|\log _2k$$|V|log2kqubits. The contributions of this paper are as follows: (i) a novel decomposition of the phase-separation operator based on the binary encoding into basis gates is provided for the MAX$$k$$k-CUT problem for$$k>2$$k>2. (ii) Numerical simulations on a suite of test cases comparing different encodings are performed. (iii) An analysis of the resources (number of qubits, CX gates) of the different encodings is presented. (iv) Formulations and simulations are extended to the case of weighted graphs. For small k and with further improvements when k is not a power of two, our algorithm is a possible candidate to show quantum advantage on NISQ devices.
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?
Several other approaches have been identified where ansatz adaptations happen as a secondary effect.
“Several other approaches have been identified where the ansatz adaptations happen as a secondary effect, e.g., References [36, 48, 82, 131, 153].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [48]
After introducing a binary encoding as an alternative to one-hot encoding, a comparative empirical resource analysis is provided by Fuchs et al.
“After introducing a binary encoding as an alternative to one-hot encoding, a comparative empirical resource analysis is provided by Fuchs et al. [48].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [48]
The encoding of constraints in the cost Hamiltonian rather than restricting the subspace via the mixing Hamiltonian has been considered.
“Continuing with the encoding of discrete problems, the encoding of constraints in the cost Hamiltonian rather than restricting the subspace via the mixing Hamiltonian has also been considered [48].”
From Quantum Combinatorial Optimization in the NISQ Era: A Systematic Mapping Study (2024) · cites this paper as [48]
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 supremacy using a programmable superconducting processor
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandao, F. G. S. L., Buell, D. A., et al. (2019) · Nature · doi:10.1038/s41586-019-1666-5 · Cited by 7,720 · 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
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · see citing works
Wu, F. Y. (1982) · Reviews of Modern Physics · doi:10.1103/revmodphys.54.235 · Cited by 3,570 · 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
A Quantum Approximate Optimization Algorithm
Farhi, E., Goldstone, J., & Gutmann, S. (2014) · arXiv · doi:10.48550/arxiv.1411.4028 · Cited by 1,789 · see citing works
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913 · see citing works
From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
Hadfield, S., Wang, Z., O’Gorman, B., Rieffel, E. G., Venturelli, D., & Biswas, R. (2019) · Algorithms · doi:10.3390/a12020034 · Cited by 772 · 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
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
Khot, S., Kindler, G., Mossel, E., & O’Donnell, R. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447372 · Cited by 592 · see citing works
Improved approximation algorithms for MAXk-CUT and MAX BISECTION
FRIEZE, A. M., & Jerrum, M. (1997) · Algorithmica · doi:10.1007/bf02523688 · Cited by 405 · see citing works
Models and solution techniques for frequency assignment problems
Aardal, K., van Hoesel, S. P. M., Koster, A. M. C. A., et al. (2007) · Annals of Operations Research · doi:10.1007/s10479-007-0178-0 · Cited by 341 · see citing works
QAOA for Max-Cut requires hundreds of qubits for quantum speed-up
Guerreschi, G. G., & Matsuura, A. Y. (2019) · Scientific Reports · doi:10.1038/s41598-019-43176-9 · Cited by 337 · see citing works
Obstacles to Variational Quantum Optimization from Symmetry Protection
Bravyi, S., Kliesch, A., Koenig, R., & Tang, E. (2020) · Physical Review Letters · doi:10.1103/physrevlett.125.260505 · Cited by 278 · see citing works
Warm-starting quantum optimization
Egger, D. J., Mareček, J., & Woerner, S. (2021) · Quantum · doi:10.22331/q-2021-06-17-479 · Cited by 269 · see citing works
Zhu, L., Tang, H. L., Barron, G. S., Calderon-Vargas, F. A., Mayhall, N. J., Barnes, E., & Economou, S. E. (2022) · Physical Review Research · doi:10.1103/physrevresearch.4.033029 · Cited by 245 · see citing works
Wang, Z., Rubin, N. C., Dominy, J. M., & Rieffel, E. G. (2020) · Physical Review A · doi:10.1103/physreva.101.012320 · Cited by 190 · see citing works
Complexity: Knots, Colourings and Countings
Welsh, D. J. A. (1993) · Cambridge University Press eBooks · doi:10.1017/cbo9780511752506 · Cited by 186 · see citing works
Performance of the Quantum Approximate Optimization Algorithm on the Maximum Cut Problem
Crooks, G. E. (2018) · arXiv · doi:10.48550/arxiv.1811.08419 · Cited by 158 · see citing works
Efficient Quantum Algorithms for GHZ and W States, and Implementation on the IBM Quantum Computer
Cruz, D., Fournier, R., Gremion, F., Jeannerot, A., Komagata, K. N., Tošić, T. N., Thiesbrummel, J., Chan, C. L., Macris, N., Dupertuis, M. ‐., et al. (2019) · Advanced Quantum Technologies · doi:10.1002/qute.201900015 · Cited by 128 · see citing works
Optimization of quantum circuit mapping using gate transformation and commutation
Itoko, T., Raymond, R., Imamichi, T., & Matsuo, A. (2019) · Integration · doi:10.1016/j.vlsi.2019.10.004 · Cited by 115 · see citing works
Unique Games with Entangled Provers Are Easy
Kempe, J., Regev, O., & Toner, B. (2010) · SIAM Journal on Computing · doi:10.1137/090772885 · Cited by 74 · see citing works
On Approximate Graph Colouring and MAX-k-CUT Algorithms Based on the θ-Function
de Klerk, E., Ṗasechnik, D. V., & Warners, J. P. (2004) · Journal of Combinatorial Optimization · doi:10.1023/b:joco.0000038911.67280.3f · Cited by 71 · see citing works
ANALYTIC ONE-BIT AND CNOT GATE CONSTRUCTIONS OF GENERAL n-QUBIT CONTROLLED GATES
Liu, Y., LONG, G. L., & Sun, Y. (2008) · International Journal of Quantum Information · doi:10.1142/s0219749908003621 · Cited by 70 · see citing works
The capacitated max k-cut problem
Gaur, D. R., Krishnamurti, R., & Kohli, R. (2007) · Mathematical Programming · doi:10.1007/s10107-007-0139-z · Cited by 29 · see citing works
The Unique Games Conjecture with Entangled Provers is False
Kempe, J., Regev, O., & Toner, B. (2008) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · doi:10.4230/dagsemproc.07411.6 · Cited by 5 · see citing works
Flagged first, then by citations
Research works printed but not linked: 3
- Egger DJ, Marecek J, Woerner S. Warm-starting quantum optimi- zation. arXiv preprint. 2020; arXiv:2009.10095. · arXiv
- Kann V, Khanna S, Lagergren J, Panconesi A. On the hardness of approximating max k-cut and its dual. In: ISTCS, Citeseer; 1996. pp. 61-67.
- Kempe J, Regev O, Toner B. Unique games with entangled prov- ers are easy. SIAM J Comput. 2010;39(7):3207-29.https ://doi. org/10.1137/09077 2885. · DOI
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
“Continuing with the encoding of discrete problems, the encoding of constraints in the cost Hamiltonian rather than restricting the subspace via the mixing Hamiltonian has also been considered [48].”
BackgroundMethodInfluential
- Authors
- Fuchs, F. G., Kolden, H. Ø., Aase, N. H., & Sartor, G.
- Affiliations
- SINTEF (NO)
- Norwegian University of Science and Technology (NO)
- Corresponding author
- Fuchs, Franz G.
- Venue
- SN Computer Science
- Published
- 2021-02-13
- Volume
- 2
- Issue
- 2
- ISSN
- 2661-8907 (ISSN-L)
- 2662-995X
- OpenAlex
- W3082098561
- Cited by
- 56
- References
- 26
- Citations by year
- 2026: 3 · 2025: 9 · 2024: 12 · 2023: 11 · 2022: 15 · 2021: 6
- FWCI
- 3.89
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Locations
- SN Computer Science (publishedVersion, cc-by)
- arXiv (Cornell University) (submittedVersion)
- NORA - Norwegian Open Research Archives (submittedVersion, cc-by)
- arXiv (Cornell University)
- Funders
- SINTEF AS
- 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
- quantum approximate optimization algorithm, binary encoding, NISQ devices, graph partitioning, edge crossings, quantum advantage, combinatorial 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
