論文の概要: On the Quantum Chromatic Numbers of Small Graphs
- arxiv url: http://arxiv.org/abs/2311.08194v1
- Date: Tue, 14 Nov 2023 14:27:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-15 13:50:13.020399
- Title: On the Quantum Chromatic Numbers of Small Graphs
- Title（参考訳）: 小さなグラフの量子色数について
- Authors: Olivier Lalonde
- Abstract要約: パラメータ $chi(1)_q$ と $chi(2)_q$ の分離の最小の例を示す。
さらに$G_21$は、パラメータ $chi(1)_q$ と $chi(2)_q$ の最初の証明可能な分離を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We make two contributions pertaining to the study of the quantum chromatic
numbers of small graphs. Firstly, in an elegant paper, Man\v{c}inska and
Roberson [\textit{Baltic Journal on Modern Computing}, 4(4), 846-859, 2016]
gave an example of a graph $G_{14}$ on 14 vertices with quantum chromatic
number 4 and classical chromatic number 5, and conjectured that this is the
smallest graph exhibiting a separation between the two parameters. We describe
a computer-assisted proof of this conjecture, thereby resolving a longstanding
open problem in quantum graph theory. Our second contribution pertains to the
study of the rank-$r$ quantum chromatic numbers. While it can now be shown that
for every $r$, $\chi_q$ and $\chi^{(r)}_q$ are distinct, few small examples of
separations between these parameters are known. We give the smallest known
example of such a separation in the form of a graph $G_{21}$ on 21 vertices
with $\chi_q(G_{21}) = \chi^{(2)}_q(G_{21}) = 4$ and $ \xi(G_{21}) =
\chi^{(1)}_q(G_{21}) = \chi(G_{21}) = 5$. The previous record was held by a
graph $G_{msg}$ on 57 vertices that was first considered in the aforementioned
paper of Man\v{c}inska and Roberson and which satisfies $\chi_q(G_{msg}) = 3$
and $\chi^{(1)}_q(G_{msg}) = 4$. In addition, $G_{21}$ provides the first
provable separation between the parameters $\chi^{(1)}_q$ and $\chi^{(2)}_q$.
We believe that our techniques for constructing $G_{21}$ and lower bounding its
orthogonal rank could be of independent interest.
- Abstract（参考訳）: 我々は、小さなグラフの量子色数の研究に2つの貢献をする。
まず、エレガントな論文である Man\v{c}inska と Roberson [\textit{Baltic Journal on Modern Computing}, 4(4), 846-859, 2016] において、量子色数 4 と古典色数 5 を持つ 14 の頂点上のグラフ $G_{14}$ の例を示し、このグラフは二つのパラメータの分離を示す最小のグラフであると推測した。
本稿では、この予想のコンピュータ支援による証明を説明し、量子グラフ理論における長年のオープン問題を解く。
第2の貢献は、ランク-$r$量子色数の研究に関するものである。
すべての$r$, $\chi_q$ と $\chi^{(r)}_q$ は異なるが、これらのパラメータ間の分離の小さな例はほとんど知られていない。
そのような分離の最小の例として、$\chi_q(g_{21}) = \chi^{(2)}_q(g_{21}) = 4$ および $ \xi(g_{21}) = \chi^{(1)}_q(g_{21}) = \chi(g_{21}) = 5$ の21頂点上のグラフ $g_{21}$ がある。
前回の記録は、前述のMan\v{c}inska と Roberson の論文で最初に考慮された57の頂点上のグラフ $G_{msg}$ で保持され、$\chi_q(G_{msg}) = 3$ と $\chi^{(1)}_q(G_{msg}) = 4$ を満たす。
さらに、$g_{21}$ はパラメータ $\chi^{(1)}_q$ と $\chi^{(2)}_q$ の間の最初の証明可能な分離を提供する。
我々は、G_{21}$ と、その直交ランクを下限とする我々の手法は、独立した関心を持つことができると考えている。
関連論文リスト
- 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) - 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) - Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect
Alignment [51.74913666829224]
強い反相関を持つデータセットに対して、適切なグラフは正および負のエッジ重みの両方を含むことを示す。
本稿では,平衡符号グラフの概念に着目した線形時間符号グラフサンプリング手法を提案する。
実験結果から, 署名付きグラフサンプリング手法は, 各種データセットにおいて, 既存の高速サンプリング方式よりも優れた性能を示した。
論文 参考訳（メタデータ） (2022-08-18T09:19:01Z) - Beyond the Berry Phase: Extrinsic Geometry of Quantum States [77.34726150561087]
状態の量子多様体のすべての性質がゲージ不変のバーグマンによって完全に記述されることを示す。
偏光理論への我々の結果の即時適用について述べる。
論文 参考訳（メタデータ） (2022-05-30T18:01:34Z) - Repeated Averages on Graphs [2.363388546004777]
我々は$frac(1-epsilon)2log2nlog n-O(n)$が$n$ノード上のすべての連結グラフに対する一般的な下界であることを証明する。
また、星、膨張星、ダンベル、サイクルなど、いくつかの重要なグラフの族に対して、$t_epsilon,1$の急激な等級も得られる。
論文 参考訳（メタデータ） (2022-05-09T20:18:31Z) - Random Graph Matching in Geometric Models: the Case of Complete Graphs [21.689343447798677]
本稿では, エッジ重み付き2つの完全グラフが潜在測地によって相関する問題について検討する。
近似最大極大推定器を導出し、高い確率で$pi*$の完全回復を確実に達成する。
副次的な発見として、[Ume88] の有望なスペクトルアルゴリズムが幾何モデルにおける最大可能性のさらなる近似として現れることを示す。
論文 参考訳（メタデータ） (2022-02-22T04:14:45Z) - 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) - Exact Matching of Random Graphs with Constant Correlation [2.578242050187029]
本稿では, ErdHos--R'enyi グラフに対するグラフマッチングやネットワークアライメントの問題を扱う。
これはグラフ同型問題のうるさい平均ケース版と見なすことができる。
論文 参考訳（メタデータ） (2021-10-11T05:07:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。