De-quantisation of the quantum Fourier transform

DOI10.1016/J.AMC.2011.06.057MaRDI QIDQ2249000zbMATHOpenAlexFDO

Authors Alastair A. Abbott

Publication date 27 June 2014

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.3989

zbMATH Keywords

quantum Fourier transformquantum computingclassical simulationde-quantisation

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Quantum computation (81P68)

Abstract: 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.

Recommendations

• Quantum Fourier transform revisited.
• Quantum algorithms and the Fourier transform
• A decomposition of quantum Fourier transformation
• Quantum Fourier sampling simplified

Cites work

• DE-QUANTIZING THE SOLUTION OF DEUTSCH'S PROBLEM
• On the role of entanglement in quantum-computational speed-up
• Quantum algorithms and the Fourier transform
• Quantum algorithms revisited
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Rapid solution of problems by quantum computation
• SEPARABILITY OF PURE N-QUBIT STATES: TWO CHARACTERIZATIONS
• The Deutsch-Jozsa problem: de-quantisation and entanglement
• Understanding the quantum computational speed-up via de-quantisation

Cited in

(8)

• Quantum digital-to-analog conversion algorithm using decoherence
• Quantum Fourier transform revisited.
• The road to quantum computational supremacy
• Quantum Fourier analysis
• Quantum deconvolution
• Quantum Fourier transform, Heisenberg groups and quasi-probability distributions
• An observer-based de-quantisation of Deutsch's algorithm
• Structural stability of the quantum Fourier transform

This page was built for publication: De-quantisation of the quantum Fourier transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249000)