Foundations of quantum mechanics · Theory (AI-assisted)

A Tensor-Algebraic No-Go Theorem for High-Dimensional Photonic Greenberger–Horne–Zeilinger States Discovered with AlphaProof Nexus

Mario Krenn, Moritz Firsching, George Tsoukalas, Rishikesh Gajjala, Xuemei Gu, Swarat Chaudhuri

arXiv:2611.26300v1 ↗PDF ↗Submitted 19 November 2026

Question
Linear-optical experiments with probabilistic photon-pair sources, conditioned on one photon in every detector, are described by edge-coloured graphs with complex edge weights, in which the amplitude of each output term is a coherent sum over perfect matchings. Qubit GHZ states can be made this way for any even number of photons, and four-photon qutrit GHZ states too. A 2017 conjecture says nothing else is possible. Proofs existed only for restricted graphs (non-negative weights, no bichromatic edges, no multi-edges). Can an unrestricted graph with \(N\) vertices produce an \(N\)-photon GHZ state of dimension \(D\)?
Result
No complex-weighted graph produces an \(N\)-photon, \(D\)-dimensional GHZ state for any even \(N\ge4\) once \(D\ge N\). The proof builds one linear functional of the amplitude array whose coefficients factor vertex by vertex. Fixing the coefficients at one vertex to all ones leaves an \((N-1)\times N\) matrix of effective edge weights, and a short counting lemma picks the other coefficients so that the functional vanishes on every graph's amplitudes but not on the GHZ target. The proof was found as a Lean formal proof by the AlphaProof Nexus agent and then rewritten by hand, together with a reading of the functional as a coincidence that every graph forbids and the GHZ state allows.

The paper in detail

In the graph picture of a photonic experiment, each vertex is a path ending in a detector, and each edge is a possible photon pair whose two ends carry colours (the internal modes, such as orbital angular momentum) and whose complex weight is the pair's amplitude. Keeping only events with exactly one photon per detector selects the perfect matchings of the graph. Each matching gives every vertex a colour, and the amplitude of the output term \(\ket{c_1,\dots,c_N}\) is the sum of the weight products of all matchings that produce that colouring. Summing parallel edges into effective weights \(W^{ab}_{rs}\), the four-vertex amplitude is \(W_{12}W_{34}+W_{13}W_{24}+W_{14}W_{23}\) with the colours as superscripts. The GHZ target asks for amplitude 1 on the \(D\) one-colour terms and 0 on all others, a system of \(D^N\) polynomial equations in \(D^2N(N-1)/2\) unknowns.

To prove that this system has no solution, it suffices to find one linear functional \(\mathcal F\) that takes different values on the graph's amplitude array \(\omega\) and on the target \(\Delta\). The paper takes coefficients that are products of one function \(\lambda_r\) per vertex. Because a perfect matching uses each vertex exactly once, the functional then factorises over the pairs of every matching. Setting \(\lambda_1\equiv1\) at the first vertex makes the factor for the pair containing that vertex a linear form in \(\lambda_r\) alone, given by row \(r\) of an \((N-1)\times N\) matrix \(A\) of colour-summed weights. If all \(N-1\) row forms vanish, every matching contributes zero, whatever the other weights are.

The remaining task is to make all row forms vanish while keeping \(\sum_j\prod_r\lambda_r(j)\), the functional's value on the GHZ target, non-zero. There are \(N-1\) rows but \(N\) colours, so some colour is not the only non-zero entry of any row. Each \(\lambda_r\) is built from that colour and one auxiliary colour so that its row form cancels, and the auxiliary colours are chosen not all equal, so only the chosen colour survives in the target sum. For \(D>N\), deleting all edges with one colour at either end keeps the remaining amplitudes and lowers the dimension, so the case \(D=N\) suffices. The construction uses no division, so the theorem holds over any commutative ring without zero divisors.

The functional has a physical reading. With \(\lambda_1\equiv1\), photon 1 is projected onto the uniform superposition of its modes, and the other \(\lambda_r\) are local projections chosen so that, whichever photon was photon 1's partner, that pairing interferes destructively. The joint coincidence is then impossible for any pair-source experiment, but has non-zero probability in the GHZ state (\(1/16\) for \(N=D=4\) when a whole column of \(A\) vanishes). Open questions are which states such experiments can make at all, and how far photon-triple sources, which do produce high-dimensional GHZ states, can go; the authors propose adding both to the Formal Conjectures repository.

