Content deleted Content added
classical case also maybe, for comparison.. |
Cool paper that needs to be here as well :) Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
Line 1:
{{Short description|Change of basis applied in quantum computing}}
{{Use American English|date=January 2019}}In [[quantum computing]], the '''quantum Fourier transform (QFT)''' is a [[linear transformation]] on [[qubit|quantum bits]], and is the quantum analogue of the [[discrete Fourier transform]]. The quantum Fourier transform is a part of many [[quantum algorithms]], notably [[Shor's algorithm]] for factoring and computing the [[discrete logarithm]], the [[quantum phase estimation algorithm]] for estimating the [[eigenvalue]]s of a [[unitary operator]], and algorithms for the [[hidden subgroup problem]]. The quantum Fourier transform was discovered by [[Don Coppersmith]].<ref name="dc_qft">{{cite report |type=Preprint |last1=Coppersmith |first1=D. |title=An approximate Fourier transform useful in quantum factoring |date=2002 |arxiv=quant-ph/0201067 }}</ref> With small modifications to the QFT, it can also be used for performing fast [[Integer (computer science)|integer]] arithmetic operations such as addition and multiplication.<ref>{{cite arXiv|last=Draper|first=Thomas G.|eprint=quant-ph/0008033|title=Addition on a Quantum Computer|date=7 Aug 2000}}</ref><ref>{{cite journal|last1=Ruiz-Perez|first1=Lidia|last2=Juan Carlos|first2=Garcia-Escartin|title=Quantum arithmetic with the quantum Fourier transform|journal=Quantum Information Processing|arxiv=1411.5949v2|date=2 May 2017|volume=16|issue=6|page=152 |doi=10.1007/s11128-017-1603-1|bibcode=2017QuIP...16..152R |s2cid=10948948}}</ref><ref>{{cite journal | last=Şahin | first=Engin | title=Quantum arithmetic operations based on quantum Fourier transform on signed integers | year=2020 | journal=International Journal of Quantum Information | volume=18 | issue=6 | pages=2050035 | issn=1793-6918 | doi=10.1142/s0219749920500355 | arxiv=2005.00443v3}}</ref>
The quantum Fourier transform can be performed efficiently on a quantum computer with a decomposition into the product of simpler [[unitary matrix|unitary matrices]]. The discrete Fourier transform on <math>2^n</math> amplitudes can be implemented as a [[quantum circuit]] consisting of only <math>O(n^2)</math> [[Hadamard gate]]s and [[Quantum logic gate#Controlled gates|controlled]] [[phase shift gate]]s, where <math>n</math> is the number of qubits.<ref name=":0">{{cite book |doi=10.1017/CBO9780511976667 |title=Quantum Computation and Quantum Information |date=2012 |last1=Nielsen |first1=Michael A. |last2=Chuang |first2=Isaac L. |isbn=978-1-107-00217-3 }}</ref> This can be compared with the classical discrete Fourier transform, which takes <math>O(n2^n)</math> gates (where <math>n</math> is the number of bits), which is exponentially more than <math>O(n^2)</math>.
| |||