It's often said that for any quantum circuit with intermediate measurements, there exists an equivalent circuit where all measurements are at the end of the circuit. Is anything ever argued about the complexity of the circuit with delayed measurements?

I'm imagining a circuit with $n$ qubits and $\mathrm{poly}(n)$ depth, where the first $n/2$ qubits are measured and depending on the out outcomes I apply one of the $2^{n/2}$ unitaries on the remaining qubits. If I was to naively delay measurements, I would add $2^{n/2}$ $C\mbox{-}U_i$ gates instead of measuring, but have now made the circuit $\exp(n)$ depth instead.

Is there a way to delay measurements to the end of the computation without changing the complexity of the circuit?

  • $\begingroup$ The easy incomplete answer is that the complexity is unchanged when there is no feedforward (the circuit does not depend on the outcomes of the intermediate measurements) $\endgroup$ Feb 11 at 18:17
  • $\begingroup$ @QuantumMechanic I suppose in that scenario, the measurements are already at the end of the computation. delaying measurements in teleportation doesn't seem to affect complexity but that's because each controlled gate is dependant only on one measurement outcome. Basing it off joint outcomes seems to make things a lot harder? $\endgroup$
    – Ethan
    Feb 13 at 12:25
  • $\begingroup$ Ethan I agree, I think your question is much richer in that scenario $\endgroup$ Feb 13 at 15:37


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.