If a quantum algorithm requires a measurement, how can we use that as a subroutine in another quantum algorithm?

Question

Some algorithms (like period finding), use one or more measurement step. The post measurement state is then acted upon by another set of gates to complete the algorithm. If I imagine this as blackbox algorithm $f$ which takes $x$ as input and computes $f(x)$; then one can write a corresponding quantum circuit and use it as a subroutine in another quantum algorithm (like Grover's).

Now if one wants to implement this in a circuit, doesn't the measurement operation hiding inside $f$ create an issue of a possibly exponential number of measurements (like in Grover where we construct the full superposition)? I read somewhere that a CPTP operation can be embedded in a larger space as a unitary, but I recall it as an existence result. But even if that larger circuit has a construction, can't complexity/size of that circuit be much bigger?

Answer 1

Welcome to QCSE. Often for theoretical reasons within the gate model, we appeal to the deferred measurement principle to say that we can wait to have all measurements at the end of the circuit. We just imagine moving to a larger and larger Hilbert space while we postpone our measurements.

For example, if a circuit proposes to measure a single-qubit register in-situ, and then perform various operations based on the results of the measurement (e.g. whether it's $|0\rangle$ or $|1\rangle$), we can always rewrite that circuit so that the measurement is done at the end. By doing this, our Hilbert space may be doubled in size.

Other models such as one-way quantum computation are a bit trickier to visualize, because there the measurements and post-measurement gates applied drive the calculation. But nonetheless the deferred measurement principle still applies.

Note that in-situ measurements and post-measurement actions are done during quantum error correction and I haven't thought too much about the deferred measurement principle in the context of QEC, but still we can always pray at the church of the higher Hilbert space.