Необходимо реализовать такую фичу: пользователь вводит запрос (допустим фамилию), и пока он его вводит выдаются возможные варианты.
Аля поиск в яндексе или гугле.

Варианты должны подхватываться на лету из базы.
Есть ли встроенные средства облегчающие реализацию?
И если нет, как бы это грамотно реализовать с точки зрения работы с БД(не перегружать запросами)?

есть и средства и готовые примеры (%QTDIR%\examples\tools\completer и %QTDIR%\examples\tools\customcompleter)

вот с этим прийдётся самостоятельно заниматся, тем более что

Во-первых, какая СУБД?

Есть смысл заранее выбрать возможные варианты из таблиц, а затем использовать QCompleter.
Актуальность выборки можно поддерживать на основе триггеров СУБД, реагирующих на изменение данных в выбранных столбцах, либо перечитывая варианты при общем обновлении данных по команде пользователя.
Если всё же необходимо обращаться к СУБД каждый раз, нужно создать индексы по столбцам, данные из которых представляют выборку - по одному индексу на каждых столбец.

СУБД MySQL. QCompleter само собой, даже не обсуждается)
Насчет триггеров почитаю, спасибо.

почему?

Он отвечает требованиям "выпадающего списка с вариантами выбора"

это что за требования такие?

Это университетские лабы ^^