The discovery of quantum mechanics in the early 20th century by physicists such as Max Planck, Albert Einstein, Niels Bohr, Werner Heisenberg, and Erwin Schrödinger revolutionized physics. In turn, quantum computers, i.e., computers that exploit quantum mechanical effects, are expected to revolutionize computing by solving problems that are intractable for today’s computers. The idea of exploiting quantum physics for computing dates back to 1980 when Paul Benioff suggested building a computer based on quantum mechanical principles [10]. Shortly thereafter, Richard Feynman proposed using such a quantum computer to efficiently simulate quantum systems, a task that is exponentially hard for classical computers [37]. One decade later, in 1992, David Deutsch and Richard Jozsa presented one of the first quantum algorithms that could solve a problem exponentially faster than a classical computer [29]. However, since the Deutsch-Jozsa algorithm solves an artificial problem only, it did not raise much interest in actually building a quantum computer.