論文の概要: 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つであり、量子力学は本質的に確率的であり、それゆえ問題に対する指数的スピードアップを伴う決定論的量子アルゴリズムは問題外である、という人々の考えを変えるかもしれない。
関連論文リスト
- Towards Entropic Constraints on Quantum Speedups [0.0]
いくつかの量子アルゴリズムは「量子スピードアップ(quantum speedups)」を持ち、同じタスクを解くための最もよく知られた古典的アルゴリズムと比較して、時間複雑性を改善している。
エントロピーの観点から、これらのスピードアップに何をもたらすのか理解できますか?
情報理論は、アルゴリズムを実行する量子コンピュータの振る舞いを「量子」がいかに根本的に測定するかを測定するために、私たちが選択できる様々な指標を与えてくれる。
論文 参考訳（メタデータ） (2024-11-05T19:00:04Z) - An Exponential Separation Between Quantum and Quantum-Inspired Classical Algorithms for Machine Learning [14.955338558971787]
証明可能な指数的量子スピードアップは、線形系を解くためのセミナルHHL量子アルゴリズム以来、中心的な研究目標となっている。
量子と量子に着想を得た古典的アルゴリズム間で、このような証明可能な指数的分離を初めて提示する。
論文 参考訳（メタデータ） (2024-11-04T13:49:26Z) - Taming Quantum Time Complexity [45.867051459785976]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - 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) - Quantum Causal Unravelling [44.356294905844834]
我々は,多部量子プロセスにおける相互作用の因果構造を明らかにするための,最初の効率的な方法を開発した。
我々のアルゴリズムは、量子プロセストモグラフィーの技法で効率的に特徴付けることができるプロセスを特定するのに利用できる。
論文 参考訳（メタデータ） (2021-09-27T16:28:06Z) - Synthesis of Quantum Circuits with an Island Genetic Algorithm [44.99833362998488]
特定の演算を行うユニタリ行列が与えられた場合、等価な量子回路を得るのは非自明な作業である。
量子ウォーカーのコイン、トフォリゲート、フレドキンゲートの3つの問題が研究されている。
提案したアルゴリズムは量子回路の分解に効率的であることが証明され、汎用的なアプローチとして、利用可能な計算力によってのみ制限される。
論文 参考訳（メタデータ） (2021-06-06T13:15:25Z) - Quantum algorithmic differentiation [0.0]
本稿では,量子コンピューティングの文脈でアルゴリズムの微分を行うアルゴリズムを提案する。
アルゴリズムの2つのバージョンを提示する。1つは完全量子であり、もう1つは古典的なステップを雇用する。
論文 参考訳（メタデータ） (2020-06-23T22:52:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。