Złożoność informacji jest bardzo przydatnym narzędziem w złożoności komunikacji, stosowanym głównie w celu ograniczenia złożoności komunikacyjnej rozproszonych problemów.
Czy istnieje analogia złożoności informacji dla złożoności zapytań? Istnieje wiele podobieństw między złożonością zapytań a złożonością komunikacji; często (ale nie zawsze!) dolna granica w jednym modelu zostaje przetłumaczona na dolną granicę w drugim modelu. Czasami to tłumaczenie jest dość nietrywialne.
Czy istnieje pojęcie złożoności informacji, która jest przydatna w przypadku niższych granic złożoności problemów związanych z zapytaniami?
Pierwsze przejście wydaje się wskazywać, że złożoność informacji nie jest zbyt użyteczna; na przykład złożoność zapytania przy obliczaniu OR z bitów wynosi Ω ( N ) dla algorytmów losowych i Ω ( √przypadku algorytmów kwantowych, podczas gdy najprostsza adaptacja pojęcia złożoności informacji wskazuje, że informacja wyuczona przez dowolny algorytm kwerendy ma co najwyżejO(logN)(ponieważ algorytm zatrzymuje się, gdy zobaczy pierwszą1na wejściu).