We present a new quantum communication complexity protocol, the promise-quantum random access code, which allows us to introduce a new measure of unbiasedness for bases of Hilbert spaces. The proposed measure possesses a clear operational meaning and can be used to investigate whether a specific number of mutually unbiased bases exist in a given dimension by employing semidefinite programming techniques.