Effectiveness of Quantum Algorithms: From Compilation to Measurement

Quantum computing opens up new ways of designing algorithms, thanks to the peculiar properties of quantum mechanics, such as superposition and entanglement. The exploration of this new paradigm faces new challenges in terms of what advantages quantum computing can offer over classical computing. This thesis approaches quantum computing with the aim of proposing new quantum algorithms while investigating their effectiveness. Specifically, our journey begins with an in-depth study of the Quantum k-Nearest Neighbors (QkNN) algorithm by showing its performance with respect to its classical version. The analysis sheds light on the cost of preparing a non-trivial quantum state. Indeed, due to the memory-intensive nature of QkNN and the fact that quantum memories are still under development, the re-preparation of a quantum state encoding a data set is a non-negligible cost, which is an obstacle to the practicality of quantum algorithms that require a significant amount of data as input to achieve good performance. Therefore, we show how forking techniques can partially address this problem by allowing the reuse of the same initial quantum state between different tasks. In this context, we propose logarithmic quantum forking and discuss its effectiveness over QkNN in detail. We then turn to the challenge of identifying classical building blocks common to a variety of domains that can be translated into quantum subroutines that are more efficient than their classical counterparts. As one of these building blocks, we target variance computation and thus propose a quantum subroutine computing variance (QVAR) that exhibits logarithmic properties in both the width and depth of the quantum circuit. Moreover, we showcase two hybrid quantum algorithms employing QVAR for the tasks of Feature Selection and Outlier Detection. Finally, we turn our attention to more hardware-related problems regarding the compilation of quantum gates that are robust to noise sources. We propose a quantum reservoir-inspired architecture based on variational quantum circuits, the ultimate goal of which is to learn quantum gates that are robust to noise.