ブルームフィルタ（Bloom Filter）は、「あるかないか」を完全には教えてくれない代わりに、軽く高速に動く集合判定用のデータ構造です。返してくれる答えは二つだけで、「絶対にない」か「たぶんある」です。ここがハッシュテーブルやデータベースと決定的に違う点です。
仕組みはシンプルで、まず固定長のビット配列（0と1だけの配列）を用意し、複数個のハッシュ関数を用意します。要素を登録するときは、その値をハッシュ関数に順番に通し、得られたインデックスのビットを1に立てていきます。検索するときは、同じハッシュ関数群を使ってビットを調べ、全部が1なら「たぶんある」、一つでも0があれば「絶対にない」と判断します。
なぜ「たぶん」なのかというと、異なる複数の要素が同じビットを共有してしまう場合があるからです。その結果、本当は登録されていない値について、関連するビットがたまたますべて1になってしまい、「あるかもしれない」と誤判定することがあります。これを偽陽性と言います。一方で、本当は登録されているのに「絶対にない」と判定される偽陰性は、正しく設計されたブルームフィルタでは原理的に起こりません。
この「偽陽性はあっても偽陰性はない」という非対称な性質が、実務でとても扱いやすいポイントです。例えばスパムメール判定や危険URLリスト照合では、「怪しいかもしれないもの」は後段の重い検査に回し、「絶対に安全なもの」だけを素通しさせたい、という要件がよくあります。ここでブルームフィルタを入り口に置けば、「絶対にリストに存在しない送信者」や「登録されていないURL」を素早く除外でき、データベースや機械学習モデルへの問い合わせを大きく減らせます。
偽陽性の出やすさは、ビット配列の長さと登録する要素数、ハッシュ関数の個数によって変化します。メモリを多めに割り当てれば偽陽性率は下がりますが、そこまで厳密さがいらない用途も多いため、「このくらいの間違いなら許容できる」というビジネス要件に合わせてパラメータを決めるのが実務的な設計です。完全な正確さをあえて手放し、その代わりにメモリと速度、システム全体のスループットを稼ぐ。その割り切りこそが、「絶対にない」か「たぶんある」で判断するブルームフィルタの本質だと言えます。
ブルームフィルタと量子コンピュータは、「完全な正解」よりも「高確率で効率よく正解に近づく」発想が共通しています。実務的には、まず古典側でブルームフィルタを使い「絶対にない」候補を大量に捨て、残った「たぶんある」少数の候補だけを量子アルゴリズム（Grover探索など）に渡して高速検索する、といったハイブリッド構成が有望だと考えられます。
