Теория сложности в основном связана с ограничениями, связанными с вычислением функций: какие функции могут быть вычислены, как быстро и с использованием какого объема памяти. С квантовыми компьютерами, как и с классическими вероятностными компьютерами следует вопрос «и с какой вероятностью?». Мы уже знаем, что минимальное время вычисления может быть для $\mathcal{Q}$ меньше, чем для $\mathcal{T}$. Теория сложности для $\mathcal{Q}$ позволяет провести дальнейшее исследование.

Менее практичное, но потенциально более важное приложение теории сложности – в попытке понять спонтанный рост сложности в физических системах, например, эволюцию жизни и человеческого знания. Беннетт (1983) рассмотрел несколько различных мер сложности (или «глубина», или «знание»), которые были предложены ранее. Большая часть из них страдает от фатального недостатка, заключающегося в том, что они присваивают наивысшую «сложность» чисто случайному состоянию. Таким образом, они не отличают истинное знание от простого содержания информации. Беннетт решил эту проблему. Его «логическая глубина» есть, грубо говоря, время работы самой короткой $\mathcal{T}$-программы, которая вычисляет данное состояние $\Psi$, исходя из пустого входа. В биологической терминологии логическая глубина измеряет ту эволюцию, которая требуется, чтобы развить $\Psi$ из простейших возможных предшественников.

С первого взгляда, кажется, что конструкция Беннетта теряет свою физическую основу, когда распространяется за пределы строго детерминистской физики машин Тьюринга. В физической реальности большая часть случайных состояний порождается не «длинными программами» (т.е. предшественниками, сложность которых близка к их собственной сложности), а короткими программами, в сочетании с недетерминированным оборудованием.

Тем не менее, существует квантовый аналог идеи Беннетта, который решает эту проблему. Определим $Q$-логическую глубину квантового состояния как время выполнения самой короткой $\mathcal{Q}$-программы, которая порождает это состояние из пустого входа (или, возможно, как это делал Беннетт, среднее гармоническое время выполнения всех таких программ). Случайные числа могут быстро порождаться короткими $\mathcal{Q}$-программами.

Заметим, что $Q$-логическая глубина не наблюдаема даже в принципе, потому что она содержит информацию о всех мирах. Однако она имеет физический смысл: $Q$-логическая глубина – хорошая мера информации, так как она придает вес только сложности, которая присутствует во всех мирах и, следовательно, помещена туда «принудительно» глубоким процессом. Наблюдаемые сложные состояния, которые различны в различных мирах, являются не истинно глубокими, а всего лишь случайными. Поскольку $Q$-логическая глубина – свойство квантового состояния (вектора), не требуется, чтобы квантовая подсистема имела точно определенную $Q$-логическую глубину (хотя часто желательна хорошая степень аппроксимации). Это также следует ожидать,
поскольку информация в системе может содержаться целиком в корреляциях с другими системами. Наглядный пример этого – квантовая криптография.