Transforming graph states using single-qubit operations
arXiv:1805.05305 · doi:10.1098/rsta.2017.0325
Abstract
Stabilizer states form an important class of states in quantum information, and are of central importance in quantum error correction. Here, we provide an algorithm for deciding whether one stabilizer (target) state can be obtained from another stabilizer (source) state by single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM), and classical communication (CC) between sites holding the individual qubits. What's more, we provide a recipe to obtain the sequence of LC+LPM+CC operations which prepare the desired target state from the source state, and show how these operations can be applied in parallel to reach the target state in constant time. Our algorithm has applications in quantum networks, quantum computing, and can also serve as a design tool - for example, to find transformations between quantum error correcting codes. We provide a software implementation of our algorithm that makes this tool easier to apply. A key insight leading to our algorithm is to show that the problem is equivalent to one in graph theory, which is to decide whether some graph G' is a vertex-minor of another graph G. Here we show that the vertex-minor problem can be solved in time O(|G|^3) where |G| is the size of the graph G, whenever the rank-width of G and the size of G' are bounded. Our algorithm is based on techniques by Courcelle for solving fixed parameter tractable problems, where here the relevant fixed parameter is the rank width. The second half of this paper serves as an accessible but far from exhausting introduction to these concepts, that could be useful for many other problems in quantum information.
26 pages, 1 figure. For computational complexity and more efficient algorithms for relevant graph classes see 'How to transform graph states using single-qubit operations: computational complexity and algorithms' (1805.05306). For related work see F. Hahn et al (1805.04559)
References in corpus (3)
Cited by in corpus (26)
- A quantum network stack and protocols for reliable entanglement-based networks
- Quantum network routing and local complementation
- Tools for quantum network design
- Analysis of Multipartite Entanglement Distribution using a Central Quantum-Network Node
- Generation of arbitrary all-photonic graph states from quantum emitters
- Mapping graph state orbits under local complementation
- Delocalized information in quantum networks
- Optimized Quantum Networks
- Transforming graph states to Bell-pairs is NP-Complete
- Hard limits on the postselectability of optical graph states
- Extracting GHZ states from linear cluster states
- Limitations of nearest-neighbour quantum networks
- Graph-theoretical optimization of fusion-based graph state generation
- Rates of multi-partite entanglement transformations and applications in quantum networks
- Efficient Entanglement Measure for Graph States
- Sharp complexity phase transitions generated by entanglement
- Flexible quantum data bus for quantum networks
- Foundations of quantum mechanics and their impact on contemporary society
- Counting single-qubit Clifford equivalent graph states is #P-Complete
- Generating graph states with a single quantum emitter and the minimum number of fusions
- Transforming graph states via Bell state measurements
- Graph state extraction from two-dimensional cluster states
- Clifford Manipulations of Stabilizer States: A graphical rule book for Clifford unitaries and measurements on cluster states, and application to photonic quantum computing
- Minimising the number of edges in LC-equivalent graph states
- Multipartite Entanglement Distribution in Quantum Networks using Subgraph Complementations
- Sharing classical secrets with continuous-variable entanglement: Composable security and network coding advantage