Conjunctive normal form (CNF) represents a Boolean expression as an AND of clauses, where each clause is an OR of literals. A literal is a Boolean variable or its negation; a clause may contain one literal. section 6.5
A CNF expression
(x₀ OR x₁) AND (NOT x₀ OR NOT x₁) is a CNF expression equivalent to x₀ XOR x₁. CNF is not always the simplest representation, but every Boolean expression has a CNF, making it a convenient universal form. section 6.5
CNF supports reversible evaluation of Boolean functions on quantum computers:
- In Qiskit, represent input variables, one auxiliary qubit per clause, and an output qubit; evaluate clauses with multi-controlled OR operations, then combine their results with multi-controlled AND. section 6.5.2
- In Q#, allocate clause-result qubits inside the operation, compute clause values, apply MultiAnd, and use conjugation to uncompute intermediate results. section 6.5.3
- Test clause and expression operations against expected results; passing tests validate the implementation. section 6.5.2 section 6.5.3
Listing 6.8 Qiskit: Evaluating a Boolean expression as a quantum operation
from qiskit import QuantumCircuit
def evaluate_clause(n, literals): #1
circ = QuantumCircuit(n + 1)
if len(literals) == 0:
return circ
controls = []
for (ind, neg) in literals: #2
to serve as OR inputs/
controls.append(ind)
if not neg: #3
in literals with negations/
circ.x(ind)
circ.append(quantum_multior(len(controls)), #4
controls + [n])
for (ind, neg) in literals: #5
if not neg:
circ.x(ind)
return circ
def evaluate_expression(n, expression): #6
n_clauses = len(expression)
circ = QuantumCircuit(n + n_clauses + 1) #7
if n_clauses == 0:
circ.x(n)
return circ
for (ind, clause) in enumerate(expression): #8
stores the result in auxiliary qubits/
circ.append(evaluate_clause(n, clause),
list(range(n)) + [n + ind])
circ.append(quantum_multiand(n_clauses), #9
range(n, n + n_clauses + 1))
for (ind, clause) in enumerate(expression): #10
to free auxiliary qubits/
circ.append(evaluate_clause(n, clause),
list(range(n)) + [n + ind])
return circ
Inspect the Qiskit implementation of clause and expression evaluation, including literal handling, auxiliary qubits, and circuit composition. section 6.5.2
Listing 6.9 Q#: Evaluating a Boolean expression as a quantum operation
import Std.Arrays.*;
operation EvaluateClause( #1
x : Qubit[],
y : Qubit,
literals : (Int, Bool)[]
) : Unit is Adj + Ctl {
let controlQubits =
Mapped((ind, _) -> x[ind], literals); #2
let controlPattern =
Mapped((_, pos) -> pos, literals); #3
within {
ApplyPauliFromBitString(PauliX, false, #4
controlPattern, controlQubits);
} apply {
MultiOr(controlQubits, y); #5
} #6
}
operation EvaluateExpression( #7
x : Qubit[],
y : Qubit,
expression : (Int, Bool)[][]
) : Unit is Adj + Ctl {
let nClauses = Length(expression);
use clauseResults = Qubit[nClauses]; #8
within {
for (clause, result) in
Zipped(expression, clauseResults) { #9
EvaluateClause(x, result, clause);
}
} apply {
MultiAnd(clauseResults, y); #10
} #11
}
Inspect the Q# implementation, including clause-result allocation and within-apply conjugation for automatic uncomputation. section 6.5.3
