論文の概要: Improved Upper Bounds for the Hitting Times of Quantum Walks
- arxiv url: http://arxiv.org/abs/2005.04062v5
- Date: Tue, 12 Oct 2021 02:48:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-20 20:20:03.515438
- Title: Improved Upper Bounds for the Hitting Times of Quantum Walks
- Title（参考訳）: 量子ウォークのヒット時間に対する上限の改善
- Authors: Yosi Atia and Shantanav Chakraborty
- Abstract要約: 連続時間量子ウォークは、量子アルゴリズムの設計に非常に有用なフレームワークであることが証明されている。
我々は、いくつかのCTQWベースの量子アルゴリズムに適用可能な、量子的ヒット時間に対する上界の改善を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Continuous-time quantum walks have proven to be an extremely useful framework
for the design of several quantum algorithms. Often, the running time of
quantum algorithms in this framework is characterized by the quantum hitting
time: the time required by the quantum walk to find a vertex of interest with a
high probability. In this article, we provide improved upper bounds for the
quantum hitting time that can be applied to several CTQW-based quantum
algorithms. In particular, we apply our techniques to the glued-trees problem,
improving their hitting time upper bound by a polynomial factor: from $O(n^5)$
to $O(n^2\log n)$. Furthermore, our methods also help to exponentially improve
the dependence on precision of the continuous-time quantum walk based algorithm
to find a marked node on any ergodic, reversible Markov chain by Chakraborty et
al. [PRA 102, 022227 (2020)].
- Abstract（参考訳）: 連続時間量子ウォークは、いくつかの量子アルゴリズムの設計において非常に有用なフレームワークであることが証明されている。
しばしば、このフレームワークにおける量子アルゴリズムの実行時間は、量子ウォークが高い確率で興味のある頂点を見つけるのに必要な時間である量子ヒット時間によって特徴づけられる。
本稿では、いくつかのCTQWベースの量子アルゴリズムに適用可能な量子ヒット時間の改善した上限を提供する。
特に, この手法を接着木問題に適用し, 多項式係数による到達時間上限を, $o(n^5)$ から $o(n^2\log n)$ に改善した。
さらに本手法は,連続時間量子ウォークに基づくアルゴリズムの精度依存性を指数関数的に改善し,chakrabortyらによる任意の可逆マルコフ連鎖上のマーキングノードを探索するのに役立つ。
[PRA 102, 022227 (2020)]
関連論文リスト
- Towards Entropic Constraints on Quantum Speedups [0.0]
いくつかの量子アルゴリズムは「量子スピードアップ(quantum speedups)」を持ち、同じタスクを解くための最もよく知られた古典的アルゴリズムと比較して、時間複雑性を改善している。
エントロピーの観点から、これらのスピードアップに何をもたらすのか理解できますか?
情報理論は、アルゴリズムを実行する量子コンピュータの振る舞いを「量子」がいかに根本的に測定するかを測定するために、私たちが選択できる様々な指標を与えてくれる。
論文 参考訳（メタデータ） (2024-11-05T19:00:04Z) - Robust Implementation of Discrete-time Quantum Walks in Any Finite-dimensional Quantum System [2.646968944595457]
離散時間量子ウォーク(DTQW)は、回路実装に最も適した選択の1つである。
本稿では,ゲート数および回路深さに関する回路コストを半減することに成功した。
提案手法の工学的卓越性には、近似効率を持つ任意の有限次元量子系にDTQWを実装している。
論文 参考訳（メタデータ） (2024-08-01T13:07:13Z) - A Quantum-Classical Collaborative Training Architecture Based on Quantum
State Fidelity [50.387179833629254]
我々は,コ・テンク (co-TenQu) と呼ばれる古典量子アーキテクチャを導入する。
Co-TenQuは古典的なディープニューラルネットワークを41.72%まで向上させる。
他の量子ベースの手法よりも1.9倍も優れており、70.59%少ない量子ビットを使用しながら、同様の精度を達成している。
論文 参考訳（メタデータ） (2024-02-23T14:09:41Z) - QuantumSEA: In-Time Sparse Exploration for Noise Adaptive Quantum
Circuits [82.50620782471485]
QuantumSEAはノイズ適応型量子回路のインタイムスパース探索である。
1)トレーニング中の暗黙の回路容量と(2)雑音の頑健さの2つの主要な目標を達成することを目的としている。
提案手法は, 量子ゲート数の半減と回路実行の2倍の時間節約で, 最先端の計算結果を確立する。
論文 参考訳（メタデータ） (2024-01-10T22:33:00Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳（メタデータ） (2022-12-13T16:04:16Z) - Variational Quantum Circuits for Multi-Qubit Gate Automata [0.6445605125467573]
変分量子アルゴリズム(VQA)は、ノイズ中間スケール量子(NISQ)時代に量子優位性を提供する能力を持つ。
本稿では,VQAにインスパイアされた量子機械学習フレームワークを提案する。
論文 参考訳（メタデータ） (2022-08-31T22:05:17Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Dequantizing the Quantum Singular Value Transformation: Hardness and
Applications to Quantum Chemistry and the Quantum PCP Conjecture [0.0]
量子特異値変換は効率的に「等化」できることを示す。
逆多項式精度では、同じ問題がBQP完全となることを示す。
また、この分位化手法が中心量子PCPの進展にどう役立つかについても論じる。
論文 参考訳（メタデータ） (2021-11-17T12:50:13Z) - Imaginary Time Propagation on a Quantum Chip [50.591267188664666]
想像時間における進化は、量子多体系の基底状態を見つけるための顕著な技術である。
本稿では,量子コンピュータ上での仮想時間伝搬を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-24T12:48:00Z) - Prospects for Quantum Enhancement with Diabatic Quantum Annealing [0.0]
量子アニール(QA)の一般的な枠組みにおけるアルゴリズムの展望を評価し,量子スピードアップを実現する。
我々は、コヒーレンス時間と制御能力の改善が、いくつかの量子最適化アルゴリズムの短期的な探索を可能にすることに基づいて、QAフレームワークへの継続的な探索と関心を論じる。
これらの全てのプロトコルは、時間依存の有効横場イジング・ハミルトンにより生成される新しい平衡量子力学の全ての範囲を受け入れることによって、最先端の方法で探索することができると論じる。
論文 参考訳（メタデータ） (2020-08-22T21:25:51Z) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。
観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
論文 参考訳（メタデータ） (2020-05-05T20:11:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。