Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

数理解析研究所講究録

量子アルゴリズムによる近似文字列出現頻度問い合わせ (計算機科学基礎理論とその応用 研究集会報告集)

健了 小林, 廣隆 小野, 邦彦 定兼, 雅史 山下

Published Apr 1, 2005• 0 citations
OpenAlex

Related papers

Chaitin's halting probabiliy Ω and quantum measurements in an infinite dimensional quantum system (計算機科学基礎理論とその応用 研究集会報告集)

孝太郎 只木

This paper proposes an extension of Chaitin's halting probability 0to measurement operator in $\mathrm{a}\mathrm{a}\mathrm{n}$ infinite dimensional quantum system.Chaitin's $\Omega$ is defined as the probability that the universal self-delimiting Turing machine $U$ halts, and plays acentral role in the development of algorithmic information theory.Iri the theory, there are two equivalent ways to define the program-size complexity $H(s)$ of agiven finite binary string $\mathrm{s}$ .In the standard way, $H(s)$ is defined as the length of the shortest input string for $U$ to output 8.In the other way, the s0-called universal probability $\Pi \mathrm{L}$ is introduced first, and then $H(s)$ is defined as $-\log_{2}m(\mathrm{I}\mathrm{F})$ without reference to the concept of program-size.Mathematically, the statistics of outcomes in aquantum measurement are described by apositive operator-valued measure (POVM) in the most general setting.Based on the theory of computability structures on aBanach space developed by Pour-El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called universal semi-POVM.We also give another characterization of Chaitin's $\Omega$ numbers by universal probabilities.Then, based on this characterization, we propose to define an extension of $\Omega$ as asum of the POVM elements of auniversal semi-POVM.The validity of this definition is discussed.1Introduction Algorithmic information theory is afiamework to apply information-theoretic and probabilistic ideas to recursive function theory.One of the primary concepts of algorithmic information theory is the program-size $compl_{6\mathrm{f}\mathrm{f}\dot{i}}\not\in y$ (or Kolmogorov complez- $\dot{i}ty)\mathrm{H}\{\mathrm{s}$ ) of afinite binary string $s$ , which is defined as the length of the shortest binary input

数理解析研究所講究録•Apr 1, 2005•0 citations

量子探索アルゴリズムと量子情報幾何, 可積分系(力学系と微分幾何学)

Yoshio Uwano

•Jul 1, 2006•0 citations

一般化量子チューリング機械について (応用函数解析としての情報数理の研究 研究集会報告集)

聖史 入山, 雅則 大矢

数理解析研究所講究録•Oct 1, 2005•0 citations

量子探索アルゴリズムと量子情報幾何, 可積分系(力学系と微分幾何学)

嘉夫 上野

数理解析研究所講究録•Jul 1, 2006•0 citations

機械学習の適用による量子アルゴリズムの実装性向上に関する研究 (審査報告)

ヒロユキ テヅカ, Hiroyuki Tezuka, 宙之 手塚

•Jan 1, 2023•0 citations

代数上の汎関数の一般不確定性関係への応用 (情報科学としての函数解析とその周辺 研究集会報告集)

憲 栗山, 茂 古市, 研二郎 柳

数理解析研究所講究録•Sep 1, 2003•0 citations
This paper proposes an extension of Chaitin's halting probability 0to measurement operator in aan\mathrm{a}\mathrm{a}\mathrm{n}aan infinite dimensional quantum system.Chaitin's Ω\OmegaΩ is defined as the probability that the universal self-delimiting Turing machine UUU halts, and plays acentral role in the development of algorithmic information theory.Iri the theory, there are two equivalent ways to define the program-size complexity H(s)H(s)H(s) of agiven finite binary string s\mathrm{s}s .In the standard way, H(s)H(s)H(s) is defined as the length of the shortest input string for UUU to output 8.In the other way, the s0-called universal probability ΠL\Pi \mathrm{L}ΠL is introduced first, and then H(s)H(s)H(s) is defined as −log⁡2m(IF)-\log_{2}m(\mathrm{I}\mathrm{F})−log2​m(IF) without reference to the concept of program-size.Mathematically, the statistics of outcomes in aquantum measurement are described by apositive operator-valued measure (POVM) in the most general setting.Based on the theory of computability structures on aBanach space developed by Pour-El and Richards, we extend the universal probability to an analogue of POVM in an infinite dimensional quantum system, called universal semi-POVM.We also give another characterization of Chaitin's Ω\OmegaΩ numbers by universal probabilities.Then, based on this characterization, we propose to define an extension of Ω\OmegaΩ as asum of the POVM elements of auniversal semi-POVM.The validity of this definition is discussed.1Introduction Algorithmic information theory is afiamework to apply information-theoretic and probabilistic ideas to recursive function theory.One of the primary concepts of algorithmic information theory is the program-size compl6ffi˙∉ycompl_{6\mathrm{f}\mathrm{f}\dot{i}}\not\in ycompl6ffi˙​∈y (or Kolmogorov complez- i˙ty)H{s\dot{i}ty)\mathrm{H}\{\mathrm{s}i˙ty)H{s ) of afinite binary string sss , which is defined as the length of the shortest binary input