2025/03/31 by Davies, James, Jena, Andrew · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2504.00291
Measurement based quantum computing is preformed by adding non-Clifford measurements to a prepared stabilizer states. Entangling gates like CZ are likely to have lower fidelities due to the nature of interacting qubits, so when preparing a stabilizer state, we wish to minimize the number of required entangling states. This naturally introduces the notion of CZ-distance. Every stabilizer state is local-Clifford equivalent to a graph state, so we may focus on graph states \vert G ⟩. As a lower bound for general graphs, there exist n-vertex graphs G such that the CZ-distance of \vert G ⟩ is Ω(n2 / log n). We obtain significantly improved bounds when G is contained within certain proper classes of graphs. For instance, we prove that if G is a n-vertex circle graph with clique number ω, then \vert G ⟩ has CZ-distance at most 4n log ω+ 7n. We prove that if G is an n-vertex graph of rank-width at most k, then \vert G ⟩ has CZ-distance at most (2^2k+1 + 1) n. More generally, this is obtained via a bound of (k+2)n that we prove for graphs of twin-width at most k. We also study how bounded-rank perturbations and low-rank cuts affect the CZ-distance. As a consequence, we prove that Geelen's Weak Structural Conjecture for vertex-minors implies that if G is an n-vertex graph contained in some fixed proper vertex-minor-closed class of graphs, then \vert G ⟩ has CZ-distance at most O(nlog n). Since graph states of locally equivalent graphs are local Clifford equivalent, proper vertex-minor-closed classes of graphs are natural and very general in this setting.