0
$\begingroup$

Qiskit's mcx has four different modes:

  • 'noancilla': Requires 0 ancilla qubits.
  • 'recursion': Requires 1 ancilla qubit if more than 4 controls are used, otherwise 0.
  • 'v-chain': Requires 2 less ancillas than the number of control qubits.
  • 'v-chain-dirty': Same as for the clean ancillas (but the circuit will be longer).

The default is 'noancilla', so I was wondering what's their runtime like? Are they any better than the one proposed here? Is either one of them using this method? Can someone provide sources for the methods used in each?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

"Runtime" is not so easily quantified, it depends a lot on the compilation, the other operations in your circuit and whether you simulate or have a real backend.

Generally, the different methods trade off circuit depth (more gates, but less qubits) against circuit width (more qubits, less gates). If we define the runtime by the number of gates we need to execute, then the 'noancilla' mode would be the slowest since it has the most gates. However, if you simulate then more qubits are expensive, so using less qubits and more gates might be faster.

But there are other cases with might render the above rule of thumb invalid. The MCX could be a subroutine in a much larger circuit, so using more qubits is not a problem. Or maybe the coupling map of your device is restrictive and the Toffolis of 'v-chain' require many SWAP gates, effectively increasing the gate depth.

There are many trade offs and depending on your particular use-case either option might be the best. In the end, you can just construct the different circuits, compile them and see what gives you the smallest circuits (in depth and width).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Mentioning that I need to consider the tradeoffs when the question itself is asking about tradeoffs doesn't really answer my question. I guess what I'm asking is, what is the algorithm they used for each implementation? They sparsely mention them in the comments, for example, the 'noancilla' uses some type of Gray code algorithm which implies the runtime is probably exponential, defeating the purpose of any quantum speed up. I'm looking for sources. $\endgroup$
    – Dani007
    Jul 20, 2021 at 23:31

Your Answer

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

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