Minimum LU–LC counterexample for graph states

Problem

What is the least number of qubits for which two graph states can be locally unitary equivalent without being locally Clifford equivalent? For a simple graph $G=(V,E)$ with $V=\{1,\ldots,n\}$, define its graph state by

\begin{equation} \lvert G\rangle :=\left(\prod_{\{u,v\}\in E}\mathrm{CZ}_{uv}\right) \lvert+\rangle^{\otimes n}, \qquad \lvert+\rangle:=\frac{\lvert0\rangle+\lvert1\rangle}{\sqrt2}. \tag{1} \end{equation}

For graphs $G$ and $H$ on $n$ vertices, use the state convention in Eq. (1) and write

\begin{equation} \begin{aligned} G\sim_{\mathrm{LU}}H &\iff \lvert H\rangle=e^{i\phi} \left(\bigotimes_{j=1}^{n}U_j\right)\lvert G\rangle &&\text{for some }U_j\in U(2),\ \phi\in\mathbb R,\\ G\sim_{\mathrm{LC}}H &\iff \lvert H\rangle=e^{i\theta} \left(\bigotimes_{j=1}^{n}C_j\right)\lvert G\rangle &&\text{for some }C_j\in\mathcal C_1,\ \theta\in\mathbb R, \end{aligned} \tag{2} \end{equation}

where $\mathcal C_1$ is the single-qubit Clifford group. Since $\mathcal C_1\subset U(2)$, LC equivalence implies LU equivalence. Define the minimum counterexample size by

\begin{equation} n_{\min} :=\min\left\{n:\text{there exist $n$-vertex graphs $G,H$ with $G\sim_{\mathrm{LU}}H$ and $G\not\sim_{\mathrm{LC}}H$}\right\}. \tag{3} \end{equation}

Determine the integer in Eq. (3).

Source

Krüger and Werner record the original conjecture that LU equivalence of graph states always implies LC equivalence [KW05]. After Ji, Chen, Wei, and Ying constructed a 27-qubit counterexample, Claudet isolated and resolved the minimum-size question in Eq. (3) [JCWY10], [Cla26].

Progress

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

Krüger and Werner posed the universal implication $G\sim_{\mathrm{LU}}H\Rightarrow G\sim_{\mathrm{LC}}H$. This formulation did not include a minimum counterexample size [KW05].
Ji, Chen, Wei, and Ying disproved the universal implication by constructing LU-equivalent but non-LC-equivalent graph states on 27 qubits. Their construction proves $n_{\min}\leq27$ but does not by itself exclude smaller counterexamples [JCWY10].
Claudet proved that LU and LC equivalence coincide for every pair of graph states on at most 26 qubits. Combining this lower bound with the 27-qubit construction gives

\begin{equation} n_{\min}=27. \tag{4} \end{equation}

Thus Eq. (4) resolves the minimum-size problem [Cla26].

Comment

Equation (4) concerns the minimum size at which LU and LC equivalence can differ; it does not say that 27 qubits are required for LU–LC equivalence. The original universal conjecture was already resolved negatively by the 27-qubit construction. As of September 2026, the matching lower bound through 26 qubits is contained in a recent arXiv v1 preprint, so the archived solved status records its theorem rather than its peer-review history.

References

[KW05]: O. Krüger and R. F. Werner (eds.), “Some Open Problems in Quantum Information Theory,” arXiv:quant-ph/0504166 (2005), Problem 28, pp. 70–71.DOI arXiv
[JCWY10]: Z. Ji, J. Chen, Z. Wei, and M. Ying, “The LU-LC Conjecture Is False,” Quantum Information and Computation 10, 97–108 (2010).DOI arXiv
[Cla26]: N. Claudet, “The 27-qubit Counterexample to the LU-LC Conjecture Is Minimal,” arXiv:2603.25219v1 (2026).DOI arXiv

Minimum LU–LC counterexample for graph states

Problem

Source

Progress

Comment

References

Cite this problem

BibTeX

Plain text

Problem

Source

Progress

Comment

References

Related problems