論文の概要: Symmetric Reduction Techniques for Quantum Graph Colouring

• arxiv url: http://arxiv.org/abs/2510.16784v1
• Date: Sun, 19 Oct 2025 10:16:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 00:56:39.143868
• Title: Symmetric Reduction Techniques for Quantum Graph Colouring
• Title（参考訳）: 量子グラフカラー化のための対称性低減技術
• Authors: Lord Sen, Shyamapada Mukherjee,
• Abstract要約: 本稿では,グラフ着色問題における特殊グラフの削減に有効な量子計算法を提案する。 ゲートの数とイテレーション数は、最先端の量子アルゴリズムと比較して大幅に減少する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: This paper introduces an efficient quantum computing method for reducing special graphs in the context of the graph coloring problem. The special graphs considered include both symmetric and non-symmetric graphs where the axis passes through nodes only, edges only, and both together. The presented method reduces the number of coloring matrices, which is important for realization of the number of quantum states required, from $K^{N}$ to $K^{\frac{N+m}{2}}$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes, where $K$ is the number of colours required and \emph{N} being total number of nodes. Similarly for other types also, the number of quantum states is reduced. The complexity in the number of qubits has been reduced by $\delta C_q= \frac{9N^2}{8}-\frac{3m^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}$ upon one symmetric reduction of graphs, symmetric about an axis passing through $m$ nodes and other types as presented in the paper. Additionally, the number of gates and number of iterations are reduced massively compared to state-of-the-art quantum algorithms. Like for a graph with 20 nodes and symmetric line passing through 2 nodes, the number of iterations decreased from 5157 to 67. Therefore, the procedure presented for solving the graph coloring problem now requires a significantly reduced number of qubits compared to before. The run time of the proposed algorithm for these special type of graphs are reduced from $O(1.9575^{N})$ to $O(1.9575^{(\frac{N+m}{2})})$ upon one symmetric reduction of graphs symmetric about an axis passing through $m$ nodes and similarly for others cases.
• Abstract（参考訳）: 本稿では,グラフ着色問題における特殊グラフの削減に有効な量子計算法を提案する。 考慮された特殊グラフは対称グラフと非対称グラフの両方を含み、軸はノードのみを通過し、エッジのみであり、両方を同時に通過する。 K^{N}$から$K^{\frac{N+m}{2}}$までの量子状態の数を実現するのに重要なカラー行列の数を、$m$ノードを通る軸について対称に1つのグラフを減少させると、$K$は必要な色数であり、 \emph{N} はノードの総数である。 他の型と同様に、量子状態の数は減少する。 量子ビットの数の複雑さは$\delta C_q= \frac{9N^2}{8}-\frac{3Nm^2}{8}-\frac{3Nm}{4}-\frac{N}{4}+\frac{m}{4}$ によって減少し、グラフの1つの対称化では、この論文で示されるような$m$ノードと他の種類の軸について対称となる。 さらに、ゲートの数やイテレーション数は最先端の量子アルゴリズムと比較して大幅に減少する。 20ノードと対称線が2ノードを通過するグラフのように、イテレーションの数は5157から67に減少した。 したがって、グラフ彩色問題を解くために提示される手順は、これまでに比べて大幅に削減されたキュービット数を必要とする。 これらの特殊なグラフに対する提案アルゴリズムの実行時間は、$O(1.9575^{N})$から$O(1.9575^{(\frac{N+m}{2})})$に短縮される。

関連論文リスト

• Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry [2.6140509675507384]
  我々は、$n$-vertex graph $G$の頂点を$n$-leafのルートツリー$mathcalB$の葉に埋め込む問題を考える。 我々は、グラフの異なる族における渋滞境界を、正規構造(ハイパーキューブと格子)、ランダムグラフ、量子回路のテンソルネットワーク表現と数値的に比較する。
  論文  参考訳（メタデータ） (2025-10-03T04:58:40Z)
• Toward Minimum Graphic Parity Networks [9.459397370755115]
  グラフ$G$のグラフパリティネットワークは、CNOTゲートのみからなる量子回路である。 我々は、$n$頂点と$m$エッジを持つ連結グラフに対するグラフパリティネットワークが、少なくとも$m+n-1$ゲートを必要とすることを示す。 これらのグラフはすべて、新しく定義されたグラフクラスに属すると推測する。
  論文  参考訳（メタデータ） (2025-09-12T09:00:38Z)
• Spectral Gaps with Quantum Counting Queries and Oblivious State Preparation [47.600794349481966]
  本研究では、量子ビットの対数数を用いて、加算誤差$epsilonDelta_k$まで値を近似する量子アルゴリズムを提案する。 この分析における重要な技術的ステップは、適切なランダム初期状態の準備であり、最終的には閾値よりも小さい固有値の数を効率的に数えることができる。
  論文  参考訳（メタデータ） (2025-08-28T17:04:18Z)
• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  本稿では,QUBO行列におけるテクステミシンメトリの概念を紹介する。 提案アルゴリズムは結合数と回路深さを最大45%削減することを示した。
  論文  参考訳（メタデータ） (2024-12-18T12:05:18Z)
• Reducing QAOA Circuit Depth by Factoring out Semi-Symmetries [4.958204128486634]
  修正 QUBO 行列 $Q_Hamilton$ が元の $Q$ と同じエネルギースペクトルを記述することを示す。 提案アルゴリズムは結合数を最大49%$、回路深さを最大41%$に削減した。
  論文  参考訳（メタデータ） (2024-11-13T18:04:01Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。 振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
  論文  参考訳（メタデータ） (2022-01-31T22:19:49Z)
• Robust Estimation for Random Graphs [47.07886511972046]
  我々は、$n$ノード上のErdHos-R'enyiランダムグラフのパラメータ$p$を頑健に推定する問題について検討する。 情報理論の限界であるすべての$gamma 1/2$に対して、同様の精度で非効率なアルゴリズムを与える。
  論文  参考訳（メタデータ） (2021-11-09T18:43:25Z)
• Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix Factorization [49.090785356633695]
  非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
  論文  参考訳（メタデータ） (2021-06-27T17:25:24Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  微分量子化グラディエントDescence (DQ-GD) が$maxsigma_mathrmGD, rhon 2-R$の線形収縮係数を得ることを示す。 あるクラス内のアルゴリズムは$maxsigma_mathrmGD, 2-R$よりも早く収束できない。
  論文  参考訳（メタデータ） (2020-02-06T20:40:53Z)

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

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