論文の概要: Circuit complexity and functionality: a thermodynamic perspective

• arxiv url: http://arxiv.org/abs/2309.05731v2
• Date: Sun, 21 Apr 2024 15:46:06 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-24 00:52:28.755911
• Title: Circuit complexity and functionality: a thermodynamic perspective
• Title（参考訳）: 回路の複雑さと機能--熱力学の視点から
• Authors: Claudio Chamon, Andrei E. Ruckenstein, Eduardo R. Mucciolo, Ran Canetti,
• Abstract要約: 与えられた機能の回路に対する複雑性と熱力学の関連について検討する。 特に、我々のフレームワークは任意の長さのプログラムの難読化に関する新しい視点を提供する。 我々は、複雑性クラス NP と coNP が一致しない限り、断片化は避けられないと主張する。
• 参考スコア（独自算出の注目度）: 2.2988732018837177
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Circuit complexity, defined as the minimum circuit size required for implementing a particular Boolean computation, is a foundational concept in computer science. Determining circuit complexity is believed to be a hard computational problem [1]. Recently, in the context of black holes, circuit complexity has been promoted to a physical property, wherein the growth of complexity is reflected in the time evolution of the Einstein-Rosen bridge (``wormhole'') connecting the two sides of an AdS ``eternal'' black hole [2]. Here we explore another link between complexity and thermodynamics for circuits of given functionality, making the physics-inspired approach relevant to real computational problems, for which functionality is the key element of interest. In particular, our thermodynamic framework provides a new perspective on 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 be 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 computational complexity theory to its first level.
• Abstract（参考訳）: 特定のブール計算を実装するのに必要な最小回路サイズとして定義される回路複雑性は、コンピュータ科学の基本的な概念である。 回路の複雑さを決定することは、難しい計算問題である [1] であると考えられている。 近年、ブラックホールの文脈では、回路の複雑さが物理的性質へと促進され、AdS `eternal'' ブラックホールの両側を繋ぐアインシュタイン・ローゼン橋 (``wormhole'') の時間発展に複雑性の増大が反映されている。 ここでは、与えられた関数の回路に対する複雑性と熱力学の別の関係を探求し、物理に着想を得たアプローチを実際の計算問題に関連付ける。 特に、我々の熱力学フレームワークは、回路の隣り合う部分の再帰的な混合による熱化として、任意の長さのプログラムの難読化(暗号における重要な問題)について、新たな視点を提供する。 この再帰過程は平均複雑性を平衡させ、回路のエントロピーが飽和し、回路全体の機能を保存する。 私たちが予想する回路空間におけるエルゴード性に関する熱力学の議論は、断片化による非連結エルゴードセクターに限られる。 フラグメンテーションの概念は、回路難読化の問題に重要な意味を持ち、これは、局所移動によって接続できない同じ大きさと機能を持つ回路が存在することを意味する。 さらに、複雑性クラス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)

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

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