量子の世界


2019.8.7-TOSHIBA-https://www.toshiba-clip.com/detail/7685
量子コンピューター研究から生まれた 組合せ最適化の新解法

物流網構築や渋滞緩和、新薬開発など、様々なジャンルにおよぶ社会問題を解決するには、膨大な組合せパターンの中から目的に合ったものを見つけ出す「組合せ最適化問題」と呼ばれる難問を解く必要がある。そこで期待されているのが量子コンピューターの活用だ。このほど東芝は、量子コンピューターの研究を通して、従来のコンピューター(古典コンピューター)で高速に組合せ最適化問題を解く新たな解法(アルゴリズム)を発見した。
量子コンピューターを使わずとも各分野の社会課題を解決できるとなれば、世の中に与える影響は計り知れない。著名な米国オンライン科学雑誌「Science Advances」に論文が掲載され、国内外から注目を集める新解法「シミュレーテッド分岐アルゴリズム」の全容、そして今後の展望をひもといていこう。
「組合せ最適化問題」とは何か
物事を効率化するためには、数多くの選択肢から、最良の組合せを選択する必要がある。これが「組合せ最適化問題」だ。例えば昨今、慢性的な人手不足が問題視される物流業界では、できるだけ短い走行距離で配送できる輸送経路が求められるし、渋滞緩和のためには各自動車がスムーズに走行できるルートを採る必要がある。
しかし、問題の規模が大きくなるほど、組合せの総数も爆発的に大きくなり、最大限の効果が得られる解をはじき出すことは困難になる。この「組合せ爆発」のために、組合せ最適化問題は難問として知られる。
例えば、セールスマンが複数の都市の全てを1回ずつ訪問して出発点に戻る際に、移動距離が最小になる経路を求める「巡回セースルマン問題」と言われるものがある。10都市を回るルートでも181,440通りあり、30都市、50都市にもなると途方もない数字になり、通常の計算機では追いつかないレベルになる。その中から最適なルートを導き出すにはとてつもない時間がかかり、現実的には不可能に近いとされている。
「問題が大規模になるほど、しらみつぶしに最良の組合せを見つけることは難しくなります。物流網構築や渋滞緩和はもちろん、効能が最も高くなる分子の組合せを求める新薬開発や、低リスクで高い収益性のある株の組合せを求める金融ポートフォリオ作成などはその典型例です。
こうした膨大な組合せを持つ課題が、社会やビジネスにおいて無数に存在しています」

こうした組合せ最適化問題は以前から存在するが、その解法が課題とされていた。最適解を求めるための計算は、「イジング問題」という標準問題に置き換えて行うことが研究者の中では通例だ。現在、様々な方式が研究され、イジング問題専用の計算機の開発が進んでいる。ただ、従来の古典コンピューターを使った方式は、膨大な変数を持つ大規模計算に対応できるものの、並列計算による高速化が原理的に困難であるとされる一方で、量子コンピューターは並列計算が可能ながら、大規模計算が不得手という問題があった。(注1:「イジングモデル」と呼ばれる磁石の最も単純なモデルにおいて、そのエネルギー最小の状態を求める、一種の組合せ最適化問題。)
そのため、解法を得ることができれば社会的にも産業的にも絶大なメリットが得られるのは間違いないが、現状では計算処理が極めて困難とされるのが組合せ最適化問題なのだ。
「これまで、超電導回路やレーザーを用いた専用計算機(量子コンピューター)による研究が進められてきましたが、量子コンピューターの本格的な実用化はまだ先で、おまけに多くのコストが必要です。そこで様々な手法が研究される中、並列計算によって高速処理を行なう現行の計算機を駆使して高速な組合せ最適化を可能とするのが、今回開発した『シミュレーテッド分岐アルゴリズム』です」(後藤氏)
東芝社内で長年にわたり量子コンピューターの研究に取り組んできた後藤氏によれば、このアルゴリズムは量子力学のロジックにインスパイアされて生まれたものであるという。


2019.10.25-NHK NEWS WEB-https://www3.nhk.or.jp/news/html/20191024/k10012146191000.html
スパコンで1万年かかる計算を3分20秒で? 量子コンピューター

