STRATA
Skip to study
XLVII

VII.09 / QUANTUM

Quantum computing

How many physical operations are needed to complete a logical circuit at a specified error rate?

A source-led introduction1 source references0 related experiments

Start with the question.

Quantum computing studies algorithms implemented through controlled quantum operations and measurement. Shor's factoring work provides a landmark theoretical example in which the structure of a problem changes the resource analysis. An implementation claim adds a second layer: physical qubits, logical operations, noise, error correction, and input/output costs. Keeping those layers visible makes a small demonstration informative without equating it with an arbitrary large-scale computation.

Separate a mathematical algorithm from a device run.

Draw a factoring workflow with classical preprocessing, quantum period finding, measurement, and classical postprocessing. For a small illustrative input, identify any values supplied in advance or compiled into the circuit. Then ask which resources must grow when the input becomes larger and the answer is no longer partly built into the setup.

What would you inspect?

  • Input size, logical gate count, measurement success probability, and error model.
  • Physical-to-logical overhead and the classical work included in the comparison.

Take the next step.

Choose a published quantum-computing demonstration and label which parts test the general algorithm and which depend on a specially prepared instance.

Read the supporting material.

  1. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer

    Peter W. Shor · Theoretical quantum algorithms and asymptotic resource claims.

Follow the comparisons.

Read the neighboring questions.