論文の概要: Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations

• arxiv url: http://arxiv.org/abs/2405.07625v3
• Date: Fri, 07 Nov 2025 00:37:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-10 16:56:00.893417
• Title: Analytical Lower Bound on Query Complexity for Transformations of Unknown Unitary Operations
• Title（参考訳）: 未知のユニタリ演算の変換におけるクエリ複雑度に関する解析的下界
• Authors: Tatsuki Odake, Satoshi Yoshida, Mio Murao,
• Abstract要約: 単元反転, 転置, 複素共役の問合せ複雑性に対する解析的下界を確立する。 単位反転に対する$d2$の低い境界は、決定論的正確な反転プロトコルの最適性を示している。 入力ユニタリ演算は$mathrmSU(d)$と確率的部分群設定の範囲内で約束される。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recent developments have revealed deterministic and exact protocols for performing complex conjugation, inversion, and transposition of a general $d$-dimensional unknown unitary operation using a finite number of queries to a black-box unitary operation. In this work, we establish analytical lower bounds for the query complexity of unitary inversion, transposition, and complex conjugation, which hold even if the input unitary is an unknown logarithmic-depth unitary. Specifically, our lower bound of $d^2$ for unitary inversion demonstrates the asymptotic optimality of the deterministic exact inversion protocol, which operates with $O(d^2)$ queries. We introduce a novel framework utilizing differentiation to derive these lower bounds on query complexity for general differentiable functions $f: \mathrm{SU}(d)\to \mathrm{SU}(d)$. As a corollary, we prove that a catalytic protocol -- a new concept recently noted in the study of exact unitary inversion -- is impossible for unitary complex conjugation. Furthermore, we extend our framework to the partially known setting, where the input unitary operation is promised to be within a subgroup of $\mathrm{SU}(d)$ and the probabilistic setting, where transformations succeed probabilistically.
• Abstract（参考訳）: 近年, 複雑な共役, 逆転, 一般の$d$次元未知のユニタリ演算を有限個のクエリを用いてブラックボックスユニタリ演算に変換するための決定論的かつ正確なプロトコルが明らかにされている。 本研究では、入力ユニタリが未知の対数-深度ユニタリであっても保たれるユニタリ反転、転置、複素共役のクエリ複雑性に対する解析的下界を確立する。 具体的には、単項逆転に対する$d^2$の低い境界は、$O(d^2)$クエリで動作する決定論的正確な逆転プロトコルの漸近的最適性を示す。 一般微分可能関数 $f: \mathrm{SU}(d)\to \mathrm{SU}(d)$ に対するクエリ複雑性の下位境界を導出するために微分を利用した新しいフレームワークを導入する。 結論として、単体複素共役では触媒プロトコル(最近、正確な単体反転の研究で言及された新しい概念)は不可能であることを示す。 さらに、入力ユニタリ演算が$\mathrm{SU}(d)$のサブグループと確率的設定に含まれ、変換が確率的に成功する。

関連論文リスト

• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective [55.15192437680943]
  連続状態と行動空間を持つ非線形力学系に対するオンライン強化学習のサンプル複雑性について検討した。 我々のアルゴリズムは、その単純さ、事前知識を組み込む能力、そして良心的な過渡的行動のために、実際に有用である可能性が高い。
  論文  参考訳（メタデータ） (2025-01-27T10:01:28Z)
