論文の概要: Quantum walks advantage on the dihedral group for uniform sampling problem

• arxiv url: http://arxiv.org/abs/2312.15693v1
• Date: Mon, 25 Dec 2023 11:21:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-27 16:52:24.344108
• Title: Quantum walks advantage on the dihedral group for uniform sampling problem
• Title（参考訳）: 均一サンプリング問題に対する二面群上の量子ウォーキングの利点
• Authors: Shyam Dhamapurkar, Yuhang Dang, Saniya Wagh, and Xiu-Hao Deng
• Abstract要約: 歩行を混合することは、マルコフ連鎖が群に対する定常分布を近似する過程である。 量子ウォークは古典的な場合よりも時間混合の潜在的な利点を示しているが、有限群の場合では一般的な証明が欠如している。 この研究は、非アーベル群、グラフ同型テスト等をサンプリングするアルゴリズムに潜在的な応用がある。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random walk algorithms, including sampling and approximations, have played a significant role in statistical physics and theoretical computer science. Mixing through walks is the process for a Markov chain to approximate a stationary distribution for a group. Quantum walks have shown potential advantages in mixing time over the classical case but lack general proof in the finite group case. Here, we investigate the continuous-time quantum walks on Cayley graphs of the dihedral group $D_{2n}$ for odd $n$, generated by the smallest inverse closed symmetric subset. We present a significant finding that, in contrast to the classical mixing time on these Cayley graphs, which is typically of order $O(n^2 \log(2n/\epsilon))$, the continuous-time quantum walk mixing time on $D_{2n}$ is of order $O(n (\log n)^5 \log(1/\epsilon))$, achieving a quadratic improvement over the classical case. Our paper advances the general understanding of quantum walk mixing on Cayley graphs, highlighting the improved mixing time achieved by continuous-time quantum walks on $D_{2n}$. This work has potential applications in algorithms for sampling non-abelian groups, graph isomorphism tests, etc.
• Abstract（参考訳）: サンプリングや近似を含むランダムウォークアルゴリズムは、統計物理学や理論計算機科学において重要な役割を果たす。 歩行を混合することは、マルコフ連鎖が群に対する定常分布を近似する過程である。 量子ウォークは古典的な場合よりも時間混合の潜在的な利点を示しているが、有限群の場合では一般的な証明がない。 ここでは、最小の逆対称部分集合によって生成される奇数$n$に対して、二面体群 $d_{2n}$ のケイリーグラフ上の連続時間量子ウォークを調べる。 ケイリーグラフ上の古典的な混合時間(典型的には$O(n^2 \log(2n/\epsilon))$)とは対照的に、$D_{2n}$の連続時間量子ウォーク混合時間は$O(n(\log n)^5 \log(1/\epsilon)$である。 本稿では,cayleyグラフ上の量子ウォーク混合の一般理解を深め,$d_{2n}$における連続時間量子ウォークによる混合時間の改善を強調する。 この研究は、非可換群やグラフ同型テストなどをサンプリングするアルゴリズムに潜在的な応用がある。

関連論文リスト

• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。 この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。 サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
  論文  参考訳（メタデータ） (2024-11-06T22:51:27Z)
• KPZ scaling from the Krylov space [83.88591755871734]
  近年,Cardar-Parisi-Zhangスケーリングをリアルタイムの相関器や自動相関器に示す超拡散が報告されている。 これらの結果から着想を得て,Krylov演算子に基づく相関関数のKPZスケーリングについて検討する。
  論文  参考訳（メタデータ） (2024-06-04T20:57:59Z)
• Non-uniform Mixing of Quantum Walks on the Symmetric Group [0.0]
  我々は、対称群の表現論を用いて、セゲディ・ウォーク作用素のスペクトルを分析する。 我々の手法は一般であり、他の非可換群に対して同様の解析結果を得るために応用できると信じている。
  論文  参考訳（メタデータ） (2023-11-06T03:17:36Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  非対数確率分布からサンプリングする量子アルゴリズムを提案する。 f$ は有限和 $f(x):= frac1Nsum_k=1N f_k(x)$ と書くことができる。
  論文  参考訳（メタデータ） (2023-10-17T17:55:32Z)
• Quantum walk mixing is faster than classical on periodic lattices [0.0]
  従来のランダムウォークに比べて高速な混合を実現する2つの量子ウォークを提案する。 最終的な目標は、正則グラフ上の量子ウォークの一般予想を証明することである。
  論文  参考訳（メタデータ） (2023-09-28T11:23:10Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Discrete Quantum Walks on the Symmetric Group [0.0]
  量子ウォークでは、伝播は量子力学的規則によって制御され、ランダムウォークを量子状態へ一般化する。 本稿では,非可換フーリエ解析によるツールを用いた離散時間生成量子ウォーク(DTCQW)モデルについて検討する。 具体的には、対称群(sym$)が生成するケイリーグラフ上の DTCQW を適切な生成集合で特徴づけることに興味がある。
  論文  参考訳（メタデータ） (2022-03-28T23:48:08Z)
• Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
  連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。 連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
  論文  参考訳（メタデータ） (2021-12-23T17:57:49Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  製品公式(英: Product formulas)またはトロッター化(英: Trotterization)は、量子系をシミュレートする最も古い方法であり、いまだに魅力的な方法である。 我々は、ほとんどの入力状態に対して、トロッター誤差が定性的に優れたスケーリングを示すことを証明した。 我々の結果は、平均的なケースにおける量子アルゴリズムの研究の扉を開く。
  論文  参考訳（メタデータ） (2021-11-09T18:49:48Z)
• Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
  時間依存ハミルトニアンの下でのユニタリ進化は、量子ハードウェアにおけるシミュレーションの重要な構成要素である。 本稿では、トロッターステップを1ブロックの量子ゲートに圧縮するアルゴリズムを提案する。 この結果、ハミルトニアンのある種のクラスに対する固定深度時間進化がもたらされる。
  論文  参考訳（メタデータ） (2021-08-06T19:38:01Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。 低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
  論文  参考訳（メタデータ） (2020-05-13T14:53:36Z)

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

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