大手IT企業「グーグル」の研究者などのチームは、次世代のコンピューターとして注目される量子コンピューターが、従来のコンピューターをはるかに上回る性能を持つことを実証したとする論文を発表し、複雑な計算が必要とされる医薬品の合成や、経済・金融分野への応用など、実用化に向けた期待が高まっています。
  アメリカの大手IT企業「グーグル」などの研究チームは、23日付けのイギリスの科学雑誌、「ネイチャー」に、量子コンピューターについての論文を掲載しました。
  それによりますと、実験用に開発したプロセッサーを使って、乱数を生成する問題を計算させたところ、従来のコンピューターではおよそ1万年かかるという結果が出ましたが、量子コンピューターは3分20秒で計算を終わらせたということです。
  量子コンピューターは、理論的には従来のコンピューターでは不可能な計算ができるとされていましたが、実証されたのは今回の研究が初めてだとみられ、グーグルは、実用化に向けた「大きな飛躍だ」としています。
  将来的には、より複雑な計算が必要な医薬品の合成や、経済や金融分野の予測などへの応用が期待されていて、開発競争が今後、さらに激しくなりそうです。
「コンピューターの世界の新たな可能性開いた」
  子コンピューターは、従来のコンピューターとは異なる仕組みに基づいて計算を行います。
  従来のコンピューターは、「0」または「1」のいずれかの状態の組み合わせで計算します。
  これに対し、量子コンピューターは量子力学の原理に基づき、「0でも1でもある」という「重ね合わせ」の状態も利用。
より多くの情報を扱うことができて、理論上は従来のコンピューターをはるかに超える性能を実現できるとされてきました。
  しかし、実際に計算を行える量子コンピューターを開発するには、技術的に解決しなくてはならない問題が数多くあり、従来のコンピューターにはできない計算が本当にできるのかは証明されていませんでした。
  今回の研究は、量子コンピューターでなくてはとけない問題があることを実際に示し、その可能性を実証しました。
  マサチューセッツ工科大学のコンピューターの専門家は「ネイチャー」に寄せた記事で、初めて飛行機を飛行させたライト兄弟の業績になぞらえて「初めて量子コンピューターの超越性が示された」と評価しています。
  グーグルのサンダー・ピチャイCEOは「今回の成果はコンピューターの世界の新たな可能性を開いた」とコメントしています。一方で、今回の発表に関してはIBMなど一部の研究者から、検証の方法に疑義があがっているほか、計算で起きるエラーの訂正の手法や、新たな記録媒体の開発など、解決しなくてはならない課題が多くあり、従来のコンピューターのように一般に普及するまでには、まだ時間がかかる見通しです。
“暗号”めぐる不安も
不安もあります。
それが、インターネットなどあらゆる通信の分野で不可欠となっている暗号の技術をめぐってです。
暗号の技術は、どんどん複雑化していますが、桁違いの計算能力がある量子コンピューターが完成するといまの暗号は解かれてしまうと指摘されているのです。
暗号資産の価格急落 その背景は…
  論文が発表された23日、ビットコインなどのいわゆる仮想通貨=暗号資産の価格が一時、10%以上、急落しました。
  背景には、▽フェイスブックが計画していた暗号資産「リブラ」の発行を先送りする方針を示したことに加え、
▽量子コンピューターの開発によって、暗号資産を支える暗号技術が揺るがされるのではないかという懸念が広がったためとの見方が出ています。
  現在、インターネットなどの通信で使われている暗号技術は、巨大な数の素因数分解など、従来のコンピューターでは計算するのに現実的ではないほどの長い時間がかかる問題を応用して作られています。
  しかし、量子コンピューターがこうした計算を短い時間でとけるようになれば、暗号が解読される危険性が高まると指摘されています。
計算速度を飛躍的に向上させる量子コンピューターの出現は、私たちの生活をより便利にしてくれる可能性がある一方で、情報や通信の安全に対する脅威ともなり得ます。このため、量子コンピューターでも解読できない「耐量子コンピューター暗号」の技術開発も進められています。


量子コンピュータ
出典: フリー百科事典『ウィキペディア(Wikipedia)』

