使用 Toffoli 门实现或门

Question

是否可以使用不超过 2 个 Toffoli 门来实现“或”门？

我已经使用 3 个 Toffoli 门实现了它，但找不到任何方法来使用 2 个 Toffoli 门实现它。

Answer 1

我假设您的意思是两个量子位上的“或”门，这应该具有以下效果：

\n\n

|x\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|x\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y\xe2\x9f\xa9 \xe2\x86\x92 |x\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|x\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y \xe2\x8a\x95 (x\xe2\x82\x80 \xe2\x88\xa8 x\xe2\x82\x81)\xe2\x9f\xa9\n

\n\n

您可以使用德摩根定律 x\xe2\x82\x80 \xe2\x88\xa8 x\xe2\x82\x81 = \xc2\xac (\xc2\xacx\xe2\x82\x80 \xe2\x88\xa7\xc2\xacx\xe2\x82\x81），如下：

\n\n

\n
1. 将 X 门应用于每个输入量子位：
   \n|x\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|x\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y\xe2\x9f\xa9 \xe2\x86\x92 |\xc2\xacx\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|\xc2\xacx\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y\xe2\x9f\xa9
\n
2. 应用具有两个输入量子位作为控制、输出量子位作为目标的 Toffoli 门：
   \n|\xc2\xacx\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|\xc2\xacx\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y\xe2\x9f\xa9 \xe2\x86\x92 |\xc2\xacx\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|\xc2\xacx\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y \xe2\x8a\x95 (\xc2\xacx\xe2\x82\x80 \xe2\x88\xa7 \xc2\xacx\xe2\x82\x81)\xe2\x9f\xa9
\n
3. 再次对每个输入量子位应用 X 门，将它们返回到初始状态：
   \n|\xc2\xacx\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|\xc2\xacx\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y \xe2\x8a\x95 (\xc2\xacx\xe2\x82\x80 \xe2\x88\xa7 \xc2\xacx\xe2\x82\x81)\xe2\x9f\xa9 \xe2\x86\x92 |x\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|x\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y \xe2\x8a\x95 (\xc2\xacx\xe2\x82\x80 \xe2\x88\xa7 \xc2\xacx\xe2\x82\x81)\xe2\x9f\xa9
\n
4. 将 X 门应用于输出量子位以否定结果：
   \n|x\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|x\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y \xe2\x8a\x95 (\xc2\xacx\xe2\x82\x80 \xe2\x88\xa7 \xc2\xacx\xe2\x82\x81)\xe2\x9f\xa9 \xe2\x86\x92 |x\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|x\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y \xe2\x8a\x95 \xc2\xac(\xc2\xacx\xe2\x82\x80 \xe2\x88\xa7 \xc2\xacx\xe2\x82\x81)\xe2\x9f\xa9 = |x\xe2\x82\x80\xe2\x9f\xa9\xe2\x8a\x97|x\xe2\x82\x81\xe2\x9f\xa9\xe2\x8a\x97|y \xe2\x8a\x95 (x\xe2\x82\x80 \xe2\x88\xa8 x\xe2\x82\x81)\xe2\x9f\xa9
\n

\n