$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\mathbf{Exercise\ 7.1}$
In the standard circuit model of section 5.6, the computation takes place by applying quantum gates. Only at the end are measurements performed. Imagine a computation that proceeds instead as follows. Gates $G_{0}, G_{1}, \dots, G_{n}$ are applied, then qubit $i$ is measured in the standard basis and never used again. If the result of the measurement is $0$, the gates $G_{01}, G_{02}, \dots, G_{0k}$ are applied. If the result is $1$, then gates $G_{11}, G_{12}, \dots, G_{1l}$ are applied. Find a single quantum circuit in the standard circuit model, with only measurement at the very end, that carries out this computation.
It is a little puzzeling what to make of this exercise, here is one take.
Assume we have an $(n+1)$-qubit register $q_{n}, \ldots, q_0$. Without loss of generality we can take the top qubit $q_n$ in the circuit diagram to be the one being measured and also to be the most significant bit.
In the normal ordering of the standard basis, the first half of the basis elements have 0 as MSB (to the left):
(1)and the second half have 1 as MSB:
(2)Let
(3)be the application of the first gate sequence to the $n$ lowest qubits $q_{n-1}, \ldots, q_0$, and let similarly,
(4)be the composition of the second gate sequence. These transformations are $2^{n-1} \times 2^{n-1}$ unitary matrices.
(5)Now we form the $2^n \times 2^n$ unitary matrix
If we apply this to $\frac1{\sqrt2}(\ket0 + \ket1)\otimes q_{n-1}\otimes \ldots \otimes q_0$ and measure $q_n$, then the effect will be that the superposition of $G_0, G_1$ collapses and $G_0$ is applied if 0 was measured and $G_1$ is applied if 1 was measured, and $q_n$ is left as it is.
Hence, the circuit can be given as:
But is this physically realizable?
Another take:
Apply the Walsh transform $W$ to the register $q_{n}, \ldots, q_0$ in the initial state $\ket{0\ldots00}$ to obtain a maximally entangled linear combination of the $2^{n+1}$ basis elements.
Then apply the given gate sequence $G_0, G_1, \ldots \,.$
Measuring $q_n = \ket0$ amounts to projecting the state onto the subspace
(1)(all terms with $q_n = \ket1$ vanish) and the first gate that correponds to the zero transformation on this subspace, will terminate the given gate sequence.
Hence, there is a subsequence of gates $G_{01}, G_{02}, \ldots$ providing the effective action.
Similarly, if $q_n = \ket1$ is measured, then there is an effective gate sequence $G_{11}, G_{12}, \ldots$ providing the resulting transformation.
Any measurement of a single qubit leads to a subspace decompostion into the direct sum:
(2)where
(3)