15

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


13

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


12

While the QFT and Hadamard transforms are different, their action on the input state $|00\ldots 0\rangle$ is identical; both produce the uniform superposition of all states. So, if you've got a choice of which to use, you shoulduse the one that is the easiest to implement: the Hadamard transform. Hadamard Transform: $$ H|0\rangle=\frac{|0\rangle+|1\rangle}{\...


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


9

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


9

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


9

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


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

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


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

Starting from the beginning (a very good place to start, after all), the state $\left| 0\right\rangle^{\otimes n}\left| -\right\rangle$ is input into $H^{\otimes n}\otimes I$ (here, called the 'Fourier sample'). This generates the state $$\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\right)\left|-\right\rangle = \frac{1}{2^{n/2}}\left(\left|0\right\...


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


7

I expect you're referring to this image: Where it says that $R_m$ is given by a particular 2x2 matrix. In this notation, $R_m$ is a 1-qubit unitary, but the circuit is applying a different gate, what we might call $CR_m$: a controlled version of $R_m$. This is a 2-qubit gate, given by a 4x4 matrix, with the definition $$ CR_m (|0\rangle |\psi\rangle) = |0\...


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


6

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


6

In the general case I think it's easier to consider the matrix in the form $$ M = \sum_{i_1,\dots,i_n, j_1, \dots j_n} c_{i_1,\dots,j_n} |i_1 \dots i_n\rangle \langle j_1 \dots j_n|, $$ where the $i_1, \dots, i_n,j_1, \dots, j_n$ are all binary and the $c$ with the awful index are the elements of the matrix. Now we know the transformation rules so it's not ...


5

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


5

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


5

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


5

Given that the QFT is exponentially faster than the FFT, The problem with quantum computing is that they are not actually parallel computers: One is tweaking the qubits in such a way that when reading out the result, the desired result gets a high probability. The power of quantum computing comes from the vast phase-space that grows exponentially with ...


4

TLDR: the Fourier transform is entangling. We can immediately agree on two things: if you input a computational basis state (separable) to the Fourier transform, it outputs a separable state the circuit involves entangling gates Neither of these actually resolves the question. Could there be another separable basis which is converted to entangled states? ...


4

By looking to the circuit for the QFT presented in the M. Nielsen and I. Chuang textbook (Figure 5.1.) we can notice that all controlled rotations can be neglected because for each control rotation gate the control qubits are in $| 0\rangle$ state (for the case described in the question). Here is the Figure from the book: So effectively, in this case, we ...


4

I have found the solution! The problem is that each time you use the transpile function, it generates a different transpiled circuit and the order of the outcome is not necessary the same as the order of the input, so you have to use swap gates to obtain the correct one. In order to always obtain the same circuit you have to fit the seed_transpiler (as with ...


4

Let's see what QFT does on two qubit (and then on three qubit) computational basis states and try to gain some insights. The QFT action on $|j\rangle$ basis state: $$QFT |j\rangle = \frac{1}{2^{\frac{n}{2}}} \sum_{k=0}^{2^n -1} e^{2 \pi i \frac{jk}{2^n}} |k\rangle$$ where $n$ is the qubit number. Now suppose $n=2$, then: \begin{align*} QFT |00\rangle &= ...


4

For preference, in a phase estimation algorithm, you would set the state of the second register equal to an eigenstate of the unitary operator $U$, the plan being to find its eigenvalue, which depends on the period $r$. In fact, any of the eigenvectors $|u_s\rangle$ would do for values $s=0,1,\ldots r-1$ as these have eigenvalues related to $s/r$. However, ...


4

I am not sure why, but you cannot add controls to $T$ or $S$ (and their inverses) in the composer. What you can do is instead use the Phase gate (which you can add a control to) and set these angles for identical behaviour: $P(\pi/2) = S$ $P(\pi/4) = T$ $P(-\pi/2) = S^\dagger$ $P(-\pi/4) = T^\dagger$


4

In the Lieb-Robinson bound, the velocity depends on the strength (operator norm) of the interaction. This is intuitive: Twice as strong couplings will propagate information twice as fast (effectively, you can think of this as renormalizing time). Here comes the catch with bosonic systems: For bosons, the norm of interactions is unbounded (e.g. $a^\dagger a$ ...


4

The appropriate $d$-dimensional analogue of $H$ turns out to be the Quantum Fourier Transform. This is obscured by the fact that even though $(1)$ is conjugation the inverse is written implicitly since $H^\dagger = H$. Thus, $d$-dimensional generalization of $(1)$ is $$ QFT \circ X_d \circ QFT^\dagger = Z_d.\tag{1'} $$ Proof The following calculation shows ...


4

Quantum Fourier transform for a single-qubit case is just the Hadamard gate, so $QFT |\psi\rangle = \alpha H|0\rangle + \beta H|1\rangle = \frac{\alpha+\beta}{\sqrt2}|0\rangle + \frac{\alpha-\beta}{\sqrt2}|1\rangle$ And $QFT(|\psi\rangle) = |\psi\rangle$ is possible if $|\psi\rangle$ is an eigenvector of $H$.


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


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