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.
21 pages, 7 figures
References in corpus (21)
- Multi-party entanglement in graph states
- Resource-efficient linear optical quantum computation
- Deterministic Generation of a Cluster State of Entangled Photons
- How good must single photon sources and detectors be for efficient linear optical quantum computation?
- Sequential generation of linear cluster states from a single photon emitter
- Graph States as a Resource for Quantum Metrology
- Fusion of deterministically generated photonic graph states
- Optimal preparation of graph states
- 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