Graph States, Pivot Minor, and Universality of (X,Z)-measurements
arXiv:1202.6551
Abstract
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 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.
References in corpus (9)
- High-speed linear optics quantum computing using active feed-forward
- Universal resources for measurement-based quantum computation
- Generalized Flow and Determinism in Measurement-based Quantum Computation
- Both Toffoli and Controlled-NOT need little help to do universal quantum computation
- Finding Optimal Flows Efficiently
- Information Flow in Secret Sharing Protocols
- New Protocols and Lower Bound for Quantum Secret Sharing with Graph States
- Towards Minimal Resources of Measurement-based Quantum Computation
- Optimal accessing and non-accessing structures for graph protocols
Cited by in corpus (13)
- Self-testing of quantum systems: a review
- Verification of quantum computation: An overview of existing approaches
- Interactive proofs for BQP via self-tested graph states
- There and back again: A circuit extraction tale
- Pivoting makes the ZX-calculus complete for real stabilizers
- Contextuality in multipartite pseudo-telepathy graph games
- Y-Calculus: A Language for Real Matrices Derived from the ZX-Calculus
- Quantum Iterative Deepening with an application to the Halting problem
- Reversibility in the Extended Measurement-based Quantum Computation
- Quantum computational universality of hypergraph states with Pauli-X and Z basis measurements
- Interactive proofs for BQP via self-tested graph states (extended abstract)
- Shadow Pauli Flow: Characterising Determinism in MBQCs involving Pauli Measurements
- A dataflow programming framework for linear optical distributed quantum computing