⚛️ quantum physics

Minimising the number of edges in LC-equivalent graph states

This paper proposes integer linear programming and simulated annealing methods to solve the edge-minimization problem for LC-equivalent graph states, identifying minimum edge representatives to reduce the resources required for quantum state preparation.

Original authors: Hemant Sharma, Kenneth Goodenough, Johannes Borregaard, Filip Rozpędek, Jonas Helsen

Published 2026-02-11

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Hemant Sharma, Kenneth Goodenough, Johannes Borregaard, Filip Rozpędek, Jonas Helsen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a professional organizer tasked with tidying up a massive, tangled web of Christmas lights. Each light bulb is a "qubit" (a unit of quantum information), and the wires connecting them are "edges."

In the quantum world, these webs are called Graph States. They are incredibly useful for building super-fast quantum computers and secure communication networks, but there is a catch: the more wires (edges) you have, the harder, more expensive, and more error-prone it is to build them.

This paper is about finding the "neatest" version of a specific web.

The Problem: The Tangled Web

Imagine someone hands you a messy, tangled ball of wires. They tell you, "This is the specific pattern I need, but you can move the bulbs around or change how they are connected, as long as the underlying 'logic' of the pattern stays the same."

In quantum physics, this "moving around" is called Local Clifford (LC) operations. These operations allow you to transform a messy graph into a cleaner one without changing its fundamental quantum properties. The goal is to find the Minimum Edge Representative (MER)—the absolute simplest, cleanest version of that web with the fewest possible wires.

The Solution: Three Different "Organizers"

The researchers created three different "digital organizers" (algorithms) to solve this:

The "Quick & Dirty" Organizer (EDM-SA):
Think of this like a person quickly shaking the box of lights to see if they settle into a better shape. It uses a technique called Simulated Annealing. It starts by being very "hot" (making wild, random changes to the wires) and slowly "cools down" (making smaller, more careful adjustments). It’s incredibly fast and can handle huge webs (up to 100 qubits), but it might not find the perfect cleanest version—it just gets "close enough."
The "Perfectionist" Organizer (EDM-ILP):
This is like a mathematician with a massive spreadsheet. It uses complex math (Integer Linear Programming) to check every single possible combination to guarantee it finds the absolute minimum number of wires. It is perfect, but it is slow. If the web gets too big, the mathematician will be working for a billion years.
The "Hybrid" Organizer (EDM-SAILP):
This is the "Dream Team." First, the Quick & Dirty organizer shakes the box to get the wires mostly untangled. Then, the Perfectionist takes that semi-organized mess and does the final, precise polishing. This allows them to find the perfect solution much faster than the mathematician could do alone.

The Real-World Payoff: Building Quantum Repeaters

Why does this matter? The authors applied their "organizers" to a real problem: Quantum Repeaters.

Think of a quantum repeater like a signal booster for a long-distance internet connection. Currently, sending quantum signals over long distances is like trying to throw a ball through a hurricane—most of the signal gets lost. To fix this, we use "photonic" repeaters, which are built using these graph states.

By using their algorithms, the researchers found a way to "pre-untangle" the instructions for building these repeaters. Instead of trying to build a complex, messy web and hoping it works, they build a simplified, "clean" version first and then use a few quick quantum "tricks" to turn it into the final shape.

The result? They reduced the amount of equipment and "light particles" (photons) needed by more than 10 times. They essentially turned a high-cost, high-failure construction project into a much cheaper, much more reliable one.

Summary

The Goal: Find the simplest way to connect quantum bits without changing their "soul."
The Method: A mix of "shaking the box" (fast) and "math perfection" (accurate).
The Win: Making quantum communication much more efficient and much less wasteful.

Technical Summary: Minimising the Number of Edges in LC-equivalent Graph States

1. Problem Statement

Graph states are a vital class of multipartite entangled states used in quantum communication, measurement-based quantum computation, and error correction. A graph state $|G\rangle$ is defined by a graph $G$ where vertices represent qubits and edges represent controlled-Z (CZ) gates.

The core problem addressed in this paper is edge minimization within a Local Clifford (LC) equivalence class. Applying single-qubit Clifford operations (local complementations) can transform one graph state into another LC-equivalent graph state, often resulting in a different number of edges. The goal is to find the Minimum Edge Representative (MER)—the graph in the LC-orbit with the fewest possible edges. Identifying MERs is critical because reducing the number of edges directly minimizes the physical resources (e.g., CZ gates, fusion operations, or photon sources) required to prepare the state.

2. Methodology

The authors propose three distinct algorithmic approaches to tackle the edge-minimization problem, ranging from heuristic approximations to exact global optimizations:

EDM-SA (Simulated Annealing): A heuristic approach designed for scalability. It uses a simulated annealing process where "states" are graphs and "moves" are local complementations. To improve efficiency, the authors introduce a guiding metric, the local clustering coefficient multiplied by the vertex degree ( $M_v \equiv C_G(v)D_v$ ), to bias the search toward vertices that are more likely to reduce edge density. This allows the algorithm to handle graphs with up to 100 qubits.
EDM-ILP (Integer Linear Program): An exact optimization method. The authors leverage Bouchet’s algebraic formulation of LC-equivalence to encode the problem as an integer linear program. They transform the non-linear symplectic constraints of Clifford operations into a linear system by introducing auxiliary integer variables. While it guarantees the global minimum (the true MER), its runtime scales exponentially with the number of qubits.
EDM-SAILP (Hybrid Approach): A combination of the two previous methods. EDM-SA is used to find an approximate MER, which then serves as a "preconditioner" for the EDM-ILP. By starting the ILP closer to the optimal solution, the number of constraints is reduced, significantly speeding up the computation. This hybrid method enables exact MER identification for graphs up to 16 qubits.

The authors also extend the ILP to weighted-edge minimization, where edges have different costs. They prove that this weighted version is NP-complete via a reduction from the vertex-minor problem.

3. Key Contributions

New Algorithmic Framework: Developed a scalable hierarchy of algorithms (SA $\rightarrow$ Hybrid $\rightarrow$ ILP) to solve the edge-minimization problem.
Mathematical Proof: Formally proved the NP-completeness of the weighted-edge minimization problem.
Resource Optimization Protocol: Introduced the "Commute-LC" protocol. Instead of creating a dense graph and then applying LC gates, this protocol applies LC gates to the initial resource states (converting them into non-graph states) and then performs fusions according to the topology of the MER. This allows for an optimized fusion order that is more resilient to photon loss.

4. Results

Algorithm Performance:
- EDM-SA provides high-quality approximations, typically staying within ~10% of the true MER edge count, even for large graphs.
- EDM-SAILP achieves a constant-factor speedup over the standard EDM-ILP.
Practical Application (All-Photonic Repeaters): When applied to generalized repeater graph states (gRGS), the Commute-LC protocol demonstrated a massive efficiency gain. Under realistic high-loss conditions, the method achieved more than an order-of-magnitude reduction in the required number of single-photon sources and fusion operations compared to naive construction methods.

5. Significance

This work bridges the gap between abstract graph theory and practical quantum hardware implementation. By providing tools to find the most "economical" representation of an entangled state, the authors provide a roadmap for building more efficient quantum networks and repeaters. The ability to transform complex, dense entanglement structures into sparse, manageable ones is a fundamental requirement for scaling up all-photonic quantum technologies.