Efficient decomposition of single-qubit gates into V basis circuits
Alex Bocharov, Yuri G. Gurevich, Krysta M. Svore · Physical Review A · 2013
We develop efficient algorithms for compiling single-qubit unitary gates into circuits over the universal $V$ basis. The $V$ basis is an alternative universal basis to the more commonly studied basis consisting of Hadamard and $\ensuremath{\pi}/8$ gates. We propose two classical algorithms for quantum circuit compilation: the first algorithm has expected polynomial time [in precision $\mathrm{log}(1/\ensuremath{\epsilon})$] and produces an $\ensuremath{\epsilon}$ approximation to a single-qubit unitary with a circuit depth $\ensuremath{\le}12\phantom{\rule{0.16em}{0ex}}{\mathrm{log}}_{5}(2/\ensuremath{\epsilon})$. The second algorithm performs optimized direct search and yields circuits a factor of 3 to 4 times shorter than our first algorithm, but requires time exponential in $\mathrm{log}(1/\ensuremath{\epsilon})$; however, we show that in practice the runtime is reasonable for an important range of target precisions. Decomposing into the $V$ basis may offer advantages when considering the fault-tolerant implementation of quantum circuits.