量子コンピュータ (りょうしコンピュータ、英語:quantum computer) は、量子力学的な重ね合わせを用いて並列性を実現するとされるコンピュータ。従来のコンピュータの論理ゲートに代えて、「量子ゲート」を用いて量子計算を行う原理のものについて研究がさかんであるが、他の方式についても研究・開発は行われている。
  いわゆる電子式など従来の一般的なコンピュータ(以下「古典コンピュータ」)の素子は、情報について、「0か1」などなんらかの2値をあらわすいずれかの状態しか持ち得ない「ビット」で扱う。量子コンピュータは「量子ビット」 (qubit; quantum bit、キュービット) により、重ね合わせ状態によって情報を扱う。
  数個の量子ビットがあれば状態が同時に計算され、重ね合わされた結果が得られる。しかし、重ね合わされた結果を観測してもランダムに選ばれた結果が1つ得られるだけで、古典コンピュータに対する高速性は得られない。高速性を得るには欲しい答えを高確率で求める工夫を施した量子コンピュータ専用のアルゴリズムが必須である。もし、数千qubitのハードウェアが実現した場合、この量子ビットを複数利用して、量子コンピュータは古典コンピュータでは実現し得ない規模の並列コンピューティングが実現すると言われる。
  量子コンピュータの能力については、計算理論上の議論と、実際に実現されつつある現実の機械についての議論がある。計算能力の節を参照。現実の機械の能力については実際の項を参照。

理論(詳細は「w:Quantum complexity theory」、「計算複雑性理論」、および「複雑性クラス」を参照)
ヴァジラーニらは、量子チューリングマシンと古典チューリングマシンの計算可能性が等価であることを示した。したがって、計算可能性の点では既存のあらゆるコンピュータと量子チューリングマシンは変わらない。つまり、量子チューリングマシンで「計算可能」な問題は古典チューリングマシンでも「計算可能」であるし、古典チューリングマシンで「計算可能」でない問題は量子チューリングマシンでも「計算可能」でない。(なお、ここで「計算可能」というのは、計算理論の専門用語であって、「原理的に解くことができない」というような表現から一般の人がイメージするような素朴な印象はおそらくたいていは正確ではない)
計算可能性の理論に関しては以上のようであるのだが、では、計算複雑性の理論としてはどうだろうか、というのが関心のある所であろう。
量子コンピュータは容易に古典コンピュータをエミュレートすることが可能であるため、古典コンピュータで速く解ける問題(汎用問題)は、量子コンピュータでも同程度以上に速く解くことができる。よって汎用問題について、量子コンピュータは古典コンピュータ「以上」に強力な計算速度を持つ。ただし、同程度は可能だとしても、「大幅に上回る」かどうかはよくわかっていない。また、「大幅に上回る」問題の範囲についても、「より大きい」かどうかはよくわかっていない。量子コンピュータに関係する複雑性クラスBQPがある。BQPとNPの関係は明確ではないが、BQPのほうが大きいだろうと考えられ、2010年代ころより、NPを含むPHにBQPが含まれない、ということを示唆する結果がいくつか示されてきている。
実際
量子ゲートマシンは理論的には古典コンピューターをシミュレート出来るとされるが、現実には古典ゲートによる小規模演算器もシミュレート出来ない。 そのため、量子ゲートマシンの利用には専用アルゴリズム開発が必ず伴う。Googleは量子ゲートマシンの高速性が2017年末までに実証されると予想した。古典コンピューターよりも実際の量子ゲートマシンの方が高速に解ける問題が存在することを、量子超越性と呼び、このような問題の探索が続けられている。2019年10月23日、Googleは、ランダムに作った量子回路の出力結果を推定すると言う問題で、量子超越性を実証したと発表した。
量子ゲートマシン上で素因数分解を行うショアのアルゴリズムは、2001年にIBMが世界で初めて15(=3×5)の分解に成功した。2012年にブリストル大学が21(=3×7)の素因数分解を行い記録を更新したが、22以上の数の素因数分解の報告はない(2019年9月時点)。
2017年現在始まっているIBM Qなどではごく限られた数の量子ビットしか扱えない。重ね合わせ状態を保ちデータを記憶する量子メモリが実現されていない事、量子複製不可能定理により、計算結果を使いまわすことができない事、複数の量子コンピューターを接続し計算規模を大きくする技術が実現していない事、量子ゲートに起因する誤差が蓄積する事などから、計算大規模化が困難である。従って、現状では、与えられた問題を解くことに使われる状態ではなく、既に提案されている小規模な量子アルゴリズムの実証から始め、量子コンピュータで得ける有用な問題の模索が続いている。
量子コンピュータとしては、量子ゲート型以外に、D-Waveなどの量子アニーリングやその他いくつかのタイプが提案されている、量子イジングマシンはQUBO(制約のない二値二次式の最適化)に特化した専用計算機と言える。





















このTopに戻る





monomousu   もの申す
最近のニュース
TOPにもどる