論文の概要: New Lower-bounds for Quantum Computation with Non-Collapsing Measurements

• arxiv url: http://arxiv.org/abs/2411.04085v2
• Date: Sat, 17 May 2025 23:11:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-20 17:08:51.634931
• Title: New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
• Title（参考訳）: 非ラップ計測による量子計算のための新しい下界法
• Authors: David Miloschewsky, Supartha Podder,
• Abstract要約: 複雑性クラスPDQP(当初はnaCQPと呼ばれていた)を紹介します。 PDQPにはSZKが含まれているが、構造化されていない検索を解決するには$Omega(N1/4)$クエリが必要である。 正重み付き対向下界法を証明し、複数の厳密な境界を確立し、クエリと非折り畳み測定とのトレードオフを確立する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Aaronson, Bouland, Fitzsimons and Lee introduced the complexity class PDQP (which was original labeled naCQP), an alteration of BQP enhanced with the ability to obtain non-collapsing measurements, samples of quantum states without collapsing them. Although PDQP contains SZK, it still requires $\Omega(N^{1/4})$ queries to solve unstructured search. We formulate an alternative equivalent definition of PDQP, which we use to prove the positive weighted adversary lower-bounding method, establishing multiple tighter bounds and a trade-off between queries and non-collapsing measurements. We utilize the technique in order to analyze the query complexity of the well-studied majority and element distinctness problems. Additionally, we prove a tight $\Theta(N^{1/3})$ bound on search. Furthermore, we use the lower-bound to explore PDQP under query restrictions, finding that when combined with non-adaptive queries, we limit the speed-up in several cases.
• Abstract（参考訳）: Aaronson、Bouland、Fitzsimons、Leeは複雑性クラスPDQP(もともとnaCQPと呼ばれていた)を導入した。 PDQPにはSZKが含まれているが、構造化されていない検索を解決するには$\Omega(N^{1/4})$クエリが必要である。 PDQPの別の等価定義を定式化し、正重み付き対向下界法を証明し、複数の厳密な境界を確立し、クエリと非折り畳み測定のトレードオフを確立する。 本稿では,この手法を用いて,よく研究されている多数派のクエリ複雑性と要素識別性の問題を分析する。 さらに、厳密な$\Theta(N^{1/3})$を検索で証明する。 さらに,クエリ制限下でのPDQPの探索には下位バウンドを用いることで,非適応的なクエリと組み合わせることで,いくつかのケースでスピードアップを制限することができる。

関連論文リスト

• On additive error approximations to #BQP [0.34089646689382486]
  我々は、#BQPとして知られる数え上げクラスの量子一般化に対する加法近似について研究する。 まず,#BQP問題に対する加算近似を,対応する検証回路における証人量子ビット数の誤差指数に近似する効率的な量子アルゴリズムが存在することを示す。
  論文  参考訳（メタデータ） (2024-11-04T20:51:20Z)
• Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms [65.268245109828]
  我々はカーンズのSQオラクルとヴァリアントの弱い評価オラクルからインスピレーションを得ます。 評価クエリから学習するための非条件の下限を出力する,広範かつ直感的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-10-26T18:23:21Z)
• A Generalized Quantum Branching Program [0.5584060970507505]
  本稿では,GQBPと呼ばれる量子分岐プログラムモデルを提案する。 我々は、GQBPとAQBP、GQBPとNQBP、GQBPとクエリ複雑度の間にいくつかの等価性を示す。
  論文  参考訳（メタデータ） (2023-07-21T07:27:51Z)
• PACIFIC: Towards Proactive Conversational Question Answering over Tabular and Textual Data in Finance [96.06505049126345]
  我々はPACIFICという新しいデータセットを提案する。既存のCQAデータセットと比較すると、PACIFICは(i)活動性、(ii)数値推論、(iii)表とテキストのハイブリッドコンテキストの3つの重要な特徴を示す。 質問生成とCQAを組み合わせたPCQA(Proactive Conversational Question Answering)に基づいて,新しいタスクを定義する。 UniPCQAはPCQAのすべてのサブタスク上でマルチタスク学習を行い、Seeq2Seqの上位$kのサンプルをクロスバリデーションすることで、マルチタスク学習におけるエラー伝搬問題を緩和するための単純なアンサンブル戦略を取り入れている。
  論文  参考訳（メタデータ） (2022-10-17T08:06:56Z)
• Towards Clear Expectations for Uncertainty Estimation [64.20262246029286]
  不確実性定量化(UQ)は、信頼できる機械学習(ML)を実現するために不可欠である ほとんどのUQ手法は、異なる不整合評価プロトコルに悩まされている。 この意見書は、これらの要件を5つの下流タスクを通して指定することで、新たな視点を提供する。
  論文  参考訳（メタデータ） (2022-07-27T07:50:57Z)
• Quantum Proofs of Proximity [6.160793572747927]
  近接検定のQMA証明は古典的近接検定や量子検定よりも指数関数的に強いことを示す。 この結果には、表現力のある特性のクラスをテストするための量子スピードアップを可能にするアルゴリズムフレームワークが含まれている。 また、このファミリーの外部にある特性であるグラフ双分極性をテストするためのQMAアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-08T13:15:30Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  形状対応を見つけることは、NP-hard quadratic assignment problem (QAP)として定式化できる。 本稿では,アルファ拡大アルゴリズムに触発されたQAPの反復量子法Q-Matchを提案する。 Q-Match は、実世界の問題にスケールできるような長文対応のサブセットにおいて、反復的に形状マッチング問題に適用できる。
  論文  参考訳（メタデータ） (2021-05-06T17:59:38Z)
• Geometry of Banach spaces: a new route towards Position Based Cryptography [65.51757376525798]
  我々は幾何学的機能解析の観点から位置ベース量子暗号(PBQC)について検討し,その量子ゲームとの関係について考察した。 私たちが関心を持っている主な質問は、PBQCプロトコルのセキュリティを損なうために、攻撃者の連合が共有しなければならない、最適な絡み合いの量を求めることです。 より複雑なバナッハ空間の型プロパティの理解は、仮定を捨て、我々のプロトコルを攻撃するのに使用されるリソースに条件のない低い境界をもたらすことを示します。
  論文  参考訳（メタデータ） (2021-03-30T13:55:11Z)
• PAQ: 65 Million Probably-Asked Questions and What You Can Do With Them [70.09741980324912]
  問合せ(QA)ペアを直接活用するオープンドメイン問合せ解答モデルは、スピードとメモリの点で有望である。 PAQを補完する新しいQAペアレトリバー、RePAQを紹介します。 PAQはテスト質問をプリエンプションし、キャッシュするので、RePAQは最近の検索・読み取りモデルの精度と一致させることができる。
  論文  参考訳（メタデータ） (2021-02-13T23:43:45Z)
• The Limits of Efficiency for Open- and Closed-World Query Evaluation Under Guarded TGDs [10.042878093985458]
  制約が存在する場合のオントロジーによるクエリとクエリは2つの重要なデータベース問題である。 保護されたTGDとUCQのコンテキストにおける効率的なクエリ評価の限界を実際のクエリとして検討する。
  論文  参考訳（メタデータ） (2019-12-28T11:08:33Z)

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

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