Quantum Information and Quantum Computation
Open Problem Zoo
Random Unsolved Solved

Is bipartite Quantum Max-Cut in BPP?

Unsolved ID op_1576e5f52f7ff3b2 Last edited 8 September 2026
Edit
Field
Topics

Problem

Is the following bipartite Quantum Max-Cut promise problem in \(\mathrm{BPP}\)? Given a bipartite graph \(G=(V,E)\) with \(|V|=n\), polynomially bounded nonnegative rational weights \(w_{ij}\), and rational thresholds \(a<b\) with \(b-a\geq1/\operatorname{poly}(n)\), define

\begin{equation} H_G:=\sum_{\{i,j\}\in E}w_{ij}(X_iX_j+Y_iY_j+Z_iZ_j), \qquad E_0:=\lambda_{\min}(H_G). \tag{1} \end{equation}

Here \(X_i,Y_i,Z_i\) are Pauli operators on qubit \(i\). For the energy in Eq. (1), distinguish \(E_0\leq a\) from \(E_0\geq b\), promised one holds, using a randomized classical algorithm polynomial in the input length and correct with probability at least \(2/3\).

Source

The remaining classical part of Open question 3.4 in Gharibian’s The 7 faces of quantum NP, Section 3, arXiv page 7 [Gha24]. The original question asks for the complexity of bipartite QMC; the present formulation focuses on \(\mathrm{BPP}\) membership following the 2026 \(\mathrm{BQP}\) upper bound [RT26].

Progress

  • Earlier upper bound: conjugating one bipartition by Pauli \(Y\) makes \(H_G\) stoquastic, placing bipartite QMC in \(\mathrm{StoqMA}\) (summarized in Section 3) [Gha24].

  • July 2026: Rayudu–Takahashi prove a Lee-Yang spectral gap at least \(h/4\) under field strength \(h>0\), enabling adiabatic ground-energy estimation to inverse-polynomial additive error and establishing \(\mathrm{BQP}\) membership (Theorem 11; Section 1.1) [RT26].

  • Independently, Bravyi–Gosset–Liu–Wong give a \(\operatorname{poly}(n,J,1/\epsilon)\)-time quantum algorithm for additive-\(\epsilon\) ground-energy estimation on weighted bipartite graphs, where \(J=\max_{\{i,j\}\in E}w_{ij}\) (Corollary 2) [BGLW26].

Comment

Membership in \(\mathrm{BPP}\) remains open: the quantum upper bound leaves classical complexity unresolved [RT26]. Here \(\mathrm{BPP}\) and \(\mathrm{BQP}\) denote their promise-problem versions. The target is inverse-polynomial additive precision.

References

[Gha24]
S. Gharibian, "Guest Column: The 7 faces of quantum NP," ACM SIGACT News 54(4), 54–91 (2024).(2023 preprint).DOIarXiv
[RT26]
C. Rayudu and J. Takahashi, "Spectral gap of Lee-Yang Hamiltonians," arXiv preprint (July 2026).DOIarXiv
[BGLW26]
S. Bravyi, D. Gosset, Y. Liu, and B. Wong, "Efficient quantum algorithm for Heisenberg spin systems," arXiv preprint (July 2026).DOIarXiv

Page edit log

  • Record created
  • Last edited
  • Revisions1

View the full history on GitHub

Your contribution is welcome!

Found progress, a correction, or a resolution? Edit this record on GitHub and open a pull request, or report an update with the primary sources. The proposal page explains the available submission route; see the contribution guide for details.

Cite this page

“Is bipartite Quantum Max-Cut in BPP?,” Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo), ID op_1576e5f52f7ff3b2, accessed 2026-09-08.

Use the Cite button above for BibTeX and the permanent link.

Cite this problem

Please also cite the primary sources listed under References. Cite this page for the statement, status, and stable identifier.

BibTeX

@incollection{qiqcop_op_1576e5f52f7ff3b2,
  title = {Is bipartite Quantum Max-Cut in BPP?},
  booktitle = {Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo)},
  year = {2026},
  howpublished = {\url{https://qiqc-op.com/problem/op_1576e5f52f7ff3b2/}},
  note = {Stable ID op_1576e5f52f7ff3b2; status: Unsolved; accessed 2026-09-08}
}

Plain text

“Is bipartite Quantum Max-Cut in BPP?,” Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo), https://qiqc-op.com/problem/op_1576e5f52f7ff3b2/, ID op_1576e5f52f7ff3b2, accessed 2026-09-08.

Share this problem

Permanent link

Identifiers

op_1576e5f52f7ff3b2
01M20E31B526DAX81WYGMDD01T