論文の概要: Toward Minimum Graphic Parity Networks
- arxiv url: http://arxiv.org/abs/2509.10070v1
- Date: Fri, 12 Sep 2025 09:00:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-09-15 16:03:08.022981
- Title: Toward Minimum Graphic Parity Networks
- Title（参考訳）: 最小グラフパリティネットワークを目指して
- Authors: Yixin Cao, Yiren Lu, Junhong Nie, Xiaoming Sun, Guojing Tian,
- Abstract要約: グラフ$G$のグラフパリティネットワークは、CNOTゲートのみからなる量子回路である。
我々は、$n$頂点と$m$エッジを持つ連結グラフに対するグラフパリティネットワークが、少なくとも$m+n-1$ゲートを必要とすることを示す。
これらのグラフはすべて、新しく定義されたグラフクラスに属すると推測する。
- 参考スコア（独自算出の注目度）: 9.459397370755115
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Quantum circuits composed of CNOT and $R_z$ are fundamental building blocks of many quantum algorithms, so optimizing the synthesis of such quantum circuits is crucial. We address this problem from a theoretical perspective by studying the graphic parity network synthesis problem. A graphic parity network for a graph $G$ is a quantum circuit composed solely of CNOT gates where each edge of $G$ is represented in the circuit, and the final state of the wires matches the original input. We aim to synthesize graphic parity networks with the minimum number of gates, specifically for quantum algorithms addressing combinatorial optimization problems with Ising formulations. We demonstrate that a graphic parity network for a connected graph with $n$ vertices and $m$ edges requires at least $m+n-1$ gates. This lower bound can be improved to $m+\Omega(m) = m+\Omega(n^{1.5})$ when the shortest cycle in the graph has a length of at least five. We complement this result with a simple randomized algorithm that synthesizes a graphic parity network with expected $m + O(n^{1.5}\sqrt{\log n})$ gates. Additionally, we begin exploring connected graphs that allow for graphic parity networks with exactly $m+n-1$ gates. We conjecture that all such graphs belong to a newly defined graph class. Furthermore, we present a linear-time algorithm for synthesizing minimum graphic parity networks for graphs within this class. However, this graph class is not closed under taking induced subgraphs, and we show that recognizing it is $\textsf{NP}$-complete, which is complemented with a fixed-parameter tractable algorithm parameterized by the treewidth.
- Abstract（参考訳）: CNOTと$R_z$からなる量子回路は多くの量子アルゴリズムの基本構成ブロックであるため、そのような量子回路の合成を最適化することが不可欠である。
本稿では, グラフパリティネットワーク合成問題を研究することにより, 理論的観点からこの問題に対処する。
グラフ$G$のグラフパリティネットワーク(英: graphic parity network)は、CNOTゲートのみからなる量子回路で、G$の各エッジが回路内に表現され、ワイヤの最終状態が元の入力と一致する。
我々は最小ゲート数でグラフパリティネットワークを合成することを目指しており、特にIsingの定式化による組合せ最適化問題に対処する量子アルゴリズムを対象としている。
我々は、$n$頂点と$m$エッジを持つ連結グラフに対するグラフパリティネットワークが少なくとも$m+n-1$ゲートを必要とすることを示した。
この下限は$m+\Omega(m) = m+\Omega(n^{1.5})$に改善することができる。
この結果を単純なランダム化アルゴリズムで補完し、期待される$m + O(n^{1.5}\sqrt{\log n})$ gatesでグラフパリティネットワークを合成する。
さらに、正確な$m+n-1$ゲートを持つグラフパリティネットワークを実現するコネクテッドグラフの探索も開始する。
これらのグラフはすべて、新しく定義されたグラフクラスに属すると推測する。
さらに,このクラス内のグラフに対する最小グラフパリティネットワークを合成するための線形時間アルゴリズムを提案する。
しかし、このグラフクラスは、誘導された部分グラフを取る際には閉じられず、木幅でパラメータ化された固定パラメータ抽出可能なアルゴリズムを補完する$\textsf{NP}$-completeであることが示される。
関連論文リスト
- Universal graph representation of stabilizer codes [1.6385815610837167]
安定化器符号の表現を特定の構造を持つグラフとして導入する。
グラフ表現は、コード構築とアルゴリズムの両方について洞察を与える。
距離、重み、符号化回路深さなどの鍵符号特性はすべてグラフ次数によって制御される。
論文 参考訳（メタデータ） (2024-11-07T18:58:58Z) - Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。
CTQWを効率的に実装する方法は難しい問題である。
本稿では,スパースグラフ上でのCTQWの実装について検討する。
論文 参考訳（メタデータ） (2024-08-20T05:20:55Z) - Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。
我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。
提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
論文 参考訳（メタデータ） (2024-08-03T20:08:02Z) - Graph Mixup with Soft Alignments [49.61520432554505]
本研究では,画像上での使用に成功しているミキサアップによるグラフデータの増大について検討する。
ソフトアライメントによるグラフ分類のための簡易かつ効果的な混合手法であるS-Mixupを提案する。
論文 参考訳（メタデータ） (2023-06-11T22:04:28Z) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Learning quantum graph states with product measurements [22.463154358632472]
我々は、未知の$n$-qubit量子グラフ状態の同一コピーを製品測定で学習する問題を考察する。
このようなグラフ状態の複数の同一コピー上で製品計測を用いて学習する明示的なアルゴリズムを詳述する。
論文 参考訳（メタデータ） (2022-05-13T02:55:21Z) - AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph
Convolution [79.44066256794187]
我々は、グラフ畳み込みネットワーク(GCN)を構築するために使用される生成グラフモデルを導入することにより、グラフに非グラフデータセットを変換する方法を示す。
アンカーによって構築された二部グラフは、データの背後にある高レベル情報を利用するために動的に更新される。
理論的には、単純な更新が退化につながることを証明し、それに従って特定の戦略が設計される。
論文 参考訳（メタデータ） (2021-11-12T07:08:13Z) - 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) - Random Graph Matching with Improved Noise Robustness [2.294014185517203]
本稿では確率モデルに基づくグラフマッチングの新しいアルゴリズムを提案する。
我々のアルゴリズムは、$alpha le 1 / (log log n)C$ のとき、その基礎となるマッチングを高い確率で復元する。
これにより、以前の作業で達成された条件 $alpha le 1 / (log n)C$ が改善される。
論文 参考訳（メタデータ） (2021-01-28T02:39:27Z) - Scalable Deep Generative Modeling for Sparse Graphs [105.60961114312686]
既存のディープニューラルネットワーク手法では、隣接行列を構築することで、$Omega(n2)$複雑さを必要とする。
我々は,この空間を利用して完全隣接行列を生成する新しい自己回帰モデルBiGGを開発した。
トレーニング中、この自己回帰モデルは$O(log n)$同期ステージで並列化できる。
論文 参考訳（メタデータ） (2020-06-28T04:37:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。