OR gate implementation using Toffoli gate

Question

Can an OR gate be implemented using not more than 2 Toffoli gates?

I have already implemented it using 3 Toffoli gates but couldn't find any way to implement it using 2 Toffoli gates.

Answer 1

I'm assuming you mean OR gate on two qubits, which should have the following effect:

|x₀⟩⊗|x₁⟩⊗|y⟩ → |x₀⟩⊗|x₁⟩⊗|y ⊕ (x₀ ∨ x₁)⟩

You can do it with just one Toffoli gate, using De Morgan's law x₀ ∨ x₁ = ¬ (¬x₀ ∧ ¬x₁), as follows:

1. Apply an X gate to each of the input qubits:
   |x₀⟩⊗|x₁⟩⊗|y⟩ → |¬x₀⟩⊗|¬x₁⟩⊗|y⟩
2. Apply a Toffoli gate with two input qubits as controls and the output qubit as target:
   |¬x₀⟩⊗|¬x₁⟩⊗|y⟩ → |¬x₀⟩⊗|¬x₁⟩⊗|y ⊕ (¬x₀ ∧ ¬x₁)⟩
3. Apply an X gate to each of the input qubits again to return them to their initial state:
   |¬x₀⟩⊗|¬x₁⟩⊗|y ⊕ (¬x₀ ∧ ¬x₁)⟩ → |x₀⟩⊗|x₁⟩⊗|y ⊕ (¬x₀ ∧ ¬x₁)⟩
4. Apply an X gate to the output qubit to negate the result:
   |x₀⟩⊗|x₁⟩⊗|y ⊕ (¬x₀ ∧ ¬x₁)⟩ → |x₀⟩⊗|x₁⟩⊗|y ⊕ ¬(¬x₀ ∧ ¬x₁)⟩ = |x₀⟩⊗|x₁⟩⊗|y ⊕ (x₀ ∨ x₁)⟩

Answer 2

I think the following answers your question as originally intended, using 2 Toffoli gates with no other gates used.

Let a Toffoli gate be represented as Toffoli(x, y, z), where x and y are the 2 control bits, and z is the third input bit.

OR(x,y) = Toffoli(1,y,Toffoli(x,y,x))

The inner Toffoli gate gives |x⊕(x ∧ y)⟩

The outer Toffoli gate (acting as XOR) produces |x⊕y⊕(x ∧ y)⟩.

You can check the truth table for this expression, you will see that it corresponds to an OR gate.