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 QA: 25
Edition: v2
Editorial status: Reviewed
Relevant for: Quantum Software Engineer

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

Interview QA

Treat each question like a live interview question: answer out loud first (structure, assumptions, tradeoffs), then open the model answer to spot gaps and rehearse a tighter follow-up.

Curated: 2026-10-05 · Written: 2026-10-05 · Reviewed: 2026-10-04

QA-1

How does the quantum black-box query model differ from classical query complexity, and how is an oracle represented as a unitary transformation?

QA-2

How does preparing an ancilla in the |-⟩ state convert a bit-flip oracle |x⟩|y⟩ → |x⟩|y ⊕ f(x)⟩ into a phase oracle |x⟩ → (-1)^f(x)|x⟩ via phase kickback?

QA-3

How does the Deutsch-Jozsa algorithm determine whether a function is constant or balanced in a single query?

QA-4

Why must quantum oracles be reversible unitaries, and how do you implement a classical boolean function f(x) reversibly without leaving uncomputed garbage entangled with the output?

QA-5

How does the Deutsch algorithm differ from Deutsch-Jozsa, and why does Deutsch-Jozsa yield an exponential separation in exact query complexity but not under bounded error?

QA-6

Design and validate a quantum query workflow for Deutsch-Jozsa interference.

QA-7

Design and validate a quantum query workflow for DJ query advantage.

QA-8

Design and validate a quantum query workflow for DJ output decoding.

QA-9

Design and validate a quantum query workflow for Bernstein-Vazirani relation.

QA-10

Design and validate a quantum query workflow for Grover problem.

QA-11

Design and validate a quantum query workflow for phase oracle.

QA-12

Design and validate a quantum query workflow for diffusion.

QA-13

Design and validate a quantum query workflow for two reflections.

QA-14

Design and validate a quantum query workflow for iteration count.

QA-15

Design and validate a quantum query workflow for overshooting.

QA-16

Design and validate a quantum query workflow for multiple solutions.

QA-17

Design and validate a quantum query workflow for unknown solution count.

QA-18

Design and validate a quantum query workflow for zero solutions.

QA-19

Design and validate a quantum query workflow for candidate verification.

QA-20

Design and validate a quantum query workflow for oracle ancillas.

QA-21

Design and validate a quantum query workflow for data-loading cost.

QA-22

Design and validate a quantum query workflow for quadratic boundary.

QA-23

Design and validate a quantum query workflow for transpiled resources.

QA-24

Design and validate a quantum query workflow for shot evaluation.

QA-25