image: This figure shows that the search space size of the index selection problem causes a combinatorial explosion, where any K elements are selected from M elements and assigned log2(Q) bits of information. Even for a simple case like (M, K, Q) = (16, 8, 64), there are about 6.94 * 10^{173} candidates, which is very hard to solve. view more
Credit: Yokohama National University
横浜国立大学の石川直樹准教授は、インデックス変調と呼ばれる無線通信方式について、量子コンピュータと古典コンピュータの両方を用いる新しい最適化法を提案し、量子加速の確認に成功しました。
インデックス変調は0と1の組合せにより情報を表現します。この0と1の組合せは最小ハミング距離を最大化しつつ、1の偏りを最小化すれば最適な通信性能を達成できることが明らかにされてきました。一方で、探索空間が組合せ爆発となる場合については、古典コンピュータで解くことが難しいと認識されており、これはインデックス選択問題と呼ばれています。本論文では、グローバー適応探索と呼ばれる量子アルゴリズムを用いて、インデックス選択問題の量子加速を達成するための新しい最適化法を提案しました。まず、古典コンピュータを用いた前処理により探索空間を狭くした上で問題を定式化します。次に、量子アルゴリズムを用いて最適化することで、必要とされる量子ビット数を最小限に抑えることに成功しました。ただし、本研究のアプローチは二次的な加速であるため、問合せ計算量が指数関数的に増加する問題については従来研究と同様に解決されていません。また、誤り耐性のある量子コンピュータで多くの量子ビットを必要とするため、今後も長期的な検討を必要とします。
本研究成果は国際論文誌IEEE Accessに受理され、オンライン版が2021年8月9日に掲載されました。
Journal: IEEE Access
DOI: 10.1109/ACCESS.2021.3103207
Journal
IEEE Access
Article Title
Quantum Speedup for Index Modulation
Article Publication Date
9-Aug-2021