2018/04/30 by Hari Krovi · 1 citation
Computer Science · Mathematics · Physics and Astronomy · #Algebraic structures and combinatorial models #Algorithm #Artificial intelligence #Computer science #Quantum Computing Algorithms and Architecture #Quantum-Dot Cellular Automata #cs.DM #math.CO #quant-ph
paper · pdf · doi:10.22331/q-2019-02-14-122
published as Quantum 3, 122 (2019) · 21 pages
arxiv created 2019/02/03 · openalex publication_date 2019/02/14 · arxiv updated 2019/02/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
The Schur transform is a unitary operator that block diagonalizes the action of the symmetric and unitary groups on an <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math> fold tensor product <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:msup><mml:mi>V</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>⊗</mml:mo><mml:mi>n</mml:mi></mml:mrow></mml:msup></mml:math> of a vector space <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>V</mml:mi></mml:math> of dimension <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math>. Bacon, Chuang and Harrow [5] gave a quantum algorithm for this transform that is polynomial in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math>, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>d</mml:mi></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:msup><mml:mi>ϵ</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:math>, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>ϵ</mml:mi></mml:math> is the precision. In a footnote in Harrow's thesis [18], a brief description of how to make the algorithm of [5] polynomial in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:mi>d</mml:mi></mml:math> is given using the unitary group representation theory (however, this has not been explained in detail anywhere). In this article, we present a quantum algorithm for the Schur transform that is polynomial in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>n</mml:mi></mml:math>, <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:mi>d</mml:mi></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>log</mml:mi><mml:mo></mml:mo><mml:msup><mml:mi>ϵ</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mo>−</mml:mo><mml:mn>1</mml:mn></mml:mrow></mml:msup></mml:math> using a different approach. Specifically, we build this transform using the representation theory of the symmetric group and in this sense our technique can be considered a ''dual" algorithm to [5]. A novel feature of our algorithm is that we construct the quantum Fourier transform over the so called <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow class="MJX-TeXAtom-ORD"><mml:mtext class="MJX-tex-mathit" mathvariant="italic">permutation modules</mml:mtext></mml:mrow></mml:math>, which could have other applications.