The binary entropy function is

with the convention \(0\log 0 = 0\). (Recalled only so later magic-count lower bounds can refer to it.)

The single-qubit Pauli operators are

They satisfy \(X^2 = Z^2 = I\) and the anticommutation relation \(ZX = -XZ\). For \(\vec a = (a_1,\dots ,a_n), \vec b \in \{ 0,1\} ^n\) an (\(n\)-qubit) Pauli string is

possibly multiplied by a global phase in \(\{ \pm 1, \pm i\} \). The set of all such operators (with phases) forms the \(n\)-qubit Pauli group. We freely use \(X^{\vec x}\lvert 0\cdots 0\rangle = \lvert \vec x\rangle \) for \(\vec x\in \{ 0,1\} ^n\).

The phase gate is \(P = \begin{pmatrix} 1 & 0 \\ 0 & i \end{pmatrix}\). It satisfies the conjugation relation \(P X P^\dagger = i X Z\) (so conjugating a Pauli \(X\) by \(P\) produces a Pauli up to phase) and \(PZP^\dagger = Z\).

A unitary \(C\) on \(n\) qubits is a Clifford operator if it normalizes the Pauli group, i.e. \(C\, Q\, C^\dagger \) is a Pauli string (up to global phase) for every Pauli string \(Q\). The Clifford group is generated by the Hadamard gate \(H\), the phase gate \(P\) (Definition 3), and \(\mathrm{CNOT}\). A Clifford circuit is a circuit composed only of Clifford gates.

A magic gate (equivalently, non-Clifford gate) is any unitary that is not a Clifford operator. The weight of a gate is the number of qubits on which it acts. The \(T\) gate is \(T = \begin{pmatrix} 1 & 0 \\ 0 & e^{i\pi /4} \end{pmatrix}\), a weight-\(1\) magic gate; the Clifford\(+T\) gate set is \(\{ H,P,\mathrm{CNOT},T\} \). A Clifford\(+\)Magic circuit is a circuit composed of Clifford gates and magic gates. The \(T\) gate satisfies \(T X T^\dagger = e^{-i\pi /4} P X\) and \(TZ = ZT\) (it commutes with Pauli \(Z\)).

Write a Clifford\(+T\) circuit as a sequence of layers, where each layer is either a Clifford circuit or a layer of (parallel) \(T\) gates. The \(T\)-depth of the circuit is the number of \(T\)-layers in such a decomposition; the \(T\)-depth of a unitary \(U\) is the minimum \(T\)-depth over Clifford\(+T\) circuits implementing \(U\). The magic-depth is defined analogously with general magic-gate layers in place of \(T\)-layers.

A density operator \(\rho \) is a positive semidefinite operator with \(\operatorname {Tr}\rho = 1\). The trace norm of an operator \(A\) is \(\lVert A \rVert _{1} = \operatorname {Tr}\! \sqrt{A^\dagger A}\), and the trace distance between density operators \(\rho ,\sigma \) is \(\tfrac 12\lVert \rho -\sigma \rVert _{1}\).

For a Hermicity-preserving superoperator \(\Phi \) (e.g. a difference of quantum channels), the diamond norm is

the maximum taken over density operators \(\rho \) on the input space tensored with an ancilla of the same dimension. For unitaries \(U,U'\) we write \(\lVert U-U' \rVert _{\diamond }\) for the diamond norm of the difference of the channels \(\rho \mapsto U\rho U^\dagger \) and \(\rho \mapsto U'\rho U'^\dagger \).

For subsets \(S_A, S_B \subseteq [n]\), the associated parity function on inputs \(x,y \in \{ 0,1\} ^n\) is

More generally a parity function of \((x,y)\) is any \(\mathbb {F}_2\)-affine function of the bits of \((x,y)\).

An EPR pair is the two-qubit state \(\tfrac {1}{\sqrt2}(\lvert 00\rangle +\lvert 11\rangle )\). A Bell-basis measurement on two qubits projects onto the four maximally entangled states \((X^a Z^b \otimes I)\tfrac {1}{\sqrt2}(\lvert 00\rangle +\lvert 11\rangle )\), \(a,b\in \{ 0,1\} \), returning the outcome \((a,b)\). Teleportation: if Alice holds a state \(\lvert \phi \rangle \) and one half of an EPR pair whose other half is held by Bob, then a Bell-basis measurement by Alice on \(\lvert \phi \rangle \) and her EPR half, with outcome \((a,b)\), leaves Bob’s half in the state \(X^a Z^b \lvert \phi \rangle \). The outcome \((a,b)\) is uniformly random and independent of \(\lvert \phi \rangle \).