論文の概要: Taming Quantum Time Complexity

• arxiv url: http://arxiv.org/abs/2311.15873v3
• Date: Thu, 22 Aug 2024 16:20:24 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-23 19:56:46.284380
• Title: Taming Quantum Time Complexity
• Title（参考訳）: 量子時間複雑性のモデリング
• Authors: Aleksandrs Belovs, Stacey Jeffery, Duyal Yolcu,
• Abstract要約: 時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
• 参考スコア（独自算出の注目度）: 45.867051459785976
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum query complexity has several nice properties with respect to composition. First, bounded-error quantum query algorithms can be composed without incurring log factors through error reduction (exactness). Second, through careful accounting (thriftiness), the total query complexity is smaller if subroutines are mostly run on cheaper inputs -- a property that is much less obvious in quantum algorithms than in their classical counterparts. While these properties were previously seen through the model of span programs (alternatively, the dual adversary bound), a recent work by two of the authors (Belovs, Yolcu 2023) showed how to achieve these benefits without converting to span programs, by defining quantum Las Vegas query complexity. Independently, recent works, including by one of the authors (Jeffery 2022), have worked towards bringing thriftiness to the more practically significant setting of quantum time complexity. In this work, we show how to achieve both exactness and thriftiness in the setting of time complexity. We generalize the quantum subroutine composition results of Jeffery 2022 so that, in particular, no error reduction is needed. We give a time complexity version of the well-known result in quantum query complexity, $Q(f\circ g)=O(Q(f)\cdot Q(g))$, without log factors. We achieve this by employing a novel approach to the design of quantum algorithms based on what we call transducers, and which we think is of large independent interest. While a span program is a completely different computational model, a transducer is a direct generalisation of a quantum algorithm, which allows for much greater transparency and control. Transducers naturally characterize general state conversion, rather than only decision problems; provide a very simple treatment of other quantum primitives such as quantum walks; and lend themselves well to time complexity analysis.
• Abstract（参考訳）: 量子クエリの複雑さは、構成に関していくつかの優れた特性を持っています。 第一に、境界付きエラー量子クエリアルゴリズムは、エラー低減(実行性)を通じてログファクターを発生させることなく構成できる。 第二に、注意深い会計 (thriftiness) を通じて、サブルーチンがより安価な入力で実行される場合、クエリ全体の複雑さは小さくなります。 これらの性質は、以前はスパンプログラムのモデルを通して見られたが、最近の2人の著者 (Belovs, Yolcu 2023) による研究は、量子ラスベガスのクエリ複雑性を定義することによって、スパンプログラムに変換せずにこれらの利点を実現する方法を示した。 独立に、著者の1人(Jeffery 2022)を含む最近の研究は、より現実的に重要な量子時間複雑性の設定に緩和性をもたらすことに取り組んできた。 本研究では,時間的複雑性の設定において,正確さと遠心性を両立させる方法について述べる。 我々はJeffery 2022の量子サブルーチン合成結果を一般化し、特にエラーの低減は不要である。 量子クエリ複雑性のよく知られた結果の時間複雑性版である$Q(f\circ)を与える。 g)=O(Q) (f)\cdot Q (g)$、ログファクタなしで。 我々は、トランスデューサと呼ばれるものに基づいて、量子アルゴリズムの設計に新しいアプローチを適用することで、これを実現する。 スパンプログラムは完全に異なる計算モデルであるが、トランスデューサは量子アルゴリズムの直接的な一般化であり、透明性と制御をより大きくすることができる。 トランスデューサは、決定問題だけでなく、一般的な状態変換を自然に特徴付け、量子ウォークのような他の量子プリミティブの非常に単純な処理を提供し、時間複雑性解析によく役立てる。

関連論文リスト

• Quantum complexity and localization in random quantum circuits [0.0]
  ランダム量子回路の複雑性を計測・無測定で研究する。 測定なしの$N$ qubitsの場合、飽和値は$2N-1$、飽和時間は$2N$となる。 複雑性はアンダーソンの局所化と多体局在の新しいプローブとして機能する。
  論文  参考訳（メタデータ） (2024-09-05T16:10:54Z)
• Quantum algorithms: A survey of applications and end-to-end complexities [90.05272647148196]
  期待されている量子コンピュータの応用は、科学と産業にまたがる。 本稿では,量子アルゴリズムの応用分野について検討する。 私たちは、各領域における課題と機会を"エンドツーエンド"な方法で概説します。
  論文  参考訳（メタデータ） (2023-10-04T17:53:55Z)
• Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.9208007322096533]
  一般高次量子計算におけるブール関数の問合せ複雑性について検討する。 最近導入された因果順序の量子制御を持つ量子回路のクラスは、クエリの複雑さを減らすことは不可能である。 因果不確定なスーパーマップを利用する場合、2つのクエリで計算できる最小誤差が厳密に低い関数がいくつか見つかる。
  論文  参考訳（メタデータ） (2023-07-18T13:12:55Z)
• One-Way Ticket to Las Vegas and the Quantum Adversary [78.33558762484924]
  量子ラスベガスのクエリの複雑さは、量子対向境界と全く同じであることを示す。 これは、逆反転問題に対する実現可能な解を量子クエリーアルゴリズムに変換することで達成される。
  論文  参考訳（メタデータ） (2023-01-05T11:05:22Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)
• How smooth is quantum complexity? [0.0]
  ユニタリ作用素の「量子複雑性」は、基本量子ゲートの集合から構成の難しさを測定する。 本稿では、ユニタリ作用素の空間上の関数と見なされる様々な量子複雑性の概念について統一的な視点を示す。
  論文  参考訳（メタデータ） (2021-06-15T17:58:08Z)
• Characterization of exact one-query quantum algorithms (ii): for partial functions [0.2741266294612775]
  クエリモデル(またはブラックボックスモデル)は、古典コンピューティングと量子コンピューティングの両方のコミュニティから多くの注目を集めている。 通常、量子の利点は、古典的なアルゴリズムよりもクエリの複雑さが高い量子アルゴリズムを提示することで明らかにされる。 例えば、Deutsch-Jozsaアルゴリズム、Simonアルゴリズム、Groverアルゴリズムといったよく知られた量子アルゴリズムは、クエリ複雑性の観点から量子コンピューティングのかなりの利点を示している。
  論文  参考訳（メタデータ） (2020-08-27T09:06:34Z)
• Span programs and quantum time complexity [2.4182732872327186]
  時間複雑性が$f$で量子アルゴリズムを$f$でスパンプログラムに変換し、時間複雑性が$widetildeO(T)$で$f$で量子アルゴリズムにコンパイルする方法を示す。 特に、時間複雑性$T$で量子アルゴリズムを$f$でスパンプログラムに変換し、時間複雑性$widetildeO(T)$で量子アルゴリズムにコンパイルする方法を示す。
  論文  参考訳（メタデータ） (2020-05-04T08:43:14Z)

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

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