Near-term quantum computational utility through simulation and algorithms

Abstract

This thesis examines the theoretical foundations that enable near-term quantum computational utility. Quantum utility occurs when a quantum computer contributes meaningfully to solving a computational task that a classical computer cannot alone replicate without additional time or loss of accuracy. Unlike quantum advantage, which requires provable superiority over all classical methods, quantum utility requires only practical usefulness, employing quantum devices as effective tools for scientific discovery. Recognising this distinction is essential for directing research towards pragmatic goals achievable with current and emerging hardware. The thesis comprises a three-part investigation encompassing theoretical limits, algorithmic design, and hybrid applications. First, it characterises the boundary between classically simulable and intrinsically quantum computations by analysing a specific class of simulable circuits. Second, it designs and analyses specialised quantum algorithms for structured problems using the framework of parameterized complexity. Finally, it demonstrates pragmatic algorithm design through a hybrid classical–quantum approach to a key problem in computational genomics, illustrating how theoretical progress can translate into tangible near-term utility.