Quantum Circuit Complexity of Genomic Data Encoding

Data encoding is a key step in almost all ap-plications of quantum computation, but one that is not very well understood in general. Extensively researched in quantum machine learning, it is pivotal to exploiting the speedups offered by quantum algorithms. Failure to efficiently represent data risks weakening or nullifying prospective quantum advantages. While naive methods, such as basis encoding, will almost always work, they are extremely inefficient in terms of qubit use, rendering them infeasible for near-term applications. We focus on data encoding for genomics, a deeply data-driven field with computationally intensive algorithms throughout, from the initial DNA sequencing to pangenome assembly and more. We first examine the compressibility of genomic data from an information-theoretic perspective and how compression affects the quantum state preparation complexity. Here, there are two opposing forces at work: compression reduces data size but at the cost of the beneficial structure within the data. We review some standard approaches to data encoding in the context of genomics data from considering both the preparation complexity in terms of gate counts, qubit use, and depth, as well as the usefulness of the resulting states. We also present some new data encoding methods designed specifically for genomics that have a low-depth preparation circuits while still maintaining the essential features the algorithms require.