# Questions tagged [quantum-fourier-transform]

Quantum Fourier Transform (QFT) is a linear transformation on quantum bits and is the quantum analogue of the discrete Fourier transform. The quantum Fourier transform is a part of many quantum algorithms, notably Shor's algorithm for factoring and computing the discrete logarithm, the quantum phase estimation algorithm for estimating the eigenvalues of a unitary operator, and algorithms for the hidden subgroup problem. (Wikipedia)

179 questions
Filter by
Sorted by
Tagged with
27 views

my code: ...
58 views

### Unitary Transformation for QFT with 2 base states is giving the columns in the wrong order

I'm trying to reproduce in Qiskit the multiplicative form of the QFT for two qubits. It is similar to what is asked in Nielsen's QCQI book in Exercise 5.2 and Box 5.1. To check the results I'm ...
156 views

### Defining the QFT over finite fields

The DFT is well-developed over $\mathbb{C}$ with fast quantum algorithms. There is a DFT defined classically over $F_q$ which mirrors the complex case when we have an $N^{th}$ root of unity in $F_q$, ...
1 vote
75 views

### quantum multiplier for large numbers

I am working on a project where I need to calculate 3x+1 for numbers 0 to infinity. I have an 8GB RAM laptop and I am using Cirq. For small numbers, I was able to perform the multiplication using the ...
• 21
1 vote
47 views

### What exactly is the change in domain for the Quantum Fourier Transform?

The (classical) Fourier Transform is famous for the reversible switch between the time-domain and frequency-domain of time dependent functions. Likewise there would be a change in domain associated ...
1 vote
70 views

### Why does the QFT provide for so many controlled rotations?

I'm new to quantum and I wanted to understand why QFT uses controlled rotation gates. Thank you all
• 19
39 views

### How to create a quantum algorithm to determine unknown coefficients in a linear function

I am trying to solve the following practice question shown below. I am stuck on part (c) where I must design a quantum algorithm to solve the stated problem. I can tell that the solution is probably ...
• 131
82 views

### Fourier transform of the product of two wave functions

Good day, I have a wave function in the coordinate representation $\Psi(x)$. The Fourier transform I am interested in is: $$\int e^{-i a x} \Psi(x) \Psi^{\star}(x-b) dx,$$ where $a$, $b$ are some ...
• 43
950 views

### Does the Quantum Fourier Transform require universality?

Background: In most setups of fault-tolerant quantum computation, universality is achieved using Clifford gates such as $(S, H, \text{CNOT})$ and the $T$-gate. The Eastin-Knill theorem can be ...
142 views

### Failed - Internal Error when running on ibmq

I tried to apply a series of an inverse QFT on a single qubit depending on a previous measurement, but when a depth of a circuit became longer I encountered an internal error, ...
77 views

### In the QFT, do the basis states $\{|k\pmod N\rangle\}_{k=0}^N$ only make sense when $N=2^n$?

When I started learning quantum computing, I learned that for an $n$ qubit system, the basis states look like $$\bigg\{ |\text{n-bit strings}\rangle\bigg\}\,.$$ So an $n$ qubit system has $2^n$ basis ...
• 23
68 views

### Why FACTORING is in second level of Fourier hierarchy?

As per comlexityzoo web, the definition of the k-th level of Fourier Hierarchy (FH) is: $FH_k$ is the class of problems solvable by a uniform family of polynomial-size quantum circuits, with k levels ...
• 741
53 views

### Unexpected Rotations in QFT Implementation with Qiskit vs. Expected Behavior in Quirk

I'm working on implementing the Quantum Fourier Transform (QFT) using Qiskit. I've encountered an issue where unexpected rotations occur in the presence of a Hadamard circuit, which contrasts with the ...
75 views

### Understanding how to solve group isomorphism given the state $\sum_{\pi \in S_n} |\pi(G) \rangle$

Let $G=([n],E)$ be an undirected graph, which is represented by a $n \choose 2$ bit string, by indicating for each $i < j$ if $(i,j) \in E$. And let $| G \rangle$ be the $n \choose 2$ qubit state ...
• 239
131 views

### Is it possible to modify the QFT circuit to use only 1-qubit gates?

[Measured Quantum Fourier Transform] I've recently learned the Quantum Fourier Transform, and was shown its circuit. The circuit I've seen is composed of Hadamard gates and controlled Rotation gates. ...
• 239
32 views

• 499
2k views

I'm pretty new in Qiskit and quantum circuits. I'm using Qiskit to implement a quantum circuit and I followed this tutorial to implement a QFT. The way this QFT was built, it applies QFT in the first $... 1 vote 1 answer 156 views ### Why is the application of a Quantum Fourier Transform constant time? I am just curious (complexity theory wise) why the unitary matrix for the QFT (Quantum Fourier Transform) is constant time. From what I know, there is no general way to represent it as a sequence of ... • 409 1 vote 1 answer 78 views ### Modify Shor’s quantum order-finding algorithm in such a way that it uses as few qubits as possible I am supposed to modify Shor’s quantum order-finding algorithm in such a way that it uses as few qubits as possible. Beforehand, I already did an exercise where I showed that the inverse Quantum ... • 23 4 votes 1 answer 152 views ### Is the phase-estimation a specific case of the Hidden Subgroup Problem? I read Nielsen & Chuang and I have difficulties understanding the links between the Hidden Subgroup Problem and the Phase Estimation. In Exercise 5.14 (Section 5.3.1 "Application: order-... • 101 0 votes 0 answers 69 views ### Period finding for amplitude encoding of function In quantum Fourier transform, amplitude encoding is used to represent function$f(x)$such that$|\psi\rangle = \sum_x f(x)|x\rangle$, with$f(x)$being amplitude. In Shor's algorithm, it is not this ... • 41 2 votes 1 answer 336 views ### Solution to Nielsen & Chuang Exercise 5.3 (FFT) Can somebody help me with the solution of Nielsen Chuang, where we are supposed to derive the FFT from the equation (5.4): $$|j_1,\ldots,j_n\rangle\rightarrow\frac{\big(|0\rangle+e^{2\pi i 0.j_n}|1\... 2 votes 1 answer 315 views ### How is the fractional binary notation used in the QFT? I am studying the Quantum Fourier Transform and my question regards section 4 from this link. Specifically, I do not understand the step where they rewrite in fractional binary notation- could someone ... 4 votes 1 answer 287 views ### How does the Hadamard gate work? I'm learning about the Quantum Fourier Transform (QFT) and from what I can see the Hadamard gate equation doesn't make sense from what I have learnt so far. Here's a link to the resource (Example 2). ... 3 votes 1 answer 321 views ### Is there a way to access the value of a classical bit after measurement and store it as a variable (qiskit)? I am trying to implement the one-qubit Approximate QFT for Shor's Algorithm in qiskit as described in this paper, which requires the gate$$ R_j^{\prime}=\left(\begin{array}{c} 1 \hspace{0.5em} 0 \\ 0 ... 1 vote 1 answer 54 views ### Alternative Versions of Quantum Fourier Transform (Decimation in Time/Frequency) Is there a good comparison of alternative versions of the Quantum Fourier Transform (QFT) that mirror the alternative decimation-in-time or decimation in frequency versions for the conventional Fast ... 5 votes 2 answers 142 views ###$QFT^{-1}$at the end of Shor's algorithm and$QFT\$ at the end of Hidden Subgroup algorithm

In the usual presentations (e.g. Nielsen and Chuang) Shor's algorithm (in its quantum part) is presented as a special case of phase estimation, meaning it uses a circuit of the form "generate ...
• 437
1 vote
107 views

### Convert an integer to its basis state in Cirq

I am trying to implement Quantum Adder using QFT in Cirq. I previously did the same problem using Pennylane, in which I converted an integer into its Basis state using the BasisStatePreparation method ...