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

• arxiv url: http://arxiv.org/abs/2312.15693v2
• Date: Fri, 29 Nov 2024 14:15:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-12-02 15:16:03.718708
• Title: Quantum walks advantage on the dihedral group for uniform sampling problem
• Title（参考訳）: 均一サンプリング問題に対する二面体群上の量子ウォークの優位性
• Authors: Shyam Dhamapurkar, Yuhang Dang, Saniya Wagh, Xiu-Hao Deng,
• Abstract要約: 本稿では、ケイリーグラフ上での量子ウォーク混合の一般的な理解を前進させる。 これは、D_2n$で連続時間量子ウォークによって達成された改良された混合時間を強調する。 この研究は、非アーベル群に基づくサンプリング問題のクラスに対するアルゴリズムに潜在的な応用をもたらす。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Random walk algorithms are crucial for sampling and approximation problems in statistical physics and theoretical computer science. The mixing property is necessary for Markov chains to approach stationary distributions and is facilitated by walks. Quantum walks show promise for faster mixing times than classical methods but lack universal proof, especially in finite group settings. 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 typically takes at least order $\Omega(n^2 \log(1/2\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 a class of sampling problems based on non-abelian groups.
• Abstract（参考訳）: ランダムウォークアルゴリズムは、統計物理学および理論計算機科学におけるサンプリングおよび近似問題に不可欠である。 マルコフ連鎖が定常分布に近づくためには混合特性が必要であり、歩行により容易になる。 量子ウォークは、古典的手法よりも高速な混合時間を示すが、特に有限群設定において普遍的な証明が欠如している。 ここでは、二面体群$D_{2n}$のケイリーグラフ上の連続時間量子ウォークを、最小の逆対称部分集合によって生成される奇数$n$に対して調べる。 これらのケイリーグラフ上の古典的な混合時間とは対照的に、通常、少なくとも位数$\Omega(n^2 \log(1/2\epsilon))$, $D_{2n}$の連続時間量子ウォーク混合時間は$O(n (\log n)^5 \log(1/\epsilon))$の次数$O(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)

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

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