論文の概要: Polynomial-time local-unitary equivalence of graph states

• arxiv url: http://arxiv.org/abs/2610.00527v2
• Date: Sun, 04 Oct 2026 15:33:17 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-07 04:43:28.498792
• Title: Polynomial-time local-unitary equivalence of graph states
• Title（参考訳）: グラフ状態の多項式時間局所単位同値
• Abstract要約: 局所単位同値 (LU) は、2つの量子状態がその量子ビットの基底の独立な変化によってのみ異なるかどうかを問う。 我々は,$widetilde O(n6.38)$ bit 演算におけるグラフのLU同値性を決定する決定論的アルゴリズムを提案する。 任意のグラフ状態に対して、これは単一キュービットクリフォードゲートがそのLUクラスの全てのグラフ状態に達するかどうかを決定する。
• 参考スコア（独自算出の注目度）: 6.472219867780061
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on $n$ labelled vertices in $\widetilde O(n^{6.38})$ bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost $\widetilde O(n^5)$ bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.
• Abstract（参考訳）: 局所単位同値 (LU) は、2つの量子状態がその量子ビットの基底の独立な変化によってのみ異なるかどうかを問う。 グラフ状態の場合、この関係が多項式時間で決定できるかどうかは10年以上も未解決のままである。 我々は、$n$ラベル付き頂点上のグラフのLU同値を$\widetilde O(n^{6.38})$ビット演算で決定する決定論的アルゴリズムを与え、状態が等価であれば、正確な単一量子ユニタリを構築する。 Claudet と Perdrix の準ポリノミカルアルゴリズムに基づいて、頂点部分集合の列挙をペアとトリプルから生成される制約のコンパクトなシステムによって置き換える。 残りのグラフ変換は、二進体上の線形方程式を解くことによって得られる。 これらの新しいステップは$\widetilde O(n^5)$ bit 演算に費やされる。 また、任意のLUクラス内のグラフ状態の局所クリフォード(LC)クラスを数える:それらの数は同じ境界内で計算可能な2つのパワーである。 任意のグラフ状態に対して、これは単一量子クリフォードゲートがそのLUクラスの全てのグラフ状態に到達するかどうかを決定し、それらがそうでないときに反例を提供する。 また、1つの論理量子ビットを符号化する安定化器符号のLU同値性も決定する。

関連論文リスト

• Local Equivalences of Graph States [0.0]
  グラフ状態は、数学グラフと1対1の対応を持つ量子状態の大きな族を形成する。 そのような2つの状態が同じ絡み合いを持つ場合、すなわち、局所的な操作のみを使用してそれらが互いに変換される場合を理解することは重要である。 我々はLC-とLU-等価性の間の局所同値の無限に厳密な階層の存在を証明した。
  論文  参考訳（メタデータ） (2025-11-27T09:49:57Z)
• Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time [0.0]
  グラフ状態の局所ユニタリ(LU)同値性を決定するために準多項式ランタイム$nlog_2(n)+O(1)$のアルゴリズムを記述する。 LU等価性は、指数的爆発を避けるために、擬多項式的に多くの線形方程式の系を解くことに還元されることを示す。
  論文  参考訳（メタデータ） (2025-02-10T15:34:41Z)
• Provably Extending PageRank-based Local Clustering Algorithm to Weighted Directed Graphs with Self-Loops and to Hypergraphs [40.215737469808026]
  この研究はグラフ局所クラスタリングに重点を置いており、様々なモダリティの内部接続性のため、グラフ以外の幅広い応用がある。 非近似型Andersen-Chung-Lang(ACL)アルゴリズムを離散グラフを超えて拡張し、その二次最適性をより広い範囲のグラフに一般化する。 理論的には、2つの穏やかな条件下では、両方のアルゴリズムが少なくとも1/2確率のコンダクタンスの観点から2次最適局所クラスターを識別できることが証明される。
  論文  参考訳（メタデータ） (2024-12-04T03:56:14Z)
• Distinguishing Graph States by the Properties of Their Marginals [0.0]
  局所ユニタリ(LU)下におけるグラフ状態の同値関係について検討する。 これらの不変量は、最大8キュービットまでの全てのグラフ状態の絡み合いクラスを一意に識別することを示す。 我々は、大きなグラフをより小さなグラフに凝縮することで機能するグラフ状態の局所クリフォード(LC)同値性をテストするツールを一般化する。
  論文  参考訳（メタデータ） (2024-06-14T12:03:10Z)
• On the Stability of a non-hyperbolic nonlinear map with non-bounded set of non-isolated fixed points with applications to Machine Learning [31.263649000946014]
  本稿では,SUCPA(Semi Unsupervised through Prior Adaptation)アルゴリズムの収束解析について述べる。 収束解析は、アルゴリズムから導出される非線形写像の局所的および大域的安定性を研究することにより、力学系問題として対処される。
  論文  参考訳（メタデータ） (2024-01-05T20:04:40Z)
• SAT-Based Algorithms for Regular Graph Pattern Matching [40.86962847131912]
  複素構造特性をチェックできるグラフ同型を一般化する。 この仕様は正規表現にインスパイアされた特殊なグラフである正規グラフパターン(ReGaP)の形で与えられる。 本稿では、対象グラフが所定のReGaPと一致するかどうかをチェックするSATベースのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-15T18:12:44Z)
• The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
  グラフ関数と出力が同一のグラフニューラルネットワーク(GNN)? 本稿では,この疑問に完全に答え,GNNで表現可能なグラフ問題のクラスを特徴付ける。 この条件は2次的に多くの制約をチェックすることで効率よく検証できることを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:54:27Z)
• Fast Computation of Generalized Eigenvectors for Manifold Graph Embedding [38.902986549367434]
  我々は、高速実行に既存の高速極端固有ベクトル計算アルゴリズムを利用する。 我々の埋め込みは文献の中では最速であり、多様体グラフのクラスタリング性能は最高のものとなっている。
  論文  参考訳（メタデータ） (2021-12-15T03:45:39Z)
• Wasserstein Embedding for Graph Learning [33.90471037116372]
  Wasserstein Embedding for Graph Learning (WEGL)は、グラフ全体をベクトル空間に埋め込むフレームワークである。 グラフ間の類似性をノード埋め込み分布間の類似性の関数として定義する上で,新たな知見を活用する。 各種ベンチマークグラフ固有性予測タスクにおける新しいグラフ埋め込み手法の評価を行った。
  論文  参考訳（メタデータ） (2020-06-16T18:23:00Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。