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

Question

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?

Answer 1

Use De Morgan's law to turn intersection into union.

Answer 2

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.

Answer 3

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.