Combinatorial optimisation is a main topic for real-world applications, where fast solutions are required. Optimisation algorithms are incredibly powerful, but still face bottlenecks for certain problems. In recent years, quantum algorithms have been proposed as a potential candidate for solving such problems. The question that naturally arises is whether they could provide meaningful speed-ups over classical approaches. The study of asymptotic complexity has become central in the development of quantum algorithms. Nevertheless, having a promising asymptotic improvement does not directly translate into good practical performance. This is already well known for classical algorithms, which can be executed and evaluated directly. When it comes to quantum algorithms, the situation is more nuanced, as solving practically relevant instances would require a fully fault-tolerant quantum computer. In this thesis, we address the challenge of assessing the practical performance of a quantum algorithm without access to quantum hardware. Our strategy is to evaluate how these algorithms would perform under idealised fault-tolerant assumptions and to identify parameter regimes in which quantum approaches could potentially become useful. Our goal is to guide algorithmic development long before implementation becomes possible. We first give a general overview of the quantum (sub)routines that serve as building blocks for more advanced algorithms, as well as of the three hybrid benchmarking techniques used throughout this thesis. Then, we elaborate on each method: we start with the algorithmic descriptions, proceed to the methodology, and conclude with their hybrid evaluation on practically relevant datasets. Within the hybrid benchmarking method 1 (gate count analysis), we analytically derive the minimum number of gates that a quantum version of the classical simplex algorithm would require to solve realistic instances. By executing classical counterparts of the quantum subroutines, we infer the execution speed required per gate for the quantum simplex to outperform its classical counterpart. Within the hybrid benchmarking method 2 (query count analysis), we benchmark functional quantum linear solvers by analytically deriving a precise number of query calls made to the same oracles as a function of problem parameters. This provides insight into which algorithm might be more suitable in a given parameter regime. It allows for a direct comparison only between different quantum algorithms and is independent of classical runtime measurements. Within the hybrid benchmarking method 3 (cycle count analysis), we develop a runtime estimation framework tailored to the quantum tree generator–based search for solving 0-1-knapsack problems. We evaluate its performance on large scale instances beyond the reach of general simulation. We compare it with state-of-the-art classical linear programming solvers in terms of processor cycle counts. Hybrid benchmarking provides a fair, systematic benchmarking methodology, ensuring reproducible and relevant comparisons not only between classical and quantum approaches, but also among different quantum algorithms.
Combinatorial optimisation is a main topic for real-world applications, where fast solutions are required. Optimisation algorithms are incredibly powerful, but still face bottlenecks for certain problems. In recent years, quantum algorithms have been proposed as a potential candidate for solving such problems. The question that naturally arises is whether they could provide meaningful speed-ups over classical approaches. The study of asymptotic complexity has become central in the development of quantum algorithms. Nevertheless, having a promising asymptotic improvement does not directly translate into good practical performance. This is already well known for classical algorithms, which can be executed and evaluated directly. When it comes to quantum algorithms, the situation is more nuanced, as solving practically relevant instances would require a fully fault-tolerant quantum computer. In this thesis, we address the challenge of assessing the practical performance of a quantum algorithm without access to quantum hardware. Our strategy is to evaluate how these algorithms would perform under idealised fault-tolerant assumptions and to identify parameter regimes in which quantum approaches could potentially become useful. Our goal is to guide algorithmic development long before implementation becomes possible. We first give a general overview of the quantum (sub)routines that serve as building blocks for more advanced algorithms, as well as of the three hybrid benchmarking techniques used throughout this thesis. Then, we elaborate on each method: we start with the algorithmic descriptions, proceed to the methodology, and conclude with their hybrid evaluation on practically relevant datasets. Within the hybrid benchmarking method 1 (gate count analysis), we analytically derive the minimum number of gates that a quantum version of the classical simplex algorithm would require to solve realistic instances. By executing classical counterparts of the quantum subroutines, we infer the execution speed required per gate for the quantum simplex to outperform its classical counterpart. Within the hybrid benchmarking method 2 (query count analysis), we benchmark functional quantum linear solvers by analytically deriving a precise number of query calls made to the same oracles as a function of problem parameters. This provides insight into which algorithm might be more suitable in a given parameter regime. It allows for a direct comparison only between different quantum algorithms and is independent of classical runtime measurements. Within the hybrid benchmarking method 3 (cycle count analysis), we develop a runtime estimation framework tailored to the quantum tree generator–based search for solving 0-1-knapsack problems. We evaluate its performance on large scale instances beyond the reach of general simulation. We compare it with state-of-the-art classical linear programming solvers in terms of processor cycle counts. Hybrid benchmarking provides a fair, systematic benchmarking methodology, ensuring reproducible and relevant comparisons not only between classical and quantum approaches, but also among different quantum algorithms.
In recent years, strong expectations have been raised for the possible power of quantum computing for solving difficult optimization problems, based on theoretical, asymptotic worst-case bounds. Can we expect this to have consequences for Linear and Integer Programming when solving instances of practically relevant size, a fundamental goal of Mathematical Programming, Operations Research and Algorithm Engineering? Answering this question faces a crucial impediment: The lack of sufficiently large quantum platforms prevents performing real-world tests for comparison with classical methods. In this paper, we present a quantum analog for classical runtime analysis when solving real-world instances of important optimization problems. To this end, we measure the expected practical performance of quantum computers by analyzing the expected gate complexity of a quantum algorithm. The lack of practical quantum platforms for experimental comparison is addressed by hybrid benchmarking, in which the algorithm is performed on a classical system, logging the expected cost of the various subroutines that are employed by the quantum versions. In particular, we provide an analysis of quantum methods for Linear Programming, for which recent work has provided asymptotic speedup through quantum subroutines for the Simplex method. We show that a practical quantum advantage for realistic problem sizes would require quantum gate operation times that are considerably below current physical limitations.
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.
Quantum algorithms are often represented in terms of quantum circuits operating on ideal (logical) qubits. However, the practical implementation of these algorithms poses significant challenges. Many quantum algorithms require a substantial number of logical qubits, and the inherent susceptibility to errors of quantum computers require quantum error correction. The integration of error correction introduces overhead in terms of both space (physical qubits required) and runtime (how long the algorithm needs to be run for). This paper addresses the complexity of comparing classical and quantum algorithms, primarily stemming from the additional quantum error correction overhead. We propose a comprehensive framework that facilitates a direct and meaningful comparison between classical and quantum algorithms. By acknowledging and addressing the challenges introduced by quantum error correction, our framework aims to provide a clearer understanding of the comparative performance of classical and quantum computing approaches. This work contributes to understanding the practical viability and potential advantages of quantum algorithms in real-world applications. We apply our framework to quantum cryptanalysis, since it is well known that quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. This analysis provides state-of-the art snap-shot estimates of the realistic costs of implementing quantum attacks on these important cryptographic algorithms, assuming quantum fault-tolerance is achieved using surface code methods, and spanning a range of potential error rates. These estimates serve as a guide for gauging the realistic impact of these algorithms and for benchmarking the impact of future advances in quantum algorithms, circuit synthesis and optimization, fault-tolerance methods and physical error rates.
Combinatorial Optimization problems play an important role in various domains such as logis- tics, life science or the financial sector. As their complexity in general grows exponentially with their problem size, finding the optimal solution classically becomes infeasible very fast. This raises the central question of whether quantum computers are in principle suitable for solving combinatorial optimization problems better and faster than classical computers. In order to find answers to that question, one needs to study quantum algorithms designed for those problems under ideal conditions (i.e., simulations, which are however limited due to exponential scaling) to investigate their potential, but one also needs real quantum hardware to test its viability and evaluate whether practical advantages are reasonable. In this regard, we consider variational quantum algorithms, especially the Quantum Approximate Optimization Algorithm (QAOA) consisting of a problem and a mixer Hamiltonian with freely selectable parameters, originally proposed as variational hybrid ansatz with classical optimization. This algorithm structure of- fers flexible and relatively shallow circuits, which makes it suitable for current NISQ hardware. However, optimizing the variational circuit parameters can be an NP-hard problem at worst. In this thesis, we study different versions of QAOA, especially with a focus on limitations, perfor- mance and potential advantages opposite classical methods. The first part of the thesis concerns the investigation of various aspects regarding the imple- mentation of the variational QAOA protocol such as: the incorporation of a problem constraint either by adding a suitable penalty term of by choosing a suitable mixer (that restricts the search space), the scaling of the problem Hamiltonian in comparison to the mixer Hamiltonian, the choice of the initial values for the classical optimization of the circuit parameters, and finally the choice of the function to be minimized (i.e., CVaR vs. expectation value). We apply this proto- col to both the portfolio optimization and the feature selection and evaluate the performance. In order to improve QAOA, we consider the warm-start QAOA for different problem instances and analyze its improved performance with regard to involved quantum effects. For this purpose, we propose a classical pre-processing method and demonstrate that the warm-start results can be reproduced or even exceeded by this method. The second part addresses the issue that the standard variational form requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which is a major limitationforachievingpotentialscalingadvantagescomparedtoclassicalmethods. Toovercome this limitation, we investigate and further develop fixed schedules for QAOA, which only rely on two free parameters. We start with introducing the continuous adiabatic theorem as it motivates the form of QAOA and show its limitations, which we address by applying a discrete version of the theorem. With our findings, a new version of QAOA based on linear-ramps (LR-QAOA) is introduced and further developed. In order to derive suitable parameter values for this schedule, we propose a method based on extrapolation from smaller towards larger problem sizes. With our results obtained on a noiseless emulator, we evaluate the quantum runtime scaling and discuss whether a scaling advantage can be achieved compared to classical methods.
Solving systems of linear equations is a key subroutine in many quantum algorithms. In the last 15 years, many quantum linear solvers (QLS) have been developed, competing to achieve the best asymptotic worst-case complexity. Most QLS assume fault-tolerant quantum computers, so they cannot yet be benchmarked on real hardware. Because an algorithm with better asymptotic scaling can underperform on instances of practical interest, the question of which of these algorithms is the most promising remains open. In this work, we implement a method to partially address this question. We consider four well-known QLS algorithms which directly implement an approximate matrix inversion function: the Harrow-Hassidim-Lloyd algorithm, two algorithms utilizing a linear combination of unitaries, and one utilizing the quantum singular value transformation (QSVT). These methods, known as functional QLS, share nearly identical assumptions about the problem setup and oracle access. Their computational cost is dominated by query calls to a matrix oracle encoding the problem one wants to solve. We provide formulas to count the number of queries needed to solve specific problem instances; these can be used to benchmark the algorithms on real-life instances, under benevolent, idealized assumptions, without requiring access to quantum hardware to implement the procedure. We select three data sets: random generated instances that obey the assumptions of functional QLS, linear systems from simplex iterations on MIPLIB, and Poisson equations. Our methods can be easily extended to other data sets and provide a high-level guide to evaluate the performance of a QLS algorithm. In particular, our work shows that HHL underperforms in comparison to the other methods across all data sets, often by orders of magnitude, while the Chebyshev-approximation based methods typically have the best performance.
Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate that a state-of-the-art quantum solver has higher accuracy (~0.013%) and a significantly faster problem-solving time (~6561×) than the best classical solver. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.