量子計算学習ノート

量子計算学習ノート - 計算問題の解析1

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。ここからは計算機によって計算される問題自体についての考察を深める。まず、計算問題についての私たちの基本的疑問は次の3つである。計算問題とはいったいどんな問題か？与えられた計算問題を解くためのアルゴリズムをうまく設計する方法は？与えられた計算問題を解くために必要最小限なリソースは何か？ここから数回は1と3について、3から1の順番で議論していくことにする。2については実際に量子アルゴリズム

量子計算学習ノート - 回路モデルとチューリング機械モデル

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。以前、回路による計算モデルとチューリング機械による計算モデルは計算できる関数のクラスが同じという意味で等価であると述べた。ここではそれを示そう。まず、回路族$${\{C_n\}}$$という集合を考えることにする。回路族とは特定の関数$${C: \mathbb{N} \to \mathbb{N}}$$を計算する回路$${C_n}$$を集めた集合である。ここで$${C_n}$$は$${n}$$ビット入

量子計算学習ノート - 回路3

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。前回、有限数ビットから有限数ビットを出力するあらゆる関数に対して、その関数を計算する回路が存在することを示した。この記事ではそのようなあらゆる回路は実はNANDゲートだけあれば構成できることを示す。前回構成した回路の構成要素には次の4つがある。配線補助ビット FANOUT AND、XOR、NOTゲートこのうち、実は4の要素は幾分冗長であり、実はNANDゲートだけあれば、任意の関数を

量子計算学習ノート - 回路2

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。前回は回路を構成するいくつかのゲートと、それを用いて自然数の和を求める回路を構成した。今回は和だけではなく、任意の関数を計算する回路がここまで使ってきたゲートで構成できることを示そう。まず、簡単のために$${n}$$入力、$${1}$$出力の場合を示す。つまり任意の$${f: \{0,1\}^n \to \{0,1\}}$$なる関数を計算する回路が構成できることを示そう。このような関数はBool関

量子計算学習ノート - 回路1

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。これまでは計算モデルとしてチューリング機械を扱ってきたが、チューリング機械は少し理想化されたモデルだった。というのもテープの長さは片方に無制限であり、実際のコンピュータは記憶領域は有限であることに反している。そこで回路による計算モデルを導入しよう。回路による計算モデルは後に示すが計算能力としてチューリング機械と等価であり、多くの応用に対してより便利かつ現実的だ。実際量子コンピュータの準備のために回

量子計算学習ノート - チューリング数3

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。前回チューリング数を定義したので、このチューリング数を用いて「万能チューリング機械」と「停止問題」について述べる。まずは万能チューリング機械について説明しよう。万能チューリング機械は、任意のチューリング機械のシミュレーションができるチューリング機械のことだ。万能チューリング機械$${UTM}$$はチューリング機械$${M}$$をシミュレートするために、次のようなテープの内容を期待する $${M}

量子計算学習ノート - チューリング数2

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。前の記事では算術の基本定理を証明した。この記事ではこれを用いて任意のチューリング機械が互いに異なる自然数に対応付けられることを示そう。実際にチューリング機械を自然数に対応付ける前に、一般性を失わない形で対象とするチューリング機械の範囲を狭める。具体的には以下の制約を加える。片方に無限に長いテープを1つ持つとする記号には $${0, 1}$$の2つしか用いない前者はすでにテープの変形によ

量子計算学習ノート - チューリング数1

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。ここではあらゆるチューリング機械の集合について議論しよう。この集合の性質を議論するためにチューリング機械に対するチューリング数という概念を導入したい。最終的に示したいことは次のことだ。これが示せると、チューリング機械を入力としてその動作を再現するチューリング機械である「万能チューリング機械」というものを定義することができるようになる。任意のチューリング機械を番号づけするためには「算術の基本

量子計算学習ノート - チューリング機械5

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。この記事では、これまで机上で議論を続けてきたチューリング機械をpythonで実際に実装してみて、その動きを確かめることにする。実際のソースコードはこちらに格納してある。肝となる実装は「SingleTapeTuringMachine」クラスである。これは単一の無限長テープを持つチューリング機械を模して実装したクラスだ。 class SingleTapeTuringMachine: is_va

量子計算学習ノート - チューリング機械4

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。ここでは、チューリング機械の物理学的に合理的な変形について見ていこう。例えば両方向に無限長のテープを持ったチューリング機械や、1次元ではなく2次元以上の高次元テープを持つようなものが考えられる。ここでは具体的に2つのテープを持つチューリング機械についてその定義を考えてみよう。2つのテープを持つチューリング機械は、これまで通りアルファベット$${\Gamma \equiv \{\triangleri

量子計算学習ノート - チューリング機械3

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。ここではチューリング機械が計算できる範囲について説明しよう。実際、チューリング機械を使うと非常に多くの種類の関数を計算できることがわかっている。具体的には基本的な算術演算、ビット列で表現されたテキストの検索などだ。実はチャーチとチューリングによって独立に発表された論文によると、現代のコンピュータで行えるすべての演算（現代の解釈における任意のアルゴリズムに対応）をチューリング機会を使ってシミュレ

量子計算学習ノート - チューリング機械2

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。この記事では具体的なチューリング機械の動きを確かめてみることにしよう。次のようなチューリング機械を考える。状態集合$${S \equiv \{q_1, q_2, q_3, q_s, q_h\}}$$ $${Tape \equiv (\triangleright, x_0, x_1, x_2, x_3, b, b, b, \cdots)}$$ ここで$${x_i}$$は任意の2進数($${0,1

量子計算学習ノート - チューリング機械1

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。ここではチューリングが提唱した計算モデルであるチューリング機械について説明し、どのように動くか実際に見ていこう。まずチューリング機械とは次の四つの要素からなる。有限な状態制御テープテープヘッドプログラム有限な状態制御有限な状態制御とは、チューリング機械の内部状態を指し示す要素$${q_0, q_1, \cdots q_n}$$および出発状態$${q_s}$$、停止状態$${q_

量子計算学習ノート - 計算モデル

この記事は「量子コンピュータと量子通信 (オーム社)」の読書ノートです。どんな大きな数でも2つの自然数を足し合わせるといった手法を私たちは学校で学ぶ。これも立派なアルゴリズムである。ではこの何らかのタスクをするときのアルゴリズムを数学的に厳密に定義することができるだろうか。この答えはYesであり、実際にチャーチとチューリングという数学者が、アルゴリズムの近代的理論と計算機科学の近代的理論の基礎を作った。この理論が生み出されるきっかけになったのがヒルベルトの解決問題だ。

フォローしませんか？

#量子計算