Efficient Quantum Modular Reduction: Crandall reduction and its Fault-tolerant resource analysis

• URL: http://arxiv.org/abs/2608.11563v1
• Date: Wed, 12 Aug 2026 02:07:24 GMT
• Title: Efficient Quantum Modular Reduction: Crandall reduction and its Fault-tolerant resource analysis
• Abstract summary: Pseudo-Mersenne moduli modq=2n-c$ allow Crandall reduction to replace division with folding and constant arithmetic.<n>This constitutes the first exact reversible quantum circuit formulation of Crandall reduction.<n> Logical resource estimates show that both variants require fewer qubits and lower T-count and T-depth than optimized Barrett folding reduction.
• Score: 0.6157382820537719
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modular arithmetic is central to quantum algorithms for cryptographic problems, including Shor's algorithm and Grover-based cryptanalysis, with modular reduction contributing substantially to circuit cost. Pseudo-Mersenne moduli $q=2^n-c$ allow classical Crandall reduction to replace division with folding and constant arithmetic, providing a structural opportunity for more efficient quantum modular reduction than Barrett reduction. We translate this advantage into a reversible quantum setting by deriving explicit folding and normalization conditions for $2n$-bit inputs. To the best of our knowledge, this constitutes the first exact reversible quantum circuit formulation of Crandall reduction. Based on this formulation, we develop two variants: Crandall reduction-1 is designed to minimize execution cost through one-step normalization, whereas Crandall reduction-2 uses two-step normalization to support a wider range of $c$ with limited overhead. Logical resource estimates show that both variants require fewer qubits and lower T-count and T-depth than optimized folding Barrett reduction. At $n=10$, Crandall reduction-1 reduces both T-count and T-depth by approximately 46.9% relative to optimized folding Barrett reduction. Surface-code analysis further shows that, at $n=20$ under the Sparse Blossom decoder, the estimated runtimes of the two variants are 30.05 ms and 35.39 ms, respectively, compared with 53.77 ms for optimized folding Barrett reduction. These results demonstrate the practical value of exploiting modulus-specific arithmetic structure in fault-tolerant quantum circuit design.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• BPDQ: Bit-Plane Decomposition Quantization on a Variable Grid for Large Language Models [56.504879072674015]
  We propose Bit-Plane Decomposition Quantization (BPDQ), which constructs a variable quantization grid via bit-planes and scalar coefficients.<n>BPDQ enables serving Qwen2.5-72B on a single GTX 3090 with 83.85% GSM8K accuracy (vs. 90.83% at 16-bit)
  arXiv  Detail & Related papers  (2026-02-04T02:54:37Z)
• Verifiable Quantum Advantage via Optimized DQI Circuits [2.149968465453488]
  Decoded Quantum Interferometry (DQI) provides a framework for superpolynomial quantum speedups.<n>We apply DQI to the Optimal Polynomial Intersection (OPI) problem, whose code is Reed-Solomon (RS)<n>We establish that DQI for OPI is the first known candidate for verifiable quantum advantage with optimal speedup.
  arXiv  Detail & Related papers  (2025-10-13T03:19:28Z)
• Optimized circuits for windowed modular arithmetic with applications to quantum attacks against RSA [45.810803542748495]
  Windowed arithmetic is a technique for reducing the cost of quantum circuits with space--time tradeoffs.<n>In this work we introduce four optimizations to windowed modular exponentiation.<n>This leads to a $3%$ improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications.
  arXiv  Detail & Related papers  (2025-02-24T16:59:16Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Space-Efficient and Noise-Robust Quantum Factoring [10.974556218898435]
  Two improvements to Regev's recent quantum factoring algorithm.<n>Regev's circuit requires $O(n3/2)$ qubits and $O(n3/2 log n)$ gates.<n>Regev's analysis of his classical postprocessing procedure requires all $approx sqrtn$ runs to be successful.
  arXiv  Detail & Related papers  (2023-10-02T04:31:21Z)
• Fast Flux-Activated Leakage Reduction for Superconducting Quantum Circuits [84.60542868688235]
  leakage out of the computational subspace arising from the multi-level structure of qubit implementations. We present a resource-efficient universal leakage reduction unit for superconducting qubits using parametric flux modulation. We demonstrate that using the leakage reduction unit in repeated weight-two stabilizer measurements reduces the total number of detected errors in a scalable fashion.
  arXiv  Detail & Related papers  (2023-09-13T16:21:32Z)
• All-microwave leakage reduction units for quantum error correction with superconducting transmon qubits [0.0]
  Minimizing leakage from computational states is a challenge when using superconducting quantum circuits as qubits. We realize and extend the quantum-hardware-efficient, all-microwave leakage reduction unit (LRU) for transmons in a circuit QED architecture proposed by Battistel et al. This LRU effectively reduces leakage in the second- and third-excited transmon states with up to $99% $ efficacy in $220mathrmns$, with minimum impact on the qubit subspace.
  arXiv  Detail & Related papers  (2023-02-20T10:10:53Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.