Publications
Explore my projects to learn more about what I do. My publications can be found on Google Scholar:
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.
Here we present two novel contributions for achieving quantum advantage in solving difficult optimisation problems, both in theory and foreseeable practice. (1) We introduce the “Quantum Tree Generator”, an approach to generate in superposition all feasible solutions of a given instance, yielding together with amplitude amplification the optimal solutions for 0-1-Knapsack problems. The QTG offers exponential memory savings and enables competitive runtimes compared to the state-of-the-art Knapsack solver COMBO for instances involving as few as 600 variables. (2) By introducing a high-level simulation strategy that exploits logging data from COMBO, we can predict the runtime of our method way beyond the range of existing quantum platforms and simulators, for various benchmark instances with up to 1600 variables. Combining both of these innovations, we demonstrate the QTG’s potential advantage for large-scale problems, indicating an effective approach for combinatorial optimisation problems.
State preparation is a fundamental routine in quantum computation, for which many algorithms have been proposed. Among them, perhaps the simplest one is the Grover-Rudolph algorithm. In this paper, we analyse the performance of this algorithm when the state to prepare is sparse. We show that the gate complexity is linear in the number of non-zero amplitudes in the state and quadratic in the number of qubits. We then introduce a simple modification of the algorithm, which makes the dependence on the number of qubits also linear. This is competitive with the best known algorithms for sparse state preparation.