Bisection Grover’s Search Algorithm and Its Application in Analyzing CITE-seq Data

With the rapid development of quantum computers, researchers have shown quantum advantages in physics-oriented problems. Quantum algorithms tackling computational biology problems are still lacking. In this article, we demonstrate the quantum advantage in analyzing CITE-seq data. CITE-seq, a single-cell technology, enables researchers to simultaneously measure expressions of RNA and surface protein detected by antibody-derived tags (ADTs) in the same cells. CITE-seq data hold tremendous potential for identifying ADTs associated with targeted genes and identifying cell types effectively. However, both tasks are challenging since the best subset of ADTs needs to be identified from enormous candidate subsets. To surmount the challenge, we develop a quantum algorithm named bisection Grover’s search (BGS) for the best subset selection of ADT markers in CITE-seq data. BGS takes advantage of quantum parallelism by integrating binary search and Grover’s algorithm to enable fast computation. Theoretical results are provided to show the privilege of BGS in the estimation error and computational complexity. The empirical performance of the BGS algorithm is demonstrated on both the IBM quantum computer and simulator. Supplementary materials for this article are available online, including a standardized description of the materials available for reproducing the work.