Quantum Computing (AL-802 (D)) - Important Questions

Derive the Quantum Fourier Transform (QFT) for $n$ qubits. Show that for $N=2^n$ the QFT operator $F_N$ acts on the computational basis state $\left|x\right>$ as

$$F_N \left|x\right> = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2\pi i \, \frac{x y}{N}} \left|y\right>$$

Obtain the matrix representation of $F_N$, prove that $F_N$ is unitary, and discuss its eigenstructure.

Construct the quantum circuit for the QFT on 3 qubits using Hadamard and controlled phase rotation gates. Explicitly show the sequence of gates and compute the total number of one‑ and two‑qubit gates used.

Prove that the inverse QFT $F_N^{-1}$ is given by the Hermitian adjoint of $F_N$ and show how $F_N^{-1}$ can be implemented by reversing the QFT circuit and replacing controlled phase gates by their inverses. Illustrate with the explicit decomposition of $F_N^{-1}$ for $n$ qubits.

Derive the Quantum Phase Estimation (QPE) algorithm. Describe the quantum circuit that uses an $m$‑qubit counting register and an $n$‑qubit eigenstate register. Show how applying controlled-$U^{2^j}$ operations followed by the inverse QFT on the counting register yields an estimate of the phase $\phi$ when $U\left|\psi\right>=e^{2\pi i \phi}\left|\psi\right>$. Include analysis of the probability of obtaining the best $m$‑bit estimate of $\phi$.

Explain how Quantum Phase Estimation (QPE) is used as a subroutine in Shor's algorithm for order finding. Describe the mapping between order finding and phase estimation and outline the steps where the QFT appears.

For Quantum Phase Estimation, derive the relationship between the number of counting qubits $m$ and the precision of the phase estimate. Show that to estimate the phase $\phi$ to $t$ bits of precision with high probability, one needs $m= t+O(1)$ counting qubits, and analyze the effect of rounding errors on the success probability.

Discuss techniques to implement the QFT on architectures with limited qubit connectivity (e.g., nearest‑neighbor constraints). Describe methods to reduce depth and two‑qubit gate count, including use of swap networks and commutation of rotations, and provide an example showing the optimized circuit depth scaling for $n$ qubits.

Define the approximate Quantum Fourier Transform (approximate QFT) obtained by omitting controlled rotations below a threshold angle. Analyze the approximation error introduced when omitting rotations of angle less than $2^{-k}\pi$ and derive the resulting gate count and circuit depth as functions of $n$ and $k$.