⚛️ quantum physics

Asymptotic yet practical optimization of quantum circuits implementing GF( $2^m$ ) multiplication and division operations

This paper presents asymptotically and practically optimized, ancilla-free quantum circuits for GF( $2^m$ ) multiplication and division that significantly reduce gate count complexities and improve performance for cryptographically relevant parameters through efficient constant polynomial multiplication and strategic selection of irreducible polynomials.

Original authors: Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Noureldin Yosri, Dmytro Gavinsky, Dmitri Maslov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a super-fast calculator, but instead of adding numbers, you are multiplying and dividing "polynomials" (which are just fancy algebraic expressions like $x^2 + 1$ ) inside a special mathematical world called Galois Field $GF(2^m)$ .

This isn't just for math class; this specific type of math is the secret sauce behind modern encryption (keeping your bank data safe) and future quantum computers.

The problem is: doing these calculations on a quantum computer is incredibly expensive. It's like trying to build a skyscraper using only tiny, fragile Lego bricks. Every time you make a mistake or use too many bricks, the whole thing collapses (or in quantum terms, the calculation fails due to noise).

This paper, written by researchers from Google Quantum AI and the Czech Academy of Sciences, is like a master architect who just redesigned the blueprints to use fewer bricks, stronger foundations, and a much faster construction method.

Here is the breakdown of their breakthroughs using simple analogies:

1. The "Multiplication" Problem: The Bottleneck

The Old Way:
Imagine you are trying to multiply two huge numbers. The standard method (Karatsuba algorithm) is like a smart assembly line. However, there was one specific step in the process—multiplying by a "constant" (a fixed number)—that was incredibly slow and messy.

The Analogy: Think of the assembly line as a highway. The multiplication step was a massive, 10-lane traffic jam where cars (data) had to weave through each other. The old method required a number of "CNOT gates" (the basic switches that move data) that grew quadratically ( $m^2$ ). If you doubled the size of the number, the traffic jam got four times worse.

The New Solution:
The authors found a way to fix that specific traffic jam. They discovered a special type of "road layout" (an irreducible polynomial) that allows that constant multiplication step to be done in a straight line.

The Result: They turned the 10-lane traffic jam into a single-lane highway. The complexity dropped from quadratic ( $m^2$ ) to linearithmic ( $m \log m$ ).
The Impact: For practical sizes used in real-world encryption, this isn't just a small improvement; it's a 100x to 350x speedup in efficiency. They saved thousands of "bricks" (gates) that would have been wasted.

2. The "Division" Problem: The Inverse Puzzle

The Old Way:
Dividing in this math world is actually just multiplying by the "inverse" (like how dividing by 2 is multiplying by 0.5). To find this inverse, the old method used a recipe called the "Itoh-Tsujii algorithm."

The Analogy: This recipe was like baking a cake where you had to mix the ingredients in a very specific, repetitive order. It worked, but it required a lot of "squaring" operations (a specific type of math step) that were inefficient. It was like having to walk back and forth across the kitchen 100 times just to get a cup of sugar.

The New Solution:
The team optimized the "kitchen layout" (the irreducible polynomial) so that the "squaring" step became incredibly fast. They also used a smarter "shopping list" (addition chains) to figure out exactly which steps were needed, cutting out unnecessary trips.

The Result: They reduced the number of steps needed to divide numbers significantly. For some sizes, they cut the work by 28%. This means quantum computers can break (or verify) encryption codes much faster and with less risk of error.

3. The "Square Root" Surprise

The Curious Discovery:
The paper also explored a weird mathematical quirk. Usually, if you have a machine that does a task, you can easily build a machine that does "half" that task (like taking a square root).

The Analogy: Imagine a machine that spins a wheel once. You'd think a machine that spins it "half a time" would be easier to build.
The Twist: The authors proved that for certain quantum operations, the "half-task" machine is actually much deeper and more complex to build than the original machine. It's like trying to build a machine that only spins the wheel halfway, but you have to build a giant, complex gear system to stop it at exactly the right moment, whereas the full spin was easy. This is a crucial warning for quantum engineers: "Just because it's a root doesn't mean it's simpler."

Why Does This Matter?

Think of quantum computers as a new type of engine. For a long time, we knew how to build the engine, but the fuel consumption was so high that the car couldn't drive very far.

Before: To run a security check, the quantum computer needed a massive amount of "fuel" (gates), making it too expensive and error-prone to be useful.
After: This paper acts like a turbocharger and a fuel injection system. By optimizing the math, they made the quantum computer drastically more efficient.

The Bottom Line:
They didn't just tweak the numbers; they found a fundamental shortcut in the math that allows quantum computers to perform complex cryptographic tasks with 100 times less effort. This brings us one giant step closer to quantum computers that can actually solve real-world problems, like cracking unbreakable codes or designing new medicines, without running out of steam.

1. Problem Statement

Galois Field arithmetic, specifically over $GF(2^m)$ , is a fundamental primitive for various quantum algorithms, including elliptic curve discrete logarithm problems (ECDLP), proofs of quantumness, and decoded quantum interferometry.

The Bottleneck: Existing ancilla-free quantum circuits for $GF(2^m)$ multiplication (based on the Karatsuba algorithm) suffer from a gate count complexity of $O(m^2)$ for CNOT gates. This quadratic cost arises primarily from the implementation of multiplication by the constant polynomial $1 + x^{\lceil m/2 \rceil}$ , which is a necessary step in Van Hoof's construction [46].
Division Complexity: Field division (inversion) typically relies on the Itoh-Tsujii algorithm, which involves repeated squaring and multiplication. Previous implementations suffered from $O(m^2 \log m)$ CNOT complexity due to inefficient linear reversible squaring circuits.
Goal: The authors aim to reduce the asymptotic complexity of these operations to $O(m \log_2 3)$ for multiplication and improve division complexity, while maintaining ancilla-free (or low ancilla) constraints and ensuring practical improvements for cryptographically relevant field sizes (e.g., $m=163, 256, 1024$ ).

2. Methodology

The paper employs a multi-pronged approach combining algebraic number theory, linear algebra optimization, and circuit synthesis techniques.

A. Optimizing Constant Multiplication ( $1 + x^{\lceil m/2 \rceil}$ )

The core innovation is reducing the cost of multiplying by the constant $1 + x^{\lceil m/2 \rceil}$ from $O(m^2)$ to $O(m)$ .

Matrix Representation: The multiplication is viewed as a linear reversible transformation (an $m \times m$ matrix over $GF(2)$).
Irreducible Polynomial Selection: The authors prove that for any $m$ $m$ , there exist irreducible polynomials where the matrix structure allows for a highly efficient CNOT circuit.
- Even $m$ : They utilize trinomials ( $x^m + x^l + 1$ ) or general polynomials where the gap between the highest and lowest non-trivial terms is small ( $l_1 - l_k \in O(1)$ ). They develop Algorithm 1 and 2 to construct CNOT circuits with $O(m)$ gates.
- Odd $m$ : They introduce a specific class of polynomials and Algorithms 5 & 6 to achieve $O(m)$ complexity, even for odd $m$ , by reducing the problem to synthesizing a specific circulant matrix.
Result: This removes the quadratic bottleneck, allowing the overall Karatsuba multiplication to achieve $O(m \log_2 3)$ CNOT complexity.

B. Optimizing Field Division

Division is performed via $b^{-1} = b^{2^m-2}$ using Fermat's Little Theorem.

Addition Chains: Instead of the standard Itoh-Tsujii addition chain, the authors utilize optimized addition chains (based on Dimitrov and Järvinen [12]) to minimize the number of multiplications required.
Simultaneous Optimization: They select irreducible polynomials that simultaneously optimize:
1. Constant multiplication (as described above).
2. Field Squaring: They design circuits for squaring ( $a \to a^2$ ) that also run in $O(m \log m)$ complexity.
Complexity Reduction: By combining optimized squaring with addition chains, the total CNOT complexity for division drops from $O(m^2 \log m)$ to $O(m^2 \log \log m / \log m)$ .

C. Toffoli Gate Reduction

Karatsuba-like Formulas: The authors generalize the Karatsuba algorithm using "Karatsuba-like" formulas (dividing inputs into $k$ pieces) to reduce the number of multiplications.
Parity Controlled Toffoli (PCTOF): They introduce a technique to group Toffoli gates based on parity controls, allowing for rank reduction of the control matrix. This reduces the Toffoli count by up to 5% for non-power-of-2 $m$ .

D. Theoretical Insight: Square Roots of Unitaries

The paper includes a theoretical lemma demonstrating that for certain linear reversible unitaries $U$ , the square root $\sqrt{U}$ can require asymptotically deeper circuits ( $\Omega(\log n)$ ) than $U$ itself (which can be constant depth), even when both are implementable with CNOTs alone.

3. Key Contributions

Asymptotic Improvement:
- Multiplication: Reduced CNOT complexity from $O(m^2)$ to $O(m \log_2 3)$ .
- Division: Reduced CNOT complexity from $O(m^2 \log m)$ to $O(m^2 \log \log m / \log m)$ .
Practical Optimization:
- Developed constructive algorithms (Algorithms 1–6) that guarantee these bounds for specific classes of irreducible polynomials.
- Demonstrated that suitable irreducible polynomials exist for all $m$ up to 10,000, covering all relevant cryptographic sizes.
Gate Count Reductions:
- Achieved a 100x+ reduction in CNOT counts for the constant multiplication step (e.g., for $m=6159$ , reduction from ~2.2M to ~6k gates).
- Overall CNOT reductions of ~20.9% and Toffoli reductions of ~18% for multiplication in Table I.
- Division gate count reductions of up to 28% for both CNOT and Toffoli gates (Table II).
Ancilla-Free Constraint: All optimizations are achieved without auxiliary qubits (ancillae) for multiplication, and with minimal ancilla overhead for division, making them suitable for near-term fault-tolerant quantum computers.

4. Results

The authors provide extensive numeric results comparing their optimized circuits against state-of-the-art implementations (Van Hoof [46], Putranto et al. [37], and Jang et al. [3]).

Multiplication (Table I):
- For $m=163$ (a standard elliptic curve size), the CNOT count drops from 36,439 to 35,070, and Toffoli from 4,387 to 3,605.
- For larger $m$ (e.g., $m=1024$ ), the CNOT count drops from 591,942 to 525,140.
- The improvement factor grows with $m$ due to the better asymptotic scaling.
Division (Table II):
- For $m=64$ , CNOT count reduced from 169,272 to 121,120 (~28% reduction).
- For $m=1024$ , CNOT count reduced from 28.3M to 22.9M, and Toffoli count reduced from 2.18M to 1.59M.
- Ancilla Register (AR) usage is also optimized, sometimes reducing the count by up to 22%.
Toom-Cook (Appendix A): The authors explored Toom-Cook algorithms but found they did not outperform the optimized Karatsuba-like approach for the tested range due to high leading constants and recursion overhead.

5. Significance

Cryptographic Impact: The reduction in gate counts directly translates to lower resource requirements for breaking elliptic curve cryptography (ECC) via Shor's algorithm or related quantum attacks. This refines the estimates of "quantum advantage" timelines.
Algorithmic Efficiency: The work proves that the "bottleneck" of constant multiplication in Karatsuba-based quantum circuits can be eliminated, making $O(m \log_2 3)$ a practical reality rather than just a theoretical bound.
Hardware Relevance: By focusing on ancilla-free and low-ancilla constructions, the results are immediately applicable to early fault-tolerant quantum computers where qubit count is the primary constraint.
Cost Model Alignment: The optimization targets the cost function $10 \times \text{Toffoli} + \text{CNOT}$ , reflecting modern error correction models where Toffoli gates are significantly more expensive than CNOTs, but CNOTs are no longer negligible.

In summary, this paper provides a comprehensive framework for optimizing $GF(2^m)$ arithmetic in quantum circuits, achieving both asymptotic optimality and substantial practical reductions in gate counts, which is critical for the feasibility of quantum algorithms in cryptography and simulation.