論文の概要: Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem

• arxiv url: http://arxiv.org/abs/2304.08395v2
• Date: Sat, 21 Oct 2023 05:10:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-25 13:06:15.031993
• Title: Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem
• Title（参考訳）: 元の単純さの復元:溶接木問題に対する簡潔かつ決定論的量子アルゴリズム
• Authors: Guanzhong Li and Lvzhou Li and Jingquan Luo
• Abstract要約: この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。 最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This work revisits quantum algorithms for the well-known welded tree problem, proposing a very succinct quantum algorithm based on the simplest coined quantum walks. It simply iterates the naturally defined coined quantum walk operator for a predetermined time and finally measure, where the predetermined time can be efficiently computed on classical computers. Then, the algorithm returns the correct answer deterministically, and achieves exponential speedups over any classical algorithm. The significance of the results may be seen as follows. (i) Our algorithm is rather simple compared with the one in (Jeffery and Zur, STOC'2023), which not only breaks the stereotype that coined quantum walks can only achieve quadratic speedups over classical algorithms, but also demonstrates the power of the simplest quantum walk model. (ii) Our algorithm theoretically achieves zero-error, which is not possible with existing methods. Thus, it becomes one of the few examples that exhibit exponential separation between deterministic (exact) quantum and randomized query complexities, which may also change people's perception that since quantum mechanics is inherently probabilistic, it impossible to have a deterministic quantum algorithm with exponential speedups for the weled tree problem.
• Abstract（参考訳）: この研究は、よく知られた溶接木問題の量子アルゴリズムを再検討し、最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。 自然に定義された量子ウォーク演算子を所定の時間だけ反復し、最後に、古典的なコンピュータ上で所定の時間を効率的に計算できるような測定を行う。 そして、アルゴリズムは正しい解を決定論的に返し、古典的アルゴリズムよりも指数的なスピードアップを達成する。 結果の意義は以下のとおりである。 (i)我々のアルゴリズムは、古典的アルゴリズムよりも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)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。