Skip to content
Tech Interview Prep
Technical interview guide

Quantum Algorithms I: Deutsch-Jozsa & Grover's Search

The foundational oracle-based algorithms that first demonstrated provable quantum speedups: exponential for Deutsch-Jozsa, quadratic for Grover's search.

Read
54 min
Practice MCQs
25
Interview Q&A
25
Edition
v2
Editorial status
Reviewed

Scope: IBM Quantum learning and Qiskit current algorithm documentation; original Deutsch-Jozsa, Grover, BBHT, and query lower-bound literature reviewed 2026-09-04.

Curated: · Written: · Reviewed:

25 questions

MCQ-3A harness must verify that a black-box f:{0,1}^n→{0,1} is balanced, the promise under which Deutsch–Jozsa separates constant from balanced in one query. Which condition on f's truth table must it check?
MCQ-25A team benchmarks a classical deterministic program against ideal Deutsch-Jozsa on n = 20 input bits, counting oracle calls in the worst case. How many queries must the classical program make before it can always decide whether the promised function is constant or balanced?
MCQ-7A team must decide with certainty (correct on every input, with no error probability) whether a black-box f:{0,1}^n→{0,1} is constant or balanced. They run the Deutsch–Jozsa circuit on a fault-tolerant quantum computer. How many oracle queries does their algorithm need?
MCQ-9An interviewer hands you the n-qubit Deutsch-Jozsa circuit unchanged: Hadamards on the n input qubits, an oracle applied with the ancilla held in |-> so that |x>|-> becomes (-1)^f(x)|x>|->, then Hadamards on the input qubits again and a measurement. She asks you to run it once on f(x) = s . x mod 2 for an unknown n-bit s, with s = 0 allowed. What does the final measurement return?
MCQ-4A team is building a Grover search over 4-bit strings. Their first oracle maps each basis state |x>|0> to |x>|f(x)>, then a cleanup step resets the input register to |0>, so the output is |0>|f(x)>. They simulate the oracle on |0000>|0> and |0001>|0>, with f(0000)=0 and f(0001)=0. The simulator reports the inner product of the two output states is 1 instead of 0. They need the standard reversible oracle that also supports phase kickback by preparing the output qubit in |->. Which change should they make?
MCQ-5A two-qubit circuit prepares the control in |+⟩ = (|0⟩+|1⟩)/√2 and the target in |−⟩ = (|0⟩−|1⟩)/√2. The oracle implements f(0)=0, f(1)=1. The control is then passed through a Hadamard and measured in the Z basis. What is the probability of measuring 1?
MCQ-6A two-input-qubit Deutsch–Jozsa circuit has two input qubits and one ancilla; the ancilla is put in |−⟩ and the input register starts in |00⟩. The oracle U_f is defined by f(00)=0, f(01)=1, f(10)=1, f(11)=0. After the final Hadamard layer on the input register, the input register is measured. What does the measurement show?
MCQ-8A team runs the n=3 Deutsch-Jozsa circuit on a noiseless simulator, preparing the ancilla in |1⟩ and applying the final Hadamard layer to the input register. They measure the qubits to decide whether the promised f is balanced. Which outcome establishes that f is balanced?
MCQ-2A 3-qubit Deutsch–Jozsa circuit is run once against an oracle for f: {0,1}^3 → {0,1} that is not promised to be constant or balanced: f(x) = 1 for exactly two of the eight inputs and 0 for the other six. The top register is measured. What is the probability that the result is 000?
MCQ-24In the standard two-dimensional geometric picture of Grover's algorithm with N basis states and M marked items, what is the rotation angle θ of one Grover iteration, and how does it depend on M and N?
MCQ-11A 4-qubit Grover circuit (N = 16) uses a phase oracle to mark |1011⟩. The team halts the circuit right after the oracle call, before the diffusion operator, and measures: |1011⟩ still appears with probability 1/16. What did the oracle do to the state vector?
MCQ-12A Grover search runs on 3 qubits (N = 8) with exactly one marked item. After the oracle call the amplitude of the marked item is -1/√8 and each of the other seven amplitudes is +1/√8. The diffusion step D = 2|s⟩⟨s| - I is then applied once, where |s⟩ is the uniform superposition. What is the amplitude of the marked item immediately after this diffusion step?
MCQ-15A Grover search runs the standard noise-free iterate over N = 16 equally likely items with exactly one marked item, so with sin(theta) = 1/sqrt(16) we have theta = arcsin(0.25) = 0.2527 rad, and the marked amplitude after k iterations is sin((2k+1)*theta). The best count for this instance is 3 iterations, giving a success probability of about 0.96. A scheduling bug runs 6 iterations before the register is measured. What is the success probability at that point?
MCQ-10A team has an unsorted list of N = 1,000,000 entries and one marked target. They implement Grover's algorithm with an oracle that flips the phase of the marked entry. They run the standard optimal number of iterations, k = floor((π/4)√N). Which outcome should they expect?
MCQ-14A team runs Grover's search over a database of N = 1,000,000 marked-free entries with exactly one marked item, using an ideal (noise-free) quantum simulator. They want the highest probability of measuring the marked item in a single run. Roughly how many Grover iterations should they apply before measurement?
MCQ-1A team implements Grover's search over a space of N = 2^20 items with exactly one marked element. Their oracle is a reversible circuit of 9,000 gates, and the diffusion operator adds 1,000 gates per iteration. They run the optimal number of iterations, ⌊(π/4)√N⌋. A reviewer asks for the total gate count of the run. What should the team report?
MCQ-23A team is writing up a Grover search for a single marked item over a 12-qubit register (N = 4096) and plans the textbook (pi/4) * sqrt(N) = about 50 iterations. On the target device the transpiler reports 66 CX gates for each 12-qubit multi-controlled Z, and there is one in the oracle and one in the diffusion operator. The H and X layers add 48 single-qubit gates per iteration. CX error is 1e-3; single-qubit error is negligible. The resource report also lists each multi-controlled Z as one opaque gate. Which two-qubit cost and error estimate should the paper quote for the full run?
MCQ-13A team runs Grover's algorithm on a database of N=1024 items with exactly one marked item. They apply 50 iterations, measure, and the marked item appears in about 0.02% of shots. Their simulator uses the standard oracle and diffusion operator. What best explains the result?
MCQ-20An 8-qubit Grover search (N = 256) uses a phase oracle: a reversible circuit writes f(x) into a fresh ancilla prepared in |0>, a Z is then applied to that ancilla, and the joint state goes straight into the diffusion operator. After 10 iterations the marked input still measures 1/256, and a state-vector check of the state leaving the oracle shows the register's reduced density matrix is exactly (1/256)I, with every off-diagonal term zero. Which reading of the failure, and which change, fix it?
MCQ-17A team runs Grover's algorithm on N items but does not know how many are marked, M. They fix the iteration count to the optimum for M=1. Why can this fixed count return a non-marked item with high probability?
MCQ-16A team runs Grover's algorithm on a search space of N = 2^20 items with M = 16 marked solutions. They budget (π/4)√N ≈ 804 iterations, the single-solution optimum, and measure a success probability of about 4×10⁻⁶. What should they do?
MCQ-18An engineer runs standard Grover on N=2^20 items with k=804 iterations. The oracle marks exactly one item if a solution exists, and marks nothing if none exists. The measured bitstring x is not marked by the oracle. The engineer claims this run certifies that no solution exists. Which statement about that claim is correct?
MCQ-19A team runs Grover's algorithm on a 20-qubit register to find one marked item in a space of N = 2^20. After the optimal number of iterations, the algorithm's success probability is 0.99999988. The quantum computer's readout has a 1% error rate per qubit. What is the correct operational response to ensure the team returns only the marked item?
MCQ-22A team has K = 10^4 quantum computers and wants to brute-force a 64-bit key by unstructured search over N = 2^64 candidates. They split the keyspace into 10^4 equal, disjoint chunks and run Grover's algorithm on one chunk per machine, all in parallel. Compared with one machine running Grover over the whole space, roughly what wall-clock speedup should they expect?
MCQ-21A team wants to find a row in a 2^40-row table and proposes Grover's algorithm, counting √N ≈ 2^20 oracle calls against the 2^40 classical scans. The table is 1 TB on NVMe and the oracle would be a reversible circuit over QRAM. Which consideration decides whether the proposal is a real speedup?