# Controlled NOT gate which flips target when at least one of the control qubits is |1>

I would like to have a controlled NOT gate which flips my target qubit when at least one of the control qubits is |1>.

I would like to be able to do this for arbitrary n. For a system with 2 control qubits this can be achieved as follows: But this gets harder as n gets larger.

So I have 2 questions:

1. [General question] How can I construct such a gate? Is there a simple custom gate I can make, or a sequence of gates?

2. [Cirq question] How would I implement this using Cirq?

Use De Morgan's law to turn intersection into union. If you have $$n$$ control qubits, the operator

$$|{0}\rangle \langle{0} |\otimes I + \sum_{k=1}^{2^n-1} |{k}\rangle \langle{k}|\otimes X$$

does the job.

Just to explain Craig Gidney's answer slightly differently: The way that you've specified the gate is that you want it to not work if all the inputs are 0. So, you can always apply $$X$$ on the target, and then apply the inverse (which also happens to be $$X$$) only in the case where all inputs are 0. This is basically the same thing as the multi-controlled-not except that it works when the inputs are all 0 rather than all 1. The solution: apply $$X$$ on every qubit to flip the all-0 to all-1, apply toffoli, then flip back. 