Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time

• URL: http://arxiv.org/abs/2502.06566v1
• Date: Mon, 10 Feb 2025 15:34:41 GMT
• Title: Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time
• Authors: Nathan Claudet, Simon Perdrix,
• Abstract summary: We describe an algorithm with quasi-polynomial runtime $nlog_2(n)+O(1)$ for deciding local unitary (LU) equivalence of graph states. We show that LU-equivalence reduces to solving a system of quasi-polynomially many linear equations, avoiding an exponential blow-up.
• Score: 0.0
• License:
• Abstract: We describe an algorithm with quasi-polynomial runtime $n^{\log_2(n)+O(1)}$ for deciding local unitary (LU) equivalence of graph states. The algorithm builds on a recent graphical characterisation of LU-equivalence via generalised local complementation. By first transforming the corresponding graphs into a standard form using usual local complementations, LU-equivalence reduces to the existence of a single generalised local complementation that maps one graph to the other. We crucially demonstrate that this reduces to solving a system of quasi-polynomially many linear equations, avoiding an exponential blow-up. As a byproduct, we generalise Bouchet's algorithm for deciding local Clifford (LC) equivalence of graph states by allowing the addition of arbitrary linear constraints. We also improve existing bounds on the size of graph states that are LU- but not LC-equivalent. While the smallest known examples involve 27 qubits, and it is established that no such examples exist for up to 8 qubits, we refine this bound by proving that LU- and LC-equivalence coincide for graph states involving up to 19 qubits.

Related papers

• A Greedy Strategy for Graph Cut [95.2841574410968]
  We propose a greedy strategy to solve the problem of Graph Cut, called GGC. It starts from the state where each data sample is regarded as a cluster and dynamically merges the two clusters. GGC has a nearly linear computational complexity with respect to the number of samples.
  arXiv  Detail & Related papers  (2024-12-28T05:49:42Z)
• Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs [40.215737469808026]
  This work focuses on graph local clustering, which has broad applications beyond graphs because of the internal connectivities within various modalities. We extend the non-approximating Andersen-Chung-Lang ("ACL") algorithm beyond discrete graphs and generalize its quadratic optimality to a wider range of graphs. We theoretically prove that, under two mild conditions, both algorithms can identify a quadratically optimal local cluster in terms of conductance with at least 1/2 probability.
  arXiv  Detail & Related papers  (2024-12-04T03:56:14Z)
• Algorithm to Verify Local Equivalence of Stabilizer States [0.0]
  We present an algorithm for verifying the local unitary equivalence of graph and stabilizer states. Our approach reduces the problem to solving a system of linear equations in modular arithmetic.
  arXiv  Detail & Related papers  (2024-10-04T22:51:11Z)
• Local equivalence of stabilizer states: a graphical characterisation [0.0]
  A fundamental property of graph states is that applying a local complementation results in a graph that represents the same entanglement as the original. This property served as the cornerstone for capturing non-trivial quantum properties in a simple graphical manner. We introduce a generalisation of local complementation which graphically characterises the LU-equivalence of graph states.
  arXiv  Detail & Related papers  (2024-09-30T10:51:15Z)
• Distinguishing Graph States by the Properties of Their Marginals [0.0]
  We introduce a family of easy-to-compute LU-invariants based on the marginal structure of the graphs. We show that these invariants can uniquely identify all LU-orbits and entanglement classes of every graph state of 8 qubits or less. We also discuss examples of entanglement classes with more nodes, where their marginal structure does not allow us to tell them apart.
  arXiv  Detail & Related papers  (2024-06-14T12:03:10Z)
• 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)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• Local optimization on pure Gaussian state manifolds [63.76263875368856]
  We exploit insights into the geometry of bosonic and fermionic Gaussian states to develop an efficient local optimization algorithm. The method is based on notions of descent gradient attuned to the local geometry. We use the presented methods to collect numerical and analytical evidence for the conjecture that Gaussian purifications are sufficient to compute the entanglement of purification of arbitrary mixed Gaussian states.
  arXiv  Detail & Related papers  (2020-09-24T18:00:36Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)

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.