Graph States, Pivot Minor, and Universality of (X, Z)-Measurements
Mehdi Mhalla and Simon Perdrix
The graph state formalism offers strong connections between quantum information processing and graph theory. Exploring these connections, first we show that any graph is a pivot-minor of a planar graph, and even a pivot minor of a triangular grid. Then, we prove that the application of measurements in the (X, Z) plane (i.e., one-qubit measurement according to the basis {cos(θ)|0 + sin(θ)|1, sin(θ)|0 − cos(θ)|1} for some θ) over graph states represented by triangular grids is a universal measurement-based model of quantum computation. These two results are in fact two sides of the same coin, the proof of which is a combination of graph theoretical and quantum information techniques.