論文の概要: Polynomial Equivalence of Complexity Geometries
- arxiv url: http://arxiv.org/abs/2205.04485v3
- Date: Tue, 25 Jun 2024 21:15:31 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-27 20:13:23.270607
- Title: Polynomial Equivalence of Complexity Geometries
- Title（参考訳）: 複雑度ジオメトリーの多項式等価性
- Authors: Adam R. Brown,
- Abstract要約: 本稿では、量子計算複雑性の幅広い定義の同値性を証明する。
ユニタリ群における右不変測度について検討する。
量子回路と同じ計算能力を持つ測定値の同値類を列挙する。
- 参考スコア（独自算出の注目度）: 0.05657375260432172
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper proves the polynomial equivalence of a broad class of definitions of quantum computational complexity. We study right-invariant metrics on the unitary group -- often called `complexity geometries' following the definition of quantum complexity proposed by Nielsen -- and delineate the equivalence class of metrics that have the same computational power as quantum circuits. Within this universality class, any unitary that can be reached in one metric can be approximated in any other metric in the class with a slowdown that is at-worst polynomial in the length and number of qubits and inverse-polynomial in the permitted error. We describe the equivalence classes for two different kinds of error we might tolerate: Killing-distance error, and operator-norm error. All metrics in both equivalence classes are shown to have exponential diameter; all metrics in the operator-norm equivalence class are also shown to give an alternative definition of the quantum complexity class BQP. My results extend those of Nielsen et al., who in 2006 proved that one particular metric is polynomially equivalent to quantum circuits. The Nielsen et al. metric is incredibly highly curved. I show that the greatly enlarged equivalence class established in this paper also includes metrics that have modest curvature. I argue that the modest curvature makes these metrics more amenable to the tools of differential geometry, and therefore makes them more promising starting points for Nielsen's program of using differential geometry to prove complexity lowerbounds.
- Abstract（参考訳）: 本稿では、量子計算複雑性の幅広い定義の多項式同値性を証明する。
我々は Nielsen が提唱した量子複雑性の定義に従って、ユニタリ群上の右不変測度(しばしば 'complexity geometries' と呼ばれる)を研究し、量子回路と同じ計算能力を持つ計量の同値類を列挙する。
この普遍性クラスの中で、1つの計量で到達できる任意のユニタリは、クラス内の任意の他の計量において、許容される誤差におけるクォービットの長さと個数における弱多項式と逆ポリノミカルのスローダウンで近似することができる。
我々は、許容される可能性のある2つの異なる種類のエラーに対する等価クラス、すなわちキルイング距離誤差と演算子ノルム誤差について述べる。
両方の同値類におけるすべての測度は指数的直径を持つことが示され、作用素-ノルム同値類におけるすべての測度もまた、量子複雑性類 BQP の代替的な定義を与える。
私の結果は、2006年にある特定の計量が量子回路と多項式的に等価であることを証明したNielsen et al の拡張である。
Nielsen et al の計量は驚くほど高い曲線である。
この論文で確立された大きく拡大した同値類は、控えめな曲率を持つ指標も含んでいることを示す。
控えめな曲率により、これらの測度は微分幾何学の道具により適しており、したがって、複雑性の低い境界を証明するために微分幾何学を使用するニールセンのプログラムにおいて、より有望な出発点となると私は論じる。
関連論文リスト
- Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳（メタデータ） (2023-11-27T14:45:19Z) - The Complexity of Being Entangled [0.0]
ニールセンの量子状態複雑性へのアプローチは、一元変換の多様体上の特定のノルムで計算された測地線の長さに状態を作るのに必要な最小の量子ゲート数に関係している。
バイパーティイトシステムでは,単一サブシステムに作用するゲートがコストがかからないノルムに対応する結合複雑性について検討する。
論文 参考訳（メタデータ） (2023-11-07T19:00:02Z) - Fluctuations, uncertainty relations, and the geometry of quantum state
manifolds [0.0]
パラメトリズド量子系の完全量子計量は、実部とシンプレクティック虚部を有する。
量子計量の実部と虚部の両方を混合した量子古典系が力学に寄与していることが示される。
論文 参考訳（メタデータ） (2023-09-07T10:31:59Z) - Enriching Disentanglement: From Logical Definitions to Quantitative Metrics [59.12308034729482]
複素データにおける説明的要因の解消は、一般化可能かつデータ効率のよい表現学習のための有望なアプローチである。
我々は、トポス理論とリッチな圏論を用いて、非絡み合いの論理的定義と量的メトリクスの間に理論的な関係を確立する。
本研究では,非交叉表現の異なる側面を分離することにより,提案手法の有効性を実証的に実証する。
論文 参考訳（メタデータ） (2023-05-19T08:22:23Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳（メタデータ） (2023-01-22T22:08:28Z) - A Quantum Complexity Lowerbound from Differential Geometry [0.0]
私はビショップ・グロモフ境界をニールセンの複雑性幾何学に適用し、典型的なユニタリの量子複雑性の下位境界を証明する。
幅広い種類のペナルティスケジュールに対して、典型的な複雑性は、キュービットの数で指数関数的に大きいことが示される。
この方法は、微分幾何学のツールを用いて量子複雑性を研究するNielsenの本来のビジョンを実現する。
論文 参考訳（メタデータ） (2021-12-10T18:28:01Z) - Universality in long-distance geometry and quantum complexity [0.04260910081285213]
低次元リー群上の測度は、非常に異なる短距離特性を持つが、遠距離でのほぼ同じ距離関数を持つことを示す。
我々は、量子複雑性の定義の大規模なクラスの存在を論じる。
論文 参考訳（メタデータ） (2021-11-24T18:52:44Z) - Finite-Function-Encoding Quantum States [52.77024349608834]
任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。
それらの構造的特性について検討する。
論文 参考訳（メタデータ） (2020-12-01T13:53:23Z) - Geometry of quantum complexity [0.0]
計算複雑性はホログラフィーにおいて重要な役割を果たす新しい量子情報の概念である。
Nielsenの幾何学的アプローチを用いて、$n$ qubitsの量子計算複雑性を考察する。
論文 参考訳（メタデータ） (2020-11-15T18:41:19Z) - A refinement of Reznick's Positivstellensatz with applications to
quantum information theory [72.8349503901712]
ヒルベルトの17番目の問題において、アルティンはいくつかの変数の任意の正定値が2つの平方和の商として書けることを示した。
レズニックはアルティンの結果の分母は常に変数の平方ノルムの$N$-次パワーとして選択できることを示した。
論文 参考訳（メタデータ） (2019-09-04T11:46:26Z) - Joint measurability meets Birkhoff-von Neumann's theorem [77.34726150561087]
我々は、この文脈でDNTの数学的特徴として関節測度が生じることを証明し、バーホフ=ヴォン・ノイマン(Birkhoff-von Neumann)と同様の性格化を確立する必要がある。
また、DNTは、一般作用素理論におけるその関連性に言及しながら、結合可測性問題の特定の事例から自然に現れることを示す。
論文 参考訳（メタデータ） (2018-09-19T18:57:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。