Over the past half century, the advent of the computer has increased our ability to perform computations tremendously. Consequently, we can now solve computational problems much more efficiently than ever before, the effects of which have revolutionized many aspects of society, ranging from how government keeps track of tax records, to how we use routing software to navigate to our destination. However, over the last decade it has become increasingly apparent that the development of conventional computational hardware is reaching its physical limits. In an attempt to overcome this barrier, new research areas have focused on rethinking the very physical principles based on which we perform computations. Quantum computing has emerged among the most promising of these new areas, and as such has experienced an explosive increase of interest over the past twenty years. Quantum computing loosely speaking encapsulates the idea of performing computations based on the principles of quantum mechanics, and as such describes a computational model that is fundamentally different from its conventional counterpart. The central question we address in this thesis is how powerful this new computational model is, i.e., we take computational problems and assess how efficiently they can be solved on a quantum computer. Oftentimes, we compare the obtained results to those in the conventional setting, to quantify the computational advantage that quantum computers provide us with on a theoretical level.