論文の概要: A Circuit Complexity Formulation of Algorithmic Information Theory
- arxiv url: http://arxiv.org/abs/2306.14087v1
- Date: Sun, 25 Jun 2023 01:30:37 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-27 17:02:44.648099
- Title: A Circuit Complexity Formulation of Algorithmic Information Theory
- Title(参考訳): アルゴリズム情報理論の回路複雑度定式化
- Authors: Cole Wyeth and Carl Sturtivant
- Abstract要約: インダクティブ推論のソロモノフ理論に着想を得て,回路複雑性に基づく先行モデルを提案する。
回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切であると主張する。
- 参考スコア(独自算出の注目度): 1.5483078145498086
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Inspired by Solomonoffs theory of inductive inference, we propose a prior
based on circuit complexity. There are several advantages to this approach.
First, it relies on a complexity measure that does not depend on the choice of
UTM. There is one universal definition for Boolean circuits involving an
universal operation such as nand with simple conversions to alternative
definitions such as and, or, and not. Second, there is no analogue of the
halting problem. The output value of a circuit can be calculated recursively by
computer in time proportional to the number of gates, while a short program may
run for a very long time. Our prior assumes that a Boolean function, or
equivalently, Boolean string of fixed length, is generated by some Bayesian
mixture of circuits. This model is appropriate for learning Boolean functions
from partial information, a problem often encountered within machine learning
as "binary classification." We argue that an inductive bias towards simple
explanations as measured by circuit complexity is appropriate for this problem.
- Abstract(参考訳): インダクティブ推論のソロモンオフ理論に着想を得て,回路複雑性に基づく事前提案を行う。
このアプローチにはいくつかの利点がある。
まず、UTMの選択に依存しない複雑性尺度に依存する。
ブール回路の普遍的な定義は、nand のような普遍的な演算と、and や not のような別の定義への単純な変換を含む。
第二に、停止問題の類似は存在しない。
回路の出力値は、ゲート数に比例した時間でコンピュータによって再帰的に計算でき、短いプログラムは非常に長い時間実行することができる。
我々の以前の仮定では、ブール関数、またはそれと同値な長さのブール弦は、ある種のベイズ回路の混合によって生成される。
このモデルは、部分的情報からブール関数を学ぶのに適しており、機械学習内で「バイナリ分類」としてしばしば発生する問題である。
回路複雑性によって測定された単純な説明に対する帰納的バイアスがこの問題に適切である。
関連論文リスト
- Taming Quantum Time Complexity [50.10645865330582]
時間複雑性の設定において、正確さと遠心性の両方を達成する方法を示します。
我々は、トランスデューサと呼ばれるものに基づく量子アルゴリズムの設計に新しいアプローチを採用する。
論文 参考訳(メタデータ) (2023-11-27T14:45:19Z) - Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。
最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。
シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文 参考訳(メタデータ) (2023-10-05T07:10:40Z) - Circuit complexity and functionality: a thermodynamic perspective [2.5113538231331685]
所定の関数の回路エントロピーと一定数のゲートを回路複雑性に結びつける。
任意の長さのプログラムの難読化のための枠組みを定式化する。
我々は、複雑性クラス NP と coNP が一致しない限り、断片化は避けられないと主張する。
論文 参考訳(メタデータ) (2023-09-11T18:02:21Z) - A Quantum Algorithm for Computing All Diagnoses of a Switching Circuit [73.70667578066775]
ほとんどの人造システム、特にコンピュータは決定論的に機能する。
本稿では、量子物理学が確率法則に従うときの直観的なアプローチである量子情報理論による接続を提供する。
論文 参考訳(メタデータ) (2022-09-08T17:55:30Z) - Circuit Complexity in an interacting quenched Quantum Field Theory [0.0]
量子クエンチが量子場理論の回路複雑性に及ぼす影響について検討する。
待ち行列および相互作用場理論における回路複雑性の解析計算について述べる。
論文 参考訳(メタデータ) (2022-09-07T18:00:03Z) - FABLE: Fast Approximate Quantum Circuits for Block-Encodings [0.0]
行列のブロック符号化のための近似量子回路を高速に生成するFABLEを提案する。
FABLE回路は単純な構造であり、1ビットと2ビットのゲートで直接定式化されている。
FABLE回路は圧縮・スパシファイド可能であることを示す。
論文 参考訳(メタデータ) (2022-04-29T21:06:07Z) - Symbolic Synthesis of Clifford Circuits and Beyond [0.0]
ユニタリ性問題は一般にコ-NP-ハードであるが、クリフォードパス和に制限された場合、P であることを示す。
次に、一意的なクリフォード経路和からクリフォード回路を合成するアルゴリズムを提供する。
また、任意の経路和に対する抽出アルゴリズムの一般化も提供する。
論文 参考訳(メタデータ) (2022-04-29T16:33:42Z) - Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
我々は、$c-不連続性を計算すること、あるいはそれを定数乗算係数の範囲内で近似することの問題はNP完全であることを示す。
CSSコード、$dコード、ハイパーグラフコードなど、さまざまなコードファミリの相違点に関するバウンダリを提供します。
以上の結果から,一般的な量子誤り訂正符号に対するフォールトトレラント論理ゲートの発見は,計算に難題であることが示唆された。
論文 参考訳(メタデータ) (2021-08-10T15:00:20Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳(メタデータ) (2021-07-28T04:28:55Z) - Learning algorithms from circuit lower bounds [0.0]
構成回路下界の様々な概念から効率的な学習アルゴリズムの既知の構成を再考する。
難しい問題を解こうとする多くのpサイズの回路の誤りを、特定のインタラクティブな方法で効率的に見つけることができれば、pサイズの回路は一様分布を通じてPACを学ぶことができることを証明します。
論文 参考訳(メタデータ) (2020-12-28T04:47:36Z) - Estimating the entropy of shallow circuit outputs is hard [77.34726150561087]
シャノンエントロピー推定の意思決定問題バージョンはエントロピー差分(ED)である
量子回路(QED)の類似の問題
オラクルと比較して、これらの問題は指数関数的に大きい回路と同等に難しいものではないことを示す。
論文 参考訳(メタデータ) (2020-02-27T15:32:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。