# Not understanding gates being generated by MCX in "recursion" mode

I was curious about the various ways of generating code for MCX when there are multiple controls. I saw that qiskit provided multiple algorithms for generating code, depending on the number of ancilla qubits provided.

I tried the following experiment:

circuit = QuantumCircuit(7)
circuit.mcx([0, 1, 2, 3, 4], 5, ancilla_qubits=[6], mode='recursion')
circuit.decompose().draw()


I got the circuit shown below with four gates

• The first and second gates perform the operating and put the result into q5.
• The third is the uncomputation to clean up the ancilla qubit.

What is the fourth gate for? I somehow feel like I'm missing some fundamental concept.

Update. I also ran my code through Quirk. To look like a Grover oracle, the input bits were initialized to |+>, the output bit to |->, and the ancilla bit to |0>. I added in excessive "detectors". I could see no difference in state caused by the fourth gate. As expected, only the input |11111> had a negative phase shift.

Update number 2. Quirk program with a time-variant dirty ancilla.

## 1 Answer

The fourth gate is necessary if the ancilla qubit is borrowed instead of clean.

Try testing the circuit when the ancilla qubit is set to ON, in addition to testing when it is OFF. Without the fourth operation, it does the wrong thing for an ON ancilla.

• Does that mean that the answer to this question is incorrect? I had considered dirty ancilla, but this said no. quantumcomputing.stackexchange.com/questions/22255/… Nov 7, 2022 at 17:40
• You are correct. I tried setting the ancilla to a time-dependent value in Quirk, and all the needs remained unchanged at the end. Given that two of the modes for mcx are v-chain and v-chain-dirty, I wonder why recursion wasn't marked as accepting dirty ancilla. My URL for the updated Quirk added to my query, since it is too long to fit here. Nov 7, 2022 at 17:47
• @FrankYellin Just because the library does something doesn't mean it's guaranteed to keep doing it. Especially when the use case involves tradeoffs between correctness-in-all-cases and optimization. Very possible that other answer was correct about the behavior in 2021 but then the behavior changed, or something more complicated. Nov 7, 2022 at 17:48
• Thank you for the reference to Gidney's paper. It both answered my question and cleared up some other issues I had been wrestling with. Most text books just say "ancilla" bits, without clarifying their constraints. Nov 7, 2022 at 18:16
• D'oh. That should have been "Thank you for the reference to your paper". I just noticed the names matched! Nov 9, 2022 at 7:23