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 (2^n) on n qubits. In particular, sets of unitaries forming 2-designs have wide applicability to quantum information protocols. We devise an O (n) -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 (n) without requiring any ancilla qubits, thereby improving upon previous approaches.