When we use the quantum fourier transform, for a function, the output is entangled, so if a measurement is made on the output, the result may not be that of the function that one wanted in the first place. For a trivial example, consider addition of two polynomials, using DFT, or even FFT, this is straight forward, but if we consider the same setting in the quantum case, where FFT, or DFTs are substituted with Quantum gates, how can the result of the addition two polynomials be accomplished.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
In fact the QFT and the DFT are very different. In the DFT we have $N$ complex values stored in several bits per value, which could be called the standard coefficients of this vector in $\mathbb C^N$, and the Fourier transform produces the Fourier coefficients, which are the coefficients of the same vector in a different basis. In this case the coefficients are stored with finite precision and in general precision will be lost in the change of basis.
The QFT is not the same algorithm implemented with quantum gates; in fact the whole encoding of the state changes. The coefficients are not encoded in qubits: if $N = 2^n$ we now need only $n$ qubits to hold the data, and the coefficients of our element of $\mathbb C^N$ are encoded as the coefficients of the general entangled state of these $n$ qubits together (so we have the restriction that they have to sum 1). In theory no precision is lost in the transform.
As you already remarked, the Fourier coefficients encoded in this way are not accessible to us, and indeed I don't see either how it would be useful to compute a product (I assume you meant product rather than sum) of two polynomials (I am not saying it is not useful for that, just that I don't see how).
If you want to make use of the QFT, it has to be in applications where you are not necessarily interested in the values of all coefficients; e.g. in Shor's algorithm for factoring (or rather period finding) you start out with a (long) periodic sequence of coefficients, and its Fourier transform (possibly after collapsing it to a vector that is 0 everywhere except at some regularly spaced coefficients) will have most coefficients close to 0 but some that are high (and exactly 0 when the period is a divisor of the number of coefficients). You cannot read out the values of the coefficients, but if you look at the qubits (i.e. you measure their values), you will most likely see one of the high coefficients. That gives you a lot of information about the period.
I hope this is (related to) what you were asking.
-
$\begingroup$ As the applications for QFT are in places where we need to find the period(to generalize the formulation of the QFT), the use for the QFT is not in polynomial multiplication, which actually uses the coefficients in an DFT to get the values of the product, as the states for the QFT are entangled(by formulation). $\endgroup$ Commented Jun 17, 2014 at 11:57
-
$\begingroup$ Comment continues here!! In the following scenario, can we use the QFT - applying the hadamard transform(I understand these gates are fundamental to the QFT) at specified points depending upon some function, and then reading the output? $\endgroup$ Commented Jun 17, 2014 at 12:12
-
$\begingroup$ You certainly can, you can do whatever you want with the coefficients afterward, as long as physics permits it (which from the point of view of quantum computation essentially means any combination of unitary operators and measurements). What you have access to in the end however is just your measurement values, i.e. a 0 or a 1 for each qubit (in the QFT + auxiliary qubits which may be entangled with them). $\endgroup$– doetoeCommented Jun 17, 2014 at 12:35
-
$\begingroup$ Keeping in mind the original question are there any algorithms there that use QFT for polynomial multiplication- this seems an intuitive task for an QFT? In the sense that one could always use a QFT construction that uses hadamard gates with registers, to get the multiplication of two polynomials(?) $\endgroup$ Commented Jun 17, 2014 at 17:07
-
$\begingroup$ My guess would be not: in that case you would at least need pointwise multiplication of two vectors, encoded in the coefficients of the superposition, but that can certainly not be implemented by a unitary transformation. $\endgroup$– doetoeCommented Jun 17, 2014 at 18:20