Compiling Shor’s algorithm for any RSA key size in seconds: scalability and structure in the Qmod compiler
Traditional quantum compilers output circuits: flat descriptions in which loops are unrolled and subroutines are duplicated for different parameter values. At an industrially relevant scale, however, executing an algorithm may involve millions or billions of primitive quantum operations (gates), even at the logical level. Expanding these algorithms into flat descriptions produces enormous programs and makes downstream processing prohibitively expensive. Hybrid workflows add another reason to preserve structure: they typically require many invocations of the same quantum subroutine with different parameter values.
Over the past six months, the Qmod compiler has undergone significant scalability improvements. At the center of this work is the compiler’s ability to preserve classical control structures—loops and conditionals—throughout quantum synthesis and decomposition. This starts with algorithms that repeatedly apply the same quantum operation, such as the Grover operator in amplitude amplification. These can be expressed directly using Qmod’s repeat or power statements. It extends to algorithms that repeat a sequence of operations with different classical parameter values on each iteration, such as quantum singular value transformation (QSVT) and generalized quantum signal processing (GQSP). Here, a foreach statement can iterate directly over phase values, or a repeat statement can use its iteration variable to index a classical array.
The biggest leap in scalability, however, comes from allowing classical iteration variables to index quantum arrays while keeping the loops intact. This enables scalable implementations of arithmetic building blocks, such as addition and multiplication, as well as algorithmic primitives such as the quantum Fourier transform (QFT) and quantum phase estimation (QPE). Implementations of built-in arithmetic operations now use symbolic qubit-array indices, allowing them to support large operand widths without unrolling their underlying loops. Similarly, functions in the Qmod open library can operate on symbolic classical parameters. As a result, the quantum period-finding subroutine in Shor’s algorithm—which uses QPE to estimate eigenphases of a modular multiplication operator—can be synthesized in nearly constant time as the input size increases.
The following is the definition of the quantum period-finding function in Qmod, using the open library’s modular multiplication function.
@qfunc
def period_finding(n: CInt, a: CInt, x: QNum, phase: QArray[QBit]):
# Prepare |1>, a superposition of eigenstates of modular multiplication.
x ^= 1
# Estimate eigenphases of the operator |x> -> |a*x mod n>.
hadamard_transform(phase)
repeat(
phase.len,
lambda k: control(
phase[k],
lambda: modular_multiply_classical_inplace(
n, (a ** (2**k)) % n, x
),
),
)
invert(lambda: qft(phase))
For the 2048-bit semiprime shown below (the size used in modern RSA) the quantum program synthesizes in under ten seconds on the Classiq platform. The coprime a is an execution parameter of main, so the same compiled quantum program can be reused across successive choices of a during Shor’s algorithm. For a fixed N, compilation is required only once.
N = int(
"21170383400786111141058284989338219359768030480050406213106590317579889531699998"
"41875217490157971480249653090834225086695833966118663652783833058435961681335833"
"18190825520919599583377482818832068135024118066518713937848498912837736392917008"
"62756762023279457031990894813410073313606401145611964169950684697278716262330619"
"03103699635022231706548229096384022068299331912898510443780121519090708926395412"
"88487843246007537585594999077820591829813075114316015051706851721327909171345554"
"21235645745667447023774693639249322161518368964328177384094886280859764055335985"
"636527124537798743504452936495967714448129324816924757873"
)
NUM_BITS = N.bit_length()
PHASE_BITS = 2 * NUM_BITS
@qfunc
def main(
a: CInt,
phase: Output[QNum[PHASE_BITS, UNSIGNED, PHASE_BITS]],
):
# phase represents a fraction in [0, 1).
x = QNum()
allocate(NUM_BITS, x)
allocate(phase)
period_finding(N, a, x, phase)
drop(x)
qprog = synthesize(main)Executing large quantum algorithms remains well beyond the reach of current quantum hardware, and classical simulation is practical only for toy-scale instances. Execution backends also differ in the control-flow and qubit-indexing features they support, even when they accept formats such as QIR or OpenQASM 3.0. Compiler scalability in this respect primarily enables programmers to analyze and reason about realistic-scale algorithms. It also provides a foundation for execution systems that can run structured quantum programs as hardware capabilities advance.
Traditional quantum compilers output circuits: flat descriptions in which loops are unrolled and subroutines are duplicated for different parameter values. At an industrially relevant scale, however, executing an algorithm may involve millions or billions of primitive quantum operations (gates), even at the logical level. Expanding these algorithms into flat descriptions produces enormous programs and makes downstream processing prohibitively expensive. Hybrid workflows add another reason to preserve structure: they typically require many invocations of the same quantum subroutine with different parameter values.
Over the past six months, the Qmod compiler has undergone significant scalability improvements. At the center of this work is the compiler’s ability to preserve classical control structures—loops and conditionals—throughout quantum synthesis and decomposition. This starts with algorithms that repeatedly apply the same quantum operation, such as the Grover operator in amplitude amplification. These can be expressed directly using Qmod’s repeat or power statements. It extends to algorithms that repeat a sequence of operations with different classical parameter values on each iteration, such as quantum singular value transformation (QSVT) and generalized quantum signal processing (GQSP). Here, a foreach statement can iterate directly over phase values, or a repeat statement can use its iteration variable to index a classical array.
The biggest leap in scalability, however, comes from allowing classical iteration variables to index quantum arrays while keeping the loops intact. This enables scalable implementations of arithmetic building blocks, such as addition and multiplication, as well as algorithmic primitives such as the quantum Fourier transform (QFT) and quantum phase estimation (QPE). Implementations of built-in arithmetic operations now use symbolic qubit-array indices, allowing them to support large operand widths without unrolling their underlying loops. Similarly, functions in the Qmod open library can operate on symbolic classical parameters. As a result, the quantum period-finding subroutine in Shor’s algorithm—which uses QPE to estimate eigenphases of a modular multiplication operator—can be synthesized in nearly constant time as the input size increases.
The following is the definition of the quantum period-finding function in Qmod, using the open library’s modular multiplication function.
@qfunc
def period_finding(n: CInt, a: CInt, x: QNum, phase: QArray[QBit]):
# Prepare |1>, a superposition of eigenstates of modular multiplication.
x ^= 1
# Estimate eigenphases of the operator |x> -> |a*x mod n>.
hadamard_transform(phase)
repeat(
phase.len,
lambda k: control(
phase[k],
lambda: modular_multiply_classical_inplace(
n, (a ** (2**k)) % n, x
),
),
)
invert(lambda: qft(phase))
For the 2048-bit semiprime shown below (the size used in modern RSA) the quantum program synthesizes in under ten seconds on the Classiq platform. The coprime a is an execution parameter of main, so the same compiled quantum program can be reused across successive choices of a during Shor’s algorithm. For a fixed N, compilation is required only once.
N = int(
"21170383400786111141058284989338219359768030480050406213106590317579889531699998"
"41875217490157971480249653090834225086695833966118663652783833058435961681335833"
"18190825520919599583377482818832068135024118066518713937848498912837736392917008"
"62756762023279457031990894813410073313606401145611964169950684697278716262330619"
"03103699635022231706548229096384022068299331912898510443780121519090708926395412"
"88487843246007537585594999077820591829813075114316015051706851721327909171345554"
"21235645745667447023774693639249322161518368964328177384094886280859764055335985"
"636527124537798743504452936495967714448129324816924757873"
)
NUM_BITS = N.bit_length()
PHASE_BITS = 2 * NUM_BITS
@qfunc
def main(
a: CInt,
phase: Output[QNum[PHASE_BITS, UNSIGNED, PHASE_BITS]],
):
# phase represents a fraction in [0, 1).
x = QNum()
allocate(NUM_BITS, x)
allocate(phase)
period_finding(N, a, x, phase)
drop(x)
qprog = synthesize(main)Executing large quantum algorithms remains well beyond the reach of current quantum hardware, and classical simulation is practical only for toy-scale instances. Execution backends also differ in the control-flow and qubit-indexing features they support, even when they accept formats such as QIR or OpenQASM 3.0. Compiler scalability in this respect primarily enables programmers to analyze and reason about realistic-scale algorithms. It also provides a foundation for execution systems that can run structured quantum programs as hardware capabilities advance.
