Efficient Preparation of Graph States using the Quotient-Augmented Strong Split Tree

• URL: http://arxiv.org/abs/2603.23892v2
• Date: Tue, 31 Mar 2026 04:40:29 GMT
• Title: Efficient Preparation of Graph States using the Quotient-Augmented Strong Split Tree
• Abstract summary: Graph states are a key resource for measurement-based quantum computation and quantum networking.<n>We introduce a split-fuse construction for arbitrary DH graph states, achieving linear scaling with respect to entangling gates, time steps, and auxiliary qubits.<n>We also discuss a generalized divide-and-conquer split-fuse strategy and a simple greedy for generic graphs based on triangle enumeration.
• Score: 1.5006258585503878
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph states are a key resource for measurement-based quantum computation and quantum networking, but state-preparation costs limit their practical use. Graph states related by local complement (LC) operations are equivalent up to single-qubit Clifford gates; one may reduce entangling resources by preparing a favorable LC-equivalent representative. However, exhaustive optimization over the LC orbit is not scalable. We address this problem using the split decomposition and its quotient-augmented strong split tree (QASST). For several families of distance-hereditary (DH) graphs, we use the QASST to characterize LC orbits and identify representatives with reduced controlled-Z count or preparation circuit depth. We also introduce a split-fuse construction for arbitrary DH graph states, achieving linear scaling with respect to entangling gates, time steps, and auxiliary qubits. Beyond the DH setting, we discuss a generalized divide-and-conquer split-fuse strategy and a simple greedy heuristic for generic graphs based on triangle enumeration. Together, these methods outperform direct implementations on sufficiently large graphs, providing a scalable alternative to brute-force optimization.

Related papers

• Efficient Recommendations via Graph Coarsening and Label Propagation [50.71909189967895]
  Graph-based recommendations are widely adopted in real-world industrial applications.<n>One promising approach is graph coarsening, an adaptive graph reduction technique.<n>We propose a flexible two-stage diffusion framework that combines graph coarsening with multi-step label propagation.
  arXiv  Detail & Related papers  (2026-07-24T13:25:26Z)
• Efficient Graph State Purification with Factorized Graph-Preserving Operations across Local Clifford Orbits [1.6005318974883016]
  Graph states form a broad class of multipartite entangled states underlying measurement quantum computation, quantum networks, and stabilizer codes.<n>We introduce a group of Clifford operations that we call "ized graph-preserving"<n>These operations map products of graph-basis states to products of graph-basis states, so their action can be represented as permutations of graph-basis labels.
  arXiv  Detail & Related papers  (2026-06-22T18:00:18Z)
• Rethinking Efficient Graph Coarsening via a Non-Selfishness Principle [56.92868481531399]
  We propose a non-selfishness principle that prioritizes the collective interference of neighborhood in coarsening.<n>We derive a faster variant NOPE*, which reduces O(dot d) interference evaluation to O(d) based on the local isotropy assumption.<n>Learning on coarsened graphs yields comparable performance to original graphs, and can even show superior performance over LLM-based graph reasoning.
  arXiv  Detail & Related papers  (2026-05-13T05:24:35Z)
• Quantum Hamlets: Distributed Compilation of Large Algorithmic Graph States [1.7856410179559383]
  We show that our algorithm, BURY, partitions graph states to require fewer Bell pairs for generation than state-of-the-art k partition algorithms.<n>We discuss how one could straightforwardly apply our methods to the dynamic case where the graph state generation and measurement are performed concurrently.
  arXiv  Detail & Related papers  (2026-03-06T15:36:22Z)
• Minimizing the number of edges in LC-equivalent graph states [0.0]
  Local Clifford operations that map one graph state to another can alter the structure of the corresponding graphs, including changing the number of edges.<n>Here, we tackle the associated edge-minimization problem: finding graphs with the minimum number of edges in the LC-equivalence class of a given graph.
  arXiv  Detail & Related papers  (2025-05-30T22:49:45Z)
• Graph Structure Refinement with Energy-based Contrastive Learning [56.957793274727514]
  We introduce an unsupervised method based on a joint of generative training and discriminative training to learn graph structure and representation.<n>We propose an Energy-based Contrastive Learning (ECL) guided Graph Structure Refinement (GSR) framework, denoted as ECL-GSR.<n>ECL-GSR achieves faster training with fewer samples and memories against the leading baseline, highlighting its simplicity and efficiency in downstream tasks.
  arXiv  Detail & Related papers  (2024-12-20T04:05:09Z)
• Rethinking and Accelerating Graph Condensation: A Training-Free Approach with Class Partition [49.41718583061147]
  Graph condensation is a data-centric solution to replace the large graph with a small yet informative condensed graph.<n>Existing GC methods suffer from intricate optimization processes, necessitating excessive computing resources and training time.<n>We propose a training-free GC framework termed Class-partitioned Graph Condensation (CGC)<n>CGC condenses the Ogbn-products graph within 30 seconds, achieving a speedup ranging from $102$X to $104$X and increasing accuracy by up to 4.2%.
  arXiv  Detail & Related papers  (2024-05-22T14:57:09Z)
• MeanCut: A Greedy-Optimized Graph Clustering via Path-based Similarity and Degree Descent Criterion [0.6906005491572401]
  spectral clustering is popular and attractive due to the remarkable performance, easy implementation, and strong adaptability. We propose MeanCut as the objective function and greedily optimize it in degree descending order for a nondestructive graph partition. The validity of our algorithm is demonstrated by testifying on real-world benchmarks and application of face recognition.
  arXiv  Detail & Related papers  (2023-12-07T06:19:39Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Localized Contrastive Learning on Graphs [110.54606263711385]
  We introduce a simple yet effective contrastive model named Localized Graph Contrastive Learning (Local-GCL) In spite of its simplicity, Local-GCL achieves quite competitive performance in self-supervised node representation learning tasks on graphs with various scales and properties.
  arXiv  Detail & Related papers  (2022-12-08T23:36:00Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  We propose a graph gradual pruning framework termed CGP to dynamically prune GNNs. Unlike LTH-based methods, the proposed CGP approach requires no re-training, which significantly reduces the computation costs. Our proposed strategy greatly improves both training and inference efficiency while matching or even exceeding the accuracy of existing methods.
  arXiv  Detail & Related papers  (2022-07-18T14:23:31Z)
• Distributed Multi-Agent Reinforcement Learning Based on Graph-Induced Local Value Functions [7.6860514640178]
  We propose a general computationally efficient distributed framework for cooperative multi-agent reinforcement learning (MARL) We introduce three coupling graphs describing three types of inter-agent couplings in MARL. We propose two distributed RL approaches based on local value-functions derived from the coupling graphs.
  arXiv  Detail & Related papers  (2022-02-26T03:01:51Z)
• LCS Graph Kernel Based on Wasserstein Distance in Longest Common Subsequence Metric Space [22.215852332444904]
  We propose a graph kernel to compute more comprehensive similarity between paths and walks. We also combine it with optimal transport theory to extract more in-depth features of graphs. Our proposed method outperforms many state-of-the-art graph kernel methods.
  arXiv  Detail & Related papers  (2020-12-07T11:59:14Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

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.