12

Introduction to the Classical Discrete Fourier transform: The DFT transforms a sequence of $N$ complex numbers $\{\mathbf{x}_n\}:=x_0,x_1,x_2,...,x_{N-1}$ into another sequence of complex numbers $\{\mathbf{X}_k\}:=X_0,X_1,X_2,...$ which is defined by $$X_k=\sum_{n=0}^{N-1}x_n.e^{\pm\frac{2\pi i k n}{N}}$$ We might multiply by suitable normalization ...


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: $$ F_{2^n} = \frac{1}{\sqrt{2^n}} \sum_{k,x \in \{0,1\}^n} \exp\bigl(i Q(k,x)\...


8

This is deviating a little from the original question, but I hope gives a little more insight that could be relevant to other problems. One might ask "What is it about order finding that lends itself to efficient implementation on a quantum computer?". Order Finding is the main component of factoring algorithms, and includes the Fourier transform as part of ...


8

Imagine you have an eigenvector $|u\rangle$ of $U$. If you have a state such as $|1\rangle|u\rangle$ and you apply controlled-$U$ to it, you get out $e^{i\phi}|1\rangle|u\rangle$. The phase isn't attached to a specific register, it's just an overall multiplicative factor. Now let's use a superposition on the first register: $$ (|0\rangle+|1\rangle)|u\rangle\...


7

You probably shouldn't be thinking of the Quantum Fourier Transform as being something where you want to extract the outcoming probability amplitudes. As you say, when you start measuring, you destroy the superposition. The only way to extract the amplitudes is to make the same state many, many times, and keep repeating your measurements until you get enough ...


7

A first remark This same phenomenon of 'control' qubits changing states in some circumstances also occurs with controlled-NOT gates; in fact, this is the entire basis of eigenvalue estimation. So not only is it possible, it is an important fact about quantum computation that it is possible. It even has a name: a "phase kick", in which the control qubits (or ...


7

Yes. You have been given a factorization $QFT=U_1 \cdots U_n$ where each $U_i$ is an individual gate. $$ QFT^{-1} = U_n^{-1} \cdots U_1^{-1}\\ = U_n^{\dagger} \cdots U_1^{\dagger}\\ $$ A lot of the individual gates will have the property that $U_i = U_i^\dagger = U_i^{-1}$. These are the involutions like NOT, CNOT, etc. In those cases you are lucky and ...


7

The essential feature of this problem is that while both the quantum and classical algorithms can make use of the efficient classical function of calculating $a^k\text{ mod }N$, the issue is how many times does each have to evaluate the function. For the classical algorithm you're suggesting, you'd calculate $a\text{ mod }N$, and $a^2\text{ mod }N$, and $a^...


6

If you have a quantum state like $$|\Psi\rangle_n = a_0|0\rangle_n+a_1|1\rangle_n+...+a_n|2^n-1\rangle_n$$ and you measure it in the $\{|0\rangle_n,...,|2^{n-1}\rangle_n\}$ basis, then the probability $p(y)$ of getting the state $|y\rangle_n$ is $|a_y|^2$ where $a_y \in \Bbb C$ (i.e it's a complex number). In your example, $$a_y = e^{2\pi i x_0 y/2^n} \...


5

Formula 5.2 refers to an encoding we call amplitude encoding. Imagine you have a vector $x$ with components $x_i$, the components are then encoded as amplitudes of a quantum state. This encoding is very important as a vector that has a dimension $N$, will be encoded in quantum form using about $log(N)$ qubits. This is the main reason why in many quantum ...


5

For Shor's algorithm, it actually doesn't matter which one you use. If you apply the QFT twice, it is equivalent to a classical multiplication by -1 modulo $2^n$ where $n$ is the size of the register. That is to say, it reverses the order of all of the computational basis states except for $|0\rangle$ which stays where it started. $|k\rangle$ becomes $|-k\...


4

Let me attempt to give a rather unconventional answer to this question: As a non-mathematician/software programmer I'm trying to grasp how QFT (Quantum Fourier Transformation) works. Suppose that we have a quantum computer which is able to manipulate $n$ qubits. The quantum state of such a quantum computer precisely describes the current state of this ...


4

You don't convert a classical input to the r.h.s. of Eq. (5.2). The r.h.s. of Eq. (5.2) is something you get as the output of a preceding quantum computation as a quantum state, such as in Shor's algorithm. This is the only way to get an exponential speedup -- if you had to start from an exponentially big classical vector, there would be no way to solve ...


4

The intuition, roughly speaking, is that the only way that you're going to get some difference between classical and quantum computing is if you are able to prepare qubits in a superposition. If you remain in a basis state the whole time, you just have a classical computation. So, you need superposition. Hadamard is the gate that prepares superpositions at ...


3

A QFT can't arbitrarily raise the probability of any state you want to any value you want. Once you create a superposition, you need to find some way to make destructive interference occur between the states you don't want, and construct interference between the states you do want. Finding ways to do this is essentially the entire field of quantum algorithms....


3

Let me augment the discussion by adding some insight into the derivation of the estimate provided. This will give you a good understanding of when the result is an approximation and when it is precise. After the algorithm has run, we are left with the following state on the first register: $$\frac{1}{2^{n}}\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1}e^{-\frac{...


3

Given that there is an efficient way to create the sequence classically, can we not just add a little check for whether we have encountered $x^{r} = 1 \ \text{mod} N$? During the creation process, it should not increase complexity to exponential-time, right? Why bother with quantum Fourier transform at all? Did I misunderstand it in some way? ...


3

Within the paper itself that you linked to, on page 4 section 1.2 "Nonabelian Fourier Transforms" and page 5 section 1.3 "Weak vs Strong Sampling and the Choice of Basis", they define what they mean by representation on page 4 third indent from the top. It specifies that they represent the finite group G as a homomorphism (structure-preserving map) ρ : G → U(...


3

You are mis-quoting the definition of the QFT. You simply take the product of the decimal values of $j$ and $k$, and don't use their binary representations.


3

Expanding and generalising from Jitendra's answer: the key observation in this case is that you must use how scalar factors behave over tensor products. Specifically, $$ a (U \otimes V) = (aU) \otimes V = U \otimes (aV), $$ or more generally $$ a_1 a_2 \cdots a_k \,(U_1 \otimes U_2 \otimes \cdots \otimes U_k) = (a_1 U_1) \otimes (a_2 U_2) \otimes \cdots \...


3

You can actually perform convolution on a quantum computer (and exponentially faster for that matter), if your input signals have a certain structure. But for general inputs, this seems challenging and maybe even physically impossible, which is what the paper seems to argue. Consider how you would compute the convolution of two discrete signals $f$ and $g$ ...


3

I am highly suspicious of the result. If you look at Theorem 16, it claims that there is no operation that achieves the map $$ \sum_{ij}\alpha_i\beta_j|ij\rangle\mapsto \sum_i\alpha_i\beta_i|i\rangle $$ up to normalisation. However, consider the measurement operator $$ P=\sum_{i}|i\rangle\langle ii|. $$ This clearly implements the desired map (for that ...


3

The question is whether taking the Fourier transform $\operatorname{QFT}|gH\rangle$ followed by sampling allows to efficiently recover generators of the hidden subgroup $H\leq G$. While the problem is wide open for non-abelian groups (see this paper for a discussion of the limitations of the Fourier sampling method for instances in case of $G=S_n$, $G=PSL(2,\...


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 ...


3

Talking about efficiency here isn't exactly a fair question: as you change n, the number of qubits in the Fourier transfer, you're changing the gate that you're talking about using (because the smallest phase will be something like controlled-$Z(\pi/2^n)$). After all, if I can do controlled-$Z$ when I have two qubits, why would I suddenly lose the ability to ...


3

You'll need to cast your qubit array as type LittleEndian: let LEArray = LittleEndian(qs); A good example of this is in the QuantumKatas under Quantum Phase Estimation.


3

There is one main key point in the description of your question: Is $s$ meant to be a classical secret or a quantum secret? If $s$ is meant to be a classical secret, then the answer is yes, but there is not really much quantum in the positive answer. If $s_A$, $s_B$, and $s_C$ are all $d$-state digits, then there is a simple construction that works in ...


2

In your example the pattern is made by a modular multiplication function or circuit f(x) = ax (mod N) This quantum circuit and pattern is also given in the IBM Q manual of the IBM Q Experience. So in a loop with start input x = 1 x=1 f(x) = 7 * 1 (mod 15) = 7 x=7 f(x) = 7 * 7 (mod 15) = 4 x=4 => 13 x=13 =>...


2

The tensor products for the individual gates are all being calculated correctly, and the matrices are being multiplied in the correct order. In this case, it turns out that it is a Mathematica programming error, using the * operator for element-by-element multiplication of matrices rather than matrix multiplication. The first clue was that the overall output ...


2

The endian-ness of the qubits is the answer. Both QFT and phase estimation rely on certain endianness of the register, and the representations used in the controlled-unitary part has to match the endianness used in the QFT part (and in the answer). This circuit produces the expected outcome with the inverse QFT block:


Only top voted, non community-wiki answers of a minimum length are eligible