A practical quantum algorithm for the Schur transform
العنوان: | A practical quantum algorithm for the Schur transform |
---|---|
المؤلفون: | William M. Kirby, Frederick W. Strauch |
المصدر: | Quantum Information and Computation. 18:721-742 |
بيانات النشر: | Rinton Press, 2018. |
سنة النشر: | 2018 |
مصطلحات موضوعية: | Quantum Physics, Nuclear and High Energy Physics, Basis (linear algebra), Dimension (graph theory), FOS: Physical sciences, General Physics and Astronomy, Statistical and Nonlinear Physics, 01 natural sciences, 010305 fluids & plasmas, Theoretical Computer Science, Combinatorics, Computer Science::Emerging Technologies, Computational Theory and Mathematics, Symmetric group, Qubit, Irreducible representation, 0103 physical sciences, Quantum algorithm, Quantum Physics (quant-ph), 010306 general physics, Quantum, Mathematical Physics, Quantum computer, Mathematics |
الوصف: | We describe an efficient quantum algorithm for the quantum Schur transform. The Schur transform is an operation on a quantum computer that maps the standard computational basis to a basis composed of irreducible representations of the unitary and symmetric groups. We simplify and extend the algorithm of Bacon, Chuang, and Harrow, and provide a new practical construction as well as sharp theoretical and practical analyses. Our algorithm decomposes the Schur transform on $n$ qubits into $O\left(n^4\log\left(\frac{n}{\epsilon}\right)\right)$ operators in the Clifford+T fault-tolerant gate set and uses exactly $2\lfloor\log_2(n)\rfloor-1$ ancillary qubits. We extend our qubit algorithm to decompose the Schur transform on $n$ qudits of dimension $d$ into $O\left(d^{1+p}n^{3d}\log^p\left(\frac{d n}{\epsilon}\right)\right)$ primitive operators from any universal gate set, for $p\approx3.97$. Comment: Erratum: the algorithm in this paper implements the inverse Schur transform. Thanks to Adam Wills for pointing this out! Since the algorithm compiles the inverse Schur transform into a quantum circuit, the Schur transform can be obtained by inverting that circuit, so the costs of the algorithm are unchanged. See paper for details |
تدمد: | 1533-7146 |
URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::32ecef0597db67d40922502ad2a0611e https://doi.org/10.26421/qic18.9-10-1 |
حقوق: | OPEN |
رقم الأكسشن: | edsair.doi.dedup.....32ecef0597db67d40922502ad2a0611e |
قاعدة البيانات: | OpenAIRE |
تدمد: | 15337146 |
---|