Pourquoi la transformée de Fourier discrète peut-elle être mise en œuvre efficacement en tant que circuit quantique?

17

C'est un résultat bien connu que la Transformée de Fourier Discrète (DFT) de N=2n nombres a la complexité O(n2n) avec le meilleur algorithme connu , tout en effectuant la transformée de Fourier des amplitudes d'un état quantique, avec le classique L'algorithme QFT ne nécessite que des portes élémentaires O(n2) .

Y a-t-il une raison connue pour laquelle c'est le cas? J'entends par là s'il existe des caractéristiques connues de la DFT qui permettent d'en implémenter une "version quantique" efficace.

En effet, une DFT sur des vecteurs à N dimensions peut être considérée comme l'opération linéaire

y=DFTx,DFTjk1Nexp(2πiNjk).

La "version quantique" de ce problème est la tâche de, étant donné un état quantique |xk=1Nxk|k , l' obtention de l'état de sortie |yk=1Nyk|k telle que

|y=DFT|x=QFT|x.
  1. Une première simplification semble venir du fait que, du fait de la linéarité de QM, on peut se concentrer sur les états de base |j,j=1,...,N , avec l'évolution des vecteurs généraux|x venir alors gratuitement.
  2. Si N=2n , on peut exprimer |j en base deux, ayant |j=|j1,...,jn .
  3. Dans l'algorithme QFT standard, on exploite alors le fait que la transformation peut s'écrire
    |j1,...,jn2n/2l=1n[|0+exp(2πi(0.jnl+1jn))|1],
    qui peut ensuite être implémenté comme un circuit quantique de la forme U k est mis en oeuvre avec O ( n )
    QFT|j1,...,jn=(k=1nUk)|j1,...,jn,
    UkO(n) Les portes élémentaires.

Supposons que nous ayons maintenant une transformation unitaire , et que nous voulons trouver un circuit implémentant efficacement la transformation quantique équivalente | y = A | x . Les deux premières astuces mentionnées ci-dessus peuvent toujours être appliquées, mais il n'est alors pas trivial quand et comment l'autre point peut être utilisé pour obtenir des résultats d'efficacité comme nous l'avons fait pour le QFT.A

|y=A|x.

Existe-t-il des critères connus pour que cela soit vrai? Ou en d'autres termes, est-il possible de déterminer précisément quelles sont les caractéristiques de la DFT qui permettent de mettre en œuvre efficacement la transformation quantique associée?

glS
la source
1
The recursive structure of the QFT with number of qubits seems to contribute to that efficiency.
AHusain

Réponses:

12

Introduction to the Classical Discrete Fourier transform:

La DFT transforme une suite de nombres complexes { x n } : = x 0 , x 1 , x 2 , . . . , X N - 1 dans une autre séquence de nombres complexes { X k } : = X 0 , X 1 , X 2 , . . . qui est défini par X k = N - 1 N{xn}:=x0,x1,x2,...,xN1{Xk}:=X0,X1,X2,... Nous pourrions multiplier par des constantes de normalisation appropriées si nécessaire. De plus, que nous prenions le signe plus ou moins dans la formule dépend de la convention que nous choisissons.

Xk=n=0N1xn.e±2πiknN

Supposons qu'il soit donné que et x = ( 1 2 - i - i - 1 + 2 i ) .N=4x=(12ii1+2i)

We need to find the column vector X. The general method is already shown on the Wikipedia page. But we will develop a matrix notation for the same. X can be easily obtained by pre multiplying x by the matrix:

M=1N(11111ww2w31w2w4w61w3w6w9)

where w is e2πiN. Each element of the matrix is basically wij. 1N is simply a normalization constant.

Finally, X turns out to be: 12(222i2i4+4i).

Now, sit back for a while and notice a few important properties:

  • All the columns of the matrix M are orthogonal to each other.
  • All the columns of M have magnitude 1.
  • If you post multiply M with a column vector having lots of zeroes (large spread) you'll end up with a column vector with only a few zeroes (narrow spread). The converse also holds true. (Check!)

