論文の概要: 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)$の混合時間を持つと推測されている。
その結果, 一般化周期格子上の古典混合時間の二次速度向上を示す。
予測されたより高速な混合時間を支える解析的証拠と数値シミュレーションを提供する。
最終的な目標は、正則グラフ上の量子ウォークの一般予想を証明することである。
関連論文リスト
- Quantum walks advantage on the dihedral group for uniform sampling
problem [0.0]
歩行を混合することは、マルコフ連鎖が群に対する定常分布を近似する過程である。
量子ウォークは古典的な場合よりも時間混合の潜在的な利点を示しているが、有限群の場合では一般的な証明が欠如している。
この研究は、非アーベル群、グラフ同型テスト等をサンプリングするアルゴリズムに潜在的な応用がある。
論文 参考訳(メタデータ) (2023-12-25T11:21:55Z) - Spacetime-Efficient Low-Depth Quantum State Preparation with
Applications [93.56766264306764]
任意の量子状態を作成するための新しい決定論的手法は、以前の方法よりも少ない量子資源を必要とすることを示す。
我々は、量子機械学習、ハミルトンシミュレーション、方程式の線形系を解くことなど、この能力が役立ついくつかのアプリケーションを強調した。
論文 参考訳(メタデータ) (2023-03-03T18:23:20Z) - 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) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳(メタデータ) (2022-10-12T17:54:02Z) - 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) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳(メタデータ) (2022-01-31T22:19:49Z) - Quadratic speedup for spatial search by continuous-time quantum walk [0.0]
連続時間量子ウォークは、空間探索として知られるグラフ内のマークされたノードの集合の中のノードを見つけるという根本的な問題に取り組むためのフレームワークを提供する。
連続時間量子ウォーク探索アルゴリズムでは,任意のノード数を持つグラフにおいて,従来のランダムウォークよりも2次的に高速なマークノードを見つけることができる。
論文 参考訳(メタデータ) (2021-12-23T17:57:49Z) - Quantum algorithms for escaping from saddle points [7.191453718557392]
本研究では,サドル点からの脱出を保証できる保証付き量子アルゴリズムについて検討する。
我々の主な貢献は、勾配降下法における古典的摂動を置き換えるという考え方である。
また、Jordanによる量子勾配計算アルゴリズムの使い方を示す。
論文 参考訳(メタデータ) (2020-07-20T16:42:53Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。