論文の概要: Composing Quantum Algorithms

• arxiv url: http://arxiv.org/abs/2502.09240v1
• Date: Thu, 13 Feb 2025 11:56:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:47:58.938498
• Title: Composing Quantum Algorithms
• Title（参考訳）: 量子アルゴリズムの構成
• Authors: Stacey Jeffery,
• Abstract要約: ゼロエラー量子アルゴリズムは合成されていないことが長年知られてきたが、正しいアルゴリズムレンズを用いることで、有界エラー量子アルゴリズムが成立することが判明した。 本稿では,一般のコンピュータサイエンスの読者を対象に,これらの結果に対する直感を提示する。
• 参考スコア（独自算出の注目度）: 0.59829224684009
• License:
• Abstract: Composition is something we take for granted in classical algorithms design, and in particular, we take it as a basic axiom that composing ``efficient'' algorithms should result in an ``efficient'' algorithm -- even using this intuition to justify our definition of ``efficient.'' Composing quantum algorithms is a much more subtle affair than composing classical algorithms. It has long been known that zero-error quantum algorithms \emph{do not} compose, but it turns out that, using the right algorithmic lens, bounded-error quantum algorithms do. In fact, in the bounded-error setting, quantum algorithms can even avoid the log factor needed in composing bounded-error randomized algorithms that comes from amplifying the success probability via majority voting. In this article, aimed at a general computer science audience, we try to give some intuition for these results: why composing quantum algorithms is tricky, particularly in the zero-error setting, but why it nonetheless works \emph{better} than classical composition in the bounded-error setting.
• Abstract（参考訳）: 合成は、古典的なアルゴリズム設計において当然のことですが、特に、" `efficient'' アルゴリズムを構成する基本的な公理として、" `efficient' アルゴリズムを生成するべきです -- この直観を使って `efficient' の定義を正当化します。 「量子アルゴリズムを構成することは、古典的なアルゴリズムを構成するよりもずっと微妙な事柄である。 ゼロ・エラー量子アルゴリズム \emph{do not} が合成されることは以前から知られていたが、正しいアルゴリズムレンズを用いることで、バウンド・エラー量子アルゴリズムが成立することが判明した。 実際、有界エラー設定では、量子アルゴリズムは、多数決による成功確率の増幅から生じる有界エラーランダム化アルゴリズムを構成するのに必要なログファクターを回避できる。 本稿では、一般のコンピュータサイエンスの読者を対象に、量子アルゴリズムの構成が難しい理由、特にゼロエラー環境ではなぜそれが古典的な構成よりも難しいのか、といった結果に対する直感を与える。

関連論文リスト

• 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)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  量子アリーモト・ブラフトアルゴリズムをRamakrishnanらにより一般化する。 3つの量子系を持つ量子情報ボトルネックに対して,我々のアルゴリズムを適用した。 数値解析により,我々のアルゴリズムはアルゴリズムよりも優れていることが示された。
  論文  参考訳（メタデータ） (2023-11-19T00:06:11Z)
• Quantum Multiplication Algorithm Based on the Convolution Theorem [0.0]
  時間複雑性を持つ整数乗算の量子アルゴリズムをO(sqrtnlog2 n)$で提案する。 Harveyアルゴリズムとは異なり、我々のアルゴリズムは極大数にのみ適用できるという制限はない。 また、古典的乗法アルゴリズムの歴史と発展を概観し、量子資源がこの根本的な問題に対してどのように新たな視点と可能性を提供できるかを探求する動機付けとなる。
  論文  参考訳（メタデータ） (2023-06-14T12:40:54Z)
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem [4.555392897705548]
  Deutschのアルゴリズムは、古典的アルゴリズムよりも優位性を示す最初の量子アルゴリズムである。 この問題を解決するために、不明確な因果順序を持つ新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-09T13:04:28Z)
• Recovering the original simplicity: succinct and deterministic quantum algorithm for the welded tree problem [0.0]
  この研究は、よく知られた溶接木問題に対する量子アルゴリズムを再考する。 最も単純な量子ウォークに基づく非常に簡潔な量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-04-17T16:03:50Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vaziraniアルゴリズムは、オラクルに符号化されたビット文字列を決定できる。 我々はベルンシュタイン・ヴァジラニアルゴリズムの量子資源を詳細に分析する。 絡み合いがない場合、初期状態における量子コヒーレンス量とアルゴリズムの性能が直接関係していることが示される。
  論文  参考訳（メタデータ） (2022-05-26T20:32:36Z)
• Quantum Inspired Adaptive Boosting [0.0]
  量子アンサンブル法は古典的アルゴリズムに勝らないことを示す。 本稿では,量子アンサンブル法と適応的なブースティングを組み合わせた手法を提案する。 アルゴリズムはテストされ、公開データセット上のAdaBoostアルゴリズムに匹敵することがわかった。
  論文  参考訳（メタデータ） (2021-02-01T16:33:14Z)

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

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