Transferable methods

  1. A separating functional with vertex-factorised coefficients

    An impossibility proof for a polynomial system needs a certificate that no choice of weights can reach the target. A linear functional that annihilates every reachable amplitude array but not the target is such a certificate. Choosing its coefficients as a product over vertices makes it compatible with the perfect-matching structure: each matching splits into independent pair factors, so a single vanishing factor per matching kills the whole sum.

    Let \(\mathcal F(X)=\sum_{\mathbf c}\bigl(\prod_{r=1}^N\lambda_r(c_r)\bigr)X_{\mathbf c}\). For a fixed perfect matching \(P\), each colour variable appears in exactly one pair factor, so the colour sums separate: \[\mathcal F(\omega)=\sum_{P}\prod_{\{r,s\}\in P}B_{rs},\qquad B_{rs}=\sum_{a,b}\lambda_r(a)\lambda_s(b)\,W^{ab}_{rs}.\] For \(N=4\) this is \(B_{12}B_{34}+B_{13}B_{24}+B_{14}B_{23}\). On the target only the \(D\) one-colour terms survive, \(\mathcal F(\Delta)=\sum_j\prod_r\lambda_r(j)\).

    With \(\lambda_1\equiv1\), the factor of the pair containing vertex 1 becomes \(B_{1r}=\sum_jA_{rj}\lambda_r(j)=R_r(\lambda_r)\), where \(A_{rj}=\sum_iW^{ij}_{1r}\) sums the weights between vertices 1 and \(r\) over the colour at vertex 1. Every matching contains exactly one pair \(\{1,r\}\), so \(R_r(\lambda_r)=0\) for all \(r\) forces \(\mathcal F(\omega)=0\) without any information about the other weights. Since a graph realising the GHZ state would satisfy \(\omega=\Delta\) and hence \(\mathcal F(\omega)=\mathcal F(\Delta)\), it is enough to also keep \(\mathcal F(\Delta)\ne0\).

    Editorial step: up to normalisation, \(\mathcal F(X)\) is the amplitude of the outcome in which photon \(r\) is projected onto the vector with components \(\lambda_r(j)\) (conjugated). For \(N=D=4\) with a zero column \(j_\star\) of \(A\), photon 1 is projected onto \(\ket{+_4}=\tfrac12\sum_j\ket j\) and the others onto \(\ket{j_\star}\). The GHZ amplitude is \(\tfrac12\cdot\tfrac12=\tfrac14\), so the coincidence has probability \(1/16\), the value the paper gives, while every graph assigns it amplitude zero. Editorial check: on random sparse complex graphs with \(N=D=4\) and \(N=D=6\), the coefficients from the lemma below give \(|\mathcal F(\omega)|\) at rounding level (\(\le3\times10^{-13}\)) and \(|\mathcal F(\Delta)|\) of order one.

    How to reuse it

    Showing that a parametrised family cannot reach a target by exhibiting one functional that vanishes on the whole family is a general certificate strategy. When the parametrisation is a sum over perfect matchings, hyperedges or other partitions, coefficients that factor over the parts turn the functional into a sum of products and make it easy to force a zero factor. The same idea applies to photon-triple sources (hypergraphs) and to other photonic state-design questions.

  2. The row–column counting lemma

    The functional needs \(N-1\) vectors, one per row of \(A\), each orthogonal to its row, whose entrywise product still has a non-zero sum. The only obstruction is a row with a single non-zero entry, which forces that colour to zero in its vector. With fewer rows than colours, pigeonhole leaves a colour that no row blocks, and two-entry vectors built around that colour do the rest. The same count explains exactly where the theorem stops.

    Call colour \(j\) blocked if some row of \(A\) is non-zero only in column \(j\). Each row blocks at most one colour and there are \(N-1\) rows and \(N\) colours, so some \(j_\star\) is unblocked (if a column is entirely zero, take \(\lambda_r=e_{j_\star}\) for that column and stop). For each row with \(A_{rj_\star}=0\), take \(\lambda_r=e_{j_\star}\); otherwise pick an auxiliary colour \(q_r\ne j_\star\) with \(A_{rq_r}\ne0\) and set \[\lambda_r=A_{rq_r}e_{j_\star}-A_{rj_\star}e_{q_r},\qquad R_r(\lambda_r)=A_{rj_\star}A_{rq_r}-A_{rq_r}A_{rj_\star}=0.\]

    Every \(\lambda_r(j_\star)\) is non-zero. If the auxiliary colours could only all be the same \(q\), every row would be supported on \(\{j_\star,q\}\), and any third colour would give a zero column, which was excluded. So the \(q_r\) can be chosen not all equal, and then for each \(j\ne j_\star\) some \(\lambda_r(j)=0\). Only one term survives: \(\mathcal F(\Delta)=\prod_r\lambda_r(j_\star)\ne0\). In the paper's example, rows \((1,1,2,0)\), \((1,1,0,3)\), \((1,1,4,5)\) with \(j_\star=0\) and auxiliary colours \(2,3,1\) give \(\mathcal F(\Delta)=2\cdot3\cdot1=6\); choosing the same auxiliary colour \(1\) for all rows would give \(1+(-1)^3=0\).

    The count also shows where the method breaks. For \(N=4\), \(D=3\), the graph with \(W^{00}_{12}=W^{00}_{34}=W^{11}_{13}=W^{11}_{24}=W^{22}_{14}=W^{22}_{23}=1\) produces exactly the qutrit GHZ state, and its matrix is \(A=I_3\): every colour is blocked, the row conditions force \(\lambda_2(0)=\lambda_3(1)=\lambda_4(2)=0\), and the target value vanishes along with the graph's. Editorial check: summing the three perfect matchings of this graph reproduces the GHZ array exactly.

    How to reuse it

    Choosing vectors in the kernels of several linear forms while keeping a multilinear diagonal sum non-zero is a recurring step in proofs about tensor rank and polynomial identities. A pigeonhole count of supports (fewer constraints than coordinates) together with two-entry kernel vectors is a cheap construction, and the case where the count is tight usually points to an explicit counterexample.

Source: Background (graphs and perfect matchings, Eqs. (1)–(10)); the proof sections (separating functional, Eqs. (11)–(16); the case \(N=D=4\), Eqs. (17)–(52); general even \(N\), Eqs. (53)–(64); \(D>N\) and \(D<N\), Eqs. (65)–(67)); physical interpretation. Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. This is the first unconditional result on the conjecture for complex weights and every even \(N\), and the first AI-found proof in this line that has been turned into an argument a reader can follow and check in a few pages. Since then, according to the paper, Kitamura proved \(D\le N-2\) for \(N\ge6\) and Rajasekaran proved the full conjecture, both with AI assistance and verified in Lean but not yet understood by any human. The paper's contribution is therefore as much the readable mechanism as the theorem. In physical terms, high-dimensional GHZ states of many photons need heralding, ancilla photons or higher-order sources.

Limitations. The argument covers only \(D\ge N\); it fails at \(D<N\), and the paper shows the failure at \(N=4\), \(D=3\), where a GHZ-producing graph exists. The intermediate range for \(N\ge6\) is settled only by the later, not yet human-digested formal proof. The model is the one-photon-per-detector graph picture without ancilla photons, heralding or photon-triple sources, so the result says nothing about those resources. The proof was discovered by an AI system (AlphaProof Nexus, in the Formal Conjectures project), formally verified in Lean, and then explained by the authors; the Lean source was not inspected for this summary.

Description based on the full arXiv HTML of v1, read 2026-11-21: all sections, including the graph background, the Lean formalisation, the complete proof for \(N=D=4\), the general \((N-1)\times N\) lemma, the extension to \(D>N\), the counterexample at \(D<N\) and the physical interpretation. The Lean proof itself was not inspected. Editorial checks: amplitude arrays computed by explicit perfect-matching sums for three random sparse complex graphs with \(N=D=4\) and one with \(N=D=6\) (46,656 colourings); the lemma's coefficients give \(|\mathcal F(\omega)|\le3\times10^{-13}\) against \(|\mathcal F(\Delta)|\) between 0.69 and 14.5. The worked example of Eqs. (47)–(52) (row contractions zero, \(Q_4=6\)) and the \(N=4\), \(D=3\) graph of Eq. (65), which reproduces the GHZ array exactly, were also checked.