A Boolean clause is an OR of several literals, where each literal is a Boolean variable or its negation. A single literal also forms a clause. section 6.5
Clauses provide the components of a conjunctive normal form (CNF): evaluate each clause with OR, then combine the clause results with AND. section 6.5 section 6.5.1
CNF with two clauses
(x₀ OR x₁) AND (NOT x₀ OR NOT x₁) contains the clauses (x₀ OR x₁) and (NOT x₀ OR NOT x₁). The expression is equivalent to x₀ XOR x₁, although CNF offers a universal representation for Boolean expressions. section 6.5
Use clauses as reversible-computation components by:
- Allocating one auxiliary qubit per clause to hold its OR result. section 6.5.1
- Computing the AND of the auxiliary results into the output qubit. section 6.5.1
- Cleaning up the auxiliary qubits before releasing them, because superposition can entangle them with the inputs and output. section 6.5.1
Table 6.3 The steps of the Bennett’s trick
| Step | Input | Auxiliary qubits | Auxiliary output | Final output |
| Initialize | \(\ket{x}\) | \(\ket{0}\) | \(\ket{0}\) | \(\ket{y}\) |
| \(\ket{x}\) | \(\ket{\text{aux}}\) | \(\ket{f(x)}\) | \(\ket{y}\) | |
| \(\ket{x}\) | \(\ket{\text{aux}}\) | \(\ket{f(x)}\) | \(\ket{y \oplus f(x)}\) | |
| \(\ket{x}\) | \(\ket{0}\) | \(\ket{0}\) | \(\ket{y \oplus f(x)}\) |
Use the Bennett-trick table to follow auxiliary-qubit initialization, computation, output formation, and uncomputation. section 6.5.1
