Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 39 ยท Projects and Practice

Quantum Computing Practice Problems with Worked Solutions

Ten practice problems on algorithms, error correction, noise, cryptography and gradients, each with a worked solution and runnable verification code.

The best way to make the ideas stick is to solve problems with pencil and paper first, then check the answer by running code. This page has ten problems that cover the algorithms, noise, error-correction, application and tooling lessons of this course. Try each problem before opening the solution. The runnable blocks recompute every answer.

Problems

1. Interference. Start with |0> and apply a Hadamard, then an S gate (diag(1, i)), then another Hadamard. What are the probabilities of measuring 0 and 1?

2. Grover scaling. How many Grover iterations are optimal when searching 2^20 items for a single marked one, and how many oracle calls would a classical random search need on average?

3. Deutsch-Jozsa. For two input qubits and the balanced function f(x1, x2) = x1 XOR x2, what is the amplitude of |00> on the input register after the final Hadamards?

4. QFT phases. For three qubits, compute the QFT of the basis state |5>. What is the magnitude of each amplitude and which phases (as multiples of 2*pi/8) appear?

5. Phase estimation. A unitary has an eigenphase phi = 0.8125. With 4 counting qubits, what integer is measured?

6. Error correction. Each physical qubit of the three-qubit bit-flip code flips independently with probability p = 0.05. What is the logical error probability?

7. Shor by hand. Find the order of 2 modulo 21 and use it to factor 21.

8. BB84 bookkeeping. Alice sends 1,000 qubits in random bases and Bob measures in random bases. How many sifted bits do you expect, and how many errors if Eve intercepts and resends every qubit?

9. Noise budget. A qubit has T1 = 80 us. What is the probability that a |1> state is still |1> after 40 us? If every gate has error 0.1%, how many gates can run before the success probability drops under 50%?

10. Gradients. After RY(theta) on |0>, the expectation <Z> equals cos(theta). Use the parameter-shift rule to compute the derivative at theta = 0.9 and compare it with the analytic one.

Solutions: problems 1 to 5

1. H sends |0> to |+>; S multiplies the |1> part by i, giving (|0> + i|1>)/sqrt(2); the second H gives amplitudes (1 + i)/2 and (1 - i)/2, each with magnitude squared 1/2. The result is a 50/50 split. The relative phase i is a quarter turn, which makes the two Hadamards act like a half-way rotation.

2. theta = asin(1 / sqrt(N)), k = round(pi / (4 * theta) - 1/2), about (pi/4) * sqrt(2^20) = 804 iterations. A classical search needs N/2 = 524,288 tries on average.

3. The amplitude of |00> is the average of (-1)^f(x) over all inputs. For the XOR function, two inputs give +1 and two give -1, so the average is 0 (as for any balanced function).

4. All amplitudes have magnitude 1/sqrt(8) = 0.3536. The amplitude of output k has phase 2*pi*5*k/8, so the phases (in units of 2*pi/8) are 5k mod 8 = 0, 5, 2, 7, 4, 1, 6, 3.

5. m = phi * 2^4 = 0.8125 * 16 = 13, binary 1101. Because phi is exactly representable with 4 bits, the outcome is certain.

Python Check problems 1 to 5

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions: problems 6 to 10

6. The code fails when at least two of the three qubits flip: 3p^2(1 - p) + p^3 = 3p^2 - 2p^3. For p = 0.05 that is 0.0075 - 0.00025 = 0.00725, about 0.7%, seven times better than 5%. See bit-flip codes.

7. The powers of 2 mod 21 are 2, 4, 8, 16, 11, 1, so the order is r = 6 (even). 2^3 = 8, and gcd(8 - 1, 21) = 7, gcd(8 + 1, 21) = 3. Hence 21 = 3 x 7. See Shor's algorithm.

8. About half the bases match: around 500 sifted bits. With intercept-resend, 25% of the sifted bits are wrong, about 125 errors. See BB84.

9. exp(-40/80) = e^-0.5 = 0.607. Gates: ln(0.5) / ln(0.999) = 692. See noise and decoherence.

10. (cos(theta + pi/2) - cos(theta - pi/2)) / 2 = (-sin(theta) - sin(theta)) / 2 = -sin(theta), which at 0.9 is about -0.783. See PennyLane and the parameter-shift rule.

Python Check problems 6 to 10 (with a simulation for 8)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Going further

When you can solve these quickly, try the following challenges on your own:

  • Modify problem 3 for three input qubits with a function that is neither constant nor balanced. What does the algorithm output, and why is the promise important?
  • Implement quantum counting: run phase estimation on the Grover iteration for a small N and recover the number of marked items.
  • Extend the Grover SAT solver to 3-coloring of a small graph.
  • Add depolarizing noise to the quantum walk and find the noise level at which the speed advantage disappears.
  • Compute the circuit fidelity (1 - epsilon)^G for the QFT circuit of 20 qubits with epsilon = 10^-3. What does it tell you about running it without error correction?

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. After H, S, H on |0>, what are the probabilities of 0 and 1?

    The amplitudes are (1+i)/2 and (1-i)/2, each with magnitude squared 1/2.
  2. 2. A phase eigenvalue phi = 0.8125 with 4 counting qubits gives which measurement?

    0.8125 * 16 = 13 = 1101 in binary.
  3. 3. What is the logical error rate of the 3-qubit bit-flip code at p = 0.05?

    3p^2 - 2p^3 = 0.0075 - 0.00025 = 0.00725.
  4. 4. What is the order of 2 modulo 21?

    2^6 = 64 = 3 * 21 + 1, and no smaller power equals 1.

Summary

  • Pencil-and-paper reasoning plus a quick simulation is the fastest way to build intuition.
  • Key formulas: Grover k ~ (pi/4) sqrt(N/M), QPE m = phi * 2^t, bit-flip code 3p^2 - 2p^3, BB84 25% error under intercept-resend, noise decay exp(-t/T1), parameter shift (f(theta + pi/2) - f(theta - pi/2)) / 2.
  • Make your own variations of these problems, and verify them in code.

Next: back to the Quantum Computing track