  The coined quantum walk is a discretization of the Dirac equation of
relativistic quantum mechanics, and it is the basis of many quantum algorithms.
We investigate how it searches the complete bipartite graph of $N$ vertices for
one of $k$ marked vertices with different initial states. We prove intriguing
dependence on the number of marked and unmarked vertices in each partite set.
For example, when the graph is irregular and the initial state is the typical
uniform superposition over the vertices, then the success probability can vary
greatly from one timestep to the next, even alternating between 0 and 1, so the
precise time at which measurement occurs is crucial. When the initial state is
a uniform superposition over the edges, however, the success probability
evolves smoothly. As another example, if the complete bipartite graph is
regular, then the two initial states are equivalent. Then if two marked
vertices are in the same partite set, the success probability reaches 1/2, but
if they are in different partite sets, it instead reaches $1$. This differs
from the complete graph, which is the quantum walk formulation of Grover's
algorithm, where the success probability with two marked vertices is 8/9. This
reveals a contrast to the continuous-time quantum walk, whose evolution is
governed by Schr\"odinger's equation, which asymptotically searches the regular
complete bipartite graph with any arrangement of marked vertices in the same
manner as the complete graph.
