De-quantisation of the quantum Fourier transform

DOI10.1016/J.AMC.2011.06.057zbMATH Open1448.68241arXiv1006.3989OpenAlexW2048949258MaRDI QIDQ2249000FDOQ2249000

Authors: Alastair A. Abbott 

Publication date: 27 June 2014

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

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (8)

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

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)