Матрица регистра до и после очистки рабочих битов

Пусть $f:\{1,\ldots,N\}\to\{0,1\}$. Алгоритм готовит равномерную суперпозицию входов, вычисляет $f$ и обратным ходом очищает рабочие биты. Получаются три состояния

$$\frac1{\sqrt N}\sum_x |x\rangle\ \longmapsto\ \frac1{\sqrt N}\sum_x |x\rangle|g_x\rangle|f(x)\rangle\ \longmapsto\ \frac1{\sqrt N}\sum_x|x\rangle|f(x)\rangle.$$

Опишите отдельно матрицу плотности регистра $|x\rangle$ на каждом шаге. Можно считать отображение $x\mapsto g_x$ взаимно однозначным. Для определённости можно взять $f(x)=1$ при $x\ge N/2$ и 0 в остальных случаях.