論文の概要: Revisiting BQP with Non-Collapsing Measurements
- arxiv url: http://arxiv.org/abs/2411.04085v1
- Date: Wed, 06 Nov 2024 18:06:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-07 19:22:29.400553
- Title: Revisiting BQP with Non-Collapsing Measurements
- Title(参考訳): 非崩壊測定によるBQPの再検討
- Authors: David Miloschewsky, Supartha Podder,
- Abstract要約: 非折り畳み測定機能を備えた場合、BQPはBQPとSZKの両方を含むことを示す。
PDQPの代替等価モデルを定式化することにより、正重み付き逆法を証明できる。
また、関連する設定についても検討し、任意の状態をコピーできるBQPの厳密な境界を求める。
- 参考スコア(独自算出の注目度): 0.0
- License:
- Abstract: The study of non-collapsing measurements was initiated by Aaronson, Bouland, Fitzsimons, and Lee, who showed that BQP, when equipped with the ability to perform non-collapsing measurements (denoted as PDQP), contains both BQP and SZK, yet still requires $\Omega (N^{1/4})$ queries to find an element in an unsorted list. By formulating an alternative equivalent model of PDQP, we prove the positive weighted adversary method, obtaining a variety of new lower bounds and establishing a trade-off between queries and non-collapsing measurements. The method allows us to examine the well-studied majority and element distinctness problems, while also tightening the bound for the search problem to $\Theta (N^{1/3})$. Additionally, we explore related settings, obtaining tight bounds in BQP with the ability to copy arbitrary states (called CBQP) and PDQP with non-adaptive queries.
- Abstract(参考訳): 非折り畳み測定の研究は、Aaronson, Bouland, Fitzsimons, Leeによって始められ、BQPは非折り畳み測定(PDQPと表記される)を行う能力を備えており、BQPとSZKの両方を含むが、ソートされていないリストの要素を見つけるには$\Omega (N^{1/4})$クエリが必要であることを示した。
PDQPの代替等価モデルを定式化することにより、正重み付き逆法を証明し、様々な新しい下界を求め、クエリと非折り畳み測定のトレードオフを確立する。
提案手法では,探索問題の境界を$\Theta (N^{1/3})$に絞った上で,よく研究された多数決問題と要素の相違性問題を調べることができる。
さらに,BQP の任意の状態 (CBQP) と PDQP を非適応的クエリでコピーする機能により,BQP の厳密な境界を求める。
関連論文リスト
- 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。