Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/itsubaki/qasm-playground/llms.txt

Use this file to discover all available pages before exploring further.

Shor’s algorithm finds the prime factors of an integer by reducing the problem to period-finding, which a quantum computer solves exponentially faster than any known classical method. This example factors N=15 using base a=7: it finds the order r such that 7^r ≡ 1 (mod 15), then computes the factors using the greatest common divisor.

​
Circuit overview

The circuit uses 3 phase-estimation qubits (q) and 4 ancilla qubits (a) initialized to |1⟩ (via x a[3]). Applying Hadamard to q creates superposition, then the controlled modular exponentiation encodes the period into the phase, and the inverse QFT extracts it.
Shor's Algorithm (N=15, a=7)
// Shor's Algorithm (N=15, a=7)
//
// Uses phase estimation to find the order r of 7 mod 15.
// where r is the order such that a^r ≡ 1 (mod N).
// From the measured phase (e.g., 1/4 or 3/4), we recover r = 4,
// which yields the factors 3 and 5.
//
// 010: 0.010 = 0.25 = 1/4; r=4.
// 110: 0.110 = 0.75 = 3/4; r=4.
// otherwise: reject and repeat.
//
// gcd(pow(a, r/2)-1, N) = gcd(pow(7, 4/2)-1, 15) = 3.
// gcd(pow(a, r/2)+1, N) = gcd(pow(7, 4/2)+1, 15) = 5.

OPENQASM 3.0;

gate x q { U(pi, 0, pi) q; }
gate h q { U(pi/2.0, 0, pi) q; }
gate cx c, t { ctrl @ U(pi, 0, pi) c, t; }
gate ccx c0, c1, t { ctrl(2) @ U(pi, 0, pi) c0, c1, t; }
gate cr(theta) c, t { ctrl @ U(0, 0, theta) c, t; }

def modexp(qubit[3] q, qubit[4] a) {
    // controlled-U^(2^0)
    cx q[0], a[1];
    cx q[0], a[2];

    // controlled-U^(2^1)
    cx        a[0], a[2];
    ccx q[1], a[2], a[0];
    cx        a[0], a[2];

    cx        a[3], a[1];
    ccx q[1], a[1], a[3];
    cx        a[3], a[1];
}

def inv_qft(qubit[3] q) {
    h q[2];

    cr(-pi/2) q[2], q[1];
    h q[1];

    cr(-pi/4) q[2], q[0];
    cr(-pi/2) q[1], q[0];
    h q[0];
}

// N=15, a=7
qubit[3] q;
qubit[4] a;
reset q;
reset a;

h q;
x a[3];

modexp(q, a);
inv_qft(q);

measure a;

​
Reading the results

After running, the ancilla register a is measured. The meaningful outcomes and their interpretation:
Measured aBinary fractionPhase φOrder rFactors
0100.010 = 0.251/443 and 5
1100.110 = 0.753/443 and 5
other——rejectretry
From the order r=4, compute the factors using GCD:
  • gcd(7^(4/2) − 1, 15) = gcd(48, 15) = 3
  • gcd(7^(4/2) + 1, 15) = gcd(50, 15) = 5
Shor’s algorithm is probabilistic. If you measure a state other than 010 or 110, the run is discarded and repeated. The useful outcomes occur with roughly 50% probability.

​
How the circuit works

1

Initialize

Three phase-estimation qubits q start in |0⟩. Four ancilla qubits a start in |0001⟩ (the number 1 mod 15), set by x a[3].
2

Superposition

Hadamard gates h q put all three phase-estimation qubits into equal superposition, creating a uniform sum over all 8 input states.
3

Controlled modular exponentiation

modexp(q, a) applies controlled-U^(2^i) operations. Each controlled step multiplies the ancilla register by 7^(2^i) mod 15 when the corresponding control qubit is |1⟩. This encodes the periodic structure of 7^x mod 15 into entangled phase.
4

Inverse QFT

inv_qft(q) extracts the period from the phase register. It applies a 3-qubit inverse quantum Fourier transform using Hadamard gates and controlled-phase rotations.
5

Measure and interpret

Measure a. Convert the 3-bit result to a binary fraction to get the phase φ, then use continued fractions to recover r. Finally, compute gcd(a^(r/2)±1, N) to obtain the prime factors.
This circuit uses 7 total qubits (3 phase + 4 ancilla), well within the 12-qubit limit. The modular exponentiation subroutine is hardcoded for a=7, N=15 — a general implementation would require significantly more qubits and gates.

Build docs developers (and LLMs) love

Get started for freeTalk to us