Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
11

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


9

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


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

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

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


5

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


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

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


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

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


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

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

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


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


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:


2

This paper by Andreas Klappenecker might be a good starting point. The paper spearheaded quantum wavelet transforms and so-called wavelet packet transforms. A wavelet packet transforms yields an iterated decomposition into high-pass and low-pass filtered signals, whereas a wavelet transform only further decomposes the low-pass filtered and down-scaled ...


1

I think my circuit is wrong is as there is indeed a conditional phase shift on q[1], but as I said it also adds to him a 'global' phase which I didn't care for. This 'global' phase isn't actually global for the whole 2-qubits system, as it doesn't affect q[2]. A reminder for me of the necessity to look at the system as a whole when talking about qubits, as ...


1

First point: in most of the cases, the QPE algorithm cannot output the integer $x$. That is why $w$ is introduced in the algorithm: to represent the closest approximation of $x$ that can be returned by the QPE. About your question, no the QPE is not always 100% successful (in this case successful means that the algorithm returns $w$, the closest ...


1

You have to put an extra SWAP-gate after the QFT, see this circuit. Furthermore, the two controlled-Z gates on the same qubit are not necessary. This can reduce the circuit further to this.


1

For question c, c) What can go wrong in Shor’s algorithm if the integer $N$ to be factored is even (that is, one of the prime factors, $p$ and $q$, is equal to $2$)? In order for the period-finding algorithm to work, there needs to be a period to find in the first place. Let us do the modular exponentiation (repeated squaring) unitary $U_f$ on the ...


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