論文の概要: Circuit complexity and functionality: a thermodynamic perspective
- arxiv url: http://arxiv.org/abs/2309.05731v1
- Date: Mon, 11 Sep 2023 18:02:21 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-13 15:29:30.964257
- Title: Circuit complexity and functionality: a thermodynamic perspective
- Title(参考訳): 回路の複雑さと機能性:熱力学的展望
- Authors: Claudio Chamon, Andrei E. Ruckenstein, Eduardo R. Mucciolo, Ran
Canetti
- Abstract要約: 所定の関数の回路エントロピーと一定数のゲートを回路複雑性に結びつける。
任意の長さのプログラムの難読化のための枠組みを定式化する。
我々は、複雑性クラス NP と coNP が一致しない限り、断片化は避けられないと主張する。
- 参考スコア(独自算出の注目度): 2.5113538231331685
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We explore a link between complexity and physics for circuits of given
functionality. Taking advantage of the connection between circuit counting
problems and the derivation of ensembles in statistical mechanics, we tie the
entropy of circuits of a given functionality and fixed number of gates to
circuit complexity. We use thermodynamic relations to connect the quantity
analogous to the equilibrium temperature to the exponent describing the
exponential growth of the number of distinct functionalities as a function of
complexity. This connection is intimately related to the finite compressibility
of typical circuits. Finally, we use the thermodynamic approach to formulate a
framework for the obfuscation of programs of arbitrary length -- an important
problem in cryptography -- as thermalization through recursive mixing of
neighboring sections of a circuit, which can viewed as the mixing of two
containers with ``gases of gates''. This recursive process equilibrates the
average complexity and leads to the saturation of the circuit entropy, while
preserving functionality of the overall circuit. The thermodynamic arguments
hinge on ergodicity in the space of circuits which we conjecture is limited to
disconnected ergodic sectors due to fragmentation. The notion of fragmentation
has important implications for the problem of circuit obfuscation as it implies
that there are circuits with same size and functionality that cannot be
connected via local moves. Furthermore, we argue that fragmentation is
unavoidable unless the complexity classes NP and coNP coincide, a statement
that implies the collapse of the polynomial hierarchy of complexity theory to
its first level.
- Abstract(参考訳): 我々は,与えられた機能を持つ回路の複雑性と物理の関係を考察する。
統計力学における回路計数問題とアンサンブルの導出との関係を生かして,与えられた関数の回路のエントロピーと一定数のゲートのエントロピーを回路複雑性に結びつける。
熱力学的関係を用いて平衡温度に類似した量を指数関数に結びつけ、異なる関数の数の指数関数的な成長を複雑性の関数として記述する。
この接続は典型回路の有限圧縮性と密接に関連している。
最後に、熱力学的手法を用いて任意の長さのプログラム -- 暗号において重要な問題 -- の難読化のための枠組みを、回路の隣接部分の再帰的混合による熱化として定式化し、これは2つの容器と「ゲートのガス」との混合と見なすことができる。
この再帰的過程は、平均的な複雑性を平衡させ、回路全体の機能を保ちながら、回路エントロピーの飽和に繋がる。
私たちが予想する回路空間におけるエルゴード性に関する熱力学の議論は、断片化による非連結エルゴードセクターに限られる。
フラグメンテーションの概念は、回路難読化の問題に重要な意味を持ち、これは局所移動によって接続できない同じ大きさと機能を持つ回路が存在することを意味する。
さらに、複雑性クラス NP と coNP が一致しない限り、断片化は避けられないと主張する。
関連論文リスト
- Unified framework for efficiently computable quantum circuits [0.0]
クリフォードとマッチゲートからなる量子回路は、古典的コンピュータ上で効率的にシミュレート可能であることが知られている2種類の回路である。
我々は、これらの回路を効率的にシミュレートできる特別な構造を透過的に示す統一されたフレームワークを導入する。
論文 参考訳(メタデータ) (2024-01-16T08:04:28Z) - Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - The Complexity of Being Entangled [0.0]
ニールセンの量子状態複雑性へのアプローチは、一元変換の多様体上の特定のノルムで計算された測地線の長さに状態を作るのに必要な最小の量子ゲート数に関係している。
バイパーティイトシステムでは,単一サブシステムに作用するゲートがコストがかからないノルムに対応する結合複雑性について検討する。
論文 参考訳(メタデータ) (2023-11-07T19:00:02Z) - Krylov complexity and Trotter transitions in unitary circuit dynamics [0.0]
ハミルトン力学のトロッター分解にともなうフロケット回路について検討した。
局所極大エルゴード作用素は臨界トロッターステップに現れる。
論文 参考訳(メタデータ) (2023-08-07T18:01:29Z) - A Circuit Complexity Formulation of Algorithmic Information Theory [1.5483078145498086]
インダクティブ推論のソロモノフ理論に着想を得て,回路複雑性に基づく先行モデルを提案する。
回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切であると主張する。
論文 参考訳(メタデータ) (2023-06-25T01:30:37Z) - Adaptive Planning Search Algorithm for Analog Circuit Verification [53.97809573610992]
シミュレーションの少ない機械学習(ML)アプローチを提案する。
提案手法により,OCCを全回路の仕様に近づけることができることを示す。
論文 参考訳(メタデータ) (2023-06-23T12:57:46Z) - An Exponential Separation Between Quantum Query Complexity and the
Polynomial Degree [79.43134049617873]
本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。
アルファベットのサイズについては、定値対分離の複雑さがある。
論文 参考訳(メタデータ) (2023-01-22T22:08:28Z) - Circuit Complexity in an interacting quenched Quantum Field Theory [0.0]
量子クエンチが量子場理論の回路複雑性に及ぼす影響について検討する。
待ち行列および相互作用場理論における回路複雑性の解析計算について述べる。
論文 参考訳(メタデータ) (2022-09-07T18:00:03Z) - Decimation technique for open quantum systems: a case study with
driven-dissipative bosonic chains [62.997667081978825]
量子系の外部自由度への不可避結合は、散逸(非単体)ダイナミクスをもたらす。
本稿では,グリーン関数の(散逸的な)格子計算に基づいて,これらのシステムに対処する手法を提案する。
本手法のパワーを,複雑性を増大させる駆動散逸型ボゾン鎖のいくつかの例で説明する。
論文 参考訳(メタデータ) (2022-02-15T19:00:09Z) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
シャノンエントロピー推定の意思決定問題バージョンはエントロピー差分(ED)である
量子回路(QED)の類似の問題
オラクルと比較して、これらの問題は指数関数的に大きい回路と同等に難しいものではないことを示す。
論文 参考訳(メタデータ) (2020-02-27T15:32:08Z) - Hardware-Encoding Grid States in a Non-Reciprocal Superconducting
Circuit [62.997667081978825]
本稿では、非相互デバイスと、基底空間が2倍縮退し、基底状態がGottesman-Kitaev-Preskill(GKP)符号の近似符号であるジョセフソン接合からなる回路設計について述べる。
この回路は、電荷やフラックスノイズなどの超伝導回路の一般的なノイズチャネルに対して自然に保護されており、受動的量子誤差補正に使用できることを示唆している。
論文 参考訳(メタデータ) (2020-02-18T16:45:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。