It can be very simply noticed that the classical DFT has a time complexity O(N2). That is because for obtaining every row of X, N operations need to be performed. And there are N rows in X.


The Fast fourier transform:

Now, let us look at the Fast fourier transform. The fast Fourier transform uses the symmetry of the Fourier transform to reduce the computation time. Simply put, we rewrite the Fourier transform of size N as two Fourier transforms of size N/2 - the odd and the even terms. We then repeat this over and over again to exponentially reduce the time. To see how this works in detail, we turn to the matrix of the Fourier transform. While we go through this, it might be helpful to have DFT8 in front of you to take a look at. Note that the exponents have been written modulo 8, since w8=1.

enter image description here

Notice how row j is very similar to row j+4. Also, notice how column j is very similar to column j+4. Motivated by this, we are going to split the Fourier transform up into its even and odd columns.

enter image description here

In the first frame, we have represented the whole Fourier transform matrix by describing the jth row and kth column: wjk. In the next frame, we separate the odd and even columns, and similarly separate the vector that is to be transformed. You should convince yourself that the first equality really is an equality. In the third frame, we add a little symmetry by noticing that wj+N/2=wj (since wn/2=1).

Notice that both the odd side and even side contain the term w2jk. But if w is the primitive Nth root of unity, then w2 is the primitive N/2 nd root of unity. Therefore, the matrices whose j, kth entry is w2jk are really just DFT(N/2)! Now we can write DFTN in a new way: Now suppose we are calculating the Fourier transform of the function f(x). We can write the above manipulations as an equation that computes the jth term f^(j).

enter image description here

Note: QFT in the image just stands for DFT in this context. Also, M refers to what we are calling N.

This turns our calculation of DFTN into two applications of DFT(N/2). We can turn this into four applications of DFT(N/4), and so forth. As long as N=2n for some n, we can break down our calculation of DFTN into N calculations of DFT1=1. This greatly simplifies our calculation.

In case of the Fast fourier transform the time complexity reduces to O(Nlog(N)) (try proving this yourself). This is a huge improvement over the classical DFT and pretty much the state-of-the-art algorithm used in modern day music systems like your iPod!


The Quantum Fourier transform with quantum gates:

The strength of the FFT is that we are able to use the symmetry of the discrete Fourier transform to our advantage. The circuit application of QFT uses the same principle, but because of the power of superposition QFT is even faster.

The QFT is motivated by the FFT so we will follow the same steps, but because this is a quantum algorithm the implementation of the steps will be different. That is, we first take the Fourier transform of the odd and even parts, then multiply the odd terms by the phase wj.

In a quantum algorithm, the first step is fairly simple. The odd and even terms are together in superposition: the odd terms are those whose least significant bit is 1, and the even with 0. Therefore, we can apply QFT(N/2) to both the odd and even terms together. We do this by applying we will simply apply QFT(N/2) to the n1 most significant bits, and recombine the odd and even appropriately by applying the Hadamard to the least significant bit.

Now to carry out the phase multiplication, we need to multiply each odd term j by the phase wj . But remember, an odd number in binary ends with a 1 while an even ends with a 0. Thus we can use the controlled phase shift, where the least significant bit is the control, to multiply only the odd terms by the phase without doing anything to the even terms. Recall that the controlled phase shift is similar to the CNOT gate in that it only applies a phase to the target if the control bit is one.

enter image description here

Note: In the image M refers to what we are calling N.

The phase associated with each controlled phase shift should be equal to wj where j is associated to the k-th bit by j=2k. Thus, apply the controlled phase shift to each of the first n1 qubits, with the least significant bit as the control. With the controlled phase shift and the Hadamard transform, QFTN has been reduced to QFT(N/2).

enter image description here

Note: In the image, M refers to what we are calling N.

Example:

