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.
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.
Quantum computing has progressed from theoretical speculation to experimental realization, leading to milestone demonstrations that claim computational superiority over classical systems. Among these milestones, quantum supremacy experiments have attracted considerable attention by showcasing tasks that are infeasible for classical computation within reasonable time limits. However, the practical value of such demonstrations remains a subject of debate. This paper critically evaluates the distinction between quantum supremacy and quantum utility, emphasizing their conceptual differences, experimental foundations, and real-world relevance. By examining key experimental results, algorithmic developments, and benchmarking approaches, the study argues that quantum utility-defined by practical, application-oriented performance-provides a more meaningful metric for long-term progress. The paper highlights the limitations of supremacy-based demonstrations and discusses pathways toward achieving utility-driven quantum advantage in the near and long term.
These days, research groups such as Google, Microsoft, and Rigetti are working towards fabricating quantum devices which have hundreds to thousands of qubits. In recently proposed quantum algorithms, i.e. hybrid quantum-classical algorithms, such quantum devices are used as subroutines for calculation of classically intractable tasks. However, the applicability of hybrid algorithms was quite limited, for example, the search of the ground state, and simulation of the dynamics of quan- tum systems. In addition, near-term quantum devices are expected to be quite noisy, impairing the precision of computation seriously and removing any potential advantages with quantum computers. Therefore, it is necessary to extend the applicability of hybrid algorithms and mitigate errors on quantum computers. In this thesis, we describe the generalisation of hybrid algorithms so that they can be applied to variety of problems, such as search of the spectrum of quantum systems, simulation of open quantum systems and even general mathematical tasks. The algorithm for finding spectra is useful for applications such as new drug discovery, design of batteries. Generally speaking, quantum systems of interest to physicists, chemists, and materials scientists inevitably interact with their environments, and quantum states are decohered. Therefore, to investigate quantum phenomena, new algorithms simulating open quantum systems are described in this thesis. Algorithms for general mathematical tasks such as matrix multiplication to a vector and solving linear equations, useful for a large number of problems, such as machine learning, are also presented. Furthermore, in order to make hybrid algorithms useful, we also invented a practical error mitigation method for suppressing physical errors, which may make hybrid algorithms useful. We showed that errors can be suppressed for a quantum system with over 50 qubits for the current achievable error rate, which is believed to be hard to simulate with classical computers. Also, we generalised the error mitigation technique to be applied to mitigate algorithmic errors, which may enhance the accuracy of Hamiltonian simulation.
Many important physical and mathematical problems are difficult to solve on classical computers, resulting in difficulty in finding new advanced materials, simulating quantum field theories and solving large combinatorial optimisation tasks. Quantum computers have shown great promise in being able to solve these (and many other) problems faster than their classical counterparts, and therefore should be thoroughly investigated as a significant tool for enabling the acceleration of scientific progress. This work develops methods to tackle several problems across the spectrum of quantum algorithms, providing methods suitable for the near-term hardware, to the future where large fault-tolerant quantum computers exist. Therefore, the works in this thesis range from efficiently making use of limited quantum hardware to taking advantage of hardware benefits (e.g. excess qubits) as quantum computation advances. Covered topics include: an alternative paradigm for the optimisation of variational circuits and quantum neural networks; techniques for improving energy estimation of quantum states through the collection and processing of large amounts of randomised measurement data; the use of entanglement in guiding the automatic discovery of quantum circuits; investigating the role of symmetries in adiabatic state preparation of molecules and the large scale parallelisation of a common fault-tolerant subroutine, potentially producing large runtime speed-ups for the simulation of chemistry on quantum computers. Although there are many challenges remaining from both hardware and algorithms perspectives before the large-scale utility of quantum computers can be demonstrated, the contributions of this work make steps towards the efficient utilisation of quantum hardware that will be available in the coming years.
Fault-tolerant quantum computers, when realized, guarantee significant speedups for particular computational tasks. Quantum hardware in the near term, however, is limited to low hundreds of noisy qubits that are not error-corrected. To leverage such devices as well as accommodate rapid developments in both hardware and algorithms, variational quantum algorithms (VQAs) were introduced. These algorithms have the potential to be useful in areas such as chemistry, optimization, machine learning, among others. Despite this potential, the largest experiment to date has employed just twelve qubits to implement the Variational Quantum Eigensolver (VQE), a VQA for simulating ground state energies of fermionic systems. In this dissertation, we present several methods for extending and further developing VQAs to step closer towards realizing applications in which quantum computers can provide meaningful advantages over classical computers. In the first part, we present methods for analyzing and optimizing parameterized quantum circuits (PQCs), a core component in VQAs for approximating target quantum states, e.g. ground state wavefunctions in VQE. To compare among PQCs and guide their design and selection, we introduce a set of algorithm-independent descriptors that can be estimated from simulations. Using these descriptors, we rule out circuits with limited capabilities in expressive and entangling powers. Next, we present a strategy for optimizing PQCs with large parameter counts and high redundancy by removing circuit operations that are less important for optimizing the algorithm objective, effectively reducing the search space. We demonstrate that this method enables larger VQE simulations by converging previously difficult optimizations while additionally reducing circuit resources. In the second part, we present methods for developing VQAs that are related to the quantum hardware. We introduce a new algorithm for simulating components of a quantum processor using an existing quantum computer. The goal of this application is to leverage near-term devices and algorithms to aid in the design of more powerful next-generation quantum hardware. Lastly, we present a guide for algorithm prototyping by deploying instances of VQAs on quantum computers via the cloud. We demonstrate instances of two algorithms, the quantum autoencoder and classifier, on an eight-qubit device. While further advancements in hardware and algorithms lie ahead, our work, along with developments from previous studies, represents significant progress towards realizing practical quantum advantage.
In the convergence of quantum computing and life science, we explore protein structure prediction and design on near-term intermediate-scale quantum devices. We investigate the algorithmic and resource constraints of today’s quantum computers, aiming to assess their potential in solving biologically relevant problems. We describe key variational quantum algorithms, including the problem-informed Quantum Approximate Optimization Algorithm and the problem-agnostic Hardware-Efficient Ansatz. Additionally, quantum walks are examined. The computationally complex coarse-grained lattice models in protein structure prediction and design are discussed. Quantum algorithms are then applied to these models to address the utility and limitations of today’s quantum computers. The thesis critically evaluates the limitations of quantum methods in comparison to classical approaches, highlighting the trade-offs between resource requirements in today’s quantum devices and the performance of quantum algorithms. Through this interdisciplinary investigation, the work contributes to understanding how quantum algorithms may advance computational biology in today’s quantum computing landscape.
This dissertation addresses fundamental challenges in solving constrained combinatorial optimization problems using hybrid quantum-classical computing approaches. Quantum computing shows promise for tackling computationally intractable problems, current approaches face significant limitations. The path forward in computing involves combining quantum and classical computing approaches. Quantum processing units (QPUs) will play a key role in accelerating algorithms in optimization, simulation, and machine learning applications beyond what classical computers can achieve on their own, similar to how graphical processing units (GPUs) have become integral to general-purpose computing. The current generation of quantum devices is limited by noise and circuit depth constraints, making it challenging to gain practical utility. Hybrid quantum-classical approaches, which combine quantum computing resources with classical computing resources, are essential for addressing these limitations on near-term devices. In the area of combinatorial optimization, current practical state-of-the-art hybrid approaches are variational in nature, relying on parameterized quantum circuits to encode solutions and classical optimization techniques to find optimal parameters. While the ultimate goal of solving computationally intractable problems is to find provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). QAOA alternates between two operators: a problem-specific cost Hamiltonian that encodes the optimization objective, and a mixer Hamiltonian that explores the solution space. The algorithm's parameters are iteratively optimized using classical methods to maximize the probability of sampling high-quality solutions. However, these methods often struggle with solution feasibility, especially for problems where the solutions must satisfy specific constraints. Penalty-based encodings require careful parameter tuning and risk producing infeasible solutions, while feasibility-preserving methods demand deeper quantum circuits that are challenging to implement on near-term quantum devices. In this dissertation, we present novel strategies that reduce or omit dependency on penalty parameters while maintaining solution quality, effectively capturing both optimal and near-optimal solutions, and balancing the trade-offs between circuit depth and solution feasibility. We present SCOOP, a novel QAOA-based framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins. QAOA operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the effectiveness of the SCOOP framework on selected NP-hard problems, some of which can be encoded quadratically (such as Minimum Vertex Cover and Maximum Independent Set), and some that can be encoded using higher-order terms (such as Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover). We also apply our framework to constrained combinatorial optimization problems that can be solved in polynomial time, such as Minimum Edge Cover and Maximum Matching. Experimental results on full statevector simulators and tensor network simulators show that SCOOP significantly improves the probability of finding high-quality feasible solutions across various problem classes, on problems that can be encoded quadratically as well as problems that can be encoded using higher-order terms. We also demonstrate the effectiveness of SCOOP on real quantum hardware, specifically IBM Quantum Heron R2 processors with 156 qubits, showing that SCOOP can be applied to practical problems with current quantum hardware limitations. This work makes significant contributions toward achieving quantum utility by enabling systematic investigation of constrained optimization problems on quantum devices. While current quantum computing research primarily focuses on unconstrained problems like MaxCut, real-world applications typically involve constraints. SCOOP provides a scalable framework for encoding constrained problems, extending quantum computing's practical utility beyond simple unconstrained cases. By eliminating dependency on penalty parameters and providing natural problem formulations, SCOOP makes it feasible to explore quantum solutions for constrained problems where classical exact methods become intractable. This capability is crucial for identifying promising avenues for demonstrating quantum utility across diverse constrained optimization problems, advancing the practical applicability of quantum computing approaches.