Quantum circuits for OR and AND of ORs

We give the first quantum circuit for computing f(0) OR f(1) more reliably than is classically possible with a single evaluation of the function. OR therefore joins XOR (i.e. parity, f(0) X f(1)) to give the full set of logical connectives (up to relabelling of inputs and outputs) for which there is quantum speedup.