De-quantisation of the quantum Fourier transform

The quantum Fourier transform (QFT) plays an important role in many known quantum algorithms such as Shor’s algorithm for prime factorisation. In this paper we show that the QFT algorithm can, on a restricted set of input states, be de-quantised into a classical algorithm which is both more efficien...

Full description

Saved in:
Bibliographic Details
Published in:Applied mathematics and computation 2012-09, Vol.219 (1), p.3-13
Main Author: Abbott, Alastair A.
Format: Article
Language:English
Subjects:
Accounting
Algorithms
Classical simulation
Computation
Computational efficiency
De-quantisation
Fourier transforms
Linearity
Quantum computing
Quantum Fourier transform
Quantum mechanics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The quantum Fourier transform (QFT) plays an important role in many known quantum algorithms such as Shor’s algorithm for prime factorisation. In this paper we show that the QFT algorithm can, on a restricted set of input states, be de-quantised into a classical algorithm which is both more efficient and simpler than the quantum algorithm. By working directly with the algorithm instead of the circuit, we develop a simple classical version of the quantum basis-state algorithm. We formulate conditions for a separable state to remain separable after the QFT is performed, and use these conditions to extend the de-quantised algorithm to work on all such states without loss of efficiency. Our technique highlights the linearity of quantum mechanics as the fundamental feature accounting for the difference between quantum and de-quantised algorithms, and that it is this linearity which makes the QFT such a useful tool in quantum computation.
ISSN:0096-3003
1873-5649
DOI:10.1016/j.amc.2011.06.057