Quantum Bloom Filter and Its Applications
Runhua Shi · IEEE Transactions on Quantum Engineering · 2021
A quantum Bloom filter is a spatially more efficient data structure which is used to represent a set of$n$elements by using$O({{\rm{log}}nk})$qubits. In this article, we define and design a quantum Bloom filter and its corresponding algorithms. Due to the reversibility of quantum operators, it can not only add a new element to a quantum Bloom filter but also delete an existing element from the quantum Bloom filter. Furthermore, we employ the quantum Bloom filter to solve two private issues, i.e., oblivious set-member decision and multiparty private set intersection cardinality. The results show that the quantum Bloom filter has inherent advantages in privacy-preserving applications concerning set operations.