論文の概要: Analytical lower bound on query complexity for transformations of unknown unitary operations
- arxiv url: http://arxiv.org/abs/2405.07625v2
- Date: Thu, 28 Nov 2024 05:07:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-02 15:16:02.106481
- Title: Analytical lower bound on query complexity for transformations of unknown unitary operations
- Title(参考訳): 未知のユニタリ演算の変換に対するクエリ複雑性に関する解析的下界
- Authors: Tatsuki Odake, Satoshi Yoshida, Mio Murao,
- Abstract要約: 単元反転の問合せ複雑性に対する解析的下界を確立する。
フレームワークを確率的設定にまで拡張し、ある確率で変換を成功させなければなりません。
- 参考スコア(独自算出の注目度): 0.8192907805418581
- License:
- 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. 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 probabilistic setting, where transformations must succeed with a certain probability, revealing a potential trade-off between the number of queries and the required success probability.
- Abstract(参考訳): 近年, 複雑な共役, 逆転, 一般の$d$次元未知のユニタリ演算を有限個のクエリを用いてブラックボックスユニタリ演算に変換するための決定論的かつ正確なプロトコルが明らかにされている。
本研究では, 単元反転, 転置, 複素共役の問合せ複雑性に対する解析的下界を確立する。
具体的には、単項逆転に対する$d^2$の低い境界は、$O(d^2)$クエリで動作する決定論的正確な逆転プロトコルの漸近的最適性を示す。
一般微分可能関数 $f: \mathrm{SU}(d)\to \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) - The Complexity of Being Entangled [0.0]
ニールセンの量子状態複雑性へのアプローチは、一元変換の多様体上の特定のノルムで計算された測地線の長さに状態を作るのに必要な最小の量子ゲート数に関係している。
バイパーティイトシステムでは,単一サブシステムに作用するゲートがコストがかからないノルムに対応する結合複雑性について検討する。
論文 参考訳(メタデータ) (2023-11-07T19:00:02Z) - 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) - 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) - 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) - Revisiting the Sample Complexity of Sparse Spectrum Approximation of
Gaussian Processes [60.479499225746295]
本稿では,ガウス過程に対して,パラメータ空間全体に対して同時に保持可能な保証付きスケーラブルな近似を導入する。
我々の近似は、スパーススペクトルガウス過程(SSGP)のための改良されたサンプル複雑性解析から得られる。
論文 参考訳(メタデータ) (2020-11-17T05:41:50Z) - Theoretical Convergence of Multi-Step Model-Agnostic Meta-Learning [63.64636047748605]
一般的なマルチステップMAMLアルゴリズムに対して収束保証を提供するための新しい理論フレームワークを開発する。
特に,本研究の結果は,収束を保証するためには,内部段階のステップを逆比例して$N$の内段ステップを選択する必要があることを示唆している。
論文 参考訳(メタデータ) (2020-02-18T19:17:54Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。