Content deleted Content added
m →Over a finite field: fmt., style |
Rescuing 1 sources and tagging 0 as dead.) #IABot (v2.0.9.5 |
||
| (One intermediate revision by one other user not shown) | |||
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| bibcode=2020IJQI...1850035S }}</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>.
Line 100:
To obtain this state from the circuit depicted above, a [[Quantum logic gate#Swap_gate|swap operation]] of the qubits must be performed to reverse their order. At most <math>n/2</math> swaps are required.<ref name=":0" />
Because the discrete Fourier transform, an operation on ''n'' qubits, can be factored into the tensor product of ''n'' single-qubit operations, it is easily represented as a [[quantum circuit]] (up to an order reversal of the output). Each of those single-qubit operations can be implemented efficiently using one [[Hadamard gate]] and a linear number of [[Quantum gate#Controlled gates|controlled]] [[Quantum gate#Phase shift gates|phase gate]]s. The first term requires one Hadamard gate and <math>(n-1)</math> controlled phase gates, the next term requires one Hadamard gate and <math>(n-2)</math> controlled phase gate, and each following term requires one fewer controlled phase gate. Summing up the number of gates, excluding the ones needed for the output reversal, gives <math>n + (n-1) + \cdots + 1 = n(n+1)/2 = O(n^2)</math> gates, which is quadratic polynomial in the number of qubits. This value is much smaller than for the classical Fourier transformation.<ref>{{Cite book |
The circuit-level implementation of the quantum Fourier transform on a linear nearest neighbor architecture has been studied before.<ref>{{cite journal |last1=Fowler |first1=A.G. |last2=Devitt |first2=S.J. |last3=Hollenberg |first3=L.C.L. |title=Implementation of Shor's algorithm on a linear nearest neighbour qubit array |journal=Quantum Information and Computation |date=July 2004 |volume=4 |issue=4 |pages=237–251 |doi=10.26421/QIC4.4-1 }}</ref><ref>{{cite journal |last1=Maslov |first1=Dmitri |title=Linear depth stabilizer and quantum Fourier transformation circuits with no auxiliary qubits in finite-neighbor quantum architectures |journal=Physical Review A |date=15 November 2007 |volume=76 |issue=5 |page=052310 |doi=10.1103/PhysRevA.76.052310 |s2cid=18645435 |arxiv=quant-ph/0703211 |bibcode=2007PhRvA..76e2310M }}</ref> The [[Circuit complexity|circuit depth]] is linear in the number of qubits.
Line 138:
{{see also|Hadamard transform#Quantum computing applications}}
Using the generalized [[Fourier transform on finite groups|Fourier transform on finite (abelian) groups]], there are actually two natural ways to define a quantum Fourier transform on an ''n''-qubit [[quantum register]]. The QFT as defined above is equivalent to the DFT, which considers these n qubits as indexed by the cyclic group <math>\Z / 2^n \Z</math>. However, it also makes sense to consider the qubits as indexed by the [[Boolean group]] <math>(\Z / 2 \Z)^n</math>, and in this case the Fourier transform is the [[Hadamard transform]]. This is achieved by applying a [[Hadamard gate]] to each of the n qubits in parallel.<ref>[https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf Fourier Analysis of Boolean Maps– A Tutorial –, pp. 12-13] {{Webarchive|url=https://web.archive.org/web/20210501173437/https://www.staff.uni-mainz.de/pommeren/Kryptologie/Bitblock/A_Nonlin/Fourier.pdf |date=2021-05-01 }}{{full|date=June 2024}}</ref><ref>[https://web.archive.org/web/20210713134541/https://www.cse.iitk.ac.in/users/rmittal/prev_course/s19/reports/5_algo.pdf Lecture 5: Basic quantum algorithms, Rajat Mittal, pp. 4-5]</ref> [[Shor's algorithm]] uses both types of Fourier transforms, an initial Hadamard transform as well as a QFT.
== For other groups ==
| |||