矩形パッキングと量子アルゴリズム設計

矩形パッキングとは、与えられた小さな矩形の集合を、2つの小さな矩形が重ならないように、与えられた大きな多角形の中に配置することである。関連する問題は、すべての小さな長方形を重ならずに含むことができる最小の長方形を見つけることである。

例えば、この5つの長方形が1つの表面にある：

それらをコンパクトにパッキングした配置に：

簡単だろう？

この問題は、おそらく難しいからであろうが、おそらく多くの実用的な応用があるからであろう。UPSトラックの最適な箱詰めとは？ASICの機能ブロックを最適に配置する方法は？あるアイテムを収納できる最小の箱とは？正しい答えを得ることは、運送会社やチップ設計会社にとって非常に価値のあることかもしれない。

では、もっと大きな数の長方形を使ってみよう。結果はこうだ：

その方が難しいだろうし、人間がこの答えを見つけるにはかなりの時間がかかるかもしれない。

さらに長方形を取ってみよう：

何百もの長方形を手作業で並べるとしたら、どれくらいの時間がかかるだろうか？そして、もしそうするとして、それは最適解なのでしょうか？スペースを無駄にしていませんか？もっと多くの長方形を配置できないだろうか？

長方形が異なる色で、同じ色の2つの長方形を隣接させたくないとします。あるいは、ある矩形同士はどうしても近づけたいが、他の矩形はそれほど気にしないとします。

このような問題は、本当に速く、本当に難しくなる。あまりに難しいので、こうした問題は人間に解決してもらうよりも、コンピューターを使って解決した方がずっといいことがすぐにわかる。何千、何万という選択肢を探索し、高度なアルゴリズムと計算を実行し、良い答えを導き出すことができるコンピューター。

量子アルゴリズム設計には多くの類似した特徴がある

量子アルゴリズムがある場合、それを利用可能な量子ビットの数に収める必要がある。どの量子ビットをどのブロックに使うか、あるコードブロックの出力を次のコードブロックの入力にどのように接続するのが最適かを決める必要がある。おそらく、最小の量子ビット数や最小の回路深さなど、特定の制約に収めたいのでしょう。あるいは、制約が違うかもしれません。あるサイズのコンピュータがあり、そこにできるだけ多くの機能ブロックを収めようとしているかもしれません。

長方形と同じように、コンピュータがこの最適化を最も得意とすることはすぐにわかる。そう、人間は数ブロックと5量子ビットで良い仕事をし、20量子ビットではあまり良くない仕事をし、200量子ビットではおそらく悪い仕事をするだろう。

設計者は "何を "設計するかに集中し、"どのように "設計するかは賢いコンピューター・プログラムに任せる。コンピュータがより強力になればなるほど、量子コンピュータの機能ブロックに適合するものを見つけるこの自動化されたアプローチが、機能し、真の価値を提供する高度な回路を設計するための最良の、そしておそらく唯一のアプローチになると信じている。