論文の概要: Space-Efficient Quantum Error Reduction without log Factors

• arxiv url: http://arxiv.org/abs/2502.09249v1
• Date: Thu, 13 Feb 2025 12:04:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-14 13:44:27.672799
• Title: Space-Efficient Quantum Error Reduction without log Factors
• Title（参考訳）: ログ係数のない空間効率の良い量子エラー低減
• Authors: Aleksandrs Belovs, Stacey Jeffery,
• Abstract要約: 本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。 我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
• 参考スコア（独自算出の注目度）: 50.10645865330582
• License:
• Abstract: Given an algorithm that outputs the correct answer with bounded error, say $1/3$, it is sometimes desirable to reduce this error to some arbitrarily small $\varepsilon$ -- for example, if one wants to call the algorithm many times as a subroutine. The usual method, for both quantum and randomized algorithms, is a procedure called majority voting, which incurs a multiplicative overhead of $O(\log\frac{1}{\varepsilon})$ from calling the algorithm this many times. A recent paper introduced a model of quantum computation called \emph{transducers}, and showed how to reduce the ``error'' of a transducer arbitrarily with only constant overhead, using a construction analogous to majority voting called \emph{purification}. Even error-free transducers map to bounded-error quantum algorithms, so this does not let you reduce algorithmic error for free, but it does allow bounded-error quantum algorithms to be composed without incurring log factors. In this paper, we present a new highly simplified construction of a purifier, that can be understood as a weighted walk on a line similar to a random walk interpretation of majority voting. In addition to providing a new perspective that is easier to contrast with majority voting, our purifier has exponentially better space complexity than the previous one, and quadratically better dependence on the soundness-completeness gap of the algorithm being purified. Our new purifier has nearly optimal query complexity, even down to the constant, which matters when one composes quantum algorithms to super-constant depth.
• Abstract（参考訳）: 例えば$1/3$のように、正解を境界誤差で出力するアルゴリズムを考えると、このエラーを任意の小さな$\varepsilon$に減らすことが望ましい。 通常の方法では、量子化アルゴリズムとランダム化アルゴリズムの両方に対して、多数決投票と呼ばれる手続きがあり、これはアルゴリズムを何度も呼び出すことから、$O(\log\frac{1}{\varepsilon})$の乗法的オーバーヘッドを引き起こす。 最近の論文では、'emph{transducers} と呼ばれる量子計算モデルを導入し、'emph{purification} と呼ばれる多数決に類似した構成を用いて、トランスデューサの '`error'' を一定のオーバーヘッドで任意に削減する方法を示した。 エラーのないトランスデューサでさえ、有界エラー量子アルゴリズムにマップするので、この方法ではアルゴリズムエラーを無償で削減することはできないが、有界エラー量子アルゴリズムはログファクターを発生させることなく構成できる。 本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新しい簡易な浄化器の構成を提案する。 多数決と対比し易い新しい視点を提供するのに加え、我々の浄化器は前よりも指数関数的に空間の複雑さが良く、浄化されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。 我々の新しい浄化器は、量子アルゴリズムを超定常深さに構成する場合に重要な定数まで、ほぼ最適なクエリ複雑性を持つ。

関連論文リスト

• Composing Quantum Algorithms [0.59829224684009]
  ゼロエラー量子アルゴリズムは合成されていないことが長年知られてきたが、正しいアルゴリズムレンズを用いることで、有界エラー量子アルゴリズムが成立することが判明した。 本稿では,一般のコンピュータサイエンスの読者を対象に,これらの結果に対する直感を提示する。
  論文  参考訳（メタデータ） (2025-02-13T11:56:35Z)
• Fault-Tolerant Implementation of the Deutsch-Jozsa Algorithm [0.46040036610482665]
  Deutsch-Joszaアルゴリズムは、小さなフォールトトレランス実験の自然な候補である。 このアルゴリズムは,フォールトトレラントエンコーディングを伴わずに,トラップイオン量子コンピュータ上で実装する。 平均して全てのオラクルで、エラー率の削減は90 %近くであった。
  論文  参考訳（メタデータ） (2024-12-06T05:55:31Z)
• Simple and Provable Scaling Laws for the Test-Time Compute of Large Language Models [70.07661254213181]
  大規模言語モデルのテスト時間計算のための2つの原理的アルゴリズムを提案する。 理論的には、1つのアルゴリズムの故障確率は、そのテスト時間計算が大きくなるにつれて指数関数的に減衰する。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• A simple quantum algorithm to efficiently prepare sparse states [0.0]
  ゲートの複雑性は状態の非零振幅数において線形であり、キュービット数では2次であることを示す。 これは、スパース状態の準備のための最もよく知られたアルゴリズムと競合する。
  論文  参考訳（メタデータ） (2023-10-30T07:05:15Z)
• Efficient quantum linear solver algorithm with detailed running costs [0.0]
  量子信号処理に基づくフィルタリング手法を用いて,アイデアダイアバティックな量子コンピューティングを組み合わせた量子線形解法アルゴリズムを提案する。 我々のプロトコルは、初期実装において、最先端技術に対する量子線形解決器のコストを桁違いに削減する。
  論文  参考訳（メタデータ） (2023-05-19T00:07:32Z)
• Experimentally demonstrating indefinite causal order algorithms to solve the generalized Deutsch's problem [4.555392897705548]
  Deutschのアルゴリズムは、古典的アルゴリズムよりも優位性を示す最初の量子アルゴリズムである。 この問題を解決するために、不明確な因果順序を持つ新しい量子アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-09T13:04:28Z)
• 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)
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm [52.77024349608834]
  Apsi(textbfr)=f(textbfr)$ という形の非等質線型偏微分方程式を解くための量子アルゴリズムを提案する。 これらの成果により、現代の技術に基づく量子アルゴリズムの実験的実装が容易になった。
  論文  参考訳（メタデータ） (2022-05-11T14:29:39Z)
• A Fully Single Loop Algorithm for Bilevel Optimization without Hessian Inverse [121.54116938140754]
  両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。 我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
  論文  参考訳（メタデータ） (2021-12-09T02:27:52Z)

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

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