膨大な古典データを処理する際の指数関数的な量子優位性

カリフォルニア工科大学（Caltech）、Google Quantum AI、マサチューセッツ工科大学（MIT）、Oratomicの研究者たちは、古典データの処理において量子コンピュータが指数関数的な空間的優位性を持つことを実証する技術論文を発表しました。この研究は、「膨大な古典データを処理する際の指数関数的な量子優位性」と題されており、量子ランダムアクセスメモリ（QRAM）の莫大なメモリオーバーヘッドなしに、古典データに量子重ね合わせでアクセスするという長年の課題である「データローディング問題」に取り組んでいます。

この研究では、量子オラクルスケッチと呼ばれるフレームワークが導入されており、これにより量子コンピュータはストリーミングされる古典データサンプルからコヒーレントなクエリを構築できます。データセット全体を保存するのではなく、アルゴリズムは各サンプルを増分的な量子回転を適用することで「オンザフライ」で処理します。これらの回転は蓄積されて量子オラクルを近似し、システムは使用後にサンプルを破棄しながら量子線形代数アルゴリズムを実行できるようになります。研究者たちは、この方法がサンプル複雑度と量子クエリの間に二次関係を達成することを証明しており、これはボルン則によって支配される基本的な限界として確立されています。