Logical NOT, or negation, reverses a Boolean value: true becomes false, and false becomes true. In reversible quantum computation, it is a primitive Boolean operation used to construct larger functions and to handle negated input literals. section 6.4 section 6.5
Implement negated literals in a Boolean-expression circuit by following this pattern:
- Apply an X gate to the input qubit corresponding to the variable being negated. section 6.5.1
- Use the transformed input while evaluating the surrounding clause, such as an OR operation. section 6.5.1
- Apply the X gate again afterward to uncompute the temporary change and restore the input. section 6.5.1
Negated literal in conjunctive normal form
In (x₀ OR NOT x₁) AND (NOT x₀ OR x₁), temporarily invert x₁ before evaluating the first clause and x₀ before evaluating the second, then undo each inversion. section 6.5 section 6.5.1
Table 6.2 The truth tables of the main Boolean operations
| \(x_0\) | \(x_1\) | NOT \(x_0\) | \(x_0\) AND \(x_1\) | \(x_0\) OR \(x_1\) | \(x_0\) XOR \(x_1\) | \(x_0\) EQUAL \(x_1\) |
| \(0\) | \(0\) | \(1\) | \(0\) | \(0\) | \(0\) | \(1\) |
| \(0\) | \(1\) | \(0\) | \(1\) | \(1\) | \(0\) | |
| \(1\) | \(0\) | \(0\) | \(0\) | \(1\) | \(1\) | \(0\) |
| \(1\) | \(1\) | \(1\) | \(1\) | \(0\) | \(1\) |
Use the truth table to check that NOT maps 0 to 1 and 1 to 0 before composing it with AND, OR, XOR, or equality. section 6.4
Figure 6.7 To convert a classical function into its quantum implementation, we start by representing it as a sequence of Boolean logic gates. Then, we replace each gate with its classical reversible equivalent. Finally, each classical reversible logic gate is replaced with a quantum gate that implements it.
Place NOT within the reversible-logic synthesis pipeline: decompose the function, replace Boolean operations with reversible equivalents, and map the result to quantum gates. section 6.4
