Mathematical foundations

Bits, logic, and reversibility

Trace a computation from a classical truth table to a reversible gate.

12 minFoundations

Intuition

A bit is a label for one of two distinguishable states. A classical gate specifies what output to produce for every input. For example, AND outputs 1 exactly when both input bits are 1.

Imagine trying to reconstruct the input from a single AND output of 0. Three different input pairs are compatible with it. A reversible gate needs enough output information to distinguish every input, which lets us undo the gate precisely.

Learning objectives

  • Read a truth table
  • Explain why AND loses information
  • Construct a reversible bit flip

Interactive exploration

Use the controls to change the state and see its calculated readout. You can return to this experiment as you work through the derivation.

Circuit composer

q0 = leftmost bit
q0q1H⊕
  1. H q0
  2. CX q1 · q0
Step 2 / 2

State at step 2

4 amplitudes
BasisAmplitudeProbability
|00⟩0.70750%
|01⟩0.0000%
|10⟩0.0000%
|11⟩0.70750%

Each shot independently prepares this step’s state. A dense simulator stores 2ⁿ complex amplitudes for n wires. The composer is capped at six wires.

Mathematical foundation

XOR gives 1 for unequal inputs. Using addition modulo two makes the inverse of XOR explicit.

a⊕b=(a+b) mod 2,(a⊕b)⊕b=aa\oplus b=(a+b)\bmod 2,\qquad (a\oplus b)\oplus b=a

A reversible implementation of AND leaves both controls intact and toggles a third bit c when both are 1. This is the Toffoli map.

(a,b,c)↦(a,b,c⊕ab)(a,b,c)\mapsto (a,b,c\oplus ab)

Worked example

Apply Toffoli to 110. Both controls are 1, so the target flips to 1. Apply it again and the output returns to 110. For 100, one control is 0 and the target stays 0.

110⟶111⟶110110\longrightarrow 111\longrightarrow 110

Guided experiment

On one wire, build a transformation that takes |0⟩ to |1⟩. Then duplicate the operation and compare the final state.

Go to the controls
Compare with the expected result

The X gate is its own inverse. With three wires, prepare |110⟩ using X on q0 and q1, then apply CCX to embed AND.

Understanding check

Circuit challenge

Prepare |1⟩ from |0⟩. Any circuit that creates the target state up to global phase is accepted.

    BasisAmplitudeProbability
    |0⟩1.000100%
    |1⟩0.0000%
    1. Why is a two-input AND gate irreversible?
    2. What does applying Toffoli twice do to a basis state?

    Next steps

    Want to keep your results? Start your learning journey

    Open Circuit Composer