Self-Assessment Quiz: Deutsch-Jozsa and Bernstein-Vazirani

Twenty questions on the first quantum algorithms, oracle models, promise problems, and how seriously to take their speedups. Aim for 16+.

Question 1

Deutsch–Jozsa decides whether $f:\{0,1\}^n\to\{0,1\}$ is:

A) Injective or surjective B) Constant or balanced, given a promise that it is one of the two C) Linear or nonlinear D) Computable

Question 2

Classically, deciding this with certainty requires in the worst case:

A) 1 query B) $n$ queries C) $2^{n-1}+1$ queries D) $2^n$ queries

Question 3

Deutsch–Jozsa requires:

A) 1 query B) $n$ queries C) $\sqrt{2^n}$ queries D) $2^n$ queries

Question 4

Classically, with a randomized algorithm accepting small error probability, you need:

A) $2^{n-1}+1$ queries B) $O(1)$ queries C) $O(n)$ queries D) $O(2^n)$

Question 5

That last fact means the Deutsch–Jozsa speedup is:

A) Exponential over any classical method B) Exponential only over deterministic classical algorithms C) Nonexistent D) Quadratic

Question 6

The final measurement in Deutsch–Jozsa gives all zeros iff:

A) $f$ is balanced B) $f$ is constant C) $f$ is linear D) Always

Question 7

Bernstein–Vazirani finds the hidden string $s$ in $f(x) = s\cdot x \bmod 2$ using:

A) 1 query B) $n$ queries C) $2^n$ queries D) $\log n$ queries

Question 8

Classically, finding $s$ requires:

A) 1 query B) $n$ queries C) $2^n$ queries D) $n^2$ queries

Question 9

So Bernstein–Vazirani's speedup is:

A) Exponential B) Linear ($n\to1$) C) Quadratic D) None

Question 10

The state after the oracle in Bernstein–Vazirani is:

A) $\frac{1}{\sqrt{2^n}}\sum_x(-1)^{s\cdot x}|x\rangle$ B) $|s\rangle$ C) Uniform with no phases D) Entangled with the ancilla

Question 11

Applying $H^{\otimes n}$ to that state yields:

A) Uniform superposition B) $|s\rangle$ exactly C) $|0\rangle$ D) A random state

Question 12

The oracle in these algorithms is:

A) A physical device you buy B) A black box counted per query — the resource being measured C) Always free D) Classical only

Question 13

A "promise problem" is one where:

A) Any input is allowed B) Inputs are guaranteed to satisfy a condition, and behavior is unconstrained otherwise C) The answer is probabilistic D) The oracle may lie

Question 14

Deutsch–Jozsa's practical importance is mainly:

A) Direct application to real problems B) Historical and conceptual — the first provable exponential separation in the query model C) Cryptanalysis D) Chemistry simulation

Question 15

Building the oracle circuit for a given $f$ typically costs:

A) Nothing B) Gates that may exceed the query savings C) Exactly one gate D) $2^n$ measurements

Question 16

True or false: Deutsch–Jozsa proves quantum computers beat classical ones on practical problems.

Question 17

True or false: Bernstein–Vazirani's output is deterministic on a noiseless device.

Question 18

True or false: These algorithms need entanglement between the input qubits.

Question 19

Short answer. Explain why the query-model speedup can be misleading when the oracle must be built from gates.

Question 20

Short answer. Why is Bernstein–Vazirani a good hardware benchmark despite being a modest speedup?

Answer Key