3. Quantum Algorithms

Deutschjozsa — Quiz

Test your understanding of deutschjozsa with 5 practice questions.

Practice Questions

Question 1

Which identity correctly describes the sum over all bitstrings $x\in\{0,1\}^n$ of the phase factor $(-1)^{x\cdot y}$?

Question 2

What is the expression for the amplitude $\alpha_y$ of the basis state $|y\rangle$ after the final Hadamard transform in the Deutsch–Jozsa algorithm?

Question 3

Which formula gives the probability of measuring $|0\rangle^{\otimes n}$ at the end of the Deutsch–Jozsa algorithm for an arbitrary Boolean function $f$?

Question 4

In complexity theory, the Deutsch–Jozsa problem is an example of a promise problem that belongs to which exact quantum complexity class?

Question 5

If the Boolean function $f(x)$ is constant with value $1$, what global phase does the oracle $U_f$ impart on the input superposition state $|\psi\rangle=\tfrac{1}{\sqrt{2^n}}\sum_x|x\rangle$?