Technical interview guide

Quantum Algorithms II: Shor's Algorithm & Cryptographic Implications

How Shor's algorithm factors integers exponentially faster than any known classical method, and why that breaks RSA/ECC and drives the shift to post-quantum cryptography.

Read: 56 min
Practice MCQs: 25
Interview QA: 25
Edition: v2
Editorial status: Review pending
Relevant for: Quantum Software Engineer

Scope: IBM Quantum current Shor/QPE documentation; Shor primary paper; NIST FIPS 203/204/205, IR 8547 draft, SP 800-57, and crypto-agility guidance 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 Shor's algorithm reduce integer factorization to order finding, and what are the exact classical and quantum steps involved?

QA-2

How is Shor's algorithm adapted to solve the discrete logarithm problem over elliptic curve groups (ECDLP), and why does it break standard curves like Ed25519 or secp256k1 using fewer logical qubits than RSA-2048?

QA-3

How do Quantum Phase Estimation and the Quantum Fourier Transform work together to find the order r in Shor's algorithm?

QA-4

What are the primary circuit and computational bottlenecks when implementing reversible modular exponentiation in Shor's algorithm on fault-tolerant hardware?

QA-5

How do continued fractions extract the candidate period r from the phase estimation measurement, and under what conditions does this classical post-processing step fail?

QA-6

Design and validate a Shor or post-quantum migration workflow for controlled powers.

QA-7

Design and validate a Shor or post-quantum migration workflow for phase estimation.

QA-8

Design and validate a Shor or post-quantum migration workflow for inverse QFT.

QA-9

Design and validate a Shor or post-quantum migration workflow for continued fractions.

QA-10

Design and validate a Shor or post-quantum migration workflow for even order.

QA-11

Design and validate a Shor or post-quantum migration workflow for plus-minus condition.

QA-12

Design and validate a Shor or post-quantum migration workflow for factor extraction.

QA-13

Design and validate a Shor or post-quantum migration workflow for classical verification.

QA-14

Design and validate a Shor or post-quantum migration workflow for RSA impact.

QA-15

Design and validate a Shor or post-quantum migration workflow for ECC impact.

QA-16

Design and validate a Shor or post-quantum migration workflow for symmetric distinction.

QA-17

Design and validate a Shor or post-quantum migration workflow for harvest now.

QA-18

Design and validate a Shor or post-quantum migration workflow for finalized standards.

QA-19

Design and validate a Shor or post-quantum migration workflow for signature choices.

QA-20

Design and validate a Shor or post-quantum migration workflow for crypto inventory.

QA-21

Design and validate a Shor or post-quantum migration workflow for crypto agility.

QA-22

Design and validate a Shor or post-quantum migration workflow for hybrid migration.

QA-23

Design and validate a Shor or post-quantum migration workflow for resource realism.

QA-24

Design and validate a Shor or post-quantum migration workflow for demo boundary.

QA-25