論文の概要: 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 が一致しない限り、断片化は避けられないと主張する。

関連論文リスト

• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  任意の指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。 クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
  論文  参考訳（メタデータ） (2024-08-15T17:09:08Z)
• Unified framework for efficiently computable quantum circuits [0.0]
  クリフォードとマッチゲートからなる量子回路は、古典的コンピュータ上で効率的にシミュレート可能であることが知られている2種類の回路である。 我々は、これらの回路を効率的にシミュレートできる特別な構造を透過的に示す統一されたフレームワークを導入する。
  論文  参考訳（メタデータ） (2024-01-16T08:04:28Z)
• Taming Quantum Time Complexity [45.867051459785976]
  時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。 我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
  論文  参考訳（メタデータ） (2023-11-27T14:45:19Z)
• The Complexity of Being Entangled [0.0]
  ニールセンの量子状態複雑性へのアプローチは、一元変換の多様体上の特定のノルムで計算された測地線の長さに状態を作るのに必要な最小の量子ゲート数に関係している。 バイパーティイトシステムでは,単一サブシステムに作用するゲートがコストがかからないノルムに対応する結合複雑性について検討する。
  論文  参考訳（メタデータ） (2023-11-07T19:00:02Z)
• A Circuit Complexity Formulation of Algorithmic Information Theory [1.5483078145498086]
  インダクティブ推論のソロモノフ理論に着想を得て,回路複雑性に基づく先行モデルを提案する。 回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切であると主張する。
  論文  参考訳（メタデータ） (2023-06-25T01:30:37Z)
• Circuit Complexity in an interacting quenched Quantum Field Theory [0.0]
  量子クエンチが量子場理論の回路複雑性に及ぼす影響について検討する。 待ち行列および相互作用場理論における回路複雑性の解析計算について述べる。
  論文  参考訳（メタデータ） (2022-09-07T18:00:03Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  本稿では,グラフニューラルネットワーク(GNN)と組み合わせた強化学習(RL)手法を提案する。 この問題は、巨大な検索スペース、重い尾の報酬分布、そして困難なクレジット割り当てのために非常に難しい。 GNNを基本方針として利用するRLエージェントが,これらの課題にどのように対処できるかを示す。
  論文  参考訳（メタデータ） (2022-04-18T21:45:13Z)
• Quantum circuit debugging and sensitivity analysis via local inversions [62.997667081978825]
  本稿では,回路に最も影響を及ぼす量子回路の断面をピンポイントする手法を提案する。 我々は,IBM量子マシン上に実装されたアルゴリズム回路の例に応用して,提案手法の実用性と有効性を示す。
  論文  参考訳（メタデータ） (2022-04-12T19:39:31Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  確率分布と量子状態のエントロピーを推定することは情報処理の基本的な課題である。 本稿では,有界ファンインと非有界ファンアウトのゲートを持つ対数深度回路か定数深度回路のいずれかによって生成された分布や状態に対するエントロピー推定が,少なくともLearning with Errors問題と同程度難しいことを示す。
  論文  参考訳（メタデータ） (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)

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

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