Feature Request: a way to discard a qubit

[DyonvVr-zz]

In certain known quantum algorithms (e.g. Grover's algorithm), some qubits are discarded during execution. This is equivalent to tracing out a qubit when speaking in terms of density matrices.

Is there a way to do this in cirq? It would be beneficial since it would essentially more than halve the computation time if the Hilbert space could be reduced by one qubit.

[dabacon]

There isn't currently a way to discard a qubit. For simulation this could be useful. It is true that for a lot of "traditional" algorithms one computes a function and then throws away the register and that you can get good speedups for simulation by considering this (projectQ for example does a good job at this IIRC, in particular because they also allow direct classical computation in an efficient manner). I don't think we are as focused on this sort of optimization in the near term, and I worry a lot about adding this as a functionality that then has to be dealt with then the code gets sent to the actual hardware (though I guess it could just ignore it?)

[Strilanc]

Would having an explicit "discard" operation have any benefit over a simulator simply noticing the qubit was no longer used and discarding it automatically?

Note that discarding a qubit doesn't make unitary simulations faster, because discarding is a non-unitary operation. If you want ten thousand samples from a circuit that only has measurement at the end, it's significantly more efficient to keep all the qubits around and get a wavefunction from which you can repeatedly sample instead of discarding the qubit and needing to run the circuit ten thousand times.

Also note that in cases such as Grover's algorithm, the ancilla qubit is not actually necessary. Every controlled NOT onto the ancilla can simply be replaced with a Z gate on the control (and every Toffoli onto the ancilla with a CZ between the controls). This is not always true of ancillae (e.g. it's not true in Shor's algorithm), but it's pretty common. For whatever reason, people find it simpler to explain conditionally flipping a qubit in the |-> state instead of conditionally applying a -1 phase.

[DyonvVr-zz]

If the simulator indeed automatically discards unused qubits, and/or is optimised for unitary computation, then I agree there's no need to explicitly discard it.

Can I be sure though that the simulator really behaves this way? In my case, I use an ancilla at the beginning of my (4+1)-qubit circuit, but it's unused in the remainder of the circuit which may be really deep. Will the simulator notice this and continue computing 2^4x2^4 matrices instead of 2^5x2^5 ones?

[Strilanc]

The simulator doesn't behave that way currently.

I am slightly wary of adding features that any new simulators have to implement before they are available and also wary of features that don't correspond to a physical operation on the hardware. In general, I would avoid adding a feature to explicitly tell the simulator to go faster when the simulator could just go faster automatically. I would instead just make the simulator go faster automatically.

In other words, this should be a feature request for the simulator to detect "qubit no longer used and never measured" and optimize it away, when appropriate.

[DyonvVr-zz]

Yes, agreed.

In that case, I will leave the issue open as this particular feature request.

[gillverd]

Any update on this issue? Being able to measure a qubit, perform a classically-controlled feedback unitary conditioned on the result, then discarding or "resetting" the qubit to |0> is something that would be very useful/crucial for multiple of our research projects currently in flight. With the new density matrix simulator I believe this shouldn't be too difficult to add as a capability for the simulator?

[daxfohl]

After #4100 this can be done by applying a reset gate to any qubit you want to discard. You can even reuse them later in the circuit, but the simulator will be fast in the steps between those ops.