While reading the chapter on Quantum Computation (starting on page 401) of the draft version of the Arora & Barak book I came across exercise §4 on page 431 that reads as:

Suppose that $f$ is computed in $T$ time by a quantum algorithm that uses a partial measurement in the middle of the computation, and then proceeds differently according to the result of the measurement. Show that $f$ is computable by $\mathcal{O}(T)$ elementary operations.

(This exercise is implicitely used on page 416.)

So far I think I understand the required definitions, but unfortunately I do not see how to solve this exercise. Could you please give me a hint?

  • 4
    $\begingroup$ Welcome to QCSE. Can you review the principle of deferred measurement? $\endgroup$ Jan 7, 2022 at 16:14
  • 2
    $\begingroup$ Check out the two examples in my answer to this question that demonstrate deferred measurement in two important cases (measurement result used to control a quantum gate and an intermediate measurement sandwiched between two gates). $\endgroup$ Jan 7, 2022 at 18:08


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.