{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,15]],"date-time":"2026-03-15T00:41:16Z","timestamp":1773535276598,"version":"3.50.1"},"reference-count":0,"publisher":"Rinton Press","issue":"15&16","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["QIC"],"published-print":{"date-parts":[[2014,11]]},"abstract":"<jats:p>We consider quantum circuits composed of Clifford and $T$ gates. In this context the $T$ gate has a special status since it confers universal computation when added to the (classically simulable) Clifford gates. However it can be very expensive to implement fault-tolerantly. We therefore view this gate as a resource which should be used only when necessary. Given an $n$-qubit unitary $U$ we are interested in computing a circuit that implements it using the minimum possible number of $T$ gates (called the $T$-count of $U$). A related task is to decide if the $T$-count of $U$ is less than or equal to $m$; we consider this problem as a function of $N=2^n$ and $m$. We provide a classical algorithm which solves it using time and space both upper bounded as $\\mathcal{O}(N^m \\text{poly}(m,N))$. We implemented our algorithm and used it to show that any Clifford+T circuit for the Toffoli or the Fredkin gate requires at least 7 $T$ gates. This implies that the known 7 $T$ gate circuits for these gates are $T$-optimal. We also provide a simple expression for the $T$-count of single-qubit unitaries.<\/jats:p>","DOI":"10.26421\/qic14.15-16-1","type":"journal-article","created":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T23:40:57Z","timestamp":1614555657000},"page":"1261-1276","source":"Crossref","is-referenced-by-count":28,"title":["An algorithm for the T-countAn algorithm for the T-count"],"prefix":"10.26421","volume":"14","author":[{"given":"David","family":"Gosset","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vadym","family":"Kliuchnikov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michele","family":"Mosca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vincent","family":"Russo","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10955","published-online":{"date-parts":[[2014,11]]},"container-title":["Quantum Information and Computation"],"original-title":[],"deposited":{"date-parts":[[2021,2,28]],"date-time":"2021-02-28T23:40:58Z","timestamp":1614555658000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rintonpress.com\/journals\/doi\/QIC14.15-16-1.html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11]]},"references-count":0,"journal-issue":{"issue":"15&16","published-online":{"date-parts":[[2014,11]]},"published-print":{"date-parts":[[2014,11]]}},"URL":"https:\/\/doi.org\/10.26421\/qic14.15-16-1","relation":{},"ISSN":["1533-7146","1533-7146"],"issn-type":[{"value":"1533-7146","type":"print"},{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11]]}}}