Bipartitioning of Graph States for Distributed Measurement-Based Quantum Computing

• URL: http://arxiv.org/abs/2601.06332v1
• Date: Fri, 09 Jan 2026 22:08:49 GMT
• Title: Bipartitioning of Graph States for Distributed Measurement-Based Quantum Computing
• Authors: Kjell Fredrik Pettersen, Matthias Heller, Giorgio Sartor, Raoul Heese,
• Abstract summary: Measurement-Based Quantum Computing (MBQC) is inherently well-suited for Distributed Quantum Computing (DQC)<n>Non-local gates acting on different Quantum Processing Units (QPUs) are a bottleneck.<n>We show that the approach is highly effective for determining qubit assignments in distributed MBQC by testing it on grid graphs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Measurement-Based Quantum Computing (MBQC) is inherently well-suited for Distributed Quantum Computing (DQC): once a resource state is prepared and distributed across a network of quantum nodes, computation proceeds through local measurements coordinated by classical communication. However, since non-local gates acting on different Quantum Processing Units (QPUs) are a bottleneck, it is crucial to optimize the qubit assignment to minimize inter-node entanglement of the shared resource. For graph state resources shared across two QPUs, this task reduces to finding bipartitions with minimal cut rank. We introduce a simulated annealing-based algorithm that efficiently updates the cut rank when two vertices swap sides across a bipartition, such that computing the new cut rank from scratch, which would be much more expensive, is not necessary. We show that the approach is highly effective for determining qubit assignments in distributed MBQC by testing it on grid graphs and the measurement-based Quantum Approximate Optimization Algorithm (QAOA).

Related papers

• Lattice Surgery Aware Resource Analysis for the Mapping and Scheduling of Quantum Circuits for Scalable Modular Architectures [2.566848881167754]
  Quantum computing platforms are evolving to a point where placing high numbers of qubits into a single core comes with difficulties.<n>We develop a framework that can take any quantum circuit, transpile it to our gate set using Qiskit, and then partition the qubits.<n>We report statistics such as the number of classical communications, the number of EPR pairs and magic states consumed, and timing overheads for pre- and post- processing.
  arXiv  Detail & Related papers  (2025-11-26T20:08:29Z)
• Network Operations Scheduling for Distributed Quantum Computing [0.0]
  We compare and contrast two approaches to solving the make span minimization problem.<n>One approach is based on the resource constrained project scheduling (RCPSP) framework, and another based on a greedy algorithm.<n>Our results illustrate the effectiveness of the RCPSP framework, while also underlining the relevance and usefulness of greedy algorithms.
  arXiv  Detail & Related papers  (2025-11-17T18:40:50Z)
• Decentralized Optimization on Compact Submanifolds by Quantized Riemannian Gradient Tracking [45.147301546565316]
  This paper considers the problem of decentralized optimization on compact submanifolds.<n>We propose an algorithm where agents update variables using quantized variables.<n>To the best of our knowledge, this is the first algorithm to achieve an $mathcalO (1/K)$ convergence rate in the presence of quantization.
  arXiv  Detail & Related papers  (2025-06-09T01:57:25Z)
• Graph state extraction from two-dimensional cluster states [37.19059223604783]
  We introduce graph state manipulation tools that allow one to increase the local degree and to merge subgraphs.<n>We show how to minimize overheads by avoiding multiple edges, and compare with a local manipulation strategy based on measurement-based quantum computation together with transport.<n>These schemes have direct applications in entanglement-based quantum networks, sensor networks, and distributed quantum computing in general.
  arXiv  Detail & Related papers  (2025-05-13T09:49:54Z)
• Non-unitary Coupled Cluster Enabled by Mid-circuit Measurements on Quantum Computers [37.69303106863453]
  We propose a state preparation method based on coupled cluster (CC) theory, which is a pillar of quantum chemistry on classical computers. Our approach leads to a reduction of the classical computation overhead, and the number of CNOT and T gates by 28% and 57% on average.
  arXiv  Detail & Related papers  (2024-06-17T14:10:10Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Applicability of Measurement-based Quantum Computation towards Physically-driven Variational Quantum Eigensolver [17.975555487972166]
  Variational quantum algorithms are considered one of the most promising methods for obtaining near-term quantum advantages. The roadblock to developing quantum algorithms with the measurement-based quantum computation scheme is resource cost. We propose an efficient measurement-based quantum algorithm for quantum many-body system simulation tasks, called measurement-based Hamiltonian variational ansatz (MBHVA)
  arXiv  Detail & Related papers  (2023-07-19T08:07:53Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Compilation of algorithm-specific graph states for quantum circuits [55.90903601048249]
  We present a quantum circuit compiler that prepares an algorithm-specific graph state from quantum circuits described in high level languages. The computation can then be implemented using a series of non-Pauli measurements on this graph state.
  arXiv  Detail & Related papers  (2022-09-15T14:52:31Z)
• Quantum Robustness Verification: A Hybrid Quantum-Classical Neural Network Certification Algorithm [1.439946676159516]
  In this work, we investigate the verification of ReLU networks, which involves solving a robustness many-variable mixed-integer programs (MIPs) To alleviate this issue, we propose to use QC for neural network verification and introduce a hybrid quantum procedure to compute provable certificates. We show that, in a simulated environment, our certificate is sound, and provide bounds on the minimum number of qubits necessary to approximate the problem.
  arXiv  Detail & Related papers  (2022-05-02T13:23:56Z)
• Benchmarking Small-Scale Quantum Devices on Computing Graph Edit Distance [52.77024349608834]
  Graph Edit Distance (GED) measures the degree of (dis)similarity between two graphs in terms of the operations needed to make them identical. In this paper we present a comparative study of two quantum approaches to computing GED.
  arXiv  Detail & Related papers  (2021-11-19T12:35:26Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages. Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data. Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
  arXiv  Detail & Related papers  (2021-06-24T08:18:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.