# Assumptions in the proofs for the optimality of Grover's Search Algorithm

I was trying to understand this paper in which it is proved that Grover's search algorithm is optimal.

On page 4, beginning of section 2 of the paper the author says the following

In the proof I assume a quantum computation consisting only of unitary transformations (plus the final measurement) without measurements during the computation.

And then,

This can be done without loss of generality: Clearly a measurement of a qubit whose outcome will not be used to make decisions on what further unitary transformations should be applied, can be delayed to the end.

My doubt is regarding the following arguments made by the author:

For a practical QC it seems likely that what further unitary transformations will be applied will depend on outcomes of intermediary measurements, like e.g. in error correction. Thus we will probably have a “hybrid” quantum-classical computer, where the classical part reads measurement outcomes and depending on that, controls the exterior fields that induce unitary transforms on the qubits.
The point now is that in principle the classical part can simply be replaced by quantum hardware which does the same.

I did not quite understand the author's argument that the classical part can be replaced by quantum hardware. Quantum measurements are non unitary processes. So, if the assumption in the proof is that the quantum computation consists only unitary transformations except for the measurement in the end then, does quantum algorithms with arbitrary number of measurements come under this assumption?

• For the optimality of Grover's search algorithm, it's better to prove it in a geometrical way so that the algorithm gives a geodesic to connect the initial and final state. – XXDD May 31 '17 at 12:37