Toffoli Gate (CCNOT)

Overview

CNOT introduced one control qubit. The Toffoli gate adds a second control qubit.

It is also called CCNOT:

• two controls (C, C),
• one NOT on a target (NOT).

This gate is important because it:

• mirrors a key idea from classical logic (“flip the output if both conditions are true”),
• provides a clean bridge between reversible classical computation and quantum gates,
• and is a standard example of how multi-qubit control scales.

Intuition

Label the three qubits as:

• control 1
• control 2
• target

Toffoli follows a simple conditional rule:

• If both controls are $|1\rangle$, apply X to the target.
• Otherwise, do nothing.

So it’s a coherent, unitary version of:

• “if (c1 AND c2) then flip t.”

The quantum twist is that the controls can be in superposition. That means “the condition” can be in superposition too, and the gate can create correlations among three qubits.

This connects back to Foundations:

• Multi-qubit states live in tensor-product spaces.
• Entanglement is about the joint state not factorizing.

Toffoli is not “a circuit model”—it’s just one more unitary mapping of multi-qubit basis states.

Formal Description

Action on computational basis states

A three-qubit basis state is

$$|abc\rangle\quad\text{with}\quad a,b,c\in\{0,1\},$$

where we interpret:

• $a$ = control 1
• $b$ = control 2
• $c$ = target

Toffoli acts as:

• If $a=b=1$, flip $c$.
• Otherwise, leave the state unchanged.

So:

$$\text{CCNOT}|110\rangle = |111\rangle,$$ $$\text{CCNOT}|111\rangle = |110\rangle,$$

and all other basis states (like $|000\rangle$, $|010\rangle$, $|101\rangle$) are unchanged.

What happens to amplitudes

If a general three-qubit state has amplitudes spread over many basis vectors, Toffoli only swaps the amplitudes of the two basis states that differ by the target bit when both controls are 1.

Concretely, it swaps the amplitudes of:

• $|110\rangle$ and $|111\rangle$,

and leaves all other amplitudes attached to their basis states.

A full matrix form exists (it is 8×8), but the basis-state rule is usually the most readable definition.

Worked Example

Start with a simple superposition in the controls and a definite target:

$$|\psi\rangle = \tfrac{1}{\sqrt{2}}(|00\rangle + |11\rangle)\otimes|0\rangle.$$

Write it as a three-qubit state:

$$|\psi\rangle = \tfrac{1}{\sqrt{2}}(|000\rangle + |110\rangle).$$

Apply CCNOT:

• $|000\rangle$ stays $|000\rangle$ (controls not both 1).
• $|110\rangle$ becomes $|111\rangle$ (controls both 1, so target flips).

So

$$\text{CCNOT}|\psi\rangle = \tfrac{1}{\sqrt{2}}(|000\rangle + |111\rangle).$$

Interpretation:

• The target is now correlated with the joint control condition.
• Measuring in the computational basis gives either 000 or 111, perfectly correlated across all three qubits.

This is an operational way to see how multi-control gates create structured correlations.

Turtle Tip

Common Pitfalls

Quick Check

What’s Next

You now know the fundamental multi-qubit gate ideas:

• conditional evolution (CNOT, CZ, controlled-$U$),
• reordering (SWAP),
• multi-control logic (Toffoli).

Next we’ll introduce circuits as a full model: composing gates in time and tracking how multi-qubit states evolve step by step.