Applications of Quantum Computation and Algorithmic Information

Abstract

Efforts to realize a sufficiently large controllable quantum processor are actively being pursued globally. These quantum devices are programmed by specifying the manipulation of quantum information via quantum algorithms. This doctoral research provides an application perspective to the design requirements of a quantum accelerator architecture. Early quantum algorithms focused specifically on the theoretical study of the benefits in computational resource cost by harnessing quantum phenomena. With small-scale quantum processors being available, the focus is now towards applying quantum algorithms to develop applications with high impact in societal, industrial, and scientific fields. No quantum devices exist that can execute quantum algorithms that can demonstrate a provable advantage for a real world use case. However, a proof of concept application pipeline can be demonstrated on a simulator framework. The research question of this dissertation is to identify high-impact long-term applications of quantum computation and formulate the corresponding logic. Three specific use cases are studied.

Use case 1 involves `quantum-accelerated genome sequence reconstruction'. Faster sequencing pipeline would enable novel downstream applications like personalized medical treatment. Two different reconstruction methods, ab initio reference alignment, and de novo read assembly, are studied to identify the computational bottleneck. Corresponding quantum techniques are formulated, based on quantum search and heuristic quantum optimization, respectively. A new algorithm, quantum indexed bidirectional associative memory (QiBAM), is explicitly designed to address the requirements for approximate alignment of DNA sequences. We also proposed the quantum accelerated sequence reconstruction (QuASeR) strategy to perform de novo assembly. This is formulated as a QUBO and solved using QAOA on a gate-model simulator, as well as, on a quantum annealer.

Use case 2 involves `quantum automata for algorithmic information'. A framework for causal inference based on algorithmic generative models is developed. This technique of quantum-accelerated experimental algorithmic information theory (QEAIT) can be ubiquitously applied to diverse domains. Specifically for genome analysis, the problem of identifying bit strings capable of self-replication is presented. We developed a new quantum circuit design of a quantum parallel universal linear bounded automata (QPULBA) model. This enables a superposition of classical models/programs to be executed, and their properties can be explored. The automaton prepares the universal distribution as a quantum superposition state which can be queried to estimate algorithmic properties of the causal model.

Use case 3 involves `universal reinforcement learning in quantum environments'. This theoretical framework can be applied for automated scientific modeling. A universal artificial general intelligence formalism is presented that can model quantum processes. The developed quantum knowledge seeking agent (QKSA) is an evolutionary general reinforcement learning model for recursive self-improvement. It uses resource-bounded algorithmic complexity of quantum process tomography algorithms. The cost function determining the optimal strategy is implemented as a mutating gene within a quine. The utility function for an individual agent is based on a selected quantum distance measure between the predicted and perceived environment.

This dissertation researches foundational techniques and develops innovative applications of quantum computation and algorithmic information. These were applied specifically for causal modeling in genomics and reinforcement learning. Further exploration of the synergies among these interdisciplinary concepts would improve our understanding of various scientific disciplines like computation, intelligence, life, and cosmology.