• Generalized Rényi entropy accumulation theorem and generalized quantum probability estimation [0.0]
  エントロピー蓄積定理は、多くのデバイス依存およびデバイス非依存の暗号プロトコルのセキュリティ解析において強力なツールである。 Affine min-tradeoff関数の構築に依存しており、実際に最適に構築することはしばしば困難である。 新たにエントロピー蓄積境界が導出され,有限サイズ性能が著しく向上した。
  論文  参考訳（メタデータ） (2024-05-09T17:11:00Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  我々は,PCAが信号の大きさの臨界値で計算的に困難になることを示す。 我々は、与えられた次数の不変量に対して明示的でほぼ直交的な基底を与える新しい対象の集合を定義する。 また、異なるアンサンブルを区別する新しい問題も分析できます。
  論文  参考訳（メタデータ） (2024-04-29T14:33:24Z)
• Complexity-Theoretic Implications of Multicalibration [8.315801422499863]
  多精度予測器はより強い条件を満たす:それらはコレクションの各セットで校正される。 この複雑性理論的正則性レンマは、異なる領域に影響を及ぼすことが知られている。 すべての函数(その硬さによらず)が不随伴なハードコア集合の小さな集合を持つことが示される。
  論文  参考訳（メタデータ） (2023-12-28T18:53:21Z)
• The Complexity of Being Entangled [0.0]
  ニールセンの量子状態複雑性へのアプローチは、一元変換の多様体上の特定のノルムで計算された測地線の長さに状態を作るのに必要な最小の量子ゲート数に関係している。 バイパーティイトシステムでは,単一サブシステムに作用するゲートがコストがかからないノルムに対応する結合複雑性について検討する。
  論文  参考訳（メタデータ） (2023-11-07T19:00:02Z)
• On Representation Complexity of Model-based and Model-free Reinforcement Learning [11.843778337443824]
  回路複雑性の文脈におけるモデルベースおよびモデルフリー強化学習(RL)の表現複雑性について検討した。 理論的には、その基底となる遷移関数と報酬関数が、大きさの一定深さの回路で表現できるような、幅広い種類のMDPが存在することを証明している。 近似誤差に注意を向け、複雑性理論への接続を構築することによって、モデルベースのアルゴリズムが、新しい表現複雑性の観点からモデルフリーアルゴリズムよりも、なぜサンプルの複雑さを楽しむのかというユニークな洞察を提供する。
  論文  参考訳（メタデータ） (2023-10-03T00:01:58Z)
• Explicit error bounds for entanglement transformations between sparse multipartite states [0.0]
  このような機能指数の非自明な族が最近構築されている。 部分加法的上界という観点から、これらの汎函数に対する新たな正規化公式を導出する。 この結果は,局所演算と古典的通信による変換の成功確率に明確な境界を与える。
  論文  参考訳（メタデータ） (2023-09-20T16:06:48Z)
• Reconstructing $S$-matrix Phases with Machine Learning [49.1574468325115]
  我々は、ユニタリティ制約の研究に現代の機械学習技術を適用した。 我々は、そのような解に対する既知の限界を以前の境界を超えるような新しい位相あいまいな解を求める。
  論文  参考訳（メタデータ） (2023-08-18T10:29:26Z)
• Generalization Guarantees via Algorithm-dependent Rademacher Complexity [33.408679482592426]
  本稿では,アルゴリズムおよびデータ依存仮説クラスの経験的ラデマッハ複雑性である一般化誤差を制御する尺度を提案する。 有限フラクタル次元に基づく新しい境界を得るが、これは (a) 従来のフラクタル型境界を連続的な仮説クラスから有限的な仮説クラスに拡張し、 (b) 相互情報項を避ける。
  論文  参考訳（メタデータ） (2023-07-04T18:37:38Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。 これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。 我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
  論文  参考訳（メタデータ） (2022-10-12T03:01:00Z)
• Reversing Unknown Qubit-Unitary Operation, Deterministically and Exactly [0.9208007322096532]
  量子回路モデルにおける未知のユニタリ演算を変換するプロトコルの最も一般的なクラスを考える。 提案プロトコルでは、入力キュービット単位演算を4回呼び、逆演算を実現する。 可能なすべてのプロトコルを表す巨大な検索空間を削減できる手法を提案する。
  論文  参考訳（メタデータ） (2022-09-07T03:33:09Z)
• The Dynamics of Riemannian Robbins-Monro Algorithms [101.29301565229265]
  本稿では,Robins と Monro のセミナル近似フレームワークを一般化し拡張するリーマンアルゴリズムの族を提案する。 ユークリッドのそれと比較すると、リーマンのアルゴリズムは多様体上の大域線型構造が欠如しているため、はるかに理解されていない。 ユークリッド・ロビンス=モンロスキームの既存の理論を反映し拡張するほぼ確実な収束結果の一般的なテンプレートを提供する。
  論文  参考訳（メタデータ） (2022-06-14T12:30:11Z)
• $O(N^2)$ Universal Antisymmetry in Fermionic Neural Networks [107.86545461433616]
  我々は、置換同変アーキテクチャを提案し、その上で行列式 Slater を適用して反対称性を誘導する。 FermiNetは、単一の行列式を持つ普遍近似能力があることが証明されている。 これは実装が容易であり、計算コストを$O(N2)$に下げることができる。
  論文  参考訳（メタデータ） (2022-05-26T07:44:54Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• Bounds on quantum evolution complexity via lattice cryptography [0.0]
  量子論における可積分運動とカオス運動の差は、対応する進化作用素の複雑さによって表される。 ここでの複雑性は、時間依存進化作用素とユニタリ群内の原点の間の最短測地線距離として理解されている。
  論文  参考訳（メタデータ） (2022-02-28T16:20:10Z)
• Instance-optimality in optimal value estimation: Adaptivity via variance-reduced Q-learning [99.34907092347733]
  本稿では,マルコフ決定過程における最適な$Q$値関数を離散状態と動作で推定する問題を解析する。 局所的なミニマックスフレームワークを用いて、この関数は任意の推定手順の精度の低い境界に現れることを示す。 他方,Q$ラーニングの分散還元版を解析することにより,状態と行動空間の対数的要因まで,下位境界のシャープさを確立する。
  論文  参考訳（メタデータ） (2021-06-28T00:38:54Z)
• Quantifying and Improving Transferability in Domain Generalization [53.16289325326505]
  アウト・オブ・ディストリビューションの一般化は、実験室から現実世界にモデルを移す際の重要な課題の1つである。 我々は、領域一般化において量子化と計算が可能な転送可能性を正式に定義する。 転送可能な特徴を学習し、様々なベンチマークデータセット上でテストするための新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-07T14:04:32Z)
• Nonparametric approximation of conditional expectation operators [0.3655021726150368]
  最小の仮定の下で、$[Pf](x) := mathbbE[f(Y) mid X = x ]$ で定義される$L2$-operatorの近似について検討する。 我々は、再生されたカーネル空間上で作用するヒルベルト・シュミット作用素により、作用素ノルムにおいて$P$が任意に適切に近似できることを証明した。
  論文  参考訳（メタデータ） (2020-12-23T19:06:12Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。 我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
  論文  参考訳（メタデータ） (2020-11-17T05:41:50Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。 これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。 ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
  論文  参考訳（メタデータ） (2020-05-11T14:52:16Z)
• Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning [63.64636047748605]
  一般的なマルチステップMAMLアルゴリズムに対して収束保証を提供するための新しい理論フレームワークを開発する。 特に,本研究の結果は,収束を保証するためには,内部段階のステップを逆比例して$N$の内段ステップを選択する必要があることを示唆している。
  論文  参考訳（メタデータ） (2020-02-18T19:17:54Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。 レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
  論文  参考訳（メタデータ） (2019-09-04T11:46:26Z)

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

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