論文の概要: 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つとなり、量子力学は本質的に確率的であるため、ウェドツリー問題に対する指数的スピードアップを持つ決定論的量子アルゴリズムを持つことは不可能であるという人々の認識を変える可能性がある。
関連論文リスト
- 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) - Practical limitations of quantum data propagation on noisy quantum
processors [1.2891210250935146]
行列を高い条件数で反転させるのに古典的な計算を必要とする量子アルゴリズムは、誤り確率が非常に低い単一および2量子ゲートを必要とすることを示す。
我々の研究は、ノイズの多い環境下で実行できるハイブリッド量子古典アルゴリズムの主流概念に挑戦する。
論文 参考訳(メタデータ) (2023-06-22T17:12:52Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。