1. 現状の延長線上のAIにできないこと

近年，深層学習をはじめとするAI技術は，画像認識から自然言語処理，科学的発見に至るまで，多岐にわたる分野で目覚ましい成功を収め，社会の様々な課題解決に不可欠な存在となりつつある．しかし，その輝かしい成果の裏で，現代の計算機（古典コンピュータ）を基盤とするAIが原理的に解くことが困難だと考えられている問題も存在する．

その代表例が，図1に示すような，現代の暗号技術の安全性を支える素因数分解に関連した学習タスクである．ある学習理論の枠組み（具体的にはPAC学習理論）では，もし素因数分解に関連する何らかのパターンを効率的に学習できる古典AIが存在するならば，それは素因数分解問題そのものを効率的に解くアルゴリズムの存在につながることが，理論的に示されている(1)．したがって，「素因数分解が古典コンピュータ上で困難である」という計算量理論上の強い信念は，「それに関連する学習タスクを，古典コンピュータによって解くことも困難である」という信念と表裏一体となる．これは，古典コンピュータ上で動作するAIが直面する，原理的な壁の一例と言える．

この壁を乗り越えるための一つの方策として，新しい計算基盤として量子計算を導入することが考えられる．本稿ではまず，量子計算が古典計算に対して有する計算量理論的優位性を整理し，次いでその性質を活用することで，どのような機械学習タスクが原理的に可能となり得るのかを，設計指針と具体例を交えて検討する．