2
$\begingroup$

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.

Drawing of Qiskit Circuit

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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/… $\endgroup$
    – Frank Yellin
    Commented Nov 7, 2022 at 17:40
  • $\begingroup$ 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. $\endgroup$
    – Frank Yellin
    Commented Nov 7, 2022 at 17:47
  • 1
    $\begingroup$ @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. $\endgroup$
    – Craig Gidney
    Commented Nov 7, 2022 at 17:48
  • $\begingroup$ 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. $\endgroup$
    – Frank Yellin
    Commented Nov 7, 2022 at 18:16
  • $\begingroup$ D'oh. That should have been "Thank you for the reference to your paper". I just noticed the names matched! $\endgroup$
    – Frank Yellin
    Commented Nov 9, 2022 at 7:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.