アカウント名:
パスワード:
私は最適化問題は重要だと思うので、「汎用じゃなくても最適化問題は高速に解けます」という方針は「有り」だと思うな。
使ってみたい人はそれなりにいると思うけど、お高いんでしょうなー。簡単にググったくらいだと価格が出てこないっすね。
意外とshorのアルゴリズムから20年なので、本物が出てきてもアリかもね。
わかっているコメントとわかっていないコメントが混在すること必至なので、自分なりに簡単に説明してみる。今の普通のコンピュータ:チューリングマシンがモデルで、クロックに合わせて状態遷移とテープ書き換えで計算する。状態は有限状態機械、テープは1マス1文字、とどれもはっきりしている。ワだか7だか区別のつかない書き方は許されない。
量子コンピュータ:量子力学的考え方を拝借(これ重要)して構成素子(キュービット)を使って計算をやらせる。量子力学が一つの粒子についてある位置の存在確率しか定まらないように、ビットも0と1が確率的に混在できると考える。このとき、確率を制御する簡単な仕組みを定めてやると、その組み合わせ+繰り返しで最適化問題の解が浮き出るように高確率で存在させることができる(shorのアルゴリズム)
量子コンピュータが作れるかどうかは、考え方を拝借したキュービットが実現できるかどうかにかかっている。別に素粒子や量子力学の素子を使っているわけではない。(使ってもべつにいいけど)
補足:キュービットそのものを単独で実現できると文句ないのだが、難しい。そこで現在知られている量子計算アルゴリズム(ショア、グローバーなど)を実現できるキュービットとその確率を操作する基本操作の組合せが量子ゲートと呼ばれるもので、この量子ゲートを実現させるのが主流の方式。
このタレこみの量子アニーリングは、キュービットを使ってシミュレーティットアニーリングを行うアルゴリズムをひとまとめにしたもの。理論としては、キュービットの定義は明確だし、アニーリングアルゴリズムのキュービット版も正確に矛盾なく書けている。量子ゲートでは、今の普通のコンピュータをシミュレートできるが、量子アニーリングだとキュービットとアニーリングアルゴリズムがセットで記述されているので、今のコンピュータをシミュレートできるかどうかはまだ未知。計算スピードは、どちらの方式でもNP完全問題が多項式時間でできる?(ここは自信なし)
で、今回の問題はそれをどうやって現実の物質で実現したか。
> 計算スピードは、どちらの方式でもNP完全問題が多項式時間でできる?(ここは自信なし)
NPとの関係はわかっていないらしhttp://ja.wikipedia.org/wiki/BQP [wikipedia.org]
纏めてしまうと、「量子力学的な確率論に基づくアナログコンピュータ」って事でいいのでしょうか?アナログコンピュータの大半が、物理的な配線のつなぎ変えでデジタルコンピュータよりも高速かつ高精度な演算をやってた時代への先祖帰りに見えたんですけど。
# まぁ、確率操作をデジタル的な意味でプログラマブルにやれるような仕組みを用意して# あるんでしょうけど。
「シャボン膜最短経路をキュービットで確率的にやった」は割とイメージが近いと思う。アナログコンピュータって言うと歯車計算機思い浮かべて、あれは完全にチューリングマシン(古典計算機)だと思う。
タイガー計算機などの歯車コンピュータはどちらかと言うとデジタルコンピュータです。アナログコンピュータはオペアンプで作られた加算器や積分器を基本部品としています。乗算は自乗特性の非線形素子で((x+y)^2-(x-y)^2)/4 などとして電圧値で計算します。結果は電圧計やオシロスコープで読み取ります。そして電圧を平衡するような回路をつくることで、方程式や常微分方程式を解くことができます。有限時間で連続な電圧値を積分器で積分できるので解釈によっては有限時間に無限回の計算をしていることになります。実際にはS/Nと帯域を考えると取り出せるデータ数は有限なのでデジタルコンピュータに性能が劣ることがほとんどです。えっ?プログラムできるかって? プログラムとはジャックにプラグコードを差し込んだ回路パターンそのものを「プログラム」といいます。想像つかないひとは最近復刻されてるアナログ・シンセサイザーの KORG MS-20 mini みたいな感じとおもってください。
なるほど。だとすると、「アナログコンピュータに確率的な要素を付け加えた」というのはシャボン膜と同じくイメージ近いかも。
D-Waveのやつは、系に初期値を設定してしばらくしてから観測すると、エネルギー準位に応じた結果になる(ので繰り返すとどれが最低かが確率的にわかる)というカンジ?
D-Waveのは二次元イジング模型を直接シミュレートする、らし
1台10億円らしいです。
問題を解くのはハードでなくソフトです。最適化問題を解くのに有利なハードができたとしても、それを活用するソフトも開発しなきゃならない。Windowsアプリを移植すればオッケーって訳にはいかないでしょう。既存のハードでは時間が掛かる問題を、高速で解きたいんだから。
アルゴリズムは「量子アニーリング」に固定で、入力が初期値のデータセットと幾つかのパラメータという感じなんじゃないのかな。
最適化問題って解き方自体はそんなにバリエーションないでしょう。
その「入力が初期値のデータセットと幾つかのパラメータ」に既存データを変換しなきゃいけない。しかし「量子アニーリング」なんてのはこれまで使ってなかったので変換アルゴリズムが確立されていない。当然逆変換アルゴリズムも必要でそれも確立しなきゃいけない。つまりアルゴリズムレイヤからデバッグしなきゃいけない。デバッグするにはテストしなきゃいけない。対象、つまり量子アニーリングに精通していなければ有効なテストができない。汎用化するまではそんな感じ、というかそれを経て汎用化するんですよ。
まさかテスト無しで盲信するつもりじゃないでしょ?
言ってることが判らない。
入力データ(+諸々パラメータ)の用意とか、通常の計算機でシミュレーテッド・アニーリングを行うのと大して変わらないでしょ。今でもやってる人はけっこういるぞ。
自分の問題を最適化問題に落とし込む段階で苦労する場合もあるけど、それはプログラミングとはまったく別の話。通常の計算機も量子計算機も関係ない。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
「科学者は100%安全だと保証できないものは動かしてはならない」、科学者「えっ」、プログラマ「えっ」
最適化問題の重要性 (スコア:0)
私は最適化問題は重要だと思うので、
「汎用じゃなくても最適化問題は高速に解けます」
という方針は「有り」だと思うな。
使ってみたい人はそれなりにいると思うけど、
お高いんでしょうなー。
簡単にググったくらいだと価格が出てこないっすね。
Re:最適化問題の重要性 (スコア:4, 参考になる)
意外とshorのアルゴリズムから20年なので、本物が出てきてもアリかもね。
わかっているコメントとわかっていないコメントが混在すること必至なので、自分なりに簡単に説明してみる。
今の普通のコンピュータ:チューリングマシンがモデルで、クロックに合わせて状態遷移とテープ書き換えで計算する。
状態は有限状態機械、テープは1マス1文字、とどれもはっきりしている。ワだか7だか区別のつかない書き方は許されない。
量子コンピュータ:量子力学的考え方を拝借(これ重要)して構成素子(キュービット)を使って計算をやらせる。
量子力学が一つの粒子についてある位置の存在確率しか定まらないように、ビットも0と1が確率的に混在できると考える。
このとき、確率を制御する簡単な仕組みを定めてやると、その組み合わせ+繰り返しで最適化問題の解が浮き出るように
高確率で存在させることができる(shorのアルゴリズム)
量子コンピュータが作れるかどうかは、考え方を拝借したキュービットが実現できるかどうかにかかっている。
別に素粒子や量子力学の素子を使っているわけではない。(使ってもべつにいいけど)
Re:最適化問題の重要性 (スコア:3, 参考になる)
補足:
キュービットそのものを単独で実現できると文句ないのだが、難しい。そこで現在知られている量子計算アルゴリズム
(ショア、グローバーなど)を実現できるキュービットとその確率を操作する基本操作の組合せが量子ゲートと呼ばれるもので、
この量子ゲートを実現させるのが主流の方式。
このタレこみの量子アニーリングは、キュービットを使ってシミュレーティットアニーリングを行うアルゴリズムをひとまとめにしたもの。
理論としては、キュービットの定義は明確だし、アニーリングアルゴリズムのキュービット版も正確に矛盾なく書けている。
量子ゲートでは、今の普通のコンピュータをシミュレートできるが、量子アニーリングだとキュービットとアニーリングアルゴリズムが
セットで記述されているので、今のコンピュータをシミュレートできるかどうかはまだ未知。
計算スピードは、どちらの方式でもNP完全問題が多項式時間でできる?(ここは自信なし)
で、今回の問題はそれをどうやって現実の物質で実現したか。
Re: (スコア:0)
> 計算スピードは、どちらの方式でもNP完全問題が多項式時間でできる?(ここは自信なし)
NPとの関係はわかっていないらし
http://ja.wikipedia.org/wiki/BQP [wikipedia.org]
Re:最適化問題の重要性 (スコア:1)
纏めてしまうと、「量子力学的な確率論に基づくアナログコンピュータ」って事でいいのでしょうか?
アナログコンピュータの大半が、物理的な配線のつなぎ変えでデジタルコンピュータよりも高速かつ高精度な演算をやってた時代への先祖帰りに見えたんですけど。
# まぁ、確率操作をデジタル的な意味でプログラマブルにやれるような仕組みを用意して
# あるんでしょうけど。
Re: (スコア:0)
「シャボン膜最短経路をキュービットで確率的にやった」は割とイメージが近いと思う。
アナログコンピュータって言うと歯車計算機思い浮かべて、あれは完全にチューリングマシン(古典計算機)だと思う。
アナログコンピュータはこういうモノ (スコア:0)
タイガー計算機などの歯車コンピュータはどちらかと言うとデジタルコンピュータです。
アナログコンピュータはオペアンプで作られた加算器や積分器を基本部品としています。
乗算は自乗特性の非線形素子で((x+y)^2-(x-y)^2)/4 などとして電圧値で計算します。
結果は電圧計やオシロスコープで読み取ります。
そして電圧を平衡するような回路をつくることで、方程式や常微分方程式を解くことができます。
有限時間で連続な電圧値を積分器で積分できるので解釈によっては有限時間に無限回の計算をしていることになります。
実際にはS/Nと帯域を考えると取り出せるデータ数は有限なのでデジタルコンピュータに性能が劣ることがほとんどです。
えっ?プログラムできるかって? プログラムとはジャックにプラグコードを差し込んだ回路パターンそのものを「プログラム」といいます。
想像つかないひとは最近復刻されてるアナログ・シンセサイザーの KORG MS-20 mini みたいな感じとおもってください。
Re: (スコア:0)
なるほど。
だとすると、「アナログコンピュータに確率的な要素を付け加えた」というのはシャボン膜と同じくイメージ近いかも。
Re: (スコア:0)
D-Waveのやつは、系に初期値を設定してしばらくしてから観測すると、エネルギー準位に応じた結果になる
(ので繰り返すとどれが最低かが確率的にわかる)
というカンジ?
Re: (スコア:0)
D-Waveのは二次元イジング模型を直接シミュレートする、らし
Re:最適化問題の重要性 (スコア:2, 参考になる)
1台10億円らしいです。
Re: (スコア:0)
問題を解くのはハードでなくソフトです。
最適化問題を解くのに有利なハードができたとしても、それを活用するソフトも開発しなきゃならない。
Windowsアプリを移植すればオッケーって訳にはいかないでしょう。
既存のハードでは時間が掛かる問題を、高速で解きたいんだから。
Re: (スコア:0)
アルゴリズムは「量子アニーリング」に固定で、
入力が初期値のデータセットと幾つかのパラメータ
という感じなんじゃないのかな。
最適化問題って解き方自体はそんなにバリエーション
ないでしょう。
Re: (スコア:0)
その「入力が初期値のデータセットと幾つかのパラメータ」に既存データを変換しなきゃいけない。
しかし「量子アニーリング」なんてのはこれまで使ってなかったので変換アルゴリズムが確立されていない。
当然逆変換アルゴリズムも必要でそれも確立しなきゃいけない。
つまりアルゴリズムレイヤからデバッグしなきゃいけない。デバッグするにはテストしなきゃいけない。
対象、つまり量子アニーリングに精通していなければ有効なテストができない。
汎用化するまではそんな感じ、というかそれを経て汎用化するんですよ。
まさかテスト無しで盲信するつもりじゃないでしょ?
Re:最適化問題の重要性 (スコア:1)
大ざっぱには「n変数の関数f(a1, a2,...,an)を与えたとき、fの値がなるべく小さくなるような(a1, a2,...,an)の値を求めてくれるブラックボックス」が有るだけなので。
ブラックボックスにも種類があって、特定の構造のfの場合しか解けないとか、aiが実数でしか使えない、整数でも使えるとか色々ありますし、 解きたい問題を関数fに落とし込むのにも多少のテクニックは要りますし、やり方次第で性能も変わるので、精通しておいた方がより良いのは確かですが。
まあ、既存のよく知られているアルゴリズムで同じ問題を解かせてみて、性能が良さそうだったらそっちを採用、ぐらいの感じでも良いんじゃないかと。 内部構造が分からない以上、とんでもない解が出てくる可能性もあって信用できない、例えば最短経路を求めるfのはずが最長経路が出てくる可能性もある、と言う懸念はありますけど。その場合でも、既存のアルゴリズムも別途走らせておいて良い方を採用する、ぐらいにしておけば、ほとんどの場合は性能が大幅に上がって、最悪、未知の原因で想定外のことが起こっても今よりは悪くならない、というのは保証できますし。
Re: (スコア:0)
言ってることが判らない。
入力データ(+諸々パラメータ)の用意とか、
通常の計算機でシミュレーテッド・アニーリングを行うのと
大して変わらないでしょ。
今でもやってる人はけっこういるぞ。
自分の問題を最適化問題に落とし込む段階で苦労する場合もあるけど、
それはプログラミングとはまったく別の話。通常の計算機も量子計算機も関係ない。