0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – XXDD May 31 '17 at 12:37
0
$\begingroup$

The deferred measurement principle guarantees that you can delay measurements until the end of a circuit without changing the expected results (though you may have to add a qubit to hold each deferred measurement result).

Deferred measurement principle

Classical control is equivalent to quantum control. As far as designing quantum circuits is concerned, measurement is just a space optimization.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.