I am trying to implement the multiplication of a scalar in $\mathbb{Z}_2$ and a polynomial in $GF(2^n)$ in Qiskit. One naive method of implementation that I can think of is:

for i in qpoly.qubit_indices:
   qc.append(CCXGate(), [new_poly.qubit_indices[i], qpoly.qubit_indices[i], scalar.index])

Here, assume that my original quantum scalar is scalar, the quantum polynomial is qpoly, and the result is being stored in new_poly. qc is the QuantumCircuit, and qubit_indices contains the index of the qubits in the register it is called from. I am performing a term-by-term AND of the polynomial terms with the scalar. This will work because the scalar can only be $0$ or $1$.

However, the implementation of a Toffoli gate is expensive in practice, so I would like to avoid its use as much as possible. One thing I can optimize here is to do the operation in place, that is, store the new polynomial in qpoly itself.

Does there exist a combination of gates that performs the AND operation in-place? If not, is there some other more efficient way to perform this multiplication? Any help would be much appreciated!


1 Answer 1


This isn't possible, since the associated operation wouldn't be unitary if the scalar is $0$, as it would map both $|0\rangle$ and $|1\rangle$ to $|0\rangle$. The operation wouldn't be reversible and thus non-unitary.

If the scalar is classical, then it is easy to do: nothing for the $0$ case and a bunch of CNOTs for the other one.

If it's not, as you've mentioned this is a bitwise logical AND operation, for which you don't have really any other choice than to apply a bunch of Toffoli gates.

Note that not all hope for optimisation is most though: if you know that one of the control is in the $|+\rangle$ state or if you later have to uncompute this Toffoli for instance, it is possible to use lighter implementations with less CNOT and $T$ gates.

  • $\begingroup$ Thanks, in my case the scalar must be a qubit, it is not classical. So, I think using the Toffoli gates cannot be avoided then $\endgroup$ Jan 14 at 6:37
  • $\begingroup$ @AshKetchum the fact that you always control on the same qubit may lead to some optimizations though! $\endgroup$
    – Tristan Nemoz
    Jan 14 at 8:37

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.