  Recent advances in qubit fidelity and hardware availability have driven
efforts to simulate molecular systems of increasing complexity in a quantum
computer and motivated us to to design quantum algorithms for solving the
electronic structure of periodic crystalline solids. To this effect, we present
a hybrid quantum-classical algorithm based on Variational Quantum Deflation
[Higgott et al., Quantum, 2019, 3, 156] and Quantum Phase Estimation
[Dob\v{s}\'i\v{c}ek et al., Phys. Rev. A, 2007, 76, 030306(R)] 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 applied to solid state systems and suggest
avenues to explore the potential of quantum computing in materials science.
