論文の概要: Quantum algorithms and the power of forgetting
- arxiv url: http://arxiv.org/abs/2211.12447v1
- Date: Tue, 22 Nov 2022 18:04:10 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 04:07:50.977340
- Title: Quantum algorithms and the power of forgetting
- Title（参考訳）: 量子アルゴリズムと忘れる力
- Authors: Andrew M. Childs, Matthew Coudron, Amin Shiraz Gilani
- Abstract要約: 本研究では,効率の良い量子アルゴリズムの自然なクラスは,ENTRANCEからEXITへの経路を確実に見つけることができないことを示す。
このことは、効率的に経路を見つける量子アルゴリズムの可能性を排除するものではないが、アルゴリズムがこの振る舞いからどのような恩恵を受けるかは定かではない。
- 参考スコア（独自算出の注目度）: 1.5791732557395555
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The so-called welded tree problem provides an example of a black-box problem
that can be solved exponentially faster by a quantum walk than by any classical
algorithm. Given the name of a special ENTRANCE vertex, a quantum walk can find
another distinguished EXIT vertex using polynomially many queries, though
without finding any particular path from ENTRANCE to EXIT. It has been an open
problem for twenty years whether there is an efficient quantum algorithm for
finding such a path, or if the path-finding problem is hard even for quantum
computers. We show that a natural class of efficient quantum algorithms
provably cannot find a path from ENTRANCE to EXIT. Specifically, we consider
algorithms that, within each branch of their superposition, always store a set
of vertex labels that form a connected subgraph including the ENTRANCE, and
that only provide these vertex labels as inputs to the oracle. While this does
not rule out the possibility of a quantum algorithm that efficiently finds a
path, it is unclear how an algorithm could benefit by deviating from this
behavior. Our no-go result suggests that, for some problems, quantum algorithms
must necessarily forget the path they take to reach a solution in order to
outperform classical computation.
- Abstract（参考訳）: いわゆる溶接木問題は、従来のアルゴリズムよりも量子ウォークによって指数関数的に高速に解くことができるブラックボックス問題の例を提供する。
特別な入口頂点の名前が与えられると、量子ウォークは多項式的に多くのクエリを使って別の区別された出口頂点を見つけることができるが、出口から出口までの特定の経路は見つからない。
このような経路を見つけるための効率的な量子アルゴリズムが存在するのか、それとも量子コンピュータでさえ経路探索が難しいのか、20年間は未解決の問題であった。
効率的な量子アルゴリズムの自然なクラスは、入り口から出口までの経路を確実に見つけることができない。
具体的には、重ね合わせの各ブランチ内では常に、入り口を含む連結部分グラフを形成する一連の頂点ラベルを格納し、これらの頂点ラベルをoracleへの入力としてのみ提供するアルゴリズムを検討する。
これは、効率的に経路を見つける量子アルゴリズムの可能性を排除するものではないが、この振る舞いからどのようにアルゴリズムが恩恵を受けるかは明らかではない。
我々のノーゴーの結果は、いくつかの問題に対して、量子アルゴリズムは古典的な計算を上回り、解に到達するための経路を必ず忘れなければならないことを示唆している。
関連論文リスト
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている
SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。
この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文 参考訳（メタデータ） (2024-08-14T19:04:13Z) - Quantum algorithms for Hopcroft's problem [45.45456673484445]
計算幾何学の基本的な問題であるホップクロフト問題に対する量子アルゴリズムについて検討する。
この問題の古典的な複雑さはよく研究されており、最もよく知られているアルゴリズムは$O(n4/3)の時間で動作する。
我々の結果は、時間複雑性が$widetilde O(n5/6)$の2つの異なる量子アルゴリズムである。
論文 参考訳（メタデータ） (2024-05-02T10:29:06Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳（メタデータ） (2023-11-19T00:06:11Z) - Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
非重みのないグラフで$s, t$が与えられたとき、パスフィンディング問題の目標は、$s$-$t$パスを見つけることである。
溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。
古典的なアルゴリズムが確率の高い指数時間で$s$-$t$パスを見つけることはできないことを証明している。
論文 参考訳（メタデータ） (2023-07-24T02:50:34Z) - Making the cut: two methods for breaking down a quantum algorithm [0.0]
現在、ノイズの多い小規模量子ハードウェアの時代において、計算上の優位性に達する可能性のある量子アルゴリズムを見つけることは、依然として大きな課題である。
我々は、量子アルゴリズムを低い(クエリ)深さのラウンドに分解する2つの方法を特定し、特徴付ける。
最初の問題では並列化が最高のパフォーマンスを提供するのに対し、2番目はより良い選択であることを示す。
論文 参考訳（メタデータ） (2023-05-17T18:00:06Z) - Recovering the original simplicity: succinct and deterministic quantum
algorithm for the welded tree problem [0.0]
この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。
最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-04-17T16:03:50Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳（メタデータ） (2022-05-26T20:32:36Z) - Robust Quantum Walk Search Without Knowing the Number of Marked Vertices [0.2320417845168326]
既存の量子ウォークに基づく探索アルゴリズムは、サッフル問題に悩まされている。
量子スピードアップを犠牲にすることなくロバスト性を実現する新しい量子ウォークベースの探索フレームワークを提案する。
論文 参考訳（メタデータ） (2021-11-17T10:04:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。