The Toffoli Gate (CCNOT)

The Toffoli Gate

The Toffoli gate (also called CCNOT or controlled-controlled-NOT) is a universal reversible 3-qubit gate. It flips the target qubit if and only if both control qubits are in state $|1\rangle$.

Truth Table

State Vector Representation

A 3-qubit system has $2^3 = 8$ basis states. We index them as:

$\text{index} = q_0 \cdot 4 + q_1 \cdot 2 + q_2$

So the basis states map to indices:

The Toffoli gate swaps amplitudes at indices 6 and 7 — it exchanges $|110\rangle \leftrightarrow |111\rangle$.

Universality

The Toffoli gate is classically universal: any Boolean function can be computed reversibly using Toffoli gates. Combined with the Hadamard gate, it is also quantum universal.

Self-Inverse

Like CNOT, the Toffoli gate is its own inverse: applying it twice returns to the original state.

$\text{Toffoli}^2 = I$

Implementation

def toffoli(state):
    result = list(state)
    result[6], result[7] = state[7], state[6]
    return result

Your Task

Implement toffoli(state) for an 8-element state vector that swaps the amplitudes of $|110\rangle$ and $|111\rangle$.