論文の概要: Recover the original simplicity: concise and deterministic quantum
algorithm for the welded tree problem
- arxiv url: http://arxiv.org/abs/2304.08395v1
- Date: Mon, 17 Apr 2023 16:03:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-04-18 14:21:40.496720
- Title: Recover the original simplicity: concise and deterministic quantum
algorithm for the welded tree problem
- Title(参考訳): 元の単純さを復元する:溶接木問題に対する簡潔で決定論的量子アルゴリズム
- Authors: Guanzhong Li and Jingquan Luo and Lvzhou Li
- Abstract要約: 元の量子アルゴリズムは連続時間量子ウォーク(CTQW)に基づいている
離散時間量子ウォーク(DTQW)に基づく効率的なアルゴリズムが存在するかは、最近になって多次元量子ウォークフレームワークが提案されるまで明らかではない。
- 参考スコア(独自算出の注目度): 0.2320417845168326
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: TThe welded tree problem is a black-box problem to find the exit of the
welded tree with $\Theta(2^n)$ vertices starting from the given entrance, for
which there are quantum algorithms with exponential speedups over the best
classical algorithm. The original quantum algorithm is based on continuous time
quantum walks (CTQW), and it has never been clear whether there are efficient
algorithms based on discrete time quantum walks (DTQW) until recently the
multidimensional quantum walk framework was proposed (Jeffery and Zur,
STOC'2023). In this paper, we propose a rather concise algorithm based purely
on the simplest coined quantum walks, which is simply to iterate the naturally
defined coined quantum walk operator for a predetermined time $T \in O(n \log
n)$ and then measure to obtain the exit name with $\Omega(\frac{1}{n})$
probability. The algorithm can be further promoted to be error-free and with
$O(n^{1.5} \log n)$ query complexity. The numerical simulation strongly implies
that the actual complexity of our algorithm is $O(n^{4/3})$.
The significance of our results may be seen as follows. (i) Our algorithm is
rather concise compared with the one in (Jeffery and Zur, STOC'2023), which not
only changes the stereotype that the exiting DTQW frameworks before the
multidimensional one can achieve at most a quadratic speedup over the best
classical algorithm, but also re-displays the power of the simplest framework
of quantum walks. (ii) Our algorithm can be made error-free theoretically,
whereas all the existing methods cannot. Thus, it is one of the few examples of
an exponential separation between the error-free (exact) quantum and the
randomized query complexities, which perhaps also change people's idea that
quantum mechanics is inherently probabilistic and thus deterministic quantum
algorithms with exponential speedups for the problem are out of the question.
- Abstract(参考訳): tthe welded tree problem(溶接された木の問題)は、与えられた入口から開始される$\theta(2^n)$の頂点を持つ溶接された木の出口を見つけるためのブラックボックス問題である。
元の量子アルゴリズムは連続時間量子ウォーク(CTQW)に基づいており、最近では多次元量子ウォークフレームワークが提案されるまで、離散時間量子ウォーク(DTQW)に基づく効率的なアルゴリズムが存在するかどうかは明らかになっていない(Jeffery and Zur, STOC'2023)。
本稿では,自然に定義された量子ウォーク演算子を所定の時間$t \in o(n \log n)$で反復し,その終了名を$\omega(\frac{1}{n})$確率で求める,最も単純な量子ウォークに基づく比較的簡潔なアルゴリズムを提案する。
このアルゴリズムは、さらにエラーフリーで、$o(n^{1.5} \log n)$クエリの複雑さで推進することができる。
この数値シミュレーションは、アルゴリズムの実際の複雑性が$o(n^{4/3})$であることを示している。
この結果の意義は以下の通りである。
(i)本アルゴリズムは,多次元前のDTQWフレームワークが古典的アルゴリズムよりも2次スピードアップで達成できるステレオタイプを変化させるだけでなく,量子ウォークの最も単純なフレームワークのパワーを再表現する(Jeffery and Zur, STOC'2023)。
(ii) 提案アルゴリズムは理論上はエラーフリーにすることができるが, 既存の手法では不可能である。
したがって、これは誤りのない(実演)量子とランダム化されたクエリの複雑度の間の指数関数的分離の数少ない例の1つであり、量子力学は本質的に確率的であり、それゆえ問題に対する指数的スピードアップを伴う決定論的量子アルゴリズムは問題外である、という人々の考えを変えるかもしれない。
関連論文リスト
- Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Generalized quantum Arimoto-Blahut algorithm and its application to
quantum information bottleneck [55.22418739014892]
量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。
3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。
数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
論文 参考訳(メタデータ) (2023-11-19T00:06:11Z) - Sample-size-reduction of quantum states for the noisy linear problem [0.0]
本稿では,量子ランダムアクセスメモリ(QRAM)の量子サンプルサイズを線形次数に削減できることを述べる。
ノイズの多い線形問題に対して,より短い実行時間を実現する。
論文 参考訳(メタデータ) (2023-01-08T05:53:17Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。
我々は距離の計算を高速化するために量子現象を利用する。
我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
論文 参考訳(メタデータ) (2022-12-13T16:04:16Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
ほとんどの人造システム、特にコンピュータは決定論的に機能する。
本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
論文 参考訳(メタデータ) (2022-09-08T17:55:30Z) - Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。
我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。
絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
論文 参考訳(メタデータ) (2022-05-26T20:32:36Z) - Establishing trust in quantum computations [0.0]
本稿では, 量子コンピュータがアルゴリズムを実行できる忠実度を計測する手法を提案する。
提案手法は,アルゴリズムの量子回路を,効率よく成功率を計測できる密接な関連回路の集合に変換する。
論文 参考訳(メタデータ) (2022-04-15T17:44:30Z) - Hybrid Quantum-Classical Search Algorithms [0.0]
古典計算は,探索問題自体が解けない限り,量子計算を補助できないことを示す。
我々はこの結果を、不安定な成功確率を持つアルゴリズムに一般化する。
論文 参考訳(メタデータ) (2022-02-23T11:43:17Z) - Demonstrating robust simulation of driven-dissipative problems on
near-term quantum computers [53.20999552522241]
量子コンピュータは物理学と化学における量子力学系のシミュレーションに革命をもたらす。
現在の量子コンピュータは、訂正されていないノイズ、ゲートエラー、デコヒーレンスのためにアルゴリズムを不完全に実行している。
ここでは、量子力学における最も難しい問題の1つとして、駆動散逸多体問題の解法が本質的にエラーに対して堅牢であることを示す。
論文 参考訳(メタデータ) (2021-08-02T21:36:37Z) - Quantum algorithmic differentiation [0.0]
本稿では,量子コンピューティングの文脈でアルゴリズムの微分を行うアルゴリズムを提案する。
アルゴリズムの2つのバージョンを提示する。1つは完全量子であり、もう1つは古典的なステップを雇用する。
論文 参考訳(メタデータ) (2020-06-23T22:52:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。