  Quantum computers promise to revolutionize our ability to simulate molecules,
and cloud-based hardware is becoming increasingly accessible to a wide body of
researchers. Algorithms such as Quantum Phase Estimation and the Variational
Quantum Eigensolver are being actively developed and demonstrated in small
systems. However, extremely limited qubit count and low fidelity seriously
limit useful applications, especially in the crystalline phase, where compact
orbital bases are difficult to develop. To address this difficulty, we present
a hybrid quantum-classical algorithm to solve the band structure of any
periodic system described by an adequate tight-binding model. We showcase our
algorithm by computing the band structure of a simple-cubic crystal with one
$s$ and three $p$ orbitals per site (a simple model for Polonium) using
simulators with increasingly realistic levels of noise and culminating with
calculations on IBM quantum computers. Our results show that the algorithm is
reliable in a low-noise device, functional with low precision on present-day
noisy quantum computers, and displays a complexity that scales as $\Omega(M^3)$
with the number $M$ of tight-binding orbitals per unit-cell, similarly to its
classical counterparts. Our simulations offer a new insight into the
``quantum'' mindset and demonstrate how the algorithms under active development
today can be optimized in special cases, such as band structure calculations.
