論文の概要: Unitary property testing lower bounds by polynomials

• arxiv url: http://arxiv.org/abs/2210.05885v2
• Date: Fri, 9 Dec 2022 03:54:52 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-22 19:48:25.746041
• Title: Unitary property testing lower bounds by polynomials
• Title（参考訳）: 多項式による下限のユニタリ特性検定
• Authors: Adrian She, Henry Yuen
• Abstract要約: 我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。 これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。 我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
• 参考スコア（独自算出の注目度）: 0.15229257192293197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary and has to decide whether it satisfies some property. In addition to containing the standard quantum query complexity model (where the unitary encodes a binary string) as a special case, this model contains "inherently quantum" problems that have no classical analogue. Characterizing the query complexity of these problems requires new algorithmic techniques and lower bound methods. Our main contribution is a generalized polynomial method for unitary property testing problems. By leveraging connections with invariant theory, we apply this method to obtain lower bounds on problems such as determining recurrence times of unitaries, approximating the dimension of a marked subspace, and approximating the entanglement entropy of a marked state. We also present a unitary property testing-based approach towards an oracle separation between $\mathsf{QMA}$ and $\mathsf{QMA(2)}$, a long standing question in quantum complexity theory.
• Abstract（参考訳）: 我々は、量子アルゴリズムがブラックボックスユニタリへのクエリアクセスを付与され、ある特性を満たすかどうかを判断するユニタリプロパティテストについて研究する。 標準的な量子クエリ複雑性モデル(ユニタリがバイナリ文字列をエンコードする)を特別なケースとして含むことに加えて、このモデルは古典的な類似点を持たない「本質的に量子的な」問題を含む。 これらの問題のクエリ複雑性を特徴づけるには、新しいアルゴリズム技術と低いバウンドメソッドが必要である。 我々の主な貢献はユニタリプロパティテスト問題に対する一般化多項式法である。 不変理論との接続を利用して、ユニタリの繰り返し時間の決定、マークされた部分空間の次元の近似、マークされた状態の絡み合いエントロピーの近似などの問題に対する下界を求める。 我々はまた,量子複雑性理論における長年の疑問である$\mathsf{qma}$と$\mathsf{qma(2)}$とのoracle分離に対する,ユニタリプロパティテストに基づくアプローチも提示する。

関連論文リスト

• Complexity Theory for Quantum Promise Problems [5.049812996253858]
  本稿では,量子暗号と複雑性理論の関係,特にImpagliazzoの5つの世界の枠組みについて考察する。 複雑性クラス p/mBQP, p/mQ(C)MA, $mathrmp/mQSZK_hv$, p/mQIP, p/mPSPACE に注目する。 我々は、このフレームワークを暗号に適用し、一方通行状態生成器、擬似ランダム状態、EFIがmQCMAで束縛されていることを示す。
  論文  参考訳（メタデータ） (2024-11-06T07:29:52Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• Lower bounds for quantum-inspired classical algorithms via communication complexity [0.5461938536945723]
  線形回帰の解法,クラスタリングの監督,主成分分析,レコメンデーションシステム,ハミルトニアンシミュレーションに焦点をあてる。 基底行列のフロベニウスノルムの観点で二次下界を証明する。 これらの問題に対する量子アルゴリズムはフロベニウスノルムにおいて線型であるため、この結果は量子古典的分離が少なくとも二次的であることを意味する。
  論文  参考訳（メタデータ） (2024-02-24T02:15:00Z)
• Lower Bounds for Unitary Property Testing with Proofs and Advice [0.0]
  本稿では,一元性検定における量子クエリの下位境界を証明するための新しい手法を提案する。 すべての得られる下限は$mathsfC$-testerで$mathsfC subseteq mathsfQMA(2)/mathsfqpoly$である。 我々は、$mathsfQMA(2) notsupset mathsfSBQP$と$mathsfQMA/mathsfqpolyの量子オラクルが存在することを示した。
  論文  参考訳（メタデータ） (2024-01-15T19:00:36Z)
• 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)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• 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)
• Quantum Hypothesis Testing with Group Structure [0.0]
  最近開発された量子信号処理技術は、量子仮説テストのためのサブルーチンを構成するように修正することができる。 性能は明示的な群準同型によって完全に定義される。 大規模グループへの拡張とノイズの多い設定について論じる。
  論文  参考訳（メタデータ） (2021-02-03T18:46:51Z)

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

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