# Minimal quantum OR circuit

The quantum OR circuit between $$|a\rangle$$ and $$|b\rangle$$ can be made out of 1 Toffoli and 2 CNOT gates, 1 ancillary qubit. Is there any other implementation? Or is this the minimal in the sense of gates used?

• How is this conceptually different than "the classical NAND gate can be made out of an AND gate and a NOR gate", or "the classical XOR gate can be made out of 4 NAND gates?" What gates are you allowing as primitives? CSWAP (Fredkin?) May 8, 2019 at 21:03

Note that there are many ways to make or into a reversible operation.

The truth table for the OR reads: $$\begin{array}{ccc} x & y & x\operatorname{or}y \\ \hline 0 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1\\ \end{array}$$ so we only need to add an ancillary degree of freedom that registers the difference between the last three cases. In other words, if $$f(x,y)=x+y+xy$$ is the OR operation ($$+$$ denotes modulo-$$2$$ sum here), our reversible operation must be some $$g(x,y)$$ such that \begin{align} g(0,0)&=(0,\alpha),\\ g(0,1)&=(1,\beta_1), \\ g(1,0)&=(1,\beta_2), \\ g(1,1)&=(1,\beta_3), \end{align} where $$\alpha$$ can be anything, and the $$\beta_i$$ have to be different from each other. Any such $$g$$ is reversible, and can therefore be implemented as a quantum gate.

To satisfy the above constraints, we clearly need at least two ancillary bits, and then any assignment to the $$\beta_i$$ works. For example, we can choose $$\beta_0=00, \beta_1=01, \beta_2=10$$.

The above argument tells you that you cannot implement a quantum OR operation with less than three qubits. As to how many "elementary gates" you need to realise such an operation as a circuit, that question is meaningless without a choice of the elementary gate set to use.

Your question is not localized to quantum gates, but can be rephrased as "how do I implement a (classical) reversible gate that can realize a logical $$\mathsf{OR}$$?"

I propose a $$3$$-input "upstart" gate acting on $$\{0,1\}^3$$ and producing $$3$$ outputs as follows:

C X Y || O X Y
==============
0 0 0 || 0 0 0
0 0 1 || 1 0 1
0 1 0 || 1 1 0
0 1 1 || 1 1 1
1 0 0 || 1 0 0
1 0 1 || 0 0 1
1 1 0 || 0 1 0
1 1 1 || 0 1 1


Here we see that the first bit is evaluated to the $$\mathsf{OR}$$ of the second and third bits when the first bit is $$0$$, and is evaluated to the $$\mathsf{NOR}$$ of the second and third bits when the first bit is $$1$$.

This can be written in matrix form as:

$$\mathsf{UPSTART}= \left( \begin{array}{cccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ \end{array} \right)$$

This of course can be written in many other ways.

• There appears to have been a small typo in your matrix - I believe I've fixed it, but it might be worth double checking May 11, 2019 at 8:42