EUVIMEDEUVIMED entdecken
Crossref

An algorithm for the T-countAn algorithm for the T-count

David Gosset, Vadym Kliuchnikov, Michele Mosca, Vincent Russo

Quantum Information and Computation · 2014-11 · 14 (15&16) · 1261-1276

DOI: 10.26421/qic14.15-16-1 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Quantum Information and Computation, 2014-11. Verfasst von David Gosset und 3 weiteren Autor:innen. Die Arbeit wurde bisher 31-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Gosset, D., Kliuchnikov, V., Mosca, M., & Russo, V. (2014). An algorithm for the T-countAn algorithm for the T-count. Quantum Information and Computation, 14(15&16), 1261-1276. https://doi.org/10.26421/qic14.15-16-1

Vancouver

Gosset D, Kliuchnikov V, Mosca M, Russo V. An algorithm for the T-countAn algorithm for the T-count. Quantum Information and Computation. 2014;14(15&16):1261-1276. doi:10.26421/qic14.15-16-1

BibTeX
@article{Gosset2014,
  author = {Gosset, David and Kliuchnikov, Vadym and Mosca, Michele and Russo, Vincent},
  title = {An algorithm for the T-countAn algorithm for the T-count},
  journal = {Quantum Information and Computation},
  year = {2014},
  volume = {14},
  number = {15&16},
  pages = {1261--1276},
  doi = {10.26421/qic14.15-16-1}
}
Kostenlos starten →