QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images

Dmitry Savostyanov

    Research output: Contribution to journalArticlepeer-review


    Quantics tensor train (QTT), a new data-sparse format for one- and multi-dimensional vectors, is based on a bit representation of mode indices followed by a separation of variables. A radix-2 recursion, that lays behind the famous FFT algorithm, can be efficiently applied to vectors in the QTT format. If input and all intermediate vectors of the FFT algorithm have moderate QTT ranks, the resulted QTT-FFT algorithm outperforms the FFT for large vectors and has asymptotically the same complexity as the superfast quantum Fourier transform. It is instructive to describe a class of such vectors explicitly. We identify all vectors that have QTT ranks one on input, intermediate steps and output of the FFT algorithm. We also give an example of QTT-rank-one vector that has the Fourier image with full QTT ranks. We show by numerical experiments that for certain rank-one vectors with full-rank Fourier images, the practical -ranks remain moderate for large mode sizes.

    Original languageEnglish
    Pages (from-to)3215-3224
    Number of pages10
    JournalLinear Algebra and its Applications
    Issue number9
    Publication statusPublished - 1 May 2012


    • Data-sparse formats
    • Fast Fourier transform
    • Quantics tensor train
    • Quantum Fourier transform


    Dive into the research topics of 'QTT-rank-one vectors with QTT-rank-one and full-rank Fourier images'. Together they form a unique fingerprint.

    Cite this