Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated just now
PreprintarXiv licencearXiv

Solving the MAX-k-CUT problem for hypergraphs with quantum computing

  • V. S. Yarmus
  • Kh. P. Gnatenko
Open at sourcePDFDOICite

Abstract

We investigate the MAX-k-CUT problem on hypergraphs by considering their representation as spin systems with Ising interactions. The corresponding cost Hamiltonian for MAX-k-CUT problem on hypergraphs is reduced to an Ising Hamiltonian with pairwise interactions. This reduction simplifies the solution of the MAX-k-CUT problem using quantum computing. As illustrative examples, a 3-uniform tight-star hypergraph and a sunflower hypergraph are considered. The corresponding Hamiltonians are constructed, and quantum protocols for the MAX-k-CUT problems are presented. The MAX-3-CUT and MAX-4-CUT instances are investigated for these hypergraphs by varying the number of Quantum Approximate Optimization Algorithm (QAOA) layers from (p=2) to (p=15) with quantum computing on IBM's Qiskit AerSimulator.

Related

  1. Alignment of the amplitudes of stored states for solving the associative memory problem using quantum annealing
    Vladimir E. Zobov, Ivan S. Pichkovskiy
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  2. Solving a non-abelian hidden subgroup problem on a trapped-ion quantum computer: the power of the measurement basis
    Oliver O'Brien
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  3. Resource and entanglement study of a hybrid qudit-qubit quantum algorithm for solving the integer programming problem
    Kapil Goswami, Rick Mukherjee, Peter Schmelcher
    arXivPreprintCC BY 4.0Full textComputational physicsQuantum physics & quantum informationarXiv
  4. Resource-efficient formulations of the Knapsack problem for quantum computing
    Pim van den Heuvel, Vrinda Mehta, Dennis Willsch +2
    arXivPreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
  5. "I don't have a good metric for what other people think:" Unpacking the double empathy problem in neurodivergent physics problem-solving
    Liam G. McDermott, Frank T. Dachille, George R. Keefe +3
    arXivPreprintCC BY 4.0Full textGeneral physicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{yarmus2026solving,
  title = {{Solving the MAX-$k$-CUT problem for hypergraphs with quantum computing}},
  author = {V. S. Yarmus and Kh. P. Gnatenko},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41678},
  eprint = {2610.41678},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41678},
}
RIS
TY  - UNPB
TI  - Solving the MAX-k-CUT problem for hypergraphs with quantum computing
AU  - V. S. Yarmus
AU  - Kh. P. Gnatenko
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41678
UR  - https://arxiv.org/abs/2610.41678
AB  - We investigate the MAX-k-CUT problem on hypergraphs by considering their representation as spin systems with Ising interactions. The corresponding cost Hamiltonian for MAX-k-CUT problem on hypergraphs is reduced to an Ising Hamiltonian with pairwise interactions. This reduction simplifies the solution of the MAX-k-CUT problem using quantum computing. As illustrative examples, a 3-uniform tight-star hypergraph and a sunflower hypergraph are considered. The corresponding Hamiltonians are constructed, and quantum protocols for the MAX-k-CUT problems are presented. The MAX-3-CUT and MAX-4-CUT instances are investigated for these hypergraphs by varying the number of Quantum Approximate Optimization Algorithm (QAOA) layers from (p=2) to (p=15) with quantum computing on IBM's Qiskit AerSimulator.
ER  -