論文の概要: Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice
Gauge Theory
- arxiv url: http://arxiv.org/abs/2202.08817v1
- Date: Thu, 17 Feb 2022 18:39:42 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-25 12:39:03.046298
- Title: Solving Hamiltonian Cycle Problem using Quantum $\mathbb{Z}_2$ Lattice
Gauge Theory
- Title（参考訳）: 量子$\mathbb{z}_2$格子ゲージ理論を用いたハミルトニアンサイクル問題の解法
- Authors: Xiaopeng Cui, Yu Shi
- Abstract要約: グラフ理論におけるハミルトンサイクル(HC)問題は、よく知られたNP完全問題である。
グラフを双対とする格子上で定義される$mathbbZ$格子ゲージ理論の観点でアプローチを提案する。
小さなグラフのランダムなサンプルでは、$sqrtN_hc$における$g_c$、$N_hc$がHCの数であり、$Nにおける$frac1g_c$の平均値に依存することが示される。
- 参考スコア（独自算出の注目度）: 9.83302372715731
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The Hamiltonian cycle (HC) problem in graph theory is a well-known
NP-complete problem. We present an approach in terms of $\mathbb{Z}_2$ lattice
gauge theory (LGT) defined on the lattice with the graph as its dual. When the
coupling parameter $g$ is less than the critical value $g_c$, the ground state
is a superposition of all configurations with closed strings of spins in a same
single-spin state, which can be obtained by using an adiabatic quantum
algorithm with time complexity $O(\frac{1}{g_c^2} \sqrt{ \frac{1}{\varepsilon}
N_e^{3/2}(N_v^3 + \frac{N_e}{g_c}}))$, where $N_v$ and $N_e$ are the numbers of
vertices and edges of the graph respectively. A subsequent search for a HC
among those closed-strings solves the HC problem. For some random samples of
small graphs, we demonstrate that the dependence of the average value of $g_c$
on $\sqrt{N_{hc}}$, $N_{hc}$ being the number of HCs, and that of the average
value of $\frac{1}{g_c}$ on $N_e$ are both linear. It is thus suggested that
for some graphs, the HC problem may be solved in polynomial time. A possible
quantum algorithm using $g_c$ to infer $N_{hc}$ is also discussed.
- Abstract（参考訳）: グラフ理論におけるハミルトンサイクル(HC)問題は、よく知られたNP完全問題である。
我々は、グラフを双対とする格子上で定義される {\mathbb{z}_2$ lattice gauge theory (lgt) という観点からのアプローチを示す。
結合パラメータ $g$ が臨界値 $g_c$ よりも小さい場合、基底状態は、同じシングルスピン状態のスピンの閉文字列を持つ全ての構成の重ね合わせであり、時間複雑性を持つ断熱量子アルゴリズム $o(\frac{1}{g_c^2} \sqrt{ \frac{1}{\varepsilon} n_e^{3/2}(n_v^3 + \frac{n_e}{g_c}})$, ここで $n_v$ と $n_e$ はそれぞれグラフの頂点と辺の数である。
その後の閉文字列間のhcの探索は、hc問題を解く。
小さなグラフのランダムな例では、$\sqrt{n_{hc}}$, $n_{hc}$ の平均値が hcs の数、$\frac{1}{g_c}$ の平均値が $n_e$ に対して線型であることが示されている。
したがって、いくつかのグラフではhc問題は多項式時間で解くことができる。
また、$g_c$を用いて$N_{hc}$を推論できる量子アルゴリズムについても論じる。
関連論文リスト
- Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
連続時間量子ウォーク(CTQW)は、量子コンピューティングにおいて重要な役割を果たす。
CTQWを効率的に実装する方法は難しい問題である。
本稿では,スパースグラフ上でのCTQWの実装について検討する。
論文 参考訳（メタデータ） (2024-08-20T05:20:55Z) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳（メタデータ） (2024-06-25T06:07:20Z) - Efficient Sampling on Riemannian Manifolds via Langevin MCMC [51.825900634131486]
本稿では,Gibs 分布 $d pi* = eh d vol_g$ over aian manifold $M$ via (geometric) Langevin MCMC。
この結果は、$pi*$ が非指数的であり、$Mh$ が負のリッチ曲率を持つような一般的な設定に適用できる。
論文 参考訳（メタデータ） (2024-02-15T22:59:14Z) - A Quantum Approximation Scheme for k-Means [0.16317061277457]
QRAMモデルにおける古典的な$k$-meansクラスタリング問題に対する量子近似スキームを提案する。
我々の量子アルゴリズムは、時間$tildeO left(2tildeO(frackvarepsilon) eta2 dright)$で実行される。
教師なし学習の以前の研究とは異なり、我々の量子アルゴリズムは量子線型代数のサブルーチンを必要としない。
論文 参考訳（メタデータ） (2023-08-16T06:46:37Z) - 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) - The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits [0.0]
量子回路におけるパターンマッチングを同時に行うアルゴリズムを提案する。
量子回路の場合、量子ビットの最大数から得られる境界を表現することができる。
論文 参考訳（メタデータ） (2023-02-13T22:09:02Z) - Near-optimal fitting of ellipsoids to random points [68.12685213894112]
楕円体をランダムな点に合わせるという基本的な問題は、低ランク行列分解、独立成分分析、主成分分析に関係している。
我々はこの予想を、ある$n = Omega(, d2/mathrmpolylog(d))$ に対する適合楕円体を構成することで対数的因子まで解決する。
我々の証明は、ある非標準確率行列の便利な分解を用いて、サンダーソン等最小二乗構成の実現可能性を示す。
論文 参考訳（メタデータ） (2022-08-19T18:00:34Z) - Accelerated Gradient Tracking over Time-varying Graphs for Decentralized Optimization [59.65871549878937]
実用的な単一ループ加速勾配追跡には$O(fracgamma1-sigma_gamma)2sqrtfracLepsilon)$が必要であることを証明している。
我々の収束率は$O(frac1epsilon5/7)$と$O(fracLmu)5/7frac1(1-sigma)1.5logfrac1epsilon)$よりも大幅に改善した。
論文 参考訳（メタデータ） (2021-04-06T15:34:14Z) - Convergence of Graph Laplacian with kNN Self-tuned Kernels [14.645468999921961]
自己チューニングされたカーネルは、各点に$sigma_i$ を $k$-nearest neighbor (kNN) 距離で適応的に設定する。
本稿では、グラフラプラシアン作用素$L_N$を、kNN自己チューニングカーネルの新しい族に対する多様体(重み付き)ラプラシアンに収束することを証明する。
論文 参考訳（メタデータ） (2020-11-03T04:55:33Z) - Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language [1.0118253437732931]
2つの問題の量子クエリ複雑性について検討する。
グリッドのエッジのいくつかが欠落している場合、グリッドグラフ上の2次元の接続問題を考える。
平衡括弧」問題をグリッドに埋め込むことで、有向2Dグリッドに対して$Omega(n1.5-epsilon)$、無向2Dグリッドに対して$Omega(n2-epsilon)$の低い境界を示す。
論文 参考訳（メタデータ） (2020-07-06T09:51:41Z) - Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast
Algorithm [100.11971836788437]
固定支持ワッサーシュタインバリセンタ問題(FS-WBP)について検討する。
我々は,有望な反復的ブレグマン射影 (IBP) アルゴリズムであるtextscFastIBP の,証明可能な高速なテキスト決定論的変種を開発する。
論文 参考訳（メタデータ） (2020-02-12T03:40:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。