Virtual two-qubit gates realized by quasi-probability sampling of single-qubit operations

Two-qubit gates are essential components of quantum computation. They are, however, often more challenging to implement experimentally than single qubit gates and also constrained by the physical connectivity of qubits. To aid this problem on the software side, we describe a strategy to decompose a two-qubit gate by quasi-probability sampling of single-qubit operations. Required operations are projective measurements of a qubit in Pauli basis, and π/2 rotation around the x, y, and z axes. The required number of sampling to get an expectation value of a target observable scales exponentially to the number of 'cuts' performed, as expected. The proposed technique enables us to perform 'virtual' gates between a distant pair of qubits, where there is no direct interaction and thus many swap gates are inevitable otherwise. Our findings can provide a resource reduction scheme suitable for first-generation quantum devices.