Lets construct QFT3. Following the algorithm, we will turn QFT3 into QFT2 and a few quantum gates. Then continuing on this way we turn QFT2 into QFT1 (which is just a Hadamard gate) and another few gates. Controlled phase gates will be represented by Rϕ. Then run through another iteration to get rid of QFT2. You should now be able to visualize the circuit for QFT on more qubits easily. Furthermore, you can see that the number of gates necessary to carry out QFTN it takes is exactly

i=1log(N)i=log(N)(log(N)+1)/2=O(log2N)

Sources:

  1. https://en.wikipedia.org/wiki/Discrete_Fourier_transform

  2. https://en.wikipedia.org/wiki/Quantum_Fourier_transform

  3. Quantum Mechanics and Quantum Computation MOOC (UC BerkeleyX) - Lecture Notes : Chapter 5

P.S: This answer is in its preliminary version. As @DaftWillie mentions in the comments, it doesn't go much into "any insight that might give some guidance with regards to other possible algorithms". I encourage alternate answers to the original question. I personally need to do a bit of reading and resource-digging so that I can answer that aspect of the question.

Sanchayan Dutta
la source
Regarding the recursive structure: one might take that more or less by definition. If you want to talk about the scaling of an algorithm, you need a family of circuits for different sized inputs. The way this is typically done is to build the circuit for size n+1 out of the circuit for size n.What I'm not really seeing here is any insight that might give some guidance with regards to other possible algorithms (not that I claim that's an easy thing to do)
DaftWullie
@DaftWullie "What I'm not really seeing here is any insight that might give some guidance with regards to other possible algorithms (not that I claim that's an easy thing to do)" Well, yes! I have been thinking about that too. This is more of a preliminary answer. I will add more to it when I get about learning a bit more (and when I get more free time). I would be very glad to see alternate answers to this question. :-)
Sanchayan Dutta
Just because you have a sequence of problems, does not mean one gives the algorithm for the next (let alone a good one). It is typical because we typically think of nice functions. Being recursive in such a simple way is a property of a sequence of problems. Here what I mean is there exists a factorization Un=Un1x. Using this question to diagnose whether a sequence U has the same efficency properties.
AHusain
Hi, in QFT is it implicitly assumed that a, say 8 x 1, input vector x_classical is amplitude encoded with 3-qubits? Then the QFT operations are done on the encoded qubits? Also, can you please elaborate on "...and recombine the odd and even appropriately by applying the Hadamard to the least significant bit."?
Abdullah Ash- Saki
10

One possible answer as to why we can realise the QFT efficiently is down to the structure of its coefficients. To be precise, we can represent it easily as a quadratic form expansion, which is a sum over paths which have phases given by a quadratic function:

