Polynomial-time local-unitary equivalence of graph states
A proof candidate replaces high-order incidence enumeration with a polynomial-size modular computation.
Yuxuan Zhang · Round 21 · Posted 22 September 2026
Full manuscript (PDF, 12 pages) · Manuscript, proof and exact checks (ZIP) · Frozen round-21 proof (text) · QIQC submission
Status: a complete proof candidate, with two internal AI reviews and finite exact checks. Independent expert review and publication priority remain unconfirmed. This post makes the existing round-21 result and its supporting files available on this website. The full proof is unchanged from the version submitted for review.
A 12-page working manuscript now presents the theorem, proofs, two algorithms, complexity analysis, and reproducibility record. It adds targeted diagnostics and makes the published reduction’s hypotheses explicit. The frozen round-21 proof remains available unchanged; the historical AI reviews refer to that frozen submission. The manuscript is a fuller presentation of the same candidate.
The question
A graph specifies a quantum state by preparing one qubit at each vertex and applying a controlled-Z gate along every edge. Two different graphs can describe states related by changing the basis of each qubit separately. The QIQCOP question asks whether this local-unitary equivalence can be decided in deterministic polynomial time for arbitrary graph states.
The vertex labels stay fixed. Given two finite simple graphs on the same labelled set of \(n\) vertices, the test asks whether there are single-qubit unitaries \(U_1,\ldots,U_n\) and a global phase \(\phi\) such that
\[\lvert H\rangle=e^{i\phi}\left(\bigotimes_{v=1}^{n}U_v\right)\lvert G\rangle.\]Claudet and Perdrix established an exact algorithm with running time \(n^{\log_2 n+O(1)}\). Their reduction converts the unitary question into discrete graph operations and linear constraints. The remaining expensive stage enumerates incidence conditions indexed by subsets of vertices. The proposed result replaces that stage while retaining their other reductions.
The candidate result
The frozen proof claims a deterministic algorithm with polynomial bit complexity for the full labelled decision problem. It includes disconnected graphs and needs no degree or restricted-graph-class promise.
The main idea is to represent all the high-order incidence constraints by a small generating matrix. For a prescribed independent support \(X\) of size \(m\), the calculation takes place over
\[R=\mathbb Z/2^r\mathbb Z.\]For a vertex \(v\) outside \(X\), let \(a_v\) record its neighbors in \(X\). Rather than list every relevant subset, the construction starts with pair and triple rows and repeatedly applies the simple maps
\[T_v(z)=2a_v\odot z,\]where the product is coordinatewise. Part I proves that the resulting row module is exactly the module generated by all the original constraints. Representing it by an integer lattice gives a termination bound: there are at most \(rm\) strict enlargements, and every retained basis has polynomial size and bit length.
Part II turns the compressed matrix into the complete binary space of possible edge toggles. This requires the kernel over \(R\), not merely a kernel over the two-element field. The proof handles modular carries and kernels that are not free modules, and keeps a multiplicity vector witnessing each generated toggle.
Part III connects these two algebraic statements to the full Claudet–Perdrix reduction. Taking \(r=O(\log n)\) leaves only polynomial computations. The integration checks labelled connected components, the hypotheses of the constrained local-Clifford reduction, and the special branch where the toggle space is zero. The auxiliary graphs have \(O(n^3)\) vertices, so they also remain polynomial in size.
What changed between rounds 20 and 21
Round 20 supplied the incidence-compression argument for a prescribed support. That intermediate statement did not by itself decide unrestricted local-unitary equivalence. Round 21 added the complete kernel-to-image construction and the integration with the published graph reductions. The downloadable proof retains these three parts so the additional obligations are visible.
The claimed advance is therefore an improvement in worst-case decision complexity. No optimized polynomial exponent or complete executable implementation of the entire graph-state algorithm is supplied. Practical performance remains a separate task.
Verification and open review
Two separate internal AI reviews examined the same frozen submission and reported no error. The existing diagnostic scripts were also rerun in isolated processes without network access on 22 September 2026. All 45 weighted-module closure comparisons and 36 modular-kernel and binary-image comparisons passed. The latter compare against exhaustive multiplicity enumeration within each finite test system.
Preparing the manuscript exposed a coverage gap: all 45 earlier closure systems stabilize at their initial seed lattice. The additional script checks 24 Boolean-pattern closure systems, including 12 that require strict enlargement. In every one of those 12 cases, omitting the closure iteration gives the wrong module. It also checks all 256 two-by-two matrices over the integers modulo 4, all 384 selected binary incidence systems against 42,752 multiplicity vectors, and five explicit boundary cases. All checks pass. These counts describe algebraic test systems, not independently solved graph-equivalence instances.
Those checks test finite algebraic assertions. They do not certify the asymptotic theorem or the complete graph-reduction pipeline. The most important review questions are whether the module closure captures every incidence condition and whether its output satisfies every interface required by the credited reductions.
The QIQC submission, issue #97, contains the same proof and scripts and is pending maintainer review. This page does not record external acceptance or a new result beyond round 21. The construction, checks, reviews, and exposition involved substantial AI assistance; no independent human mathematical verification is asserted.
Sources and files
The principal dependency is N. Claudet and S. Perdrix, Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time, ICALP 2025. Published paper · Long version used for lemma numbering. The frozen proof explicitly credits the standard-form, level, and constrained-LC results it uses.
The manuscript uses version 3 for its source numbering and records each required interface. The corresponding dependencies were compared with version 2. Scientific Agent Skills supplied writing and evidence-tracking guidance and is cited in the manuscript; it did not verify the mathematics.
The expanded archive includes the PDF and LaTeX source, unmodified frozen proof, original and additional diagnostic scripts, recorded outputs, a compact historical review record, source metadata, a claim-to-evidence map, reproduction instructions, and file hashes. Cited third-party papers are linked rather than redistributed.