An algorithm on qubits first uses the quantum-parallelism trick met with the first…
PHYSICS · Multi-part · Fermi University Physics · Quantum Information & Technology · The quantum circuit model and quantum algorithms · The quantum circuit model and quantum algorithms
Quantum Information and Technology, Ch The quantum Fourier transform and phase estimation
Problem
An algorithm on n=5 qubits first uses the quantum-parallelism trick met with the first quantum algorithms: apply H⊗5 to ∣00000⟩, then a single oracle call Uf that costs g elementary gates (left symbolic, as its internal structure is not specified). The resulting register is then fed into the QFT F32 before the qubits are measured.
((a)) Using the product-form circuit for F32, state the number of Hadamard gates, the number of controlled-phase-rotation gates, and the number of swap gates it uses.
((b)) Give the total number of two-qubit (controlled) gates used by the QFT stage alone.
((c)) Using the quantum circuit model's rule that the total gate count of a sequence of stages is the sum of the gate counts of the stages, give the total number of gates in the full circuit (state preparation, oracle call, and QFT) in terms of g.