論文の概要: Computational Work Extraction: The Complexity of Catalysts

• arxiv url: http://arxiv.org/abs/2609.40323v1
• Date: Wed, 30 Sep 2026 17:55:18 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 18:57:28.322296
• Title: Computational Work Extraction: The Complexity of Catalysts
• Title（参考訳）: 計算作業抽出:触媒の複雑さ
• Abstract要約: 非条件存在分離を確立し、ランダムなオラクルモデルに明示的な構成を与える。 この研究は、エルゴトロピーと触媒計算の複雑さの間の重要な関係を明らかにする。 量子性プロトコルの特定の証明は、古典的および量子的触媒エルゴトロピーを一般化的に分離するために利用できることを示す。
• 参考スコア（独自算出の注目度）: 37.180329931346925
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We prove maximal separations: $n$-qubit systems can have $Θ(n)$ ergotropy, while every efficient process extracts negligible work, even for Hamiltonians consisting of single-qubit terms. We establish an unconditional existential separation and give an explicit construction in the random oracle model. Assuming the existence of quantum-secure pseudorandom functions, this separation extends to the plain model. This work uncovers an important connection between ergotropy and the complexity of catalytic computation---computation where auxiliary qubits must be finally restored to their initial state. Relative to a random oracle, we establish relational and decision problems that: (i) can be solved efficiently with $λ$ catalysts; but (ii) cannot be solved by any algorithm with $cλ$ catalysts, for any $c<1$. We show this by proving query lower bounds for quantum-space bounded algorithms. As a consequence, for computational ergotropy, catalysts prove to be surprisingly powerful---there is a family of Hamiltonians and states for which catalysts enable efficient extraction of the full $Θ(n)$ ergotropy, while every efficient non-catalytic process extracts negligible work. Furthermore, catalysts also allow us to introduce and instantiate the notion of pseudoergotropy---analogous to pseudorandomness. On the other hand, we show catalysts do not change (information-theoretic) ergotropy. Finally, our work also sheds light on the classical aspect of the problem. First, most of our constructions rely on classical states and Hamiltonians and therefore imply analogous results for classical ergotropy. Second, we show that certain proof of quantumness protocols can be used to generically separate classical and quantum catalytic ergotropy.
• Abstract（参考訳）: 最大分離を証明します:$n$-qubit system can have $(n)$ ergotropy, while every efficient process extracts negligible work, for Hamiltonians consist of single-qubit terms。 非条件存在分離を確立し、ランダムなオラクルモデルに明示的な構成を与える。 量子セキュア擬似ランダム関数の存在を仮定すると、この分離は平モデルに拡張される。 この研究は、エルゴトロピーと触媒計算の複雑さとの間の重要な関係を明らかにする。 ランダムなオラクルとは対照的に、リレーショナルと決定の問題を確立します。 i) λ$触媒で効率的に解けるが、 (ii) は、任意の$c<1$に対して、$cλ$触媒を持つ任意のアルゴリズムでは解けない。 量子空間有界アルゴリズムに対するクエリローバウンドの証明によりこれを示す。 その結果、計算的エルゴトロピーの場合、触媒は驚くほど強力であることが証明され、触媒が完全な$(n)$エルゴトロピーの効率的な抽出を可能にし、全ての効率的な非触媒プロセスは無視できる作業を引き出すハミルトンと状態の族が存在する。 さらに、触媒は擬エルゴトロピーの概念を導入し、インスタンス化することができる。 一方,触媒は(情報理論的な)エルゴトロピーを変化しないことを示す。 最後に、私たちの仕事は問題の古典的な側面にも光を当てています。 第一に、我々の構成のほとんどは古典的状態とハミルトン的状態に依存しており、従って古典的エルゴトロピーに類似した結果である。 第二に、量子性プロトコルの特定の証明は、古典的および量子的触媒エルゴトロピーを一般化的に分離するのに利用できることを示す。

関連論文リスト

• Stacking the Deck: Tunable Trainability in Stacked LCUs [5.3795542973467905]
  変分量子回路は、多くの量子コンピューティングの短期的応用の中心となっている。 本稿では,大理石高原と古典的シミュラビリティの相違点を提供する変分アンサッツとして,重畳されたユニタリの線形結合(S-LCU)を提案する。
  論文  参考訳（メタデータ） (2026-07-27T17:25:14Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  ハミルトニアン$H = sum_j h_j$ の場合、ゲート上の下界と量子コンピュータ上の時間発展をシミュレートするクエリの複雑さを証明できる。 任意の項ノルムのホールドは$|h_j|$, time $t$, trace-distance error $$である。
  論文  参考訳（メタデータ） (2026-07-22T07:41:32Z)
• DQC1-completeness of normalized trace estimation for functions of log-local Hamiltonians [20.990700912031773]
  正規化トレース 2-nTr[f(A)]$ を対数局所ハミルトニアン$A$ で$n$ qubits に作用させることの計算複雑性について検討する。 この問題は自然に DQC1 モデルで生じるが、その複雑性は限定された函数のクラス$f(x)$に対してのみ理解される。 f(x)$ が近似次数 $(rm poly(n))$ の連続関数であれば、2-nTr[f(A)]$ を定数加法誤差まで見積もる。
  論文  参考訳（メタデータ） (2026-04-02T01:15:12Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。 レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
  論文  参考訳（メタデータ） (2025-10-09T17:37:33Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  量子コンピュータを用いた結合型古典的高調波発振器系の周波数応答関数の推定問題について検討する。 提案する量子アルゴリズムは,標準的な$sスパース,オーラクルベースのクエリアクセスモデルで動作する。 そこで,本アルゴリズムの簡単な適応により,時間内に無作為な結束木問題を解くことを示す。
  論文  参考訳（メタデータ） (2024-05-14T15:28:37Z)
• Catalysing Completeness and Universality [0.0]
  特定のゲート集合が計算的に普遍であることを証明し、言語の結果をより大きなフラグメントに拡張する。 位相自由なZH-計算は、単一規則を用いるだけで、より大きな完全フラグメントに拡張可能であることを示す。
  論文  参考訳（メタデータ） (2024-04-15T16:40:24Z)
• Fast Rates for Maximum Entropy Exploration [52.946307632704645]
  エージェントが未知の環境下で活動し、報酬が得られない場合、強化学習(RL)における探索の課題に対処する。 本研究では,最大エントロピー探索問題を2つの異なるタイプで検討する。 訪問エントロピーには、$widetildemathcalO(H3S2A/varepsilon2)$ sample complexity を持つゲーム理論アルゴリズムを提案する。 軌道エントロピーに対しては,次数$widetildemathcalO(mathrmpoly(S,)の複雑さのサンプルを持つ単純なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-03-14T16:51:14Z)
• Generalized Zurek's bound on the cost of an individual classical or quantum computation [0.8806033070373618]
  Zurekは、このコストは$K(xvert y)$、条件付きコルモゴロフ複雑性$x$$$$$$$$$$$によって与えられると提案した。 我々は、$K(xvert y)$が$x$から$y$にマッピングする最小のコストであることを示す。
  論文  参考訳（メタデータ） (2023-01-17T12:35:08Z)
• The complexity of quantum support vector machines [1.7887848708497243]
  量子サポートベクトルマシンは、カーネル関数を定義するために量子回路を使用する。 二重問題は$O(M4.67/varepsilon2)$量子回路評価で解けることを示す。
  論文  参考訳（メタデータ） (2022-02-28T19:01:17Z)

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

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