論文の概要: A complexity theory for non-local quantum computation

• arxiv url: http://arxiv.org/abs/2505.23893v1
• Date: Thu, 29 May 2025 18:00:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-02 19:47:52.605853
• Title: A complexity theory for non-local quantum computation
• Title（参考訳）: 非局所量子計算における複雑性理論
• Authors: Andreas Bluhm, Simon Höfer, Alex May, Mikka Stasiuk, Philip Verduyn Lunel, Henry Yuen,
• Abstract要約: 非局所量子計算(NLQC)は、2つのシステム間の局所的な相互作用を1ラウンドの通信と共有絡みで置き換える。 本研究では,NLQCタスク間のリソース効率の低下を同定し,NLQCタスクの相対的硬度について検討する。 最も顕著なのは、NLQCの最もよく研究された2つのタスクである$f$-measureと$f$-routeが、実際は$O(1)$オーバーヘッド削減の下で等価であることを証明したことである。
• 参考スコア（独自算出の注目度）: 0.9895793818721335
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Non-local quantum computation (NLQC) replaces a local interaction between two systems with a single round of communication and shared entanglement. Despite many partial results, it is known that a characterization of entanglement cost in at least certain NLQC tasks would imply significant breakthroughs in complexity theory. Here, we avoid these obstructions and take an indirect approach to understanding resource requirements in NLQC, which mimics the approach used by complexity theorists: we study the relative hardness of different NLQC tasks by identifying resource efficient reductions between them. Most significantly, we prove that $f$-measure and $f$-route, the two best studied NLQC tasks, are in fact equivalent under $O(1)$ overhead reductions. This result simplifies many existing proofs in the literature and extends several new properties to $f$-measure. For instance, we obtain sub-exponential upper bounds on $f$-measure for all functions, and efficient protocols for functions in the complexity class $\mathsf{Mod}_k\mathsf{L}$. Beyond this, we study a number of other examples of NLQC tasks and their relationships.
• Abstract（参考訳）: 非局所量子計算(NLQC)は、2つのシステム間の局所的な相互作用を1ラウンドの通信と共有絡みで置き換える。 多くの部分的な結果にもかかわらず、少なくとも特定のNLQCタスクにおける絡み合いのコストの特性は、複雑性理論において重大なブレークスルーをもたらすことが知られている。 本稿では,これらの障害を回避し,NLQCの資源要求を理解するための間接的アプローチをとる。これは複雑性理論家によるアプローチを模したもので,NLQCタスク間のリソース効率の低下を識別して,異なるNLQCタスクの相対的硬さについて検討する。 最も重要なことは、NLQCの最もよく研究された2つのタスクである$f$-measureと$f$-routeが、実際は$O(1)$オーバーヘッド削減の下で等価であることを証明している。 この結果は、文献における多くの既存の証明を単純化し、いくつかの新しい性質を$f$- measureまで拡張する。 例えば、すべての関数に対する$f$-測度上の部分指数上界と、複雑性クラス $\mathsf{Mod}_k\mathsf{L}$ の関数に対する効率的なプロトコルを得る。 さらに,NLQCタスクとその関連性について,いくつかの例について検討する。

関連論文リスト

• Rank lower bounds on non-local quantum computation [0.0]
  非局所量子計算(NLQC)は、2つの量子システム間の相互作用を1ラウンドの通信と共有絡みによって置き換える。 NLQCの2つのクラス、$f$-routingと$f$-BB84を研究し、これは古典的な情報理論の暗号と量子位置の検証に関係している。
  論文  参考訳（メタデータ） (2024-02-28T19:00:09Z)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation [66.26739783789387]
  我々は、強化学習のための新しいアルゴリズム、MQL-UCBを用いたモノトニックQ-Learningを提案する。 MQL-UCBは、$tildeO(dsqrtHK)$の最小限の後悔を実現する。 本研究は,非線形関数近似を用いたサンプル効率およびデプロイメント効率のよいQ-ラーニングの設計に重点を置いている。
  論文  参考訳（メタデータ） (2023-11-26T08:31:57Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
  本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。 一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
  論文  参考訳（メタデータ） (2023-05-28T19:40:46Z)
• Approximate traces on groups and the quantum complexity class $\operatorname{MIP}^{co,s}$ [0.0]
  量子交換相関に近似をエンコードするqc-モジュラーの概念を導入する。 計算可能なqc-モジュラーの存在は、上記の質問の自然な変形に対して負の答えを与えることを示す。
  論文  参考訳（メタデータ） (2022-09-16T15:45:49Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  回路レベルの実装とリソース推定を行い、古典データの高密度な$Ntimes N$行列をブロックエンコードして$epsilon$を精度良くすることができる。 異なるアプローチ間のリソーストレードオフを調査し、量子ランダムアクセスメモリ(QRAM)の2つの異なるモデルの実装を検討する。 我々の結果は、単純なクエリの複雑さを超えて、大量の古典的データが量子アルゴリズムにアクセスできると仮定された場合のリソースコストの明確な図を提供する。
  論文  参考訳（メタデータ） (2022-06-07T18:00:01Z)
• Causality Constraint on Circuit Complexity from $COSMOEFT$ [1.5643170704979468]
  本稿では,回路複雑度測定とエンタングルメントエントロピーのスケール係数および$c_s$に対する挙動について検討する。 窓の内側には、因果性と宇宙観測の両方によって支えられる0.024leq c_sleq 1$という、興味深い未発見の様々な特徴がある。
  論文  参考訳（メタデータ） (2021-11-22T19:09:51Z)
• Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning [82.31436758872715]
  我々は,環境相互作用の$O(1)$のエピソードのみを用いて,同一のPAC保証を実現するアルゴリズムを開発した。 値関数と有限水平マルコフ決定過程の接続を確立する。
  論文  参考訳（メタデータ） (2021-11-01T00:21:24Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
  分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。 この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
  論文  参考訳（メタデータ） (2020-07-30T04:18:51Z)

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

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