  Ensuring adequate wireless coverage in upcoming communication technologies
such as 6G is expected to be challenging. This is because user demands of
higher datarate require an increase in carrier frequencies, which in turn
reduce the diffraction effects (and hence coverage) in complex multipath
environments. Intelligent reflecting surfaces have been proposed as a way of
restoring coverage by adaptively reflecting incoming electromagnetic waves in
desired directions. This is accomplished by judiciously adding extra phases at
different points on the surface. In practice, these extra phases are only
available in discrete quantities due to hardware constraints. Computing these
extra phases is computationally challenging when they can only be picked from a
discrete distribution, and existing approaches for solving this problem were
either heuristic or based on evolutionary algorithms. We solve this problem by
proposing fast algorithms with provably optimal solutions. Our algorithms have
linear complexity, and are presented with rigorous proofs for their optimality.
We show that the proposed algorithms exhibit better performance. We analyze
situations when unwanted grating lobes arise in the radiation pattern, and
discuss mitigation strategies, such as the use of triangular lattices and
prephasing techniques, to eliminate them. We also demonstrate how our
algorithms can leverage these techniques to deliver optimum beamforming
solutions.
