Classical Computation without NOT

Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible universal sets of gates that do not utilise the NOT transformation. Thanks!

EDIT: to clarify, you can perform any set of operations you want, but if there is some sequence that you apply these operations in that is equivalent to a NOT operation then they are forbidden. For example, in quantum computing you can take the square root of a not operation, but as applying two of these gives a not operation then this would not be allowed

• You seem to be mixing classical and quantum terminology so I can't understand what you're asking. Are you talking about simulating all classical computation on a restricted quantum computer? Restricted classical computation on a general quantum computer? Something else? Jul 17 '15 at 17:56
• Welcome to Computer Science Stack Exchange. Why do you specify classical computation in the title, and then mention qbits gates in the body of the question? Where have you search for information, and what have you found? Jul 17 '15 at 17:57
• sorry "qubit" was a typo - force of habit Jul 18 '15 at 9:42
• Could you clarify what is allowed and what is not? Is a NAND gate allowed? if not, what is allowed? Jul 18 '15 at 20:13

2 Answers

You're confusing classical and quantum computation, so let me ignore the quantum aspects for now. If you forbid the unary NOT gate then you can use a binary NOT gate, say $g(a,b) = \lnot a$. You can also simulate NOT using natural gates: $XOR(a,1) = \lnot a$ (and this gate can even be made reversible!). So this kind of restriction is not really meaningful.

It is more meaningful to ask what happens if all gates are monotone, that is, they satisfy $g(x_1,\ldots,x_n) \leq g(y_1,\ldots,y_n)$ whenever $x_i \leq y_i$ (here $\text{FALSE}\leq\text{TRUE}$). Such circuits are known as monotone circuits, and they can only compute monotone functions. One natural complete basis is $\{\text{AND},\text{OR}\}$. You can show that this basis is complete using DNFs.

Yes, it is very possible to replace a one-bit not with a two-bit gate:

Few examples: not(a) = xor(a, 1) not(a) = nand(a, a) not(a) = nor(a, 0)

The keyword to describe "universal sets" is functional compplete. You can find the complete list of minimal,, functional complete sets (with 2 inputs) at wikipedia