論文の概要: Quantum walk mixing is faster than classical on periodic lattices
- arxiv url: http://arxiv.org/abs/2309.16352v1
- Date: Thu, 28 Sep 2023 11:23:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 15:01:18.341181
- Title: Quantum walk mixing is faster than classical on periodic lattices
- Title（参考訳）: 量子ウォーク混合は周期格子上の古典よりも高速である
- Authors: Shyam Dhamapurkar and Xiu-Hao Deng
- Abstract要約: 従来のランダムウォークに比べて高速な混合を実現する2つの量子ウォークを提案する。
最終的な目標は、正則グラフ上の量子ウォークの一般予想を証明することである。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work focuses on the quantum mixing time, which is crucial for efficient
quantum sampling and algorithm performance. We extend Richter's previous
analysis of continuous time quantum walks on the periodic lattice
$\mathbb{Z}_{n_1}\times \mathbb{Z}_{n_2}\times \dots \times \mathbb{Z}_{n_d}$,
allowing for non-identical dimensions $n_i$. We present two quantum walks that
achieve faster mixing compared to classical random walks. The first is a
coordinate-wise quantum walk with a mixing time of $O\left(\left(\sum{i=1}^{d}
n_i \right) \log{(d/\epsilon)}\right)$ and $O(d \log(d/\epsilon))$
measurements. The second is a continuous-time quantum walk with
$O(\log(1/\epsilon))$ measurements, conjectured to have a mixing time of
$O\left(\sum_{i=1}^d n_i(\log(n_1))^2 \log(1/\epsilon)\right)$. Our results
demonstrate a quadratic speedup over classical mixing times on the generalized
periodic lattice. We provide analytical evidence and numerical simulations
supporting the conjectured faster mixing time. The ultimate goal is to prove
the general conjecture for quantum walks on regular graphs.
- Abstract（参考訳）: この研究は、効率的な量子サンプリングとアルゴリズム性能に不可欠な量子混合時間に焦点を当てている。
我々は、周期格子 $\mathbb{Z}_{n_1}\times \mathbb{Z}_{n_2}\times \dots \times \mathbb{Z}_{n_d}$ 上の連続時間量子ウォークに関するリヒターの以前の分析を拡張し、非同一次元を$n_i$ とする。
従来のランダムウォークよりも高速な混合を実現する2つの量子ウォークを示す。
1つは座標回りの量子ウォークで、混合時間は$o\left(\sum{i=1}^{d} n_i \right) \log{(d/\epsilon)}\right)$と$o(d \log(d/\epsilon)$である。
2つ目は、$O(\log(1/\epsilon))$の連続時間量子ウォークで、$O\left(\sum_{i=1}^d n_i(\log(n_1))^2 \log(1/\epsilon)\right)$の混合時間を持つと推測されている。
その結果, 一般化周期格子上の古典混合時間の二次速度向上を示す。
予測されたより高速な混合時間を支える解析的証拠と数値シミュレーションを提供する。
最終的な目標は、正則グラフ上の量子ウォークの一般予想を証明することである。
関連論文リスト
- Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
一般化されたボトルネック補題を用いて、これらのツールの量子一般化を示す。
この補題は、古典的なハミング距離に類似する距離の量子測度に焦点を当てるが、一意に量子原理に根ざしている。
サブ線形障壁でさえも、ファインマン・カック法を用いて古典的から量子的なものを持ち上げて、厳密な下界の$T_mathrmmix = 2Omega(nalpha)$を確立する。
論文 参考訳（メタデータ） (2024-11-06T22:51:27Z) - Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。
提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。
そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
論文 参考訳（メタデータ） (2024-05-14T15:28:37Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Quantum walks advantage on the dihedral group for uniform sampling
problem [0.0]
歩行を混合することは、マルコフ連鎖が群に対する定常分布を近似する過程である。
量子ウォークは古典的な場合よりも時間混合の潜在的な利点を示しているが、有限群の場合では一般的な証明が欠如している。
この研究は、非アーベル群、グラフ同型テスト等をサンプリングするアルゴリズムに潜在的な応用がある。
論文 参考訳（メタデータ） (2023-12-25T11:21:55Z) - Quantum Speedups for Zero-Sum Games via Improved Dynamic Gibbs Sampling [30.53587208999909]
我々は、ゼロサムゲームにおける$epsilon$-approximate Nash平衡を、有界なエントリを持つ$m倍n$ペイオフ行列で計算するための量子アルゴリズムを与える。
ペイオフ行列にアクセスするための標準的な量子オラクルが与えられたとき、我々のアルゴリズムは$widetildeO(sqrtm + ncdot epsilon-2.5 + epsilon-3)$で実行され、$epsilon$-approximate Nash平衡の古典的な表現を出力する。
論文 参考訳（メタデータ） (2023-01-10T02:56:49Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - The Quantum and Classical Streaming Complexity of Quantum and Classical
Max-Cut [0.07614628596146598]
グラフストリーミング問題であるMax-Cutとその量子アナログQuantum Max-Cutの空間複雑性について検討する。
我々の研究は、$textrmo(n)$ space を用いて量子および古典マックスキュートの量子的および古典的近似性を解決する。
論文 参考訳（メタデータ） (2022-06-01T03:40:56Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。
連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
論文 参考訳（メタデータ） (2021-12-23T17:57:49Z) - Quantum Gram-Schmidt Processes and Their Application to Efficient State
Read-out for Quantum Algorithms [87.04438831673063]
本稿では、生成した状態の古典的ベクトル形式を生成する効率的な読み出しプロトコルを提案する。
我々のプロトコルは、出力状態が入力行列の行空間にある場合に適合する。
我々の技術ツールの1つは、Gram-Schmidt正則手順を実行するための効率的な量子アルゴリズムである。
論文 参考訳（メタデータ） (2020-04-14T11:05:26Z) - Quantum Coupon Collector [62.58209964224025]
我々は、$k$-要素集合$Ssubseteq[n]$が、その要素の一様重ね合わせ$|Srangleからいかに効率的に学習できるかを研究する。
我々は、$k$と$n$ごとに必要となる量子サンプルの数に厳密な制限を与え、効率的な量子学習アルゴリズムを与える。
論文 参考訳（メタデータ） (2020-02-18T16:14:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。