竜太のテクニカルメモ

物理やへっぽこなゲーム作りについて易しく解説するよ

ユニティちゃんライセンス

このブログはユニティちゃんライセンス条項の元に提供されています

タイムマシン~素因数分解のアルゴリズム~

竜太です.どーも.

今回はタイムマシンで素因数分解するアルゴリズムを発見しましたのでご報告します. これでタイムマシンは実は量子コンピュータでもあることが判明しました!

6 = 2\times 3素因数分解

まずは一番簡単な素因数分解6 = 2\times 3を実行してみましょう.

未来から1でない自然数abが送られてきたとします. このとき,掛け算は因数分解よりはるかに簡単なので大きな数でも通常のコンピュータで容易く計算できるので, a\times b = 6ならばtrueと値a,bを過去に返し, a\times b\neq 6ならば値a,bfalseを返します. また送られてこなかった場合は6未満の任意の2つの自然数a,bを量子乱数発生器で発生させ, a\times b = 6ならtruea,ba\times b \neq 6ならfalsea,bを過去に送ります. ここで,観測しないでtrueに収束させるとa\times b = 6なるa,bが手に入ります. このa,bは当然23 (順不同)になっているはずです. 注意してほしいのが,実はこのアルゴリズムを実行すると,未来から必ず正しいa,bである,23が送られてくるので 確定したtrueとともに過去に向かって送るだけでよいことになるわけです. つまり,必ず因数分解ができています.

自然数m因数分解

  1. 未来からm未満の1でない自然数m_1m_2が送られてくる.

  2. m_1\times m_2 = mならば過去に向かってm_1,m_2,trueを送り, m_1\times m_2 \neq mならば過去に向かってm_1,m_2,falseを送り, 万が一未来からなにも送られてこなかったらm未満の自然数m_1m_2を量子乱数発生器で2つ作り, m_1\times m_2 = mならば過去に向かってm_1,m_2,trueを送り, m_1\times m_2 \neq mならば過去に向かってm_1,m_2,falseを送ります.

  3. これを行うと現在はm因数分解できる数ならば重ね合わせ状態

 \displaystyle
|\psi\rangle = |m_1,m_2(m_1\times m_2 = m)\rangle\otimes |true\rangle + \sum _{m'_1,m'_2}|m'_1,m'_2(m'_1\times m'_2\neq m)\rangle\otimes |false\rangle

となります. 4. そこでここで観測しないようにしてtrueに収束させると因数分解できるm_1m_2,つまり,m_1\times m_2 = mなる m_1,m_2が手に入ります. これで1段階だけ因数分解できました!

大きな数の素因数分解はできるか?

上の手順で,もし因数分解が出来れば何らかの2つの自然数m_1m_2因数分解ができることになり, さらに自然数m_1m_2がまだ素数でなければさらにm_{11}\times m_{12} = m_1,m_{21}\times m_{22} = m_2なる 自然数m_{11},m_{12},m_{21},m_{22}によってm = m_{11}\times m_{12}\times m_{21}\times m_{22}因数分解できます. しかし,上の手順は因数分解できることを前提としているため,素数が計算のどこかで現れると,一気に破綻してしまいます. この破綻はどのようにしたら取り除けるのでしょうか?

因数分解ができないときは必ず値がm_1\times m_2\neq mになってしまう!

因数分解できるときはm_1\times m_2 = mかつtrueが返ってくるはずですが, 因数分解できないときはそもそもm_1\times m_2 = mとなる解は存在しません. そのため,例え強制的にtrueに収束させても,それは値の収束ではなく,falseである状態を 無理やりtrueに書き換えただけであることになってしまいます. このため,この状況の場合に限り,trueであるにも関わらず,m_1\times m_2 \neq mになっているわけです. これを利用しましょう.

3番目の状態を作ってみる

m因数分解したい.

  1. 未来からm_1,m_2,fが送られてきます.

  2. m_1\times m_2 = mかつf = trueなら1段階因数分解ができているのでm_1,m_2,trueを過去に向かって送ります. m_1\times m_2 \neq mかつf = trueならこれ以上因数分解できないのでm,trueを過去に向かって送ります.

  3. 次に起こらない状況としてm_1\times m_2 \neq mかつf = falseならばm_1,m_2,falseを過去に向かって送ります.

  4. また仮に何も送られてこなかった場合にはm未満の1でない自然数m_1,m_2を量子乱数発生器で発生させ, m_1\times m_2 = mならばm_1,m_2,trueを,m_1\times m_2 \neq mならばm_1,m_2,falseを過去に向かって送ります.

  5. すると現在は次の2つの重ね合わせ状態のうちのいずれかが成立していることになります: 因数分解できる場合は,

 \displaystyle
|\psi\rangle = |m_1,m_2(m_1\times m_2 = m)\rangle\otimes |true\rangle + \sum _{m'_1,m'_2}|m'_1,m'_2(m'_1\times m'_2\neq m)\rangle\otimes |false\rangle

が成り立ちます. 因数分解ができない場合は,

 \displaystyle
|\psi\rangle = |m\rangle\otimes |true\rangle + \sum _{m'_1,m'_2}|m'_1,m'_2(m'_1\times m'_2\neq m)\rangle\otimes |false\rangle

が成り立ちます. 6. ここでfを強制的にtrueに収束させると,因数分解ができる場合はm_1\times m_2 = mなるm_1,m_2因数分解ができない場合はmそれ自体が手に入ることになるわけです. 7. 後はこのm_1m_2に対して同じ手順で因数分解を繰り返せば最終的に元のm素因数分解されることになります. お疲れさまでした.

タイムマシンは最も高性能な量子コンピュータ

こうしてみると,こと素因数分解に関してはタイムマシンは最も高性能な量子コンピュータになっていることが分かります. 実際,量子コンピュータの父ともいえるドイッチェの言っているように沢山の多世界を計算に利用しているので, その意味でも量子コンピュータ的です. タイムマシンが実は量子コンピュータだなんてワクワクしませんか?

量子乱数発生器は要るか?

実はこのアルゴリズム,本当は量子乱数発生器も要らないかもしれません. というのも,確実に未来から値が送られてくると考えられるからです. つまり,量子乱数発生器が作る乱数で多世界が沢山作られているというわけではなく, 量子乱数発生器以外の部分でもすでに沢山多世界が作られてしまうという特徴があると考えられます. このため,本当は量子乱数発生器すら要らないと考えられるのですが,これを付けておかないと, 確実に読者が迷路に迷い込んでしまうと考え意図的に追加しました. つまり,恐らくは本当はなくても動くということです.

基本的未来制御法の勝利

このアルゴリズムは基本的未来制御法を深く使用しているため, この結果は基本的未来制御法の勝利と言えそうです. 基本的未来制御法はチェス必勝法にも使えますので,応用範囲は広そうです^^

ここまで読んでくださって有難うございます. 何か間違い等ございましたら,ご報告いただけると幸いです^^


物理学ランキング


宇宙開発ランキング


量子力学ランキング

にほんブログ村 科学ブログ 科学情報へ
にほんブログ村

にほんブログ村 科学ブログ 最先端科学・最新科学へ