論文の概要: Quantum Time Lower Bounds by Permutation Invariance

• arxiv url: http://arxiv.org/abs/2606.05099v1
• Date: Wed, 03 Jun 2026 17:03:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-04 20:44:18.909508
• Title: Quantum Time Lower Bounds by Permutation Invariance
• Title（参考訳）: 置換不変量による量子時間下界
• Authors: Qisheng Wang,
• Abstract要約: 我々は、量子状態の置換不変性をテストするために、量子時間複雑性の低い境界を確立するためのフレームワークを提供する。 応用として、入力量子状態へのサンプルアクセスが与えられたときに、一致した下界の一連の値を得る。 我々の知る限りでは、これは量子時間複雑性の厳密な下限を体系的に確立できる最初の方法である。
• 参考スコア（独自算出の注目度）: 13.491187998442596
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tight bounds on quantum sample complexity and quantum query complexity have been known for various computational problems in the literature, whereas tight bounds on quantum time complexity (i.e., the size of quantum circuits) remain unresolved. In this paper, we provide a framework to establish lower bounds on the quantum time complexity for testing permutation-invariant properties of quantum states, via a reduction from quantum sample complexity. As an application, we obtain a series of matching lower bounds when given sample access to the input quantum states, including: 1. The SWAP test due to Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) is time-optimal to estimate the purity $\operatorname{tr}(ρ^2)$ and the inner product $\operatorname{tr}(ρσ)$. 2. The Shift test due to Ekert, Alves, Oi, Horodecki, Horodecki, and Kwek (Phys. Rev. Lett. 2002) is time-optimal to estimate the high-order functionals $\operatorname{tr}(ρ^k)$. 3. The productness tester for multipartite pure states due to Harrow and Montanaro (J. ACM 2013) is time-optimal. 4. The LMR protocol due to Lloyd, Mohseni, and Rebentrost (Nat. Phys. 2014) is time-optimal to implement the reflection operator about a pure state. 5. The samplizer due to Wang and Zhang (IEEE Trans. Inf. Theory 2025) is time-optimal for pure states. 6. The estimator for pure-state trace distance and fidelity due to Wang and Zhang (ICALP 2026) is time-optimal. To the best of our knowledge, this is the first method that allows us to systematically establish tight lower bounds on quantum time complexity.
• Abstract（参考訳）: 量子サンプルの複雑性と量子クエリの複雑さの厳密な境界は、文学における様々な計算問題で知られているが、量子時間複雑性(すなわち、量子回路のサイズ)の厳密な境界は未解決のままである。 本稿では,量子サンプルの複雑性の低減により,量子状態の置換不変性をテストするために,量子時間複雑性の低い境界を確立する枠組みを提供する。 応用として、入力量子状態へのサンプルアクセスが与えられたとき、以下の一連の一致した下界が得られる: 1. Buhrman, Cleve, Watrous, and de Wolf (Phys. Rev. Lett. 2001) によるSWAPテストは、純度 $\operatorname{tr}(ρ^2)$ と内積 $\operatorname{tr}(ρσ)$ を推定するのに最適である。 2. Ekert, Alves, Oi, Horodecki, Horodecki, Kwek (Phys. Rev. Lett. 2002) によるシフトテストは高階函数 $\operatorname{tr}(ρ^k)$ を推定するのに最適である。 3.Harrow と Montanaro (J. ACM 2013)による多部純状態の製品性テストは、時間最適である。 4. Lloyd, Mohseni, Rebentrost (Nat. Phys. 2014)によるLMRプロトコルは、純粋な状態に関するリフレクション演算子を実装するのに最適である。 5. Wang and Zhang (IEEE Trans. Inf. Theory 2025)によるサンプリング器は、純粋な状態に最適である。 6 Wang と Zhang (ICALP 2026) による純状態トレース距離と忠実度の推定器は、時間最適である。 我々の知る限りでは、これは量子時間複雑性の厳密な下限を体系的に確立できる最初の方法である。

関連論文リスト

• Enhancing Kerr-Cat Qubit Coherence with Controlled Dissipation [64.05054054401175]
  Kerr-cat qubit (KCQ) はボゾン量子プロセッサである。 KCQはオンチップアーキテクチャや高忠実度操作と実験的に互換性がある。 KCQ におけるビットフリップ時間は、キュービット多様体からの漏れによって制限されるという直接的な証拠を示す。
  論文  参考訳（メタデータ） (2025-11-02T17:58:36Z)
• The Power of Unentangled Quantum Proofs with Non-negative Amplitudes [55.90795112399611]
  非負の振幅を持つ非絡み合った量子証明のパワー、つまり $textQMA+(2)$ を表すクラスについて研究する。 特に,小集合拡張,ユニークなゲーム,PCP検証のためのグローバルプロトコルを設計する。 QMA(2) が $textQMA+(2)$ に等しいことを示す。
  論文  参考訳（メタデータ） (2024-02-29T01:35:46Z)
• 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)
• Quantum Speed Limit for Change of Basis [55.500409696028626]
  量子速度制限の概念を量子状態の集合に拡張する。 2量子系に対して、最も高速な変換は2つのアダマールを同時に実装し、キュービットをスワップすることを示した。 キュートリット系では、進化時間は偏りのない基底の特定のタイプに依存する。
  論文  参考訳（メタデータ） (2022-12-23T14:10:13Z)
• Improved Quantum Algorithms for Fidelity Estimation [77.34726150561087]
  証明可能な性能保証を伴う忠実度推定のための新しい,効率的な量子アルゴリズムを開発した。 我々のアルゴリズムは量子特異値変換のような高度な量子線型代数技術を用いる。 任意の非自明な定数加算精度に対する忠実度推定は一般に困難であることを示す。
  論文  参考訳（メタデータ） (2022-03-30T02:02:16Z)

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

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