量子コンピューターと物流（その①）

『旅するお荷物 vol.1』
大原 欽也

何かと話題に事欠かないＩＴ業界ですが、中でも量子コンピューターは未だ完成を見ない近未来技術としてＳＦ的なロマンをかき立てられるところです。実は量子コンピューター自体は、その特徴も動作もすでに解かっています。なので、開発の暁にはその適用先や適用の仕方も予め予想できていたりするわけです。

ところで、革新的な発明というものは、大体において発明されてから使い道が考えられる、つまり泥縄式に適用されるケースが多いようです。例えば、内燃機関、電球、蓄音機、半導体等々、これらは発明された当初は使い道がよくわからなかったものです。つまり、適用されてこそ一人前の発明だ、という立場に立てば、「発明は必要の母」となるわけです。

それに対して量子コンピューターは、輝かしい未来が約束されているかのようです。そして、適用されるべき分野の一つに物流業界があります。

＜巡回セールスマン問題＞
巡回セールスマン問題（ＴＳＰ）とは、何ヶ所もの訪問先を抱えるセールスマンが、どのような順番で訪問すると最も効率的かを探し出せ、という問題です。別にセールスマンでなくても、宅配便の配送や、郵便物の配達も同じ問題といえます。

余談ですが、巡回セールスマンとは、アメリカ大陸を旅して回りながら聖書を訪問販売する、やや怪しげなセールスマンのことだそうです。１９７３年、ライアンとテータム・オニール親子が映画でも親子役で共演した「ペーパー・ムーン」をご存じでしょうか。娘テータムの不憫さを演出して、お涙頂戴で聖書を売るという手口だったかと思いますが、テータム・オニールの憎めないキャラクターに感情移入したものです。

閑話休題、要するに巡回経路をどのような順番にすれば最短距離あるいは最短時間でこなせるか、ということです。それを求めることがそんなに難しいことなのでしょうか。

＜最短ルートの求め方＞
いえいえ全然難しくありません。片っ端から、しらみつぶしに、経路の訪問ルートの組み合わせすべてについて、いちいち走行距離あるいは走行時間を計算し、その中で最短の者を選び出すだけです。簡単な話です、手間はかかるけれど、時間はかかるけれど。

さてそこで、どれだけの手間と時間がかかるかということですが…。訪問箇所が増えるほど、計算の時間も増えるだろうというのは、なんとなく予想できるかと思います。全くその通りで、訪問箇所をｎとすると、計算回数はざっくりと、ｎの階乗と見做せます（例えば、３の階乗＝３×２×１、という計算です）。そうすると、訪問箇所数と計算回数の関係は、図表１、２のようになります。

図表１ 訪問箇所数と計算回数

図表２ 訪問箇所数と計算回数

ようするに、訪問箇所が増えると、計算回数もそれに応じて増えるのではなく、とめどもなく増えていくのです。訪問箇所が２０ヶ所で、計算回数は約２４０京となります。尚、ここでいう計算回数が１回というのは、経路の訪問ルートの組み合わせの中の１つのルートについての、距離あるいは時間を算出する一連の計算のことです。この一連の計算を２４０京回やって、その上で、その中から最短距離あるいは最短時間を選び取る作業が必要になります。

仮に、１秒間に１００万回の計算回数をこなせたとして、８万年ぐらいかかることになります。こうなると、如何に馬鹿力のコンピューターとはいえ、いくら待っても答えが出てこない、という状況に陥ります。やることは単純だけれどやることが多すぎる、というのが巡回セールスマン問題の問題なのです。

ならば、この問題を量子コンピューターはどのように解決してくれるのでしょうか。それはその名の出どころである、量子力学の理論に依拠しています。

＜量子力学の流儀＞
先ずは、物理学の歴史を振り返るところから始めたいと思います。時は１８世紀後半、化学者は化学反応する物質の質量がきれいな比例関係にあることを見出し、それをきっかけに全ての物質はそれ以上分割できない最小単位、すなわち原子に還元できる、との考えを持つに至りました。これを原子論といいます。

この考えは基本的に今日でも成り立ち、例えば私は水や脂肪やタンパク質などでできていて、タンパク質は２０種類のアミノ酸というパーツで組み立てられていて、アミノ酸はカルボキシル基やアミノ基などで構成され、カルボキシル基やアミノ基は、炭素や酸素や水素などの原子が結合してできている、というわけです。あなたもそうです。

そして、この原子は種類により原子番号でナンバリングできて、周期律表という一覧表にきれいに並べることができることが見出されました。つまるところ、この世のすべては周期律表に配置される原子の組み合わせで表現できることになったのであり、ここに原子論は完成に至った、かに思えたのです。

その後、奇妙な発見が続きます。まず、原子が内部構造を持つことが発見されました。それはつまり、原子はもっと細かいものでできているということです。それでは分割できない究極の物質はなんだ、ということになり、究極の物質探しが始まりました。

分かってきたのは、原子は原子核と電子でできていて、原子核は陽子と中性子でできていて、さらにわれらが湯川秀樹は原子核を纏めておくのに中間子の存在を予測したりしたのでした。最近ではさらに細かくなっていて、それらの細かい粒子はまとめて量子と呼ばれて、現在に至っています。

さてここで、物理学者に、それでは量子が究極の物質なのか、と質問してみましょう。その答えは、「いや、それはもはや物質とは言えない」となるかもしれません。

何やら禅問答の様相を呈してきました。そもそも量子なるものは、どこにあってどう運動しているか確定できない、位置が分かれば運動が分からない、逆も真なり、いや偽なりか。同時に分かりそうなものなのに。さらに何をどう思ったのか、量子のふるまいを波を表す数式で説明しようと試みてしまい、なんと成功してしまいました、それも大成功。

量子は、もはやモノ的な属性がかすれてきて、代わりにパターンのようなものになってきたかに見えます。私の理解はこの程度でしかありませんが、普通に目に見て触れるモノを分解していったらモノじゃなくなったというのは、なんとも矛盾に満ちている…色即是空っていい線いってたかもしれません。まぁしょうがない、当の物理学者もこのモヤモヤ感を納め切れていないように思えるのです。

しかし、このなんともブラックな理屈は、コンピューターの未来を明るく照らしてくれるのです。
（続きは次月へ）

◆ 出典元
・ジャレド・ダイアモンド：銃・病原菌・鉄
・カルロ・ロヴェッリ：世界は｢関係」でできている
・田俊太郎：量子コンピュータが本当にわかる！
・吉田伸夫：量子で読み解く生命･宇宙･時間
・松井泰子 , 根元俊男 , 宇野毅明：入門ＯＲ
・藤澤 克樹 , 後藤 順哉 , 安井 雄一郎：Ｅｘｃｅｌで学ぶＯＲ