Geelen’s simulation conjecture for vertex-minor-closed graph classes

Problem

Does Geelen’s simulation conjecture hold for every nonempty proper class \(\mathcal C\subsetneq\mathcal G_{\mathrm{fin}}\) of finite simple graphs that is closed under isomorphism, local complementation, and vertex deletion? Here \(\mathcal G_{\mathrm{fin}}\) denotes all finite simple graphs, and local complementation toggles the edges between distinct neighbors of one vertex. The resource state of \(G=(V,E)\in\mathcal C\), with \(n:=|V|\), is defined in Eq. (1):

\begin{equation} \begin{aligned} |G\rangle&:=\prod_{\{u,v\}\in E}CZ_{uv}|+\rangle^{\otimes n},\\ |+\rangle&:=\frac{|0\rangle+|1\rangle}{\sqrt2}, \qquad CZ:=\operatorname{diag}(1,1,1,-1). \end{aligned} \tag{1} \end{equation}

Let \(\mathsf{BQP}_{\mathcal C}\) denote the languages decided with error at most \(1/3\) by uniform polynomial-time measurement-based quantum computations whose classical controller generates a graph in \(\mathcal C\) and adaptively specifies single-qubit projective measurements with polynomial-size, efficiently evaluable algebraic descriptions, allowing randomized polynomial-time classical processing. Let \(\mathsf{BPP}\) denote randomized classical polynomial-time decision with error at most \(1/3\). The conjectured equality is Eq. (2):

\begin{equation} \mathsf{BQP}_{\mathcal C}=\mathsf{BPP}. \tag{2} \end{equation}

Source

The Simulation Conjecture is attributed to Geelen (personal communication, 2018) and recorded by McCarty in Section 1.4, p. 18 of her thesis [McC21]. The bounded-error uniform decision interpretation is source-stated; the explicit finite algebraic-description convention in this entry is the supplied formulation of that computational model.

Progress

Theorem 5 (Section IV.A) and the decomposition discussion in Section IV.B show that bounded rank-width gives an established efficiently simulable family: for each fixed nonnegative integer \(r\), define \(\mathcal C_r:=\{G:\operatorname{rwd}(G)\leq r\}\), where \(\operatorname{rwd}(G)\) is the minimum, over subcubic trees with leaves labelled by \(V(G)\), of the maximum binary rank of the adjacency submatrix across an edge-induced bipartition; then

\begin{equation} \mathsf{BQP}_{\mathcal C_r}=\mathsf{BPP}. \tag{3} \end{equation}

The simulation establishing Eq. (3) uses a tree tensor network with bond dimension at most \(2^r\) once a width-\(r\) decomposition is supplied; for fixed \(r\), suitable bounded-width decompositions can also be found efficiently. [VDVB07]
McCarty’s thesis, Section 1.4, p. 18, records the conjecture in this bounded-error computational setting: the general inclusions are

\begin{equation} \mathsf{BPP}\subseteq\mathsf{BQP}_{\mathcal C}\subseteq\mathsf{BQP}, \tag{4} \end{equation}

In Eq. (4), \(\mathsf{BQP}\) is bounded-error quantum polynomial time, and the conjecture asserts that the first inclusion is an equality for every proper vertex-minor-closed class, not merely for bounded-rank-width classes. [McC21]
Let \(\mathcal C_{\mathrm{circ}}\) be the class of intersection graphs of chords of a circle; Harrison and coauthors establish (version 2, Corollary 7.4) efficient randomized sampling of adaptive measurement outcomes and hence

\begin{equation} \mathsf{BQP}_{\mathcal C_{\mathrm{circ}}}=\mathsf{BPP}. \tag{5} \end{equation}

The simulation equality in Eq. (5) was first announced in 2025; the corrected May 2026 version retains the sampling result but withdraws an earlier claim that arbitrary marginal probabilities can be computed in polynomial time, so weak simulation must not be conflated with that stronger task. [HIP+25]
The 2026 structural analysis (Corollary 3 and Appendix A, Lemma 4) gives an alternative simulation route for circle graphs and exhibits circle graphs of polynomially growing rank-width, in particular a constant \(c>0\) and infinitely many \(n\) for which

\begin{equation} \exists G\in\mathcal C_{\mathrm{circ}}: \qquad |V(G)|=n, \qquad \operatorname{rwd}(G)\geq c\sqrt n. \tag{6} \end{equation}

The rank-width bound in Eq. (6) shows that the circle-graph result genuinely extends the bounded-rank-width case; an August 2026 follow-up (Appendix F.1, after Definition F.2) still explicitly identifies the general simulation statement as the McCarty–Geelen conjecture. [HMNC26], [GS26]

Comment

No general proof or counterexample was found in the public literature checked through 9 September 2026; the known simulators cover particular proper classes, not every such class. The question concerns efficient bounded-error decision simulation of finitely specified computations, not exact evaluation of all marginals or an oracle for membership in an arbitrary graph class. The status audit used public primary sources and later-work searches; it is not an exhaustive citation-index audit.

References

[VDVB07]: M. Van den Nest, W. Dür, G. Vidal, and H. J. Briegel, “Classical Simulation versus Universality in Measurement-Based Quantum Computation,” Physical Review A 75, 012337 (2007).DOI arXiv
[McC21]: R. McCarty, “Local Structure for Vertex-Minors,” PhD thesis, University of Waterloo (2021). University repository.link
[HIP+25]: B. Harrison, V. Iyer, O. Parekh, K. Thompson, and A. Zhao, “Fermionic Insights into Measurement-Based Quantum Computation: Circle Graph States Are Not Universal Resources,” arXiv preprint (2025), corrected version 2, 17 May 2026.DOI arXiv
[HMNC26]: F. Hahn, R. McCarty, H. Poulsen Nautrup, and N. Claudet, “The Structure of Circle Graph States,” arXiv preprint (2026), version 2, 28 April 2026.DOI arXiv
[GS26]: K. Goodenough and M. Sales, “Asymptotic Entanglement in Circle Stabilizer States and States Forbidding Arbitrary Vertex-Minors,” arXiv preprint (2026).DOI arXiv

Geelen’s simulation conjecture for vertex-minor-closed graph classes

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems