1
$\begingroup$

How can I construct AND, OR, NAND, NOR with CNOT gates.

First off, this other question describes how to make them with matrices.

Theoretically I can construct all those gates already. I know how to construct all of them from the TOFFOLI gate, which itself I can construct based on CNOT gates.

However, the TOFFOLI gate requires 6 CNOT gates, which seems like more than I should need for those simple gates. Do I really need that many gates?

Also, what thought process could I use to come up with those gates, without requiring the TOFFOLI construction?

$\endgroup$
2
  • $\begingroup$ Hi there! If you want to construct gates for quantum computation, you need to have them reversible. The gates AND, OR and NOR are not reversible, so they can't be implemented on a quantum computer. However, you can construct quantum AND, quantum OR etc. If you are interested in the latter, I suggest changing your question so that it uses proper terminology. $\endgroup$
    – MonteNero
    Nov 7, 2022 at 4:52
  • $\begingroup$ Yes Quantum AND. What's the proper terminology? Just "quantum AND"? If so I can edit the question. $\endgroup$
    – ions me
    Nov 8, 2022 at 19:03

2 Answers 2

3
$\begingroup$

Note that all these gates are not reversible. As such, it is not possible to implement these "in place". However, you can using the well-known scheme: $$|x\rangle|y\rangle\to|x\rangle|y\oplus f(x)\rangle$$

AND Gate

By definition, the Toffoli gate is exactly the one you're looking for. So, you can't use less than 6 CNOT to implement it exactly. Note that there are some decomposition which use only 3 CNOT at the cost of a relative phase. Thus, if you plan on uncomputing this gate at some point, you can afford only using 3 CNOTs.

NAND Gate

It is quite easy to implement an AND Gate from a NAND one: simply apply an $X$ gate on the output. Since the optimal decomposition of the AND Gate is known (it's simply a Toffoli), it's not possible to do better for implementing the NAND Gate.

OR Gate

Once again, it's quite easy to implement an AND Gate from an OR one: simply apply $X$ gates on the controls qubits before and after the OR Gate. As such, this not only shows that you can't implement an OR gate using less than 6 CNOTs, it also gives you the optimal decomposition.

NOR Gate

Finally, you ca implement an OR gate from a NOR one by applying an $X$ gate on the target qubit. This also implies that this gate cannot be implemented using less than 6 CNOTs.

Conclusion

Since all these gates can be built from one to another without using additional CNOTs, their optimal decomposition in terms of CNOTs gates is the same. Since we happen to know that the optimal decomposition for the Toffoli gate uses 6 CNOTs, you cannot find an implementation that uses less than 6 CNOTs, as long as you want to implement them perfectly. You can use as less as 3 CNOTs if you allow relative phases though, which is still a 2x improvement.

$\endgroup$
4
  • $\begingroup$ How does this show that 6 gates is optimal for OR? Showing that it's easy to make from 6 gates would imply that the optimal is 6 or less right? $\endgroup$
    – ions me
    Nov 8, 2022 at 18:59
  • $\begingroup$ Or is the point that you don't add any 2 qubit gates, so 6 is the minimal number of 2-qubit gates? $\endgroup$
    – ions me
    Nov 8, 2022 at 19:00
  • $\begingroup$ Ah I see. If you had a way to construct Or with say CNOT gates, then you could just apply the one qubit gates to turn it into AND. That means you'd be able to do TOFFOLI with 4 gates. However we know that's not true, because TOFFOLI requires 6 $\endgroup$
    – ions me
    Nov 8, 2022 at 19:02
  • $\begingroup$ @IonSme Exactly! $\endgroup$
    – Tristan Nemoz
    Nov 8, 2022 at 19:34
1
$\begingroup$

Lets first have a look how CNOT works. It changes computational basis states in the following way:

  • $|00\rangle \rightarrow |00\rangle$
  • $|01\rangle \rightarrow |01\rangle$
  • $|10\rangle \rightarrow |11\rangle$
  • $|11\rangle \rightarrow |10\rangle$

As you can see, the first qubit (control) is left unchnaged. The second qubit is in state $|1\rangle$ provided control and target qubits are in different states, otherwise it is in state $|0\rangle$. This means that if input states are the basis ones, CNOT gate's second output is effectively XOR of control and target qubits.

Since XOR is not universal gate for classcial computing, it cannot be used for realization of AND, OR and NOT gates which conversely form a set of universal classical gates. To implement these logical functions, you have to use Toffoli gate which returns result of NAND applied on both control qubits provided that the target qubit is in state $|1\rangle$ before application of the Toffoli. Since NAND is universal for classical computing, this construction allows you to implement AND, OR and NOT, and any other Boolean function, on a quantum computer.

$\endgroup$
4
  • $\begingroup$ When you say XOR cannot be used to realize AND OR and NOT, you mean classically cannot be used right? (because Toffoli can be constructed from CNOT) $\endgroup$
    – ions me
    Nov 8, 2022 at 18:58
  • $\begingroup$ @IonSme: I mean that to use only CNOTs is not enough. It is true that Toffoli contains CNOTs but also T, T' and H gates. $\endgroup$ Nov 9, 2022 at 13:34
  • $\begingroup$ Classically, are XOR and NOT complete? (It seems like they aren't, which is rather interesting that cnot (quantum xor) is complete if you add one qubit gates (of which the classical computing only has one (the NOT gate). $\endgroup$
    – ions me
    Nov 9, 2022 at 23:58
  • $\begingroup$ @IonSme: Classically XOR and NOT are still not complete. Concerning the other comment, yes quantum world works differently, as you pointed out there are more single qubit gates which expands the possibilities. $\endgroup$ Nov 10, 2022 at 7:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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