論文の概要: Lower Bounds for Unitary Property Testing with Proofs and Advice
- arxiv url: http://arxiv.org/abs/2401.07912v1
- Date: Mon, 15 Jan 2024 19:00:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-17 16:14:01.923041
- Title: Lower Bounds for Unitary Property Testing with Proofs and Advice
- Title（参考訳）: 証明とアドバイスによるユニタリプロパティテストのための下限
- Authors: Jordi Weggemans
- Abstract要約: そこで本研究では,一元性検定における量子クエリ複雑性の低い境界を証明するための新しい手法を提案する。
すべての得られる下限は$mathsfC$-testerで、$mathsfC subseteq mathsfQMA(textpoly(n) / mathsfqpoly$である。
我々は、$mathsfQMA(textpoly(n) / Mathsfqpoly notsupset に対して量子オラクルが存在することを示す。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In unitary property testing a quantum algorithm, also known as a tester, is
given query access to a black-box unitary and has to decide whether it
satisfies some property. We propose a new technique for proving lower bounds on
the quantum query complexity of unitary property testing and related problems,
which utilises the connection between unitary property testing and unitary
channel discrimination. The main advantage of this technique is that all
obtained lower bounds hold for any $\mathsf{C}$-tester with $\mathsf{C}
\subseteq \mathsf{QMA}(\text{poly(n)} / \mathsf{qpoly}$, showing that even
having access to both (unentangled) quantum proofs and advice does not help for
many unitary problems. We apply our technique to prove lower bounds for
problems like quantum phase estimation, the entanglement entropy problem,
quantum Gibbs sampling and more, removing all logarithmic factors in the lower
bounds obtained by the sample-to-query lifting theorem of Wang and Zhang
(2023). As a direct corollary, we show that there exists a quantum oracle
relative to which $\mathsf{QMA}(\text{poly(n)} / \mathsf{qpoly} \not\supset
\mathsf{SBQP}$.
- Abstract（参考訳）: ユニタリプロパティテストでは、テスタとしても知られる量子アルゴリズムが、ブラックボックスユニタリへのクエリアクセスを与えられ、ある特性を満たすかどうかを判断しなければならない。
本稿では,ユニタリプロパティテストとユニタリチャネル識別の関連性を利用した,ユニタリプロパティテストと関連する問題の量子クエリ複雑性の下限を証明する新しい手法を提案する。
この手法の主な利点は、得られたすべての下限値が$\mathsf{c} \subseteq \mathsf{qma}(\text{poly(n)} / \mathsf{qpoly}$を持つ任意の$\mathsf{c}$-testerに対して成り立つことである。
本手法は, 量子位相推定, エンタングルメントエントロピー問題, 量子ギブスサンプリングなどの問題に対する下界の証明に応用し, wang and zhang (2023) の標本-問合せ浮揚定理により得られた下界のすべての対数因子を除去した。
直接系として、$\mathsf{qma}(\text{poly(n)} / \mathsf{qpoly} \not\supset \mathsf{sbqp}$ という量子オラクルが存在することを示す。
関連論文リスト
- Classical versus quantum queries in quantum PCPs with classical proofs [0.3004066195320147]
量子古典PCPを一般化し、古典的な証明に$q$の量子クエリを適用できるようにします。
驚くべきことに、このことは、定数量子古典量に対して逆から定数への約束のギャップを増幅できることを示している。
約束のギャップは達成できるが、我々の結果は、$mathsfQCMA$に対する定型クエリ量子古典的PCPが存在しないという強い証拠を与える。
論文 参考訳（メタデータ） (2024-11-01T18:00:56Z) - The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。
特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。
QMA(2) が $textQMA+(2)$ に等しいことを示す。
論文 参考訳（メタデータ） (2024-02-29T01:35:46Z) - Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower
bounds [1.3927943269211591]
本研究は、$mathsfPH$の量子検証に基づく3つの一般化を研究する。
まず、[GSSSY22] から、崩壊定理と$mathsfQCPH$に対するカルプ・リプトンの定理を含むいくつかの開問題を解く。
我々は、$mathsfpureQPH$に対する一方の誤り低減と、これらの量子変量$mathsfPH$に関する最初の境界を示す。
論文 参考訳（メタデータ） (2024-01-03T09:12:25Z) - Quantum Lower Bounds by Sample-to-Query Lifting [7.319050391449301]
本稿では,量子サンプル対クエリリフト定理を用いて,量子クエリの下限を証明するための新しい手法を提案する。
位相/振幅推定やハミルトニアンシミュレーションなど,いくつかの既知の下界に対する統一的な証明を提供する。
論文 参考訳（メタデータ） (2023-08-03T14:41:49Z) - Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。
量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
論文 参考訳（メタデータ） (2022-12-06T22:01:49Z) - Quantum Depth in the Random Oracle Model [57.663890114335736]
浅量子回路の計算能力と古典計算の組合せを包括的に評価する。
いくつかの問題に対して、1つの浅い量子回路で適応的な測定を行う能力は、適応的な測定をせずに多くの浅い量子回路を実行する能力よりも有用である。
論文 参考訳（メタデータ） (2022-10-12T17:54:02Z) - Unitary property testing lower bounds by polynomials [0.15229257192293197]
我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。
これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。
我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
論文 参考訳（メタデータ） (2022-10-12T03:01:00Z) - Complexity-Theoretic Limitations on Quantum Algorithms for Topological
Data Analysis [59.545114016224254]
トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。
我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。
我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
論文 参考訳（メタデータ） (2022-09-28T17:53:25Z) - QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum
machines [81.4597482536073]
量子近似最適化アルゴリズム(QAOAs)は、量子マシンのパワーを利用し、断熱進化の精神を継承する。
量子マシンを用いて任意の大規模MaxCut問題を解くためにQAOA-in-QAOA(textQAOA2$)を提案する。
提案手法は,大規模最適化問題におけるQAOAsの能力を高めるために,他の高度な戦略にシームレスに組み込むことができる。
論文 参考訳（メタデータ） (2022-05-24T03:49:10Z) - A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
しきい値定理は、フォールトトレラント量子計算の理論における基本的な結果である。
振幅雑音を伴う耐故障性量子計算の最大長に対する指数的上限を証明した。
論文 参考訳（メタデータ） (2022-01-31T22:19:49Z) - Quantum Proofs of Proximity [6.160793572747927]
近接検定のQMA証明は古典的近接検定や量子検定よりも指数関数的に強いことを示す。
この結果には、表現力のある特性のクラスをテストするための量子スピードアップを可能にするアルゴリズムフレームワークが含まれている。
また、このファミリーの外部にある特性であるグラフ双分極性をテストするためのQMAアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-05-08T13:15:30Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。