3. Quantum Algorithms

Shoralgorithm — Quiz

Test your understanding of shoralgorithm with 5 practice questions.

Practice Questions

Question 1

Which part of Shor’s algorithm generally dominates the total number of quantum gates required for factoring an n-bit integer?

Question 2

After obtaining a candidate period r from the continued fraction expansion, which mathematical condition must be verified to confirm that r is the correct order?

Question 3

Which quantum mechanical principle allows Shor’s algorithm to evaluate $a^x \bmod N$ simultaneously for all x in superposition?

Question 4

What is the typical classical bit-complexity of computing $a^x \bmod N$ for an n-bit integer $N$ using repeated squaring and naive multiplication?

Question 5

For an n-bit integer $N$, how many qubits are required in the first register to ensure the Quantum Fourier Transform has sufficient resolution for period finding?