Minimising the number of edges in LC-equivalent graph states
arXiv:2506.00292 · doi:10.22331/q-2026-02-09-2001
Abstract
Graph states are a powerful class of entangled states with numerous applications in quantum communication and quantum computation. Local Clifford (LC) operations that map one graph state to another can alter the structure of the corresponding graphs, including changing the number of edges. Here, we tackle the associated edge-minimisation problem: finding graphs with the minimum number of edges in the LC-equivalence class of a given graph. Such graphs are called minimum edge representatives (MER) and are crucial for minimising the resources required to create a graph state. We leverage Bouchet's algebraic formulation of LC-equivalence to encode the edge-minimisation problem as an integer linear program (EDM-ILP). We further propose a simulated annealing (EDM-SA) approach guided by the local clustering coefficient for edge minimisation. We identify new MERs for graph states with up to 16 qubits by combining EDM-SA and EDM-ILP. We extend the ILP to weighted-edge minimisation, where each edge has an associated weight, and prove that this problem is NP-complete. Finally, we employ our tools to minimise the resources required to create all-photonic generalised repeater graph states using fusion operations.
arXiv comment21 pages, 7 figures
References in corpus (34)
- Measurement-based quantum computation with cluster states
- Measurement-based quantum computation
- Multi-party entanglement in graph states
- Resource-efficient linear optical quantum computation
- All photonic quantum repeaters
- Time-Domain Multiplexed 2-Dimensional Cluster State: Universal Quantum Computing Platform
- Deterministic generation of a two-dimensional cluster state
- Deterministic Generation of a Cluster State of Entangled Photons
- Graphical description of the action of local Clifford transformations on graph states
- How good must single photon sources and detectors be for efficient linear optical quantum computation?
- The Clifford group, stabilizer states, and linear and quadratic operations over GF(2)
- One-way quantum repeater based on near-deterministic photon-emitter interfaces
- Rate-distance tradeoff and resource costs for all-optical quantum repeaters
- Sequential generation of linear cluster states from a single photon emitter
- Deterministic generation of all-photonic quantum repeaters from solid-state emitters
- Graph States as a Resource for Quantum Metrology
- Local permutations of products of Bell states and entanglement distillation
- An efficient algorithm to recognize local Clifford equivalence of graph states
- Fusion of deterministically generated photonic graph states
- Optimal preparation of graph states
- Transforming graph states using single-qubit operations
- Photonic resource state generation from a minimal number of quantum emitters
- Mapping graph state orbits under local complementation
- Generation of three-dimensional cluster entangled state
- Performance analysis of quantum repeaters enabled by deterministically generated photonic graph states
- A variational method based on weighted graph states
- All-photonic GKP-qubit repeater using analog-information-assisted multiplexed entanglement ranking
- Graph-theoretical optimization of fusion-based graph state generation
- Compilation of algorithm-specific graph states for quantum circuits
- Entanglement in Graph States and its Applications
- Deterministic generation of a 20-qubit two-dimensional photonic cluster state
- Generalized Quantum Repeater Graph States
- Optimization of deterministic photonic graph state generation via local operations
- Resource-efficient loss-aware photonic graph state preparation using atomic emitters