211service.com
量子コンピューティングに強力な検索ツールが追加されました
グローバーのアルゴリズム
1996年に、ニュージャージーのベル研究所のLov Groverと呼ばれるコンピューター科学者が、データベースを検索するための珍しいアルゴリズムを発表しました。検索アルゴリズムは、コンピュータサイエンスで最も重要なものの1つです。それらは、電話の本を探すなどのありふれたタスクだけでなく、暗号化コードの解読などのよりエキゾチックなタスクも可能にします。この種のアルゴリズムは、コンピュータサイエンスに広く普及しています。
したがって、タスクを高速化する方法は非常に重要です。標準の検索には、検索の要素数にほぼ比例する期間がかかります。これは、最悪のシナリオでは、アルゴリズムがすべての要素を検索して1つだけを見つける必要があるためです。
しかし、グローバーのアルゴリズムは異なります。かかる時間は、要素数の平方根に比例します。コンピュータ科学者はこれを二次スピードアップと呼んでいます。そして、数パーセントの速度の増加が非常に価値がある世界では、二次高速化は非常に大きな成果です。
グローバーの秘訣は、量子力学の背後にある奇妙で強力なアイデアを採用することでした。古典的な世界では、ビットは0と1だけです。しかし、量子の世界では、単一の量子ビット、つまりキュービットが同時に0と1になる可能性があります。物理学者は、キュービットは状態の重ね合わせにあると言います。
重ね合わせが鍵です。この状態では、アルゴリズムは0と1の両方を同時に検索できます。同時に複数の要素を検索できるため、量子アルゴリズムは、古典物理学の急成長によって制限されるアルゴリズムよりもはるかに高速にリストを検索できます。
量子アルゴリズムは量子コンピューターによって実装されなければならず、1996年にグローバーが彼の仕事をしたとき、これらは遠い夢に過ぎませんでした。しかし、ブレークスルーはすぐに実現しました。物理学者は1998年に最初の原始量子コンピューターを実証し、同じ年にグローバーのアルゴリズムを実行する方法を示しました。
しかし、この特定の形式の量子コンピューティングは非常に限られていました。それは数キュービットで機能しましたが、それ以上は機能せず、原則として、より大きな計算にスケールアップすることはできませんでした。スケーラブルな量子コンピューターを構築して実証するというこの問題は、それ以来、この分野を悩ませてきました。
現在、約20年後、物理学者は、スケーリングの可能性があり、より強力な計算が可能な量子コンピューターを構築し始めています。そして今日、メリーランド大学のキャロライン・フィガットと仲間たちは、スケーラブルな量子コンピューターでグローバーのアルゴリズムを初めて実行したと言います。
この作業は、量子計算の高速化を実証し、コード解読などの現実世界の課題を解読し始める可能性のあるアルゴリズムを使用した、より野心的な作業への道を開きます。
Figgattと共同で使用している量子コンピューターは、電磁場に浮遊する5つのイッテルビウムイオンのストリングで構成されています。各イオンは小さな磁石のようなもので、レーザーを使って上下に向けたり、ある状態から別の状態に反転させたりすることができます。このようにして、各イオンは情報を保存できます。たとえば、スピンアップの場合は1、スピンダウンの場合は0です。そして、それらは量子オブジェクトであるため、イオンはこれらの状態の重ね合わせで存在することができます。
イオンはまた、それらの正電荷に関連する反発力を介して互いに相互作用します。この相互作用により、あるキュービットが別のキュービットと相互作用して情報を処理できるようになります。これが量子計算の本質です。この計算のステップの順序は、量子アルゴリズム、この場合はグローバーのアルゴリズムです。
Figgattと共同研究者は、彼らのシステムを使用して、データベースに最大8つのアイテムを格納できる3キュービットの量子コンピューターを作成します。次に、グローバーのアルゴリズムを実行して、少なくとも8ビットを必要とする従来のコンピューターよりも平均して大幅に高速にアイテムを見つけることができることを示します。トラップされた原子イオンのスケーラブルな量子コンピューティング技術を使用した、従来よりも優れたパフォーマンスを備えた完全な3キュービットグローバー検索アルゴリズムの結果を報告します。
それは大きな可能性を秘めた興味深い作品です。これにより、他の量子アルゴリズムのサブルーチンとして回路を使用するなど、量子コンピューター上のより大きな問題を解決するために、グローバー検索アルゴリズムをより広範囲に使用できるようになります。
しかし、この作業は、強力な量子コンピューターを構築するための競争を垣間見ることもできます。このレースの勝者は莫大な金銭的見返りを得る可能性がありますが、どのテクノロジーが最適かは誰にもわかりません。
この世界は、Googleやロッキードマーティンなどの企業に一見強力な量子コンピューターを販売しているD-WaveSystemsと呼ばれるカナダのスタートアップによって混乱に陥っています。これらのコンピューターは、他のどのテクノロジーよりもはるかに多い1,000キュービットで動作します。
しかし、多くの理論家は、D-Waveの主張は誇張されており、そのマシンは他の量子コンピューターが実行できるはずの種類の計算能力に近い場所では生成できないと述べています。
そのため、多くのグループが、量子情報の保存と処理の方法が劇的に異なる他の量子技術を商品化しようとしています。これらは、量子入札を行うために、光子、電子、原子、イオン、および分子にさまざまに依存しています。
これらの技術のうち、最も古く、最も開発されたものの1つはイオントラップ量子コンピューティングであり、メリーランド大学グループはこの分野の世界的リーダーです。実際、グループのリーダーであるChris Monroeには、このテクノロジーの商業化を目的としたIonQというスタートアップがあります。
したがって、3キュービットしかないにもかかわらず、グローバーのアルゴリズムを実装できるスケーラブルな量子コンピューターのデモンストレーションは、意図の表明と見なすことができます。
1998年、グローバーのアルゴリズムの最初の実装後、物理学者が次のステップのスケーラブルなコンピューターを作成するのにどれくらいの時間がかかるかについて、さまざまな意見がありました。楽観的な予測に基づいて、多くのスタートアップが正式に形成され、崩壊した。しかし、当時、20年は予測の範囲の悲観的な終わりにありました。これだけ長い時間がかかったという事実は、仕事の難しさを見通しに入れます。
宇宙を量子スケールで制御するのは難しいです。技術者やベンチャーキャピタリストにとって今興味深い質問は、技術の進歩の速度を大幅に加速できるかどうかです。
参照： arxiv.org/abs/1703.10535 ：プログラム可能な量子コンピューターで3量子ビットのグローバー検索を完了する