F2n=12nk,x{0,1}nexp(iQ(k,x))|kx|,
where Q(z)=1jk2nθj,kzjzk is a quadratic form defined on 2n-bit strings. The quantum Fourier transform in particular involves a quadratic form whose angles are given by
θj,k={π/22njk,if 1jn<k2nj+10,otherwise.
The structure of these angles has an important feature, which allows the QFT to be easily realised as a unitary circuit:
  1. There is a function f:{1,2,,n}{n+1,n+2,,2n} such that θj,k=π for each 1jn (where f(j)=2nj+1 in the case of the QFT);
  2. For any 1h,jn for which θh,f(j)0, we have θj,f(h)=0.

We may think of the indices of z=(k,x){0,1}2n as input and output wires of a quantum circuit, where our task is to show what the circuit in the middle is which shows how the inputs connect to the outputs. The function f above allows us to see the association of output wires to input wires, that in each case there is a Hadamard gate which connects the two ends together, and that apart from the Hadamards (and SWAP gates which accounts for the reversal of in the order of the indices between (1,2,,n) and (f(1),f(2),,f(n))), all of the other operations are two-qubit controlled-phase gates for relative phases of exp(iθj,k). The second condition on f serves to ensure that these controlled-phase gates can be given a well-defined time ordering.

There are more general conditions which one could describe for when a quadratic form expansion gives rise to a realisable circuit, along similar lines. The above describes one of the simplest cases, in which there are no indices in the sum except for those for the standard basis of the input and output states (in which case the coefficients of the associated unitary all have the same magnitude).

Niel de Beaudrap
la source
I am not sure I fully understand. Are you saying that any evolution represented as a quadratic form expansion with a quadratic form satisfying those two conditions can be efficiently implemented? Very interesting
glS
@gIS: yes, and furthermore the structure is essentially the same as the Coppersmith QFT circuit (or rather, the fact that the QFT has that form is why the Coppersmith circuit structure suffices to realise the QFT).
Niel de Beaudrap
8

Cela s'écarte un peu de la question initiale, mais j'espère qu'elle donne un peu plus d'informations qui pourraient être pertinentes pour d'autres problèmes.

On pourrait se demander "qu'en est-il de la recherche d'ordres qui se prête à une implémentation efficace sur un ordinateur quantique?". La recherche d'ordres est le composant principal des algorithmes de factorisation et inclut la transformée de Fourier en tant que partie de celle-ci.

La chose intéressante est que vous pouvez mettre des choses comme la recherche d'ordres et le problème de Simon, dans un contexte général appelé «problème de sous-groupe caché» .

Prenons un groupe g, avec des éléments indexés par g, et une opération de groupe »'. On nous donne un oracle qui évalue la fonctionF(g), et nous sommes assurés qu'il existe un sous-groupe, K, de g avec des éléments k de telle sorte que pour tous gg et kK, f(g)=f(gk). It is our task to uncover the generators of the subgroup K. For example, in the case of Simon's problem, the group G is all n-bit numbers, and the subgroup K is a pair of elements {0,s}. The group operation is bitwise addition.

Efficient solutions (that scale as a polynomial of log|G|) exist if the group G is Abelian, i.e. if the operation is commutative, making use of the Fourier Transform over the relevant group. There are well-established links between the group structure (e.g. {0,1}n,) and the problem that can be solved efficiently (e.g. Simon's problem). For example, if we could solve the Hidden Subgroup Problem for the symmetric group, it would help with the solution of the graph isomorphism problem. In this particular case, how to perform the Fourier Transform is known, although this in itself is not sufficient for creating an algorithm, in part because there is some additional post-processing that is required. For example, in the case of Simon's Problem, we required multiple runs to find enough linearly independent vectors to determine s. In the case of factoring, we were required to run a continued fractions algorithm on the output. So, there's still some classical post-processing that has to be done efficiently, even once the appropriate Fourier transform can be implemented.


Some more details

In principle, the Hidden Subgroup Problem for Abelian groups is solved as follows. We start with two registers, |0|0, and prepare the first in a uniform superposition of all group elements,

1|G|gG|g|0,
and perform the function evaluation
1|G|g|g|f(g)=1|G|gKkK|gk|f(g),
where K is defined such that by taking each element and combining with the members of K yields the whole group G (i.e. each member of K creates a different coset, yielding distinct values of f(g)), and is known as the orthogonal subgroup. Tracing over the second register,
1|K|gKk,kK|gkgk|.
Now we perform the Fourier Transform over the group G, giving the output state
|K||G|gK|gg|.
Each of the vectors |gK has a probability of |K|/|G| of being found, and all others have 0 probability. Once the generators of K have been determined, we can figure out the generators of K via some linear algebra.
DaftWullie
la source
3

One of many possible constructions that gives some insight into this question, at least to me, is as follows. Using the CSD (cosine-sine decomposition), you can expand any unitary operator into a product of efficient gates V that fit nicely into a binary tree pattern. In the case of the QFT, that binary tree collapses to a single branch of the tree, all the V not in the branch are 1.

Réf: Transformée de Fourier rapide quantique considérée par moi-même comme un cas particulier d'application récursive de la décomposition cosinus sinusoïdale .

rrtucci
la source
intéressant, merci. Pourriez-vous inclure un croquis de l'argument dans la réponse, si possible?
glS
1
Ce que j'ai déjà présenté, c'est ma version d'un "sketch". Si vous voulez approfondir, avec des équations et des images, il est préférable d'aller à la référence arxiv donnée à la fin
rrtucci