量子計算では、たくさんの候補を重ね合わせて調べられます。それなら問い合わせを一斉に済ませても、順番に調べる場合と同じ強さがあるのでしょうか。2026年11月1日に公開されたPan PengとJingyu Wuのプレプリントは、同じ値を持つ入力を探す「衝突探索」で、その違いを明らかにしています。
対象は、現れる値がどれもちょうど同じ回数だけ出てくる、という条件を置いた問題です。問い合わせの間に量子状態を処理できる方式と、すべての問い合わせを一度の並列層にまとめる方式では、必要な問い合わせ数の増え方が異なります。
簡単にまとめると？
- 各値がちょうど同じ回数現れる条件で、同じ値の入力をすべて探すための問い合わせ数を調べた理論研究です。
- 問い合わせを順につなぐ量子方式は回数を減らせます。一ラウンド方式では、量子もつれや共同測定を使っても増え方は古典方式と同じになります。
- 比較するのは問い合わせの総数。実機の処理時間や、一般的な暗号の安全性をそのまま決める結果ではありません。
衝突とは、違う場所に同じ値があること
ここでいう衝突は、物体がぶつかることではありません。異なる入力位置を調べたときに、同じ値が返ってくることです。例えば、伏せたカードにA・A・B・B・C・Cが一枚ずつ書かれているとします。位置を指定して値を調べ、Aの書かれた二つの位置を答えられれば、二つ組の衝突を見つけたことになります。このカードは問題の意味を説明する例で、実際の量子問い合わせはカードを一枚ずつ表にする操作とは異なります。
論文では入力の総数をn、同じ値が現れる回数をkとします。現れる値はすべてちょうどk回ずつ現れ、nはkの倍数です。目的は、同じ値を持つk個の異なる位置をすべて答えること。kが3なら、二つだけ見つけても、この探索問題を解いたことにはなりません。
値を返す窓口を「オラクル」と呼びます。研究では、その窓口を何回使う必要があるかを数えます。窓口そのものをどう作るか、周辺の回路にどれだけ時間がかかるかは、この回数の尺度には含まれません。
一斉に聞くか、得た情報を次へつなぐか
適応的な量子アルゴリズムは、問い合わせと問い合わせの間に量子状態を処理します。先の問い合わせで入力についての情報を取り込んだ状態を、次の問い合わせへ渡せる構成です。途中で毎回測定し、人間が結果を見て次の質問を選ぶ、という意味ではありません。測定せずに量子状態を保ったまま、あらかじめ決めた演算を順に実行する場合も含みます。
一方、非適応的な一ラウンド方式では、問い合わせをすべて同時の層にまとめます。その前の準備で量子もつれを作ることも、その後に全体をまとめて測定することも許されます。ただし、最初の問い合わせから得た情報を利用して、さらに次の問い合わせを行う段階はありません。
衝突探索では、部分的に見つけた同じ値の組を、さらに大きな組へ育てるような段階的な手順が役立ちます。新しい論文は、順につなぐ方式で知られていたアルゴリズムの問い合わせ数に対応する下限を示すとともに、一ラウンド方式ではその少ない回数に届かないことを示しています。新しい高速アルゴリズムの実装報告ではなく、どこまで回数を減らせるかを定める理論研究です。
二つ組では、nの3乗根と平方根の差になる
kを固定し、一定の成功確率を求めるときの結果を、二つの例に絞ると次のようになります。表の値は、nが大きくなるときに必要な問い合わせ数が増える規模です。定数倍を省いているため、そのまま実際の必要回数として使うことはできません。
| 探す組 | 順につなぐ量子問い合わせ | 一ラウンドの量子問い合わせ | 古典的な問い合わせ |
|---|---|---|---|
| 二つ組（k＝2） | nの1/3乗 | nの1/2乗 | nの1/2乗 |
| 三つ組（k＝3） | nの3/7乗 | nの2/3乗 | nの2/3乗 |
例えば入力を100万個から1億個へ100倍に増やしたとき、二つ組の探索の規模は、順につなぐ量子方式では約4.6倍、一ラウンド方式や古典方式では10倍になります。これは表のべき乗を使った増え方の例です。「ある実機なら何回で必ず見つかる」という予測でも、処理時間の倍率でもありません。
また、一ラウンドだから問い合わせが一回になるわけではありません。同時にt個の窓口を使えば、ここではt回分と数えます。問い合わせの総数を減らすことと、同時に実行して待ち時間を縮めることは、別の比較になります。
「あるかを判定する」と「組を全部見つける」も異なる
論文は、すべての値が異なる入力と、各値がちょうどk回ずつ現れる入力を区別する判定問題も扱っています。一ラウンドの量子問い合わせでは、その回数の規模はn/kの平方根になります。
この判定では、同じ値の二つ組が見つかれば、「すべて異なる」入力ではないことが分かります。k個すべての位置を答える探索とは、必要な出力が違うのです。三つ組の探索の結果と、重複があるかの判定の結果を、同じ性能指標として比べることはできません。
量子アルゴリズムを比べるときの確認点
この結果を読む際は、まず入力の条件を確認する必要があります。各値の出現回数が厳密にそろうという条件は、任意のデータや一般的なハッシュ関数に、そのまま当てはまるわけではありません。論文は、問題ごとの値の種類数の条件も定めています。探索では少なくともn/k種類、判定ではすべて異なる入力も表せるよう少なくともn種類の値を扱います。
次に、何を費用として数え、何回の問い合わせ段階を許すかを分けて考えます。今回の一ラウンド下限は、量子もつれを使わない弱い方式だけを対象にしたものではありません。それらを許した上でも成り立つため、単に問い合わせを並べるだけでは埋まらない差を示しています。一方、固定された二ラウンド以上の方式を細かく比べる問題は、論文で今後の課題として挙げられています。
重ね合わせを使うかどうかに加えて、問い合わせで取り込んだ情報を次へつなげられるか。それが、この理論研究から得られる比較の軸です。
出典
- Pan Peng, Jingyu Wu, Quantum Lower Bounds for Collision Problems, arXiv:2611.01767v1, 2026年11月1日公開。主結果の定理1.1〜1.3、Table 1、問い合わせモデル、技術的概要、今後の課題を参照。本文・図表の確認日は2026年11月4日。査読前のプレプリントです。