Is bipartite Quantum Max-Cut in BPP?

Unsolved ID op_1576e5f52f7ff3b2 Last edited 8 September 2026

Edit

Field: Quantum Algorithm
Topics: Computational complexity and computability
Hamiltonian complexity
Quantum Max-Cut

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

Reports do not certify correctness or automatically change the problem's status. Progress policy.

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).DOI arXiv
[RT26]: C. Rayudu and J. Takahashi, "Spectral gap of Lee-Yang Hamiltonians," arXiv preprint (July 2026).DOI arXiv
[BGLW26]: S. Bravyi, D. Gosset, Y. Liu, and B. Wong, "Efficient quantum algorithm for Heisenberg spin systems," arXiv preprint (July 2026).DOI arXiv

Is bipartite Quantum Max-Cut in BPP?

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems