Quantum ComputingAlgorithmsUniversity

AQAAPOntarioNSWCBSEGCE O-LevelMoECAPS

Shor's Algorithm (Period Count)

Q: What are some study tips for the Shor's Algorithm (Period Count) formula?

Identify k by finding the smallest power of two that is greater than N. The value n corresponds to the number of qubits in the evaluation register, not the modular exponentiation register. Always round k up to the nearest integer bit-count before doubling it to find n.

Relationship between period 'r' and the number of qubits 'n' for integer factoring.

Understand the formulaSee the free derivationOpen the full walkthrough

n_{bi t s} \approx 2 k where N < 2^{k}

Open Full Walkthrough Try Calculator

This public page keeps the free explanation visible and leaves premium worked solving, advanced walkthroughs, and saved study tools inside the app.

Core idea

Overview

Shor's algorithm uses quantum phase estimation to find the period of modular exponentiation, a crucial step for factoring integers. To achieve the necessary precision for the continued fraction algorithm to succeed, the work register size (n) must be approximately double the bit-length (k) of the number being factored (N).

When to use: This formula is applied when determining the hardware requirements for the quantum period-finding routine. It specifically dictates the size of the first register (the precision register) needed to resolve the phase of the unitary operator to sufficient accuracy.

Why it matters: This relationship defines the scalability of quantum attacks on RSA encryption. Because n is proportional to the bit-length of N, doubling the encryption key size effectively doubles the number of qubits required in the precision register, highlighting the resource-intensive nature of quantum cryptanalysis.

Symbols

Variables

n = Required Qubits, N = Integer to Factor

n

Required Qubits

V a r iab l e

N

Integer to Factor

V a r iab l e

Walkthrough

Derivation

Formula: Shor's Algorithm — Period Finding Qubit Count

The number of qubits required for the quantum Fourier transform register in Shor's period-finding algorithm.

n = number of bits in the integer N to be factored.
The first register must have enough qubits to represent all residues mod N.

Required Qubits for QFT Register:

The QFT register needs at least 2n qubits so that the period r can be resolved with sufficient precision.

q \geq 2 n, where 2^{n} > N

Total Qubits:

Including the second register (n qubits for f(x) = $a^{x}$ mod N), Shor's algorithm requires approximately 3n qubits to factor an n-bit integer.

q_{total} = 2 n + n = 3 n

Result

q_{total} = 2 n + n = 3 n

Source: University Quantum Computing — Algorithms

Visual intuition

Graph

Graph unavailable for this formula.

The graph is a linear function where the number of qubits (n) increases proportionally as the bit-length (k) of the integer grows. Because the relationship is defined by a constant multiplier of two, the plot forms a straight line passing through the origin with a constant positive slope.

Graph type: linear

Why it behaves this way

Intuition

Visualize the quantum computer as a precision instrument, where the number of measurement 'ticks' (qubits in the precision register) must be roughly double the 'length' (bit-size)

n_{bi t s}

The number of qubits in the first quantum register (precision register) used for phase estimation.

This register stores the result of the quantum Fourier transform; more qubits here mean higher precision in measuring the phase, which directly translates to a more accurate determination of the period.

The number of bits required to represent the integer N (i.e., k is the smallest integer such that N < 2^k).

This value quantifies the 'size' or 'complexity' of the number N. A larger k means N is a larger number, requiring more computational resources.

The composite integer whose prime factors Shor's algorithm aims to find.

This is the target number for the factoring problem. Its magnitude dictates the scale of the quantum computation required.

Free study cues

Insight

Canonical usage

This equation relates the number of qubits and the bit-length of an integer, both of which are dimensionless counts.

Common confusion

Students might mistakenly try to assign physical units to 'qubits' or 'bits' instead of treating them as dimensionless counts or integer representations.

Dimension note

All quantities in this equation (number of qubits, bit-length, and the integer itself) are dimensionless counts or integer values, not physical quantities with units.

Unit systems

$n_{bi t s}$ qubits · The number of qubits in the precision register required for Shor's algorithm.

$k$ bits · The bit-length of the integer N, defined by N < 2^k.

$N$ integer value · The integer to be factored by Shor's algorithm.

Ballpark figures

Quantity:

One free problem

Practice Problem

If you are using Shor's algorithm to factor the number 15, what is the required number of qubits (n) in the first register?

Integer to Factor15

Solve for: $n$

Hint: Find the smallest integer k such that 2 to the power of k is greater than 15, then multiply by 2.

The full worked solution stays in the interactive walkthrough.

Study smarter

Tips

Identify k by finding the smallest power of two that is greater than N.
The value n corresponds to the number of qubits in the evaluation register, not the modular exponentiation register.
Always round k up to the nearest integer bit-count before doubling it to find n.

Common questions

Frequently Asked Questions

The number of qubits required for the quantum Fourier transform register in Shor's period-finding algorithm.

This formula is applied when determining the hardware requirements for the quantum period-finding routine. It specifically dictates the size of the first register (the precision register) needed to resolve the phase of the unitary operator to sufficient accuracy.

This relationship defines the scalability of quantum attacks on RSA encryption. Because n is proportional to the bit-length of N, doubling the encryption key size effectively doubles the number of qubits required in the precision register, highlighting the resource-intensive nature of quantum cryptanalysis.