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.