



@article {2515,
	title = {Optimal Two-Qubit Circuits for Universal Fault-Tolerant Quantum Computation},
	year = {2020},
	month = {1/16/2020},
	abstract = {<p>We study two-qubit circuits over the Clifford+CS gate set which consists of Clifford gates together with the controlled-phase gate CS=diag(1,1,1,i). The Clifford+CS gate set is universal for quantum computation and its elements can be implemented fault-tolerantly in most error-correcting schemes with magic state distillation. However, since non-Clifford gates are typically more expensive to perform in a fault-tolerant manner, it is desirable to construct circuits that use few CS gates. In the present paper, we introduce an algorithm to construct optimal circuits for two-qubit Clifford+CS operators. Our algorithm inputs a Clifford+CS operator U and efficiently produces a Clifford+CS circuit for U using the least possible number of CS gates. Because our algorithm is deterministic, the circuit it associates to a Clifford+CS operator can be viewed as a normal form for the operator. We give a formal description of these normal forms as walks over certain graphs and use this description to derive an asymptotic lower bound of 5log(1/epsilon)+O(1) on the number CS gates required to epsilon-approximate any 4x4 unitary matrix.\&nbsp;</p>},
	url = {https://arxiv.org/abs/2001.05997},
	author = {Andrew N. Glaudell and Neil J. Ross and J. M. Taylor}
}
@article {1533,
	title = {Optimal ancilla-free Clifford+T approximation of z-rotations},
	journal = {Quantum Information and Computation},
	volume = {16},
	year = {2016},
	pages = {901-953},
	abstract = {<p>We consider the problem of decomposing arbitrary single-qubit z-rotations into ancilla-free Clifford+T circuits, up to given epsilon. We present a new efficient algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal: In this case, it finds a solution of T-count m + O(log(log(1/epsilon))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit decompositions of T-count 3log_2(1/epsilon) + O(log(log(1/epsilon))).</p>},
	url = {http://arxiv.org/abs/1403.2975v2},
	author = {Neil J. Ross and Peter Selinger}
}
@article {1532,
	title = {Optimal ancilla-free Clifford+V approximation of z-rotations},
	journal = {Quantum Information and Computation},
	volume = {15},
	year = {2015},
	month = {2015/03/06},
	pages = {932-950},
	abstract = {  We describe a new efficient algorithm to approximate z-rotations by
ancilla-free Clifford+V circuits, up to a given precision epsilon. Our
algorithm is optimal in the presence of an oracle for integer factoring: it
outputs the shortest Clifford+V circuit solving the given problem instance. In
the absence of such an oracle, our algorithm is still near-optimal, producing
circuits of V-count m + O(log(log(1/epsilon))), where m is the V-count of the
third-to-optimal solution. A restricted version of the algorithm approximates
z-rotations in the Pauli+V gate set. Our method is based on previous work by
the author and Selinger on the optimal ancilla-free approximation of
z-rotations using Clifford+T gates and on previous work by Bocharov, Gurevich,
and Svore on the asymptotically optimal ancilla-free approximation of
z-rotations using Clifford+V gates.
},
	url = {http://arxiv.org/abs/1409.4355v2},
	author = {Neil J. Ross}
}
