3
$\begingroup$

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

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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? $\endgroup$
    – David Richerby
    Jul 17, 2015 at 17:56
  • 2
    $\begingroup$ 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? $\endgroup$
    – babou
    Jul 17, 2015 at 17:57
  • $\begingroup$ sorry "qubit" was a typo - force of habit $\endgroup$
    – jdizzle
    Jul 18, 2015 at 9:42
  • $\begingroup$ Could you clarify what is allowed and what is not? Is a NAND gate allowed? if not, what is allowed? $\endgroup$
    – Ran G.
    Jul 18, 2015 at 20:13

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0
2
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

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

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