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!
4
-
4$\begingroup$ All classical boolean logic can be represented using either just NOR gates or just NAND gates - do you regard those as a NOT? $\endgroup$– Jon CusterJul 17, 2015 at 17:44
-
1$\begingroup$ This doesn't really belong on physics.se. $\endgroup$– Norbert SchuchJul 17, 2015 at 17:57
-
5$\begingroup$ I'm voting to close this question as off-topic because it is about abstract computational logic, not physics. $\endgroup$– ACuriousMind ♦Jul 17, 2015 at 20:59
-
$\begingroup$ I agree. Not only too abstract but of course this could be done, with a bunch of extra circuitry. But why? Maybe in a fictional unicverse. This maybe should be in the Sci-Fi SE. And by the way, try it out yourself. Draw up some circuits this way then use Karnaugh maps to reduce them to their simplest, without NOTs. Then compare them to straightforward normal logic circuits, again reduced by Karnaugh. Start with a simple flip-flop or an adder. You will see why nobody would want this. $\endgroup$– SDsolarApr 10, 2017 at 22:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
This is a bit of a cop-out answer, but it's relatively easy to find a set of gates that can be substituted for NOT gates. For example:
$$[Y][Z]/i = [\text{NOT}] $$
Where $[Y]$ and $[Z]$ are Pauli gates. It's already known that quantum computing can do universal computations, using only a specific sets of gates. One such set is the Hadmard gate, a phase shift gate, and the CNOT gate. Substitute the CNOT gate with either a controlled $[Y]$ or a controlled $[Z]$, and you can recreate the CNOT using the controlled gate together with the single qubit gates, thus forming a new universal set.
-
$\begingroup$ Upvote. Yet it also can be done with classical logic. I can imagine how the necessary NOTs would be done by AND gates with a 0 on one pin coming from a register that has 0-value bits for that purpose alone. Too cumbersome to even think about very long.. $\endgroup$– SDsolarApr 10, 2017 at 22:46