Reversible Quantum Circuits for Modular Exponentiation

Hello! Welcome back to our exploration of foundational quantum algorithms.

In our last lesson, we completed the classical part of Shor's algorithm, establishing a high-probability reduction from the problem of factoring an integer $N$ to the problem of finding the order $r$ of a randomly chosen number $a$ modulo $N$ . This order-finding task, $a^{r} \equiv 1 (mod N)$ , is where quantum computation provides its exponential advantage.

Today, we will construct the very heart of that quantum advantage. Our learning outcome is to analyze the construction of a reversible quantum circuit for modular exponentiation based on the repeated squaring algorithm. This circuit implements the unitary operator $U$ that computes $a^{x} (mod N)$ . This operator is the crucial input to the Quantum Phase Estimation (QPE) algorithm, which we will use to find the period $r$ .

This lesson bridges the number-theoretic framework we've built with the practical quantum circuitry required to execute it.

1. The Classical Blueprint: Exponentiation by Squaring

Before building a quantum circuit, it's essential to understand the classical algorithm it's based on. The most efficient classical method for modular exponentiation is known as exponentiation by squaring (or binary exponentiation).

The core idea is to use the binary representation of the exponent $x$ . If $x$ is an $n$ -bit integer, we can write it as:

x = x_{n - 1} 2^{n - 1} + x_{n - 2} 2^{n - 2} + \dots + x_{1} 2^{1} + x_{0} 2^{0} = i = 0 \sum n - 1 x_{i} 2^{i}

where $x_{i} \in {0, 1}$ are the bits of $x$ .

Substituting this into the expression for $a^{x}$ gives:

a^{x} = a^{\sum_{i = 0}^{n - 1} x_{i} 2^{i}} = i = 0 \prod n - 1 a^{x_{i} 2^{i}}

Since $x_{i}$ is either 0 or 1, the term $a^{x_{i} 2^{i}}$ is either $a^{0} = 1$ or $a^{2^{i}}$ . This means we only include the term $a^{2^{i}}$ in the product if the corresponding bit $x_{i}$ is 1.

This transforms the problem of one large exponentiation into a series of multiplications. The algorithm proceeds as follows:

Initialize a result to 1.
Iterate from $i = 0$ to $n - 1$ :
- If bit $x_{i}$ is 1, multiply the result by $a^{2^{i}} (mod N)$ .

The terms $a^{2^{0}}, a^{2^{1}}, a^{2^{2}}, \dots, a^{2^{n - 1}}$ can be efficiently pre-computed classically by repeatedly squaring the previous term: $a^{2^{i}} = (a^{2^{i - 1}})^{2}$ .

This decomposition is the key to designing the quantum circuit.

2. From Classical Logic to a Quantum Circuit

The classical algorithm's structure—"if bit $x_{i}$ is 1, then perform a multiplication"—maps perfectly onto the concept of a controlled quantum operation.

We will design a quantum circuit that takes two registers as input:

An $n$ -qubit exponent register, which holds the state $∣ x ⟩ = ∣ x_{n - 1} \dots x_{0} ⟩$ . In the full Shor's algorithm, this register will be in a superposition of all possible exponents.
An $m$ -qubit result register, which will hold the computed value of $a^{x} (mod N)$ . This register must be large enough to store $N - 1$ , so we need $m = ⌈ lo g_{2} N ⌉$ qubits.

The following reading explains how to translate the classical repeated squaring logic into a sequence of quantum gates.

Shor's Algorithm - Intro to Quantum Software Development

This resource from MITRE's STEM program, titled 'Shor's Algorithm', clearly explains the 'binary substitution technique' and how it leads to a quantum circuit built from controlled modular multiplications.

Please read the sections 'The Modular Exponentiation Function' and 'Quantum Modular Exponentiation'. Focus on how the binary expansion of the exponent x transforms the problem into a series of multiplications, and how this naturally leads to using controlled quantum gates.

As the text explains, the quantum circuit will implement the following steps:

Initialize the result register to the state $∣1 ⟩$ .
For each qubit $∣ x_{i} ⟩$ in the exponent register (from $i = 0$ to $n - 1$ ):
- Apply a controlled modular multiplication operation.
- The control qubit is $∣ x_{i} ⟩$ .
- The target is the result register.
- The operation multiplies the value in the result register by the constant $c_{i} = a^{2^{i}} (mod N)$ .

Crucially, the values $c_{i}$ are pre-computed classically. The quantum circuit doesn't compute $a^{2^{i}}$ ; it simply implements the multiplication by this pre-computed constant, conditional on the state of $∣ x_{i} ⟩$ .

3. The Reversible Modular Exponentiation Circuit

Now we can visualize the complete circuit. It consists of the exponent and result registers, along with a sequence of controlled unitary gates, one for each bit of the exponent.

Caption: A quantum circuit diagram for the modular exponentiation $U|x\rangle|1\rangle = |x\rangle|a^x \pmod N\rangle$. The top register holds the exponent $|x\rangle$. The bottom register, initialized to $|1\rangle$, is the target for a series of controlled modular multiplication gates (`CMODMULT`). Each gate is controlled by a different qubit $x_i$ from the exponent register and performs a multiplication by a classically pre-computed constant $a^{2^i} \pmod N$. The gates labeled `CMODMULT^-1` are inverse operations, often required for uncomputation within the multiplier's internal workings to free up ancilla qubits.

Let's break down the components in this diagram:

Register 2 ( $∣ x ⟩$ ): This is the $n$ -qubit exponent register.
Register A ( $∣1 ⟩$ ): This is the $m$ -qubit result register, which accumulates the final product.
CMODMULT(a^(2^i) mod N): This represents a controlled modular multiplier. It is a unitary operation that performs the mapping $∣ y ⟩ \to ∣ y \cdot (a^{2^{i}} (mod N))⟩$ on the target register if the control qubit is $∣1 ⟩$ , and does nothing if it is $∣0 ⟩$ .

The entire circuit implements the transformation:

U_{a, N} : ∣ x ⟩ ∣1 ⟩ \mapsto ∣ x ⟩ ∣ a^{x} (mod N)⟩

This is exactly the unitary operator required for the period-finding stage of Shor's algorithm.

The Complexity of Modular Multiplication

We have treated the controlled modular multiplier as a black box. However, constructing this gate is the most resource-intensive part of Shor's algorithm. Building efficient quantum arithmetic circuits is a major area of research in quantum computing.

Given your background, you might appreciate the depth of this sub-problem. The following resource is a recent and comprehensive survey of quantum arithmetic circuits. You don't need to read it in its entirety, but browsing the introduction to the modular exponentiation section will give you a sense of the history and the different design strategies.

A Comprehensive Study of Quantum Arithmetic Circuits

This survey paper, 'A Comprehensive Study of Quantum Arithmetic Circuits', provides an excellent overview of the research landscape for constructing arithmetic operations, including modular exponentiation. It highlights the significant challenges and various approaches developed over the years.

Please read the first few paragraphs of Section 8, 'Quantum Modular Exponentiation' (up to the end of the paragraph discussing Beckman et al.). Also, take a look at Table 10. This will give you context on the foundational work and the distinction between different design philosophies (e.g., Clifford+T vs. QFT-based adders).

As you'll see from the paper, the first concrete proposals for these circuits by Vedral et al. and Beckman et al. in 1996 laid the groundwork. They constructed modular exponentiation from simpler blocks like quantum adders. The efficiency of these adders, multipliers, and the overall circuit architecture in terms of gate count, qubit count, and connectivity has been the subject of continuous improvement ever since.

4. Reversibility and Uncomputation

A fundamental requirement of quantum computation is that all operations (except measurement) must be unitary, and therefore reversible.

The modular exponentiation circuit we've constructed, $U ∣ x ⟩ ∣ y ⟩ = ∣ x ⟩ ∣ y \cdot a^{x} (mod N)⟩$ , is indeed unitary. Its inverse, $U^{†}$ , is given by:

U^{†} ∣ x ⟩ ∣ z ⟩ = ∣ x ⟩ ∣ z \cdot (a^{x})^{- 1} (mod N)⟩

where $(a^{x})^{- 1}$ is the modular multiplicative inverse of $a^{x}$ modulo $N$ . This inverse can be computed efficiently using the Extended Euclidean Algorithm. The circuit for $U^{†}$ would be constructed similarly, but using controlled modular multiplications by the inverse constants.

You may have noticed the CMODMULT^-1 gates in the circuit diagram. These are often necessary not for reversing the main computation, but for uncomputation of auxiliary (ancilla) qubits used inside each CMODMULT block. A quantum modular multiplier typically requires extra ancilla qubits to store intermediate results (e.g., in the adders). To make the block a clean unitary operation on just the target register and to allow the ancillas to be reused, these intermediate computations must be reversed, returning the ancillas to their initial $∣0 ⟩$ state. This is a critical principle in reversible circuit design.

Conclusion

In this lesson, we have dissected the construction of the modular exponentiation circuit, the computational core of Shor's algorithm.

Key Takeaways:

The quantum circuit for modular exponentiation is a direct translation of the classical exponentiation by squaring algorithm.
It uses the binary representation of the exponent $x$ to decompose the calculation into a sequence of controlled modular multiplications.
The circuit consists of an exponent register $∣ x ⟩$ controlling an output register, which is initialized to $∣1 ⟩$ .
Each qubit $∣ x_{i} ⟩$ controls a unitary gate that multiplies the output register by a pre-computed constant $a^{2^{i}} (mod N)$ .
The construction of the underlying modular multipliers is a complex field of research in its own right and represents the main cost of implementing Shor's algorithm.
The entire circuit is reversible, a fundamental requirement for quantum algorithms.

We have now built the specific unitary operator $U_{a, N}$ whose properties encode the period $r$ . In our next lesson, we will finally see how to use this operator within the Quantum Phase Estimation framework to extract this period, completing the quantum part of Shor's algorithm.