Quantum Bloom Filter and Its Applications
Runhua Shi
Abstract
A quantum Bloom filter is a spatially more efficient data structure which is used to represent a set of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula> elements by using <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O({{\rm{log}}nk})$</tex-math></inline-formula> 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.