論文の概要: A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting

• arxiv url: http://arxiv.org/abs/2512.01971v1
• Date: Mon, 01 Dec 2025 18:27:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-02 19:46:35.015835
• Title: A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
• Title（参考訳）: 量子サンプル・ツー・クエリ・リフティングによる特性試験における複雑度境界の一覧
• Authors: Kean Chen, Qisheng Wang, Zhicheng Zhang,
• Abstract要約: 本稿では, 量子サンプル・ツー・クエリ・リフト法により得られた特性試験のために, 量子下限と上限の値のリストをコンパイルする。 興味のある問題には、確率分布とエントロピーや近接性のような量子状態のテストの性質が含まれる。 合計で49の複雑性境界を示し、41は新しく、18は(ほぼ)最適である。
• 参考スコア（独自算出の注目度）: 33.25179630727782
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum sample-to-query lifting, a relation between quantum sample complexity and quantum query complexity presented in Wang and Zhang (SIAM J. Comput. 2025), was significantly strengthened by Tang, Wright, and Zhandry (2025) to the case of state-preparation oracles. In this paper, we compile a list of quantum lower and upper bounds for property testing that are obtained by quantum sample-to-query lifting. The problems of interest include testing properties of probability distributions and quantum states, such as entropy and closeness. This collection contains new results, as well as new proofs of known bounds. In total, we present 49 complexity bounds, where 41 are new and 18 are (near-)optimal.
• Abstract（参考訳）: Wang と Zhang (SIAM J. Comput. 2025) で提示された量子サンプルの複雑性と量子クエリの複雑性の関係である量子サンプル・ツー・クエリ・リフトは、Tang, Wright, Zhandry (2025) によって状態準備のオーラクルの場合に著しく強化された。 本稿では, 量子サンプル・ツー・クエリ・リフト法により得られた特性試験のために, 量子下限と上限の値のリストをコンパイルする。 興味のある問題には、確率分布とエントロピーや近接性のような量子状態のテストの性質が含まれる。 このコレクションは、既知の境界の新しい証明と同様に、新しい結果を含む。 合計で49の複雑性境界を示し、41は新しく、18は(ほぼ)最適である。

関連論文リスト

• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• Quantum Lower Bounds by Sample-to-Query Lifting [33.82353457014144]
  本稿では,量子サンプル対クエリリフト定理を用いて,量子クエリの下界を証明するための新しい手法を提案する。 位相/振幅推定やハミルトニアンシミュレーションなど,いくつかの既知の下界に対する統一的な証明を提供する。
  論文  参考訳（メタデータ） (2023-08-03T14:41:49Z)
• Simple Tests of Quantumness Also Certify Qubits [69.96668065491183]
  量子性の検定は、古典的検証者が証明者が古典的でないことを(のみ)証明できるプロトコルである。 我々は、あるテンプレートに従う量子性のテストを行い、(Kalai et al., 2022)のような最近の提案を捉えた。 すなわち、同じプロトコルは、証明可能なランダム性や古典的な量子計算のデリゲートといったアプリケーションの中心にあるビルディングブロックであるqubitの認定に使用できる。
  論文  参考訳（メタデータ） (2023-03-02T14:18:17Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。 これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。 我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
  論文  参考訳（メタデータ） (2022-10-12T03:01:00Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)
• Depth-efficient proofs of quantumness [77.34726150561087]
  量子性の証明は、古典的検証器が信頼できない証明器の量子的利点を効率的に証明できる挑戦応答プロトコルの一種である。 本稿では、証明者が量子回路を一定深度でしか実行できない量子性構成の証明を2つ与える。
  論文  参考訳（メタデータ） (2021-07-05T17:45:41Z)

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

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