論文の概要: A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity
- arxiv url: http://arxiv.org/abs/2607.09469v1
- Date: Fri, 10 Jul 2026 14:42:55 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-13 14:47:12.86252
- Title: A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity
- Title（参考訳）: クラスタリンググラフステートのための組合せフレームワーク:ランク積分のためのアルゴリズムと硬さ
- Abstract要約: 同じ量子ビットの集合上で、2つのグラフ状態間の距離の新たな概念を$|Grangle$ と $|G'rangle$ を導入する。
この距離は、グラフ状態 $|widehatGrangle$ におけるアシラ量子ビットの最小数である。
この距離が、多くのグラフ編集距離問題の量子ネットワークアナログをどのように生み出すかを示す。
- 参考スコア（独自算出の注目度）: 1.9607843515179006
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce a new notion of distance between two graph states $|G\rangle$ and $|G'\rangle$ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state $|\widehat{G}\rangle$ from which both $|G\rangle$ and $|G'\rangle$ can be ``easily prepared''. (When preparing graph states, we are only allowed to use one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication.) We give a graphical description of this distance through the lens of vertex-minors. We then show how this distance yields quantum network analogs of many graph edit-distance problems. Using this framework, we develop classical algorithms for identifying the ``highly entangled clusters'' of a graph state $|G\rangle$. The ancilla integrity problem asks, given a graph $G$ and integer $k$, for the minimum -- over all graph states $|G'\rangle$ with distance at most $k$ from $|G\rangle$ -- of the maximum component size of $G'$. Up to a factor of $2$ in the number of ancilla qubits, this problem is equivalent to rank integrity, where the distance between $G$ and $G'$ is instead the minimum rank of the sum of their adjacency matrices over $\text{GF}(2)$. We prove that rank integrity is XP parameterized by $k$. We also prove the complementary hardness result that rank integrity is W[1]-hard in $k$. Finally, we give an explicit $\mathcal{O}(n^6)$-time algorithm for ancilla integrity when $G$ has $n$ vertices and $k=1$.
- Abstract（参考訳）: 同じ量子ビットの集合上で、2つのグラフ状態間の距離の新たな概念である $|G\rangle$ と $|G'\rangle$ を導入する。
この距離はグラフ状態 $|\widehat{G}\rangle$ において最小の ancilla qubit であり、そこから $|G\rangle$ と $|G'\rangle$ の両方を `easily prepared' とすることができる。
(グラフ状態を作成する際には、一量子クリフォードゲート、一量子パウリ測定、古典通信しか使用できない。)
頂点ミネータのレンズを通して、この距離をグラフィカルに記述する。
次に、この距離が多くのグラフ編集距離問題の量子ネットワークアナログをどのように生成するかを示す。
このフレームワークを用いて、グラフ状態$|G\rangle$の 'highly entangled cluster'' を識別する古典的アルゴリズムを開発する。
アンシラ整合性問題は、最小値のグラフ$G$と整数$k$が与えられたとき、すべてのグラフ状態に対して$|G'\rangle$が最大成分サイズ$G'$から$|G\rangle$までの距離を持つ。
acilla qubits の数で 2$ の係数まで、この問題は階数完全性と同値であり、$G$ と $G’$ の間の距離は、代わりに$\text{GF}(2)$ の隣接行列の和の最小ランクである。
ランク完全性は$k$でXPパラメータ化されていることを証明します。
また、階数完全性が$k$の W[1]-ハードであることの相補的硬さの結果も証明する。
最後に、$G$が$n$Verticesと$k=1$を持つとき、アシラ整合性のための明示的な$\mathcal{O}(n^6)$-timeアルゴリズムを与える。
関連論文リスト
- Preparing graph states forbidding a vertex-minor [1.864621482724548]
測定に基づく量子コンピューティングは、準備された安定化状態に非クリフォード測定を加えることでプリフォームされる。
すべての安定化状態はグラフ状態と局所クリフォード同値であるため、グラフ状態$leftvert G rightrangle$にフォーカスすることができる。
グラフの特定の固有クラスに$G$が含まれているとき、かなり改善された境界を得る。
論文 参考訳（メタデータ） (2025-03-31T23:25:35Z) - A note on quantum lower bounds for local search via congestion and expansion [4.68073705539907]
G$上の局所探索の量子クエリの複雑さは$Omegabigl( fracnfrac34sqrtg bigr)$であることを示す。
古典的な設定とは対照的に、そのようなグラフに対して、下界と最もよく知られた上界の$Obigl(nfrac13 bigr)$の間の量子ケースにギャップが残っている。
論文 参考訳（メタデータ） (2024-12-17T21:42:42Z) - Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - A quantum algorithm for learning a graph of bounded degree [1.8130068086063336]
本稿では,最大$tildeO(d2m3/4)$量子クエリにおいて,$G$のエッジを学習するアルゴリズムを提案する。
特に、確率の高い確率で$tildeO(sqrtm)$量子クエリでサイクルとマッチングを学習するランダム化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-28T21:23:40Z) - Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。
複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
論文 参考訳（メタデータ） (2023-06-05T15:35:00Z) - Detection of Dense Subhypergraphs by Low-Degree Polynomials [72.4451045270967]
ランダムグラフにおける植込み高密度部分グラフの検出は、基本的な統計的および計算上の問題である。
我々は、$Gr(n, n-beta)ハイパーグラフにおいて、植えた$Gr(ngamma, n-alpha)$ subhypergraphの存在を検出することを検討する。
平均値の減少に基づく硬さが不明な微妙な対数密度構造を考えると,この結果はグラフの場合$r=2$で既に新しくなっている。
論文 参考訳（メタデータ） (2023-04-17T10:38:08Z) - Online Learning with Adversaries: A Differential-Inclusion Analysis [52.43460995467893]
我々は,完全に非同期なオンラインフェデレート学習のための観察行列ベースのフレームワークを提案する。
我々の主な結果は、提案アルゴリズムがほぼ確実に所望の平均$mu.$に収束することである。
新たな差分包摂型2時間スケール解析を用いて,この収束を導出する。
論文 参考訳（メタデータ） (2023-04-04T04:32:29Z) - A sublinear query quantum algorithm for s-t minimum cut on dense simple
graphs [1.0435741631709405]
グラフにおける$soperatorname-t$最小カットは、削除が$s$と$t$を切断するエッジの最小ウェイトサブセットに対応する。
この研究では、無向グラフ上の最小$soperatorname-t$カット問題に対する量子アルゴリズムを記述する。
論文 参考訳（メタデータ） (2021-10-29T07:35:46Z) - Fast Graph Sampling for Short Video Summarization using Gershgorin Disc
Alignment [52.577757919003844]
高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。
実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
論文 参考訳（メタデータ） (2021-10-21T18:43:00Z) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z) - Simple vertex coloring algorithms [2.8808678188754637]
1 + epsilon)Delta$-coloring に対して簡単なアルゴリズムを与える。
これは$tildeO(epsilon-1n4/3)$クエリを生成する量子クエリアルゴリズムに適応することができる。
論文 参考訳（メタデータ） (2021-02-14T07:27:10Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。