論文の概要: Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem
- arxiv url: http://arxiv.org/abs/2404.19476v1
- Date: Tue, 30 Apr 2024 11:45:49 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-01 14:25:13.225166
- Title: Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem
- Title（参考訳）: 量子検索のグローバルフェイズ:もう1つ、溶接した木の問題
- Authors: Aleksandrs Belovs,
- Abstract要約: 本稿では、離散時間量子ウォークによる溶接木問題に対する最適線形打撃時間の簡単な証明を行う。
同じ手法は他の1次元階層グラフにも適用できる。
- 参考スコア（独自算出の注目度）: 55.80819771134007
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Up to now, relatively few exponential quantum speed-ups have been achieved. Out of them, the welded tree problem (Childs, Cleve, Deotto, Farhi, Gutmann, and Spielman'2003) is one of the unusual examples, as the exponential speed-up is attained by a quantum walk. In this paper, we give a very short proof of the optimal linear hitting time for this problem by a discrete-time quantum walk, which is based on a simple modification of the electric quantum walk framework. The same technique can be applied to other 1-dimensional hierarchical graphs, yielding results similar to (Balasubramanian, Li, and Harrow'2023).
- Abstract（参考訳）: これまでのところ、指数的な量子スピードアップは比較的少ない。
そのうちの溶接木問題(Childs, Cleve, Deotto, Farhi, Gutmann, Spielman'2003)は、指数的なスピードアップが量子ウォークによって達成される特異な例の1つである。
本稿では、電気量子ウォークフレームワークの簡単な修正に基づく離散時間量子ウォークにより、この問題に対する最適線形打撃時間の非常に短い証明を与える。
同じ手法が他の1次元階層グラフにも適用でき、結果は (Balasubramanian, Li, and Harrow'2023) に類似している。
関連論文リスト
- Towards Entropic Constraints on Quantum Speedups [0.0]
いくつかの量子アルゴリズムは「量子スピードアップ(quantum speedups)」を持ち、同じタスクを解くための最もよく知られた古典的アルゴリズムと比較して、時間複雑性を改善している。
エントロピーの観点から、これらのスピードアップに何をもたらすのか理解できますか?
情報理論は、アルゴリズムを実行する量子コンピュータの振る舞いを「量子」がいかに根本的に測定するかを測定するために、私たちが選択できる様々な指標を与えてくれる。
論文 参考訳（メタデータ） (2024-11-05T19:00:04Z) - Quantum walks, the discrete wave equation and Chebyshev polynomials [1.0878040851638]
量子ウォーク(quantum walk)は、ランダムウォークの量子アナログである。
量子ウォークは、グラフ上のランダムウォークの拡散または混合速度を高速化できることを示す。
論文 参考訳（メタデータ） (2024-02-12T17:15:19Z) - Search for Multiple Adjacent Marked Vertices on the Hypercube by a Quantum Walk with Partial Phase Inversion [3.8436076642278754]
マルチループラカダシカル量子ウォークのハイパーキューブへの応用について検討する。
部分位相反転を用いることで、確率振幅を 1 に近い値に増幅できることが示される。
論文 参考訳（メタデータ） (2023-05-31T07:30:04Z) - Recovering the original simplicity: succinct and deterministic quantum
algorithm for the welded tree problem [0.0]
この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。
最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-17T16:03:50Z) - One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。
これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
論文 参考訳（メタデータ） (2023-01-05T11:05:22Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum communication complexity of linear regression [0.05076419064097732]
量子コンピュータは、いくつかの基本的な線形代数問題に対する通信の観点から、証明可能かつ指数関数的なスピードアップを持つことを示す。
本稿では,量子特異値変換のための効率的な量子プロトコルを提案する。
論文 参考訳（メタデータ） (2022-10-04T13:27:01Z) - A shortcut to adiabaticity in a cavity with a moving mirror [58.720142291102135]
量子場理論において、断熱に対するショートカットの実装方法について初めて述べる。
ショートカットは動的カシミール効果がないときに行われる。
量子場を動作系とするオットーサイクルの効率の基本的な限界を得る。
論文 参考訳（メタデータ） (2022-02-01T20:40:57Z) - On Applying the Lackadaisical Quantum Walk Algorithm to Search for
Multiple Solutions on Grids [63.75363908696257]
不足量子ウォーク(英: lackadaisical quantum walk)は、頂点が重量$l$の自己ループを持つグラフ構造を探索するために開発されたアルゴリズムである。
本稿では,グリッド上の複数解の探索に不連続な量子ウォークを適用した際の問題に対処する。
論文 参考訳（メタデータ） (2021-06-11T09:43:09Z) - Boundaries of quantum supremacy via random circuit sampling [69.16452769334367]
Googleの最近の量子超越性実験は、量子コンピューティングがランダムな回路サンプリングという計算タスクを実行する遷移点を示している。
観測された量子ランタイムの利点の制約を、より多くの量子ビットとゲートで検討する。
論文 参考訳（メタデータ） (2020-05-05T20:11:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。