論文の概要: Improved Quantum Query Complexity on Easier Inputs

• arxiv url: http://arxiv.org/abs/2303.00217v3
• Date: Tue, 2 Apr 2024 01:05:59 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-04 14:01:34.969707
• Title: Improved Quantum Query Complexity on Easier Inputs
• Title（参考訳）: 入力の簡易化による量子クエリの複雑さの向上
• Authors: Noel T. Anderson, Jay-U Chung, Shelby Kimmel, Da-Yeon Koh, Xiaohan Ye,
• Abstract要約: 改良されたスパンプログラムアルゴリズムを用いて,事前の約束なしに改善を継続することを示す。 応用として、いくつかの探索問題に対する平均クエリ複雑性における指数的および超ポリノミカル量子上の優位性を証明した。
• 参考スコア（独自算出の注目度）: 0.6990493129893112
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quantum span program algorithms for function evaluation sometimes have reduced query complexity when promised that the input has a certain structure. We design a modified span program algorithm to show these improvements persist even without a promise ahead of time, and we extend this approach to the more general problem of state conversion. As an application, we prove exponential and superpolynomial quantum advantages in average query complexity for several search problems, generalizing Montanaro's Search with Advice [Montanaro, TQC 2010].
• Abstract（参考訳）: 関数評価のための量子スパンプログラムアルゴリズムは、入力が一定の構造を持つことを約束すると、クエリの複雑さを減少させることがある。 本研究では,これらの改良を事前の約束なしに継続することを示す改良型スパンプログラムアルゴリズムを設計し,より一般的な状態変換問題にアプローチを拡張した。 応用として、モンタナロの検索・ウィズ・アドベンチャー(Montanaro, TQC 2010)を一般化し、いくつかの探索問題に対する平均クエリ複雑性における指数的および超ポリノミカル量子上の優位性を証明した。

関連論文リスト

• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• 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)
• Chaos and multifold complexity for an inverted harmonic oscillator [0.0]
  複雑性は、交互にジグザグの順序で与えられた時間の組み合わせの最も長い置換に支配されていることを証明する。 多次複雑性の一般的な構造は、一般的な量子系に対して普遍的に真であるべきであると推測する。
  論文  参考訳（メタデータ） (2022-11-06T14:19:48Z)
• Divide-and-conquer embedding for QUBO quantum annealing [0.0]
  組込み問題に焦点をあてたアプローチは、桁違いに性能を向上できることを示す。 以上の結果から,組込み問題に焦点をあてたアプローチにより,桁違いの性能向上が期待できることがわかった。
  論文  参考訳（メタデータ） (2022-11-03T23:22:06Z)
• Quantum Error Mitigation Relying on Permutation Filtering [84.66087478797475]
  本稿では,既存の置換に基づく手法を特殊なケースとして含む,置換フィルタ(permutation filters)と呼ばれる一般的なフレームワークを提案する。 提案するフィルタ設計アルゴリズムは, 常に大域的最適度に収束し, フィルタが既存の置換法よりも大幅に改善できることを示す。
  論文  参考訳（メタデータ） (2021-07-03T16:07:30Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  特に、状態準備および読み出しプロセスのような実装のいくつかのステップは、アルゴリズム自体の複雑さの側面を超越することができる。 本稿では、方程式の線形系と微分方程式の線形系を解くための量子アルゴリズムの完全な実装に関わる複雑性について述べる。
  論文  参考訳（メタデータ） (2021-06-23T16:33:33Z)

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

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