Quasi-linear graph-state resources for Pauli pairability
- Field
- Topics
Problem
Does there exist an absolute constant \(a\geq0\) such that \(N_{\mathrm P}(k)=O(k[\log_2(k+1)]^a)\) as the integer \(k\geq2\) tends to infinity? Here \(N_{\mathrm P}(k)\) is the smallest number \(n\geq2k\) of parties holding one qubit each of a graph state as defined in Eq. (1):
Every requested set of \(k\) disjoint pairs of labelled parties \((a_1,b_1),\ldots,(a_k,b_k)\) must be able to obtain \(\bigotimes_{j=1}^k|\Phi^+\rangle_{a_jb_j}\) deterministically, where \(|\Phi^+\rangle:=(|00\rangle+|11\rangle)/\sqrt2\). The allowed operations are single-qubit Clifford unitaries (unitaries normalizing the Pauli group), destructive single-qubit Pauli measurements on discarded parties, and classical communication.
Equivalently, define \(N_{\mathrm P}(k)\) by Eq. (2), with \(G\) ranging over finite simple graphs:
A perfect matching consists of \(k\) disjoint edges covering \(S\). The relation \(M\leq_{\mathrm{vm}}G\) means reachability, with surviving labels fixed, by vertex deletion and local complementation, which toggles edges between distinct neighbors of a vertex.
Source
The second open question in Section 5, p. 36:15 of Cautrès et al. asks whether pairable resource states can have quasi-linear size [CCM+24]. This entry specializes that question to graph states with single-qubit Clifford operations and destructive Pauli measurements. Propositions 4 and 5 of the same paper justify the vertex-minor formulation in Eq. (2); no equivalence with unrestricted local operations and classical communication is asserted.
Progress
Theorem 13 and Corollary 15 of Bravyi et al. show that even unrestricted local operations and classical communication impose a sublinear pairability bound when each of the \(n\) parties initially holds one qubit:
\begin{equation} k=O\!\left(\frac{n\log\log n}{\log n}\right), \qquad N_{\mathrm P}(k)=\Omega\!\left(\frac{k\log k}{\log\log k}\right). \tag{3} \end{equation}The bound in Eq. (3) concerns one qubit per party. Constructions allowing several qubits at each party do not settle the one-qubit-per-party problem. [BSSW24]
An elementary counting consequence of the Pauli-measurement normal form gives a stronger bound for the restricted model here: on a fixed set of \(2k\) terminals, there are \((2k)!/(2^k k!)\) labelled perfect matchings, and distinct matchings are not local-Clifford equivalent; the \(n-2k\) discarded qubits offer only \(3^{n-2k}\) choices of Pauli bases, with measurement outcomes affecting only local Pauli corrections, so
\begin{equation} \frac{(2k)!}{2^k k!}\leq3^{n-2k}, \qquad N_{\mathrm P}(k)\geq 2k+\left\lceil\log_3\frac{(2k)!}{2^k k!}\right\rceil =\Omega(k\log k). \tag{4} \end{equation}The bound in Eq. (4) is the direct counting deduction just given, using the normal form underlying the cited paper’s vertex-minor-universality bound (Proposition 5 and its proof), rather than a claim that the paper states this particular formula. [CMP23]
Every \(2k\)-vertex-minor-universal graph, meaning one that can produce every labelled graph on every prescribed \(2k\)-vertex subset, has the matching property defining \(N_{\mathrm P}(k)\); the 2024 quadratic existence theorem (Theorem 8) therefore gives, for each \(\varepsilon>0\) and all sufficiently large \(k\),
\begin{equation} N_{\mathrm P}(k)\leq(8+\varepsilon)k^2. \tag{5} \end{equation}Beyond the upper bound in Eq. (5), the same paper explicitly asks whether pairable resources can instead have quasi-linear size. [CCM+24]
Substituting \(2k\) for the universality parameter in the 2026 random-graph theorem (Theorem 1.1) yields the improved quadratic upper bound
\begin{equation} \limsup_{k\to\infty}\frac{N_{\mathrm P}(k)}{k^2} \leq\frac{2}{\log_2(4/3)}. \tag{6} \end{equation}Equation (6) is a consequence of the stronger universality property, not a proof of quasi-linear pairability. [AFF+26]
Comment
No quasi-linear construction or existence proof for \(N_{\mathrm P}(k)\) was found in the public literature checked through 9 September 2026; the displayed bounds leave a gap between order \(k\log k\) and order \(k^2\). This entry deliberately asks the Clifford-and-Pauli graph-state version, not an asserted equivalent formulation for unrestricted local operations and classical communication. Its finite feasibility problem is decidable by exhaustive exploration of finitely many labelled graphs and their vertex-minors. The status audit used public primary sources and later-work searches; it is not an exhaustive citation-index audit. The related deterministic vertex-minor-universality question requires all graphs on prescribed terminals and a polynomial-time construction; the present question asks only for perfect matchings and allows an existence proof.