3
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ 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?) $\endgroup$ – Mark S May 8 at 21:03
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.