We analyze three different quantum search algorithms, namely, the traditional circuit-based Grover's algorithm, its continuous-time analog by Hamiltonian evolution, and the quantum search by local adiabatic evolution. We show that these algorithms are closely related in the sense that they all perform a rotation, at a constant angular velocity, from a uniform superposition of all states to the solution state. This makes it possible to implement the two Hamiltonian-evolution algorithms on a conventional quantum circuit, while keeping the quadratic speedup of Grover's original algorithm. It also clarifies the link between the adiabatic search algorithm and Grover's algorithm.
In this paper, we initiate the study of quantum algorithms in the Graph Drawing research area. We focus on two foundational drawing standards: 2-level drawings and book layouts. Concerning
2-level drawings, we consider the problems of obtaining drawings with the minimum number of crossings,
k-planar drawings, quasi-planar drawings, and the problem of removing the minimum number of edges to obtain a
2-level planar graph. Concerning book layouts, we consider the problems of obtaining
1-page book layouts with the minimum number of crossings, book embeddings with the minimum number of pages, and the problem of removing the minimum number of edges to obtain an outerplanar graph. We explore both the quantum circuit and the quantum annealing models of computation. In the quantum circuit model, we provide an algorithmic framework based on Grover's quantum search, which allows us to obtain, ignoring polynomial terms, a quadratic speedup on the best known classical exact algorithms for all the considered problems. In the quantum annealing model, we perform experiments on the quantum processing unit provided by D-Wave, focusing on the classical
2-level crossing minimization problem, demonstrating that quantum annealing is competitive with respect to classical algorithms.