コンピューティング
量子コンピューティングで『巡回セールスマン問題』を解く
Securities.io を Google の優先ソースに追加
コンピュータサイエンスの分野で古典的なアルゴリズム問題である巡回セールスマン問題（TSP）は、組み合わせ最適化問題の代表例です。
TSPとは正確には何でしょうか？ この数学の古典は、N 個の都市を一度ずつ訪れ、出発都市に戻る最短ルートを見つけることを目的としています。しかし、都市数が増えるにつれて、可能なルート数と最適解を見つける計算時間も増大します。この問題は近似手法で解くこともできますが、量子コンピュータははるかに優れた解を、さらに迅速に提供できる可能性があります。
これは、理論物理学者 Jens Eisert 教授博士のチームが実証した通り:、このような問題が量子コンピュータでより良く、より速く解決できることを示しています。
量子コンピューティングは、量子力学を活用したハードウェアとアルゴリズムを利用して、従来のコンピュータやスーパーコンピュータの手に余る複雑な問題を解決します。これらは強力ですが、何千ものCPUやGPUコアを持つ巨大な古典コンピュータであるスーパーコンピュータは、20世紀のトランジスタ技術に依存しているため、高度に複雑な問題を解く際に限界があります。
ここで量子物理学が登場します。古典コンピュータが情報を二進ビット（0 と 1）で符号化するのに対し、量子コンピュータは量子ビット（キュービット）を用いて多次元の量子アルゴリズムを実行します。
さらに、従来のコンピュータがファンで冷却するのとは異なり、量子コンピュータは量子プロセッサを極低温に保ち、量子状態を維持する必要があります。これは超低温の超流体によって実現されます。
超伝導体は、臨界的な量子力学的効果を示す材料で、電子が抵抗なく流れることができます。電子は通過する際に対になり、バリアを越えて電荷を運びます。2 つの超伝導体が絶縁体の両側に配置されると、ジョセフソン接合が形成され、これが超伝導キュービットの伝導に利用されます。
キュービットは、量子情報を重ね合わせ状態に置く重要な役割を果たします。重ね合わせはキュービットが取り得る構成の組み合わせです。重ね合わせ状態にあるキュービットの集合は、複雑で多次元な計算空間を生成し、複雑な問題を表現できるようになります。
ここでは、2 つのキュービットのエンタングルメントにより、一方の変化が直接他方に影響を与えます。また、エンタングルされたキュービットが重ね合わせ状態になると、膨大な確率が生じます。量子コンピュータの計算は、すべての可能な計算状態の重ね合わせを準備し、干渉を通じて解を導き出すことで行われます。
もちろん、多数のキュービットを持つ量子コンピュータの構築は非常に複雑なプロセスですが、こうしたコンピュータが何を実現できるかについてはさまざまな手法が検討されています。
Helmholtz-Zentrum Berlin（HZB）の共同研究グループとフライ大学（Freie Universität Berlin）を率いるEisert氏によれば、
「この分野には多くの神話があり、時には根拠のない誇張や過熱も見られます。しかし、我々は数学的手法を用いて厳密に取り組み、確固たる結果を出しました。何よりも、どのような点で利点があるのかを明確に示すことができました。」
The Critical Traveling Salesman Problem
最適化問題であるTSPは、物流やサプライチェーン産業において極めて重要な経済的意義を持ちます。これは組み合わせ最適化問題の大きなカテゴリに属し、ジョブスケジューリング、リソース割り当て、ポートフォリオ最適化、さらにはタンパク質折りたたみまで、さまざまな分野で重要です。
これらの問題は社会的・経済的に重要であるため、集中的な研究対象となっています。その結果、最も効率的なサプライチェーンや最安の配送ルートを見つけることは、私たちの日常生活にプラスの影響を与えます。
しかし、複数の目的地への配送ルートを最適化し、交通渋滞、運用コストの上昇、突然のルート変更、直前のビジネスアポイント、顧客からの要望など様々な制約を考慮することは、TSPをさらに解くのが難しくします。これらの課題にもかかわらず、TSPの解決は商品配送の効率化に不可欠であり、持続可能なビジネスモデルを支えます。
この問題を解決することで、走行距離と時間の削減、燃料使用量の節約など多くの利点があります。走行距離を最小化することで、炭素フットプリントを大幅に削減でき、空気質の改善、気候変動の緩和、経済成長につながります。さらに、TSPの解決は商品の時間通りの配送や顧客とのミーティングの円滑化に寄与し、顧客体験やフィールドサービスビジネスを向上させます。
ご覧のとおり、問題を解くことは企業にとってだけでなく、顧客にも恩恵をもたらし、関係者全員の体験を豊かにします。
TSP問題を解くためにはさまざまな手法があります。その一つが「全探索」アプローチで、すべての可能な順列を計算して最短ルートを見つけます。分枝限定法では、問題を複数のサブ問題に分割し、各段階の解が次の段階の解に影響を与える形で解決します。
動的計画法では、冗長な計算を回避することに重点を置きます。一方、最近傍法は近似アルゴリズムで、出発地点から始めて最も近い都市へと順に移動し、すべての都市を訪れたら出発点に戻ります。実用的で比較的高速ですが、常に最適なルートを提供できるわけではありません。
技術が進歩するにつれて、ルート計画と最適化ははるかに効果的に行えるようになります。特に人工知能（AI）は、大量のデータを迅速に分析し、多くの現代企業が運用上や戦略上の意思決定を行うのに役立ちます。
量子コンピュータもこの問題の解決に向けて研究が進められています。結局のところ、量子コンピュータは古典コンピュータに比べて大幅な計算速度向上が期待できるからです。長い間、これらのコンピュータが問題の近似解を改善できる可能性が指摘されてきました。
Using Quantum Computing Techniques to Solve TSP
量子コンピューティングは大きな関心を集め、特定の問題に対して有望な結果を提供していますが、その量子優位性の範囲はまだ十分に探求されていません。
そのため、本研究は量子コンピュータが組み合わせ最適化問題の近似解を見つける際に、従来のコンピュータを実際に上回ることを完全に構成的に証明しました。
最新の研究は、Eisert と同僚の Jean‑Pierre Seifert が主導し、解析的手法のみを用いて、キュービットを持つ量子コンピュータがTSP問題をどのように解くかを評価しました。
「物理的実装に関係なく、十分な数のキュービットがあると仮定し、それらで計算操作を行う可能性を検討します」と、ベルリン工科大学の博士課程学生 Vincent Ulitzsch は説明しています。これは暗号学の一般的な問題、すなわちデータ暗号化に類似しています。
その後、チームは量子アルゴリズムであるShor アルゴリズムを使用し、整数の素因数分解を行い、これらの最適化問題のサブクラスを解きました。これにより、都市数が増加しても計算時間が爆発的に増大せず、多項式的に増加（Nx、x は定数）します。この方法で得られる解は、従来のアルゴリズムによる近似解よりも質的にはるかに優れています。
暗号概念と計算学習理論を用いることで、本研究は「量子コンピュータが組み合わせ最適化問題の近似において、古典コンピュータに対して超多項式的な優位性を持つことを完全に構成的に証明」しています。
さらに、研究チームは組み合わせ最適化問題の解の近似に対して、量子コンピュータが提供できる可能性について重要な質問に対し、顕著な進展を遂げたと指摘しています。これらの問題は社会的・経済的影響が大きいです。
本研究は、アインシュタイン研究ユニット、ベルリン数学研究センター（MATH+ クラスタ・オブ・エクセレンス）、BMBF（ハイブリッド）、BMWK（EniQmA）、ミュンヘン・クアンタム・バレー、そして DFG によって資金提供されました。ドイツ連邦教育研究省（BMBF）も財政支援を行っています。
Exploring Quantum Computing’s Potential
大きな成果ではありますが、量子コンピューティングが巡回セールスマン問題を解くのは初めてではありません。多くの熱心な研究者やエンスージアストが、量子コンピューティングを利用してこの問題の解決に取り組んできました。
2022年12月に論文が、Grover Adaptive Search（GAS）に基づくTSP用量子アルゴリズムを提案しました。GAS フレームワークでは、少なくとも二つの根本的な課題があります――解が実行可能でない可能性があること、そして現在の量子コンピュータのキュービット数が非常に限られており、最低要件を満たせないことです。これが組み合わせ最適化問題に対する量子アルゴリズムの適用を制限しています。
そのため、論文はハミルトニアン・サイクル検出（HCD）オラクルを改良し、アルゴリズム実行中に実行不可能な解を自動的に除去できるようにしました。また、量子コンピューティングの可逆性要件を完全に考慮し、キュービットを単に上書きまたは解放できないという課題を克服するために「アンカーレジスタ」戦略を設計しました。この手法により、必要なキュービットはわずか31個で済み、解の成功率は86.71％となりました。
2019年、自己定義の物理通好家 Joseph Cammidge は執筆し、アニーリング量子プロセッサを使用して7都市の巡回セールスマン問題を解決したと述べ、技術的制約が解消されれば9都市まで解く理論的可能性があるとしています。
新しい計算手法である量子アニーリングは、古典的手法よりも高速に最適化問題を解く可能性を示しています。その理論では、超低温でキュービットが最適な低エネルギー状態に達するとされています。
しかし、2021年に研究が、Supply Chain Digital と Data Science、Johnson & Johnson の資金提供のもと実施したところ、量子アニーラは8ノード以下の問題サイズしか扱えず、時間と精度の両面で古典的ソルバーに劣ることが判明しました。
量子コンピューティングを用いたTSP問題の解決は長らく続いています。20年以上前の2001年に、ある研究が探索を開始し、問題を解く量子アルゴリズムを模索しました。
論文では、アラバマ大学の Buckley Hopper がGrover と Shor の量子コンピュータアルゴリズムを検討しました。彼は、Grover のアルゴリズムは平方根の改善しか提供せず、古典的に手に負えない問題を量子コンピュータで解決可能にするほどではないと指摘しました。Shor のアルゴリズムについては、素因数分解という本来は手に負えない問題を量子マシン上で解決可能にするものの、非常に特定のタイプの問題にしか適用できないと述べました。
全体として、Hopper は「巡回セールスマン問題の近似解を計算するアルゴリズムとして満足のいく結果は得られなかった」と結論付けました。
数年後、電気電子学会（IEEE）は新しいアルゴリズムを提示し、遺伝的アルゴリズムと量子コンピューティングの両方に触発された手法です。IEEE の調査では、提案されたアルゴリズムをいくつかの巡回セールスマン問題のインスタンスに適用した結果、標準的な遺伝的アルゴリズムよりもかなり優れた結果が得られました。
量子コンピューティングの現状について学ぶにはこちらをクリックしてください。
Companies Working with Quantum Computing
それでは、量子コンピューティングの研究開発に取り組んでいる企業をいくつか見てみましょう：
#1. IBM
International Business Machines Corporation (IBM ) （IBM）は、AI、クラウドサービス、IT、クライアントファイナンス、商業ファイナンスなど幅広い分野で事業を展開しています。同社は IBM Quantum Platform を通じて量子コンピューティングにも取り組んでおり、パブリックおよびプレミアム向けにクラウドベースの量子コンピューティングサービスを提供しています。これには IBM のプロトタイプ量子プロセッサのセット、量子計算に関するチュートリアル、インタラクティブな教科書が含まれます。
最近、IBM の科学者たちは述べました、量子コンピュータのゲームチェンジングな可能性を解き放つ障壁を克服するもう一歩が近づいたと。これを実現するために、従来の手法より約10倍効率的な新しい量子誤り訂正コードを導入したとしています。
昨年後半、同社は「Condor」と呼ばれる量子コンピュータを発表し、1,121 個の超伝導キュービットをハニカム構造で配置しました。また、IBM は IBM Quantum System Two を公開し、初のモジュラー量子コンピュータと量子中心のスーパーコンピューティングアーキテクチャを提供しました。これはスケーラブルで、今後5年間で導入されるチップでアップグレード可能です。
IBM 価格チャート
時価総額 1,750 億ドルの IBM の株価は 190.86 ドルで取引されており、年初来（YTD）で 16.66% 上昇しています。IBM の直近 12 ヶ月（TTM）の売上高は 618.6 億ドル、EPS（TTM）は 8.03、P/E（TTM）は 23.76、ROE（TTM）は 33.36% です。同社は配当利回り 3.48% を支払っています。
#2. D-Wave Systems
この量子コンピューティング企業は、関連するシステム、ソフトウェア、サービスを開発・提供しています。製品には The Leap と The Advantage があり、スケジューリング、物流、医薬品探索、製造プロセスなどの量子アプリケーションを提供しています。
今月初め、D-Wave は量子マシンが実世界のアプリケーションに関わる問題を、従来のコンピュータよりも高速に解決できると発表しました。今年初めには、1,200 キュービット、10,000 カップラー、ハード最適化問題に対して 20 倍速いソリューションタイムを持つ量子コンピュータを発表しました。
QBTS 価格チャート
同社の株価は現在 1.86 ドルで取引されており、年初来（YTD）で 138.6% 上昇しています。時価総額は 2億6700 万ドルです。売上高（TTM）は 824.7 万ドル、EPS（TTM）は -0.66、P/E（TTM）は -3.19 で、2023 年度第4四半期および通年の売上高はそれぞれ 20% 超の成長を示し、受注はそれぞれ 34% と 89% 増加しました。
興味深いことに、同社の CEO である Dr. Alan Baratz は、Zapata AI との数年にわたる戦略的パートナーシップ、1,200 以上のキュービットを持つ Advantage2 プロトタイプの導入、NEC オーストラリアおよび Deloitte カナダとの共同ベンチャー、そして元国土安全保障長官 Kirstjen Nielsen の取締役会への就任を挙げ、同社の勢いを宣言しました。
Conclusion
量子コンピューティング市場は2028年に 65億ドルに達する、そしてその巡回セールスマン問題（TSP）を解く可能性は、製造業、物流、サプライチェーン管理、eコマース、輸送、研究など複数の産業に波及効果があります。結局のところ、これにより生産性が向上し、費用が削減され、さまざまな分野でイノベーションが促進されるという実質的な利益が得られます。
