Kushagra Garg supervised by Dr. Subhadip Mitra received his Master of Science – Dual Degree  in Computational Natural Sciences (CND). Here’s a summary of his research work on Early Fault-Tolerant Quantum Algorithms for Open Quantum Systems:

Quantum computing currently stands at the threshold of practical applications, although large-scale, fault tolerant quantum computers remain distant. Indeed, despite practical quantum computers having been perpetually “ten years away” for the past ten years, incremental yet substantial advances continue to fuel optimism. Remarkable progress over the past decade has led to increasingly robust, larger-scale, and better-connected quantum hardware. Notably, recent years have witnessed several demonstrations of quantum computing devices whose physical error rates lie below critical thresholds required by certain error-correction schemes, signaling a significant transitional phase in quantum computing technology. Nevertheless, fully fault-tolerant quantum computers capable of executing arbitrarily large quantum circuits with an unrestricted number of qubits are still far off. Instead, near-term quantum hardware will be limited to simpler, shallow-depth circuits operating on a restricted number of qubits. Such early fault-tolerant quantum devices cannot accommodate advanced quantum subroutines like amplitude amplification, block-encoding, or Quantum Singular Value Transformation (QSVT), which inherently rely on deep quantum circuits, multi-controlled gates, and extensive ancillary qubit resources. Consequently, it becomes imperative to rethink quantum algorithm design, focusing specifically on algorithms that operate within these restricted computational frameworks. Motivated by this challenge, this thesis develops quantum algorithms explicitly tailored for early fault tolerant quantum computing devices. We introduce a randomized quantum algorithm for efficiently simulating quantum collision models which provide a versatile theoretical framework for modeling open quantum system dynamics. Quantum collision models describe physical processes in which the system undergoes repeated interactions with a sequence of environmental degrees of freedom. Our algorithm employs a novel approach that composes multiple controlled short-time evolutions of simple Hamiltonians, interspersed with operations that trace out the environmental registers. Crucially, our method requires neither specialized quantum subroutines such as block-encodings nor extensive ancillary qubit resources, thus aligning closely with the limitations of near-term quantum devices. Moreover, by exploiting the fundamental correspondence between Lindbladian evolution and Markovian collision models, we present an end-to-end quantum algorithm for simulating Lindbladian dynamics tailored specifically for near-term quantum hardware. For a quantum system consisting of n qubits, we provide a detailed analysis of the circuit depth required to estimate expectation values of observables with respect to the state evolved under open quantum dynamics for evolution time t. Our algorithm performs this simulation using at most n+2qubits, achieving a circuit depth that scales polynomially with the number of qubits, desired precision, and evolution time. Additionally, we offer a detailed comparison of our algorithm with existing approaches, highlighting advantages in terms of required resources and suitability for near-term quantum hardware. We further generalize our framework beyond the memoryless scenario, developing an efficient method to simulate memory-retaining collision models, where successive environmental interactions give rise to non-Markovian dynamics. This extension allows us to model more intricate and realistic open-system behaviors that inherently exhibit memory effects. By providing novel quantum algorithms that robustly simulate both Markovian and non-Markovian quantum dynamics within early fault-tolerant quantum computing platforms, this thesis significantly expands the scope of feasible quantum simulations. Collectively, these advances offer a deeper understanding of the computational capabilities and inherent limitations of imminent quantum technologies, laying an essential foundation for further theoretical and practical developments in quantum computing.

December 2025