From Period Finding to Lattice Sampling: Experimental Insights into Shor's and Regev's Factoring Algorithms

This paper presents an experimental comparison of Shor's and Regev's quantum factoring algorithms on real NISQ hardware for N=15, analyzing how their distinct structural approaches to arithmetic encoding interact with device noise and sampling limitations to inform the practical benchmarking of alternative factoring strategies.

The Gist

The Big Picture: Two Different Ways to Crack a Code

Imagine you are trying to crack a secret code (factoring a number) using a new type of super-computer called a Quantum Computer. For a long time, everyone has been using one specific method to do this, invented by a mathematician named Shor. It's like the "gold standard" recipe for cracking the code.

However, current quantum computers are like "noisy" kitchens. They are small, they make mistakes, and they get confused easily. Because of this, scientists are looking for alternative recipes that might work better in these messy conditions. One of these new recipes was invented by a mathematician named Regev.

This paper is an experiment where the authors cooked up both recipes (Shor's and Regev's) on real, noisy quantum computers to see which one handles the "noise" better. They didn't try to crack a massive, real-world code (which would take years); instead, they cracked a tiny, easy number (15) just to see how the two methods behaved.

The Two Recipes: A "Flashlight" vs. A "Foggy Map"

To understand the difference, imagine you are trying to find a hidden treasure in a dark room.

1. Shor's Algorithm: The Flashlight

• How it works: Shor's method tries to shine a very bright, sharp flashlight on the treasure. It concentrates all its energy into one or two specific spots (peaks). If the light is bright enough, you see the treasure immediately.
• The Problem: In a noisy kitchen, the flashlight flickers. If the light gets too dim or shaky, you can't tell where the treasure is anymore. The "sharp peak" gets blurry, and the signal is lost.
• The Paper's Finding: On the IBM computer (which was slightly less noisy), the flashlight still worked okay. But on the QMIO computer (which was noisier), the light got so blurry that they couldn't find the treasure.

2. Regev's Algorithm: The Foggy Map

• How it works: Regev's method doesn't use a single flashlight. Instead, it throws out a bunch of dotted lines on a map. No single dot points directly to the treasure, but if you look at the pattern of all the dots together, they form a shape that reveals the location. It spreads the information out over many points.
• The Problem: In a noisy kitchen, the fog gets thicker. The dots on the map get scattered and mixed up. Because the information is spread out, it's harder to see the pattern when the noise interferes.
• The Paper's Finding: Regev's method created a "flatter" distribution of dots. On the noisy QMIO computer, the dots got so scattered that the pattern disappeared completely.

The Experiment: What Happened?

The researchers ran both "recipes" on two different quantum computers (IBM and QMIO) and compared them to a perfect, noise-free simulation.

• The "Ideal" World: In a perfect simulation, Shor's method showed a few very tall, sharp spikes (the flashlight). Regev's method showed a few slightly taller dots scattered in a pattern (the map). Both worked perfectly.
• The "Real" World (IBM):
  • Shor: The spikes got a little wider and shorter, but you could still see them. The "flashlight" was shaky but visible.
  • Regev: The dots got more scattered, but a few were still slightly higher than the rest. The "map" was foggy, but the pattern was still faintly there.
• The "Real" World (QMIO - The Noisier Machine):
  • Shor: The spikes flattened out completely. The flashlight went out. The computer couldn't tell the difference between the signal and the noise.
  • Regev: The dots became a uniform cloud. The pattern vanished entirely. The "map" was so foggy it looked like random static.

The Key Takeaway

The paper concludes that neither method is clearly "better" right now for these small, noisy machines.

• Shor's method is like a high-precision tool: it works great if the environment is clean, but it breaks easily if there is even a little bit of dirt (noise).
• Regev's method is like a distributed network: it uses shallower circuits (less complex steps), which sounds good, but because it spreads its information out, the noise scrambles the pattern just as effectively as it scrambles the flashlight.

The Bottom Line:
The authors found that the way these algorithms store information is fundamentally different. Shor "concentrates" information (like a laser), while Regev "distributes" it (like a spray). On today's noisy computers, both strategies struggle, but they fail in different ways. Shor loses its sharp focus, while Regev loses its geometric pattern.

This study doesn't say we can break real bank codes yet. Instead, it tells us that as we build better quantum computers, we need to understand how these different algorithms react to noise, so we can choose the right one for the right machine.

Technical Summary

Technical Summary: From Period Finding to Lattice Sampling

Problem Statement
While Shor's algorithm theoretically solves integer factorization in polynomial time, its practical implementation on current Noisy Intermediate-Scale Quantum (NISQ) hardware is severely constrained by circuit depth, gate errors, and decoherence. These limitations have spurred interest in alternative factoring algorithms, such as Regev's algorithm, which reformulates the problem as a higher-dimensional lattice sampling task rather than a one-dimensional period-finding problem. However, existing experimental analyses often lack systematic, multi-backend comparisons under tightly controlled conditions to understand how these distinct algorithmic structures interact with realistic hardware noise. This study addresses the gap by experimentally comparing Shor's and Regev's algorithms on real quantum hardware to characterize their relative robustness and failure modes.

Methodology
The authors conducted a controlled experimental study using the benchmark instance $N = 15$. Both algorithms were implemented using Qiskit and executed on two distinct quantum backends: the QMIO quantum computer at the Centro de Supercomputación de Galicia (CESGA) and an IBM open-access quantum processor (ibm_torino). Ideal (noiseless) simulations served as a reference baseline.

• Algorithm Configuration:
  • Shor's Algorithm: Used base $a=2$ with a control register of $k=3$ qubits to find the order $r=4$. The circuit utilized specialized, shallow modular exponentiation constructions based on permutations rather than generic arithmetic to minimize depth.
  • Regev's Algorithm: Configured as a two-dimensional instance ($d=2$) with bases $a_1=4, a_2=49$. It employed a Gaussian superposition over $\mathbb{Z}^d$ followed by Fourier sampling to approximate vectors in the dual lattice.
• Compilation and Execution: Circuits were transpiled using Qiskit with parameters adjusted for each backend's native gate sets and connectivity. All hardware runs utilized 4,096 shots.
• Evaluation Metrics: To quantify the impact of noise without relying on full classical reconstruction for every run, the authors introduced distribution-based metrics:
  • Shannon Entropy ($H(p)$): Measures the dispersion of the probability distribution.
  • Effective Support Size ($N_{eff}$): Estimates the number of outcomes contributing significantly to the distribution.
  • Top-K Mass ($M_4$): The fraction of total probability contained in the four most frequent outcomes.

Key Contributions

1. Controlled Experimental Benchmark: The paper provides a direct, low-level comparison of Shor's and Regev's algorithms on the same problem instance ($N=15$) across multiple hardware platforms and ideal simulations.
2. Multi-Backend Evaluation: Results are reported for both IBM and QMIO devices, offering insights into how different hardware architectures affect algorithmic performance.
3. Information Encoding Interpretation: The study interprets experimental outcomes through the lens of "information concentration" (Shor) versus "information distribution" (Regev). It demonstrates how these structural differences lead to qualitatively distinct noise-induced degradations in measurement histograms.
4. Reproducibility: The authors report specific algorithmic parameters and compilation pipelines used to generate the experimental distributions.

Results
The experimental data reveals distinct failure modes for the two algorithms under NISQ constraints:

• Shor's Algorithm (Information Concentration):

  • In ideal simulations, the probability mass is highly concentrated on a small number of spectral peaks (low entropy, $N_{eff} \approx 4$, $M_4 = 1.0$).
  • On IBM hardware, the distribution broadens but retains dominant peaks ($M_4 = 0.921$), allowing for partial success in order recovery.
  • On the noisier QMIO device, the spectral peaks are significantly flattened and obscured ($M_4 = 0.564$, $N_{eff} \approx 7.8$), leading to a loss of the periodic structure required for classical reconstruction.
  • Observation: Shor's algorithm is highly sensitive to phase errors; once the sharp peaks are broadened by noise, the algorithm fails to provide useful information.

• Regev's Algorithm (Information Distribution):

  • In ideal simulations, the distribution is inherently more dispersed than Shor's but still exhibits a subset of dominant vectors consistent with the dual lattice ($N_{eff} \approx 2.34$, $M_4 = 0.944$).
  • On IBM hardware, the distribution becomes more spread ($M_4 = 0.645$), yet a subset of outcomes remains dominant enough to potentially support lattice reduction.
  • On QMIO, the geometric signal is strongly diluted ($M_4 = 0.29$, $N_{eff} \approx 15.8$), with the probability mass spreading uniformly across many vectors, effectively obscuring the lattice structure.
  • Observation: Regev's algorithm relies on statistical bias across multiple correlated samples. While it uses shallower circuits (Table 2 shows Regev's compiled depth is lower than Shor's on both platforms), the multidimensional sampling stage introduces noise sensitivity that causes rapid dispersion of the geometric signal.

• Circuit Depth vs. Robustness: Despite Regev's algorithm having a shallower compiled circuit depth (e.g., 147 vs. 210 on IBM), this reduction did not translate into superior robustness on current hardware. The measurement distributions for Regev dispersed more rapidly under noise compared to Shor's.

Significance and Claims
The paper modestly claims that neither algorithm demonstrates a practical advantage over the other in the small $N$ regime ($N=15$) on current NISQ devices. Instead, the study highlights a fundamental trade-off:

• Shor's algorithm benefits from highly structured, concentrated outputs when noise is low but fails catastrophically when phase coherence is lost.
• Regev's algorithm distributes information across a higher-dimensional space, which may offer different scaling properties for larger problems but currently suffers from increased sensitivity to noise in multidimensional sampling.

The authors conclude that these results underscore the value of experimental benchmarking to understand the practical implications of algorithmic design choices. They emphasize that asymptotic relationships in the fault-tolerant setting do not guarantee similar behavior on NISQ hardware, where the specific encoding of arithmetic information (concentration vs. distribution) dictates how noise manifests and how algorithms fail. Future work is proposed to extend these benchmarks to larger $N$ and explore error mitigation strategies targeting these specific trade-offs.