liveBook · Manning

De Morgan's laws

As explained in Quantum Programming in Depth

De Morgan's laws are Boolean identities relating negated conjunctions and disjunctions.

De Morgan’s law rewrites OR as a negated AND: x₀ OR x₁ = NOT((NOT x₀) AND (NOT x₁)). This identity enables reversible quantum evaluation when no direct OR operation is available. section 6.4.1

Implement the reversible OR transformation in this order:

  • Apply X gates to negate both input qubits. section 6.4.1
  • Apply a CCNOT gate with the input qubits as controls and the output qubit as target. section 6.4.1
  • Apply an X gate to the output qubit to negate the computed AND. section 6.4.1
  • Apply X gates to the inputs again so the overall computation preserves them. section 6.4.1

How Quantum Programming in Depth covers it

How deep it goes
Derives the identity and translates it into an X–CCNOT–X gate sequence, including restoration of modified inputs.
Examples
Demonstrates a two-input OR encoded as a three-bit reversible transformation with two input qubits and one output qubit.
What it assumes
Assumes familiarity with Boolean AND and NOT operations, quantum gates, and preserving inputs during reversible computation.
What you can do after
Builds it from scratch by converting a Boolean OR expression into reversible quantum gates.
How it connects
Connects Boolean logic, AND, NOT, OR, reversible computation, controlled gates, and CCNOT gates.
Cover of Quantum Programming in Depth
liveBookmanning.com
Read Quantum Programming in Depth on liveBook Get the book at manning.com

Also explained in

Compare how 2 books explain De Morgan's laws →

This explainer was generated by Manning's knowledge graph from the text of Quantum Programming in Depth. The section links point to the parts of the book it draws on.