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

Explain Shor's algorithm for integer factorization. Describe the quantum subroutine for period finding and how the Quantum Fourier Transform (QFT) is used to extract the period. Outline all major steps of the algorithm, illustrate with a small numerical example (e.g., factor 15), and analyze the asymptotic time complexity compared to the best known classical factoring algorithms.

Explain Grover's search algorithm. Describe the role of the oracle and the diffusion (inversion-about-the-mean) operator. Derive the number of iterations required to find a marked item with high probability and express the complexity in terms of $N$ and number of solutions $M$. Include the success probability analysis and show the approximate iteration count as $$\text{iterations}\approx \frac{\pi}{4}\sqrt{\left(\frac{N}{M}\right)}$$ and the overall time complexity $$O\left(\sqrt{N}\right)\,.$$

Describe the Deutsch-Jozsa algorithm. Explain how it deterministically distinguishes between constant and balanced Boolean functions using a single quantum query. Provide the quantum circuit, show the state evolution step-by-step, and justify why the algorithm gives a deterministic result.

Compare Shor's and Grover's algorithms. Discuss their objectives, the type of speedup they provide (exponential vs quadratic), the complexity classes they impact, typical resource requirements (qubit counts and circuit depth), and practical applicability and limitations on near-term hardware.

Explain the basic programming model of IBM Qiskit. Describe how to construct quantum circuits, run local simulation, and execute circuits on cloud quantum backends. Illustrate with example code or pseudo-code to prepare and measure a Bell state $|\Phi^{+}\rangle = \frac{1}{\sqrt{2}}\left(|00\rangle + |11\rangle\right)$ and explain the sequence of transpilation and backend selection steps.

Briefly describe Microsoft Q# and Rigetti's PyQuil. For each, highlight the programming paradigm, available simulators, typical workflow to run a circuit on hardware or simulator, and key differences from IBM Qiskit.

Explain the main challenges of NISQ devices such as noise, decoherence, and gate errors. Describe mitigation techniques including error mitigation, circuit transpilation and optimization, and readout error calibration. How do open-source toolkits (e.g., Qiskit, Q#, PyQuil) assist in implementing these mitigation strategies and in evaluating noisy device behaviour?