Graph State Bipartitioning Achieves Minimal Cut Rank for Distributed Measurement-Based Quantum Computing

Measurement-Based Quantum Computing offers a promising architecture for realising distributed quantum computation, leveraging local operations and classical communication across a network of quantum processors. Kjell Fredrik Pettersen, Matthias Heller, Giorgio Sartor, and Raoul Heese from SINTEF Digital, Fraunhofer IGD, and NTT DATA respectively, have addressed a critical challenge in this field: optimising qubit allocation to minimise entanglement between distant quantum processing units. Their research focuses on efficiently dividing a shared quantum resource , a graph state , into two partitions, a task reduced to finding a bipartition with the lowest possible ‘cut rank’. This new work introduces a simulated annealing algorithm that dramatically speeds up the process of finding optimal qubit assignments, avoiding computationally expensive recalculations with each adjustment. By demonstrating its effectiveness on grid graphs and the measurement-based Quantum Approximate Optimisation Algorithm, the team provides a significant step towards practical, scalable distributed quantum computers.

Efficiently partitioning a large graph state for distribution amongst multiple quantum processors remains a significant challenge, and this work introduces a novel approach aiming to minimise the required quantum communication between nodes. The proposed method leverages a combination of graph theoretical analysis and optimisation techniques to identify optimal cuts within the graph state. The researchers focused on minimising the number of entangled pairs that must be shared across partitions, directly impacting communication overhead.

They demonstrate that a balanced bipartition, containing approximately 50% of the qubits each, can be achieved while maintaining a low entanglement cut. The algorithm considers graph properties, including node degree and connectivity, to determine the most effective partitioning strategy. Detailed analysis of the algorithm’s performance on benchmark graph states, including those relevant to quantum error correction, indicates a substantial reduction in required quantum communication compared to random partitioning schemes. The effectiveness is validated through numerical simulations, showcasing its potential for practical implementation in distributed MBQC architectures. The authors also explore the trade-offs between partition balance and entanglement cut, providing insights into the design of efficient distributed quantum algorithms. They highlight the importance of considering the specific characteristics of the graph state and the underlying quantum hardware when selecting a partitioning strategy, contributing to the advancement of distributed MBQC by offering a practical method for partitioning graph states.

Graph Partitioning via Simulated Annealing

Scientists are pioneering new methods to optimise qubit assignment for distributed measurement-based quantum computing (MBQC), addressing a critical bottleneck in scaling quantum processors. Their work centres on efficiently distributing graph states across multiple quantum processing units (QPUs), minimising the entanglement required between them. The research tackles the problem of finding bipartitions within a graph with the lowest possible ‘cut rank’, directly impacting the number of shared entangled states needed for computation. To accelerate this process, the team engineered a simulated annealing algorithm designed to update the cut rank incrementally.

Instead of recalculating the cut rank from scratch with each potential vertex swap, a computationally expensive operation, their approach focuses on determining only the change in cut rank. This innovative technique achieves a significant speedup, reducing computation time by up to two orders of magnitude for graphs containing up to 400 nodes, with the algorithm evaluating the impact of a single vertex swap in O(n2) time. The study meticulously details how this incremental calculation is achieved, leveraging the adjacency matrix of the graph to efficiently track rank modifications. Given a graph G = (V, E) and a bipartition (X, Y), the algorithm assesses the change in cut rank for every possible vertex swap by analysing how the adjacency matrix transforms, allowing for rapid determination of the new cut rank.

The researchers demonstrate the method’s effectiveness through examples, illustrating how a graph with vertices V := {0, . . . , 5} and edges E := {(0, 3), (0, 4), (1, 3), (1, 4), (1, 5), (2, 5)} can be transformed to minimise entanglement. Crucially, the work connects this algorithmic advancement directly to the practical implementation of distributed MBQC. Minimising cut rank translates to reducing the number of EPR pairs, a fundamental resource for entanglement, required between QPUs. The research team developed a simulated annealing algorithm to efficiently update the cut rank of a graph when vertices swap sides of a bipartition, avoiding computationally expensive recalculations. Tests on grid graphs revealed that the algorithm consistently minimizes inter-node entanglement of shared resource states.

For graphs ranging in size from 4 to 20, the average cut rank at the start of the process, using a random partition, was significantly reduced after the annealing process, with the average deviation from the known minimal cut rank consistently remaining below 0.4. Further experiments involved sparse Erdős-Rényi random graphs, where the team measured average runtimes and cut ranks under varying conditions. Results indicate that with a connection coefficient (c) of 1 and a partition probability (P1) of 1/2, the average runtime per sample remained below 5 milliseconds. Analysis of QAOA implementations showed the algorithm successfully identified a bipartition with a cut rank of 3 for a specific graph state, requiring six ancillary qubits to facilitate distribution across two Quantum Processing Units (QPUs).

The team evaluated the algorithm’s scalability by generating graph states up to 240 qubits and implementing measurement-based QAOA with random Hamiltonians containing between 100 and 200 terms. The minimum cut rank found by the algorithm remained below the total number of qubits in the Hamiltonian, even with increasing complexity. Using temperature schedules with 10 and 100 steps, the algorithm consistently found improved bipartitions, suggesting that further refinement with more temperature steps could yield even better results. This work represents a crucial step towards efficient algorithms for graph state partitioning in distributed MBQC.

Optimal Qubit Assignment via Simulated Annealing

This work introduces a novel and efficient algorithm for determining optimal qubit assignments in distributed measurement-based quantum computing. The researchers addressed the challenge of minimising inter-node entanglement by focusing on finding bipartitions of graph state resources with minimal cut rank, a key factor in reducing the need for shared entangled states between quantum processing units. Their simulated annealing-based approach significantly reduces computational time, by up to two orders of magnitude for graphs containing up to 400 nodes, by avoiding the need to recalculate cut rank with each vertex swap during the partitioning process. The significance of this achievement lies in its potential to facilitate scalable distributed quantum computation.

By optimising the initial distribution of entanglement, the algorithm streamlines the first stage of measurement-based quantum computation, allowing subsequent stages to proceed with only classical communication between processing units. The authors acknowledge a limitation in that their algorithm currently focuses on the initial graph state preparation stage and does not address optimisation within the subsequent adaptive measurement and Pauli correction phases. Future research could extend this work to encompass the entire computation, further enhancing the efficiency of distributed quantum algorithms.