Exact and approximate unitary 2-designs and their application to fidelity estimation

We develop the concept of a unitary $t$-design as a means of expressing operationally useful subsets of the stochastic properties of the uniform (Haar) measure on the unitary group $U\left(2^n\right)$ on $n$ qubits. In particular, sets of unitaries forming 2-designs have wide applicability to quantum information protocols. We devise an $O\left(n\right)$-size in-place circuit construction for an approximate unitary 2-design. We then show that this can be used to construct an efficient protocol for experimentally characterizing the fidelity of a quantum process on $n$ qubits with quantum circuits of size $O\left(n\right)$ without requiring any ancilla qubits, thereby improving upon previous approaches.

Figure 1

The uniformization procedure

Figure 2

Conjugating the first qubit by a random XOR is the conjugation by a randomly generated circuit of the above form, where a numerical label associated with a gate indicates that it occurs with probability of 3/4 (with probability of 1/4 there is no gate). That is, for each $k∊\left\{2,\dots ,n\right\}$, with independent probability of 3/4, there is a CNOT gate with the first qubit as target and qubit $k$ as control.

Figure 3

Part (a) shows a circuit consisting of $n=7$ CNOT gates with common target; part (b) shows an equivalent circuit (based on a binary tree of addition modulo 2) whose depth is bounded by $2\text{log}n$ and size is bounded $2n$.