⚛️ quantum physics

The Jacobi Factoring Circuit: Quantum Factoring with Near-Linear Gates and Sublinear Space and Depth

This paper introduces a compact quantum circuit that factors a specific class of classically hard integers in polynomial time using sublinear space and depth, achieved through a novel space-efficient algorithm for computing the Jacobi symbol.

Original authors: Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Vinod Vaikuntanathan, Katherine Van Kirk

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 have a giant, locked safe (a large number) and you want to find the combination (its prime factors) to open it. For decades, the best way to do this was Shor's Algorithm, a famous quantum method. But Shor's algorithm is like trying to crack that safe with a massive, industrial-sized robot arm. It requires a huge amount of space, takes a long time to swing, and uses a lot of energy. It's powerful, but currently, we don't have the hardware to build a robot that big.

This paper introduces a new tool called the Jacobi Factoring Circuit. Think of this not as a giant robot, but as a sleek, pocket-sized lockpick. It's designed to open a specific type of safe that is very common in cryptography but has a special "weakness" in its structure.

Here is how the paper breaks down, using simple analogies:

1. The Target: A Specific Type of Safe

The authors aren't trying to crack every safe (like the standard RSA locks used on the internet today). Instead, they are targeting safes made of a specific shape: $N = P^2 \times Q$ .

Imagine a safe made of two parts: a heavy, square block ( $P^2$ ) and a smaller, irregular block ( $Q$ ).
The paper focuses on cases where the smaller block ( $Q$ ) is significantly smaller than the whole safe, but not so small that classical computers can easily crack it.
The Catch: If the smaller block is too small, classical computers can already break it. If it's too big, the new method doesn't help. But in the "Goldilocks zone" (where $Q$ is just right), this new quantum method shines.

2. The Old Way vs. The New Way

The Old Way (Li, Peng, Du, and Suter - 2012):
Previous researchers found a way to crack these specific safes using quantum mechanics. However, their method was like using a giant telescope to look at a tiny ant. To find the combination, they had to look at the entire safe (all $N$ bits), which required a massive amount of quantum memory (qubits) and time.

The New Way (This Paper):
The authors realized they didn't need to look at the whole safe. They only needed to look at the small, irregular block ( $Q$ ).

The Analogy: Imagine you are trying to find a specific key in a giant library. The old method said, "Search every single book in the library." The new method says, "Actually, the key is only hidden in the small section of the library where the irregular blocks live. Let's just search that tiny section."
The Result: By focusing only on the small part, they reduced the space needed (qubits) and the depth (time/steps) to a fraction of what was previously thought possible. They achieved sublinear space, meaning the memory required grows much slower than the size of the number.

3. The Secret Tool: The "Jacobi Symbol"

How did they manage to look at just the small part? They used a mathematical tool called the Jacobi Symbol.

The Metaphor: Think of the Jacobi Symbol as a special "magic mirror." If you hold a number up to it, the mirror reflects a simple "Yes" or "No" (or +1 or -1) that tells you something about the number's relationship to the safe's combination.
The Innovation: The paper's biggest technical breakthrough is building a new, ultra-efficient version of this magic mirror.
- Old mirrors were bulky and required you to hold the whole safe in your hands to use them.
- The new mirror is tiny. It can work even if you only have a tiny piece of the safe in your hand, as long as you know the rest of the safe is "classical" (fixed and known).
- This allows the quantum computer to process the information without needing to store the entire giant number in its memory.

4. What Does This Actually Do?

The paper claims this circuit can:

Factor these specific types of numbers ( $P^2Q$ ) using near-linear gates (very efficient steps).
Use sublinear space (less memory than the size of the number).
Use sublinear depth (finish the job faster than previous methods).

Important Limitation: The paper is very clear that this does not break standard RSA encryption (which uses $N = P \times Q$ , two different primes). It only breaks numbers with a specific "square" structure. However, the authors note that this specific structure has been used in other cryptographic systems, so it is still a significant finding for that field.

5. The "Proof of Quantumness"

The paper suggests this new circuit could be used to prove a computer is truly quantum.

The Analogy: Imagine a magician claims they can pull a rabbit out of a hat. To prove it, they usually have to do a huge, complex trick.
This new method is like a magician who can pull a rabbit out of a tiny hat using a simple, quick gesture. It's much easier to verify and requires less "stage space" (hardware) to perform, making it a more practical way to demonstrate quantum power in the near future.

Summary

The authors have built a specialized, lightweight quantum tool that cracks a specific type of mathematical lock much more efficiently than ever before. They did this by realizing they didn't need to carry the whole lock; they only needed to focus on the small, weak part of it, and they built a new, tiny "mirror" (algorithm) to help them see it. While it doesn't break the most famous locks (RSA) yet, it proves that quantum computers can be much smaller and more efficient than we thought for certain difficult problems.

Technical Summary: The Jacobi Factoring Circuit

Problem Statement
Current quantum factoring algorithms, such as Shor's algorithm and Regev's recent improvements, face significant barriers to practical implementation on near-term devices due to high resource requirements. Specifically, factoring an $n$ -bit integer typically requires $\tilde{O}(n^2)$ or $\tilde{O}(n^{3/2})$ gates and $\tilde{O}(n)$ qubits. While space complexity has been reduced to $\tilde{O}(n)$ or even $O(n)$ , achieving sublinear space and depth for classically hard factoring problems remains an open challenge. Furthermore, existing quantum algorithms do not appear to benefit polynomially from specific structural properties of the input integer (e.g., small squarefree parts), unlike certain classical algorithms.

This paper addresses the question of whether quantum circuits for factoring can achieve (near-)linear gate counts while simultaneously operating with sublinear space and depth, specifically for a class of integers where the hardness is expected to be equivalent to RSA (though not including RSA integers themselves).

Methodology
The authors propose the "Jacobi Factoring Circuit," which builds upon the squarefree decomposition algorithm by Li, Peng, Du, and Suter (LPDS) [LPDS12]. The methodology consists of three primary technical components:

Refined Analysis of LPDS (Section 3):
The original LPDS circuit computes the squarefree decomposition of an integer $N = A^2 B$ by creating a uniform superposition over all $x \in [1, N]$ and computing the Jacobi symbol $(\frac{x}{N})$ . The authors demonstrate that a superposition over the full range $[1, N]$ is unnecessary. By combining Shor's period-finding analysis with Gauss sum bounds, they prove that a superposition over a much smaller range, $[1, \text{poly}(B_{\max})]$ , where $B_{\max}$ is an upper bound on the squarefree part $B$ , is sufficient to recover $B$ (or a prime factor) with constant probability. This reduction allows the circuit to operate with space proportional to $\log B$ rather than $\log N$ .
Sublinear Space Jacobi Symbol Computation (Section 4):
The computational bottleneck in the LPDS approach is computing the Jacobi symbol $(\frac{x}{N})$ where $x$ is in superposition and $N$ is a large classical integer. Standard algorithms (Extended Euclidean, Binary GCD) require space linear in $\log N$ .
The authors introduce a new quantum algorithm to compute $(\frac{x}{N})$ when $\log x \ll \log N$ . The core innovation is a "reversed" variant of long division inspired by Montgomery reduction and the binary GCD algorithm.
- Mechanism: Instead of finding a multiple of $x$ that matches the Most Significant Bits (MSBs) of $N$ (standard long division), the algorithm finds a multiple $kx$ such that $N - kx$ has its Least Significant Bits (LSBs) matching $N$ (effectively zeroing them out).
- Space Efficiency: By processing $N$ in blocks of size $m$ (where $m \approx \log x$ ) starting from the LSBs, the algorithm only needs to store the leading $O(m)$ bits of the running sum quantumly. The lower-order bits are classically known and can be uncomputed or recycled.
- Complexity: This yields a circuit with gate count $\tilde{O}(n)$ , space $\tilde{O}(m)$ , and depth $\tilde{O}(n/m + m)$ .
Complete Factorization of Special Integers (Section 5):
The paper provides a black-box reduction showing that an algorithm for squarefree decomposition can completely factor integers with distinct exponents in their prime factorization (so-called "special integers," $N = p_1^{\alpha_1} \dots p_r^{\alpha_r}$ where all $\alpha_i$ are distinct).
- Method: The algorithm recursively uses the squarefree decomposition to isolate the product of primes with odd exponents. By computing the GCD of the original number and a derived value, it isolates a single prime factor. This process is repeated until the full factorization is obtained. This approach is analogous to Yun's algorithm for polynomial factorization.

Key Contributions and Results

Theorem 1.1 (Informal): There exists a quantum circuit that factors any $n$ $n$ -bit integer of the form $N = P^2 Q$ $N = P^{2} Q$ (where $P, Q$ $P, Q$ are prime and $\log Q = \Theta(n^a)$ $lo g Q = Θ (n^{a})$ for $a \in (2/3, 1)$ $a \in (2/3, 1)$ ) using:
- Gates: $\tilde{O}(n)$
- Qubits: $\tilde{O}(m)$ (where $m = \log Q$ )
- Depth: $\tilde{O}(m + n/m)$
  When $m = \Theta(n^a)$ with $a \in (0, 1)$ , both space and depth are sublinear in $n$ .
First Sublinear Space Factoring: To the authors' knowledge, this is the first polynomial-time quantum circuit to achieve sublinear qubit counts for a classically hard factoring problem.
Comparison to Classical Hardness: For integers of the form $N = P^2 Q$ where $\log Q \ge \tilde{\Omega}((\log N)^{2/3})$ , no known classical special-purpose algorithms (such as Lenstra's Elliptic Curve Method) offer asymptotic speedups over general-purpose factoring (Number Field Sieve). Thus, the quantum advantage here is not merely exploiting a classical weakness but achieving a resource reduction impossible for classical algorithms in this regime.
Proof of Quantumness: The circuit enables a factoring-based proof of quantumness with sublinear space complexity. For $N = P^2 Q$ with $\log Q \approx n^{2/3}$ , the circuit uses $\tilde{O}(n)$ gates, $\tilde{O}(n^{2/3})$ depth, and $\tilde{O}(n^{2/3})$ qubits. This outperforms Shor's algorithm and Regev's algorithm in terms of the product of qubit count and depth/gates.

Significance and Claims
The paper claims that the Jacobi Factoring Circuit represents a significant step toward realizing integer factorization on near- or medium-term quantum devices by drastically reducing the space and depth requirements.

Independence: The technique for computing Jacobi symbols in sublinear space is of independent interest and generalizes to computing GCDs and modular inverses.
Limitations: The authors explicitly state that their method does not factor RSA integers (products of two primes of similar size) directly, as the squarefree part $B$ in RSA is 1. The method applies to integers where the squarefree part is small but non-trivial.
Modesty: The authors note that while the asymptotic scaling is improved, the concrete costs (gate counts, error correction overhead) are not analyzed in depth, and the practical realization of factoring 2048-bit integers remains a subject for future work. They also acknowledge that the algorithm does not currently extend to factoring general squarefree integers, which remains an open question.

In summary, the paper presents a theoretical breakthrough in quantum resource efficiency for a specific, cryptographically relevant class of integers, demonstrating that sublinear space and depth are achievable for factoring problems that remain hard for classical computers.