Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2608.11563

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

Changyeol Lee, Sungyeon Kook, Wooyeong Song, Kwangil Bae, Wonhyuk Lee, IlKwon Sohn

quant-phSubmitted Aug 12, 2026• Announced Aug 13, 2026• 0 citations
arXivHTMLPDF

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.

Comments
20 pages, 10 figures, 3 tables

Related papers

Optimized quantum folding Barrett reduction for quantum modular multipliers

Jian Zhang, Seong-Min Cho, Changyeol Lee +1 more

Due to the reversibility constraints of quantum circuits, the development of modular operations in quantum modular multiplication has been significantly limited. In this work, we propose an optimized modular operation scheme based on Barrett reduction and implement quantum circuits for three versions of Barrett reduction, including our optimized approach. The proposed quantum modular operation circuit can be integrated with quantum-quantum and quantum-classical multiplication circuits. Additionally, we analyze the quantum resource requirements of the proposed circuit and compare the results across the three versions. Our optimized folding Barrett reduction scheme demonstrates superior performance. Furthermore, general quantum modular reduction relies on recursive subtractors and controlled adders to avoid division operation, resulting in a T-depth of approximately [Formula: see text], where n is the bit length of the modulus. In contrast, our approach achieves a T-depth of only [Formula: see text] by utilizing the Barrett reduction.

Scientific Reports•Jul 2, 2025•1 citation

Quantum Arithmetic Circuits in Public-Key Cryptography

Siyi Wang, Kyungbae Jang, Hyunji Kim +4 more

Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.

quant-pharXiv:2607.11713•Jul 14, 2026•0 citations

A New Quantum Efficient Fault Tolerant Parity Preserving Clifford + T ALU

Shekoofeh Moghimi, Mohammad Reza Reshadinezhad, Antonio Rubio

Reversible logic is characterized by its feature of being a prominent application in low-power conventional computers and the most compatible logic in quantum computers. Quantum circuits executes quantum algorithms and are important in a new generation of advanced computing. However, they are highly error-prone and also subject to the use of limited and sensitive physical resources like qubits and quantum gates. This paper introduces a comprehensive fault tolerant quantum-based reversible circuit which can calculate a high variety number of arithmetic and logic operations. It uses both: parity preserving method for detecting one or an odd number of bit errors, and Clifford + T implementation for protecting circuits against decoherence faults. First, we propose a new fault-tolerant (parity preserving and Clifford + T) adder/subtractor and derive a quantum reversible Arithmetic and Logic Unit (ALU). These modules reach the most optimized extent of circuit line, ancilla inputs, and garbage outputs according to the logical analysis done in this work. This article focuses on reducing T-cost metrics in conjunction with enhancing the number of operations and quantum costs in proposed circuits compared to other counterparts. We propose 4-bit fault tolerant ALU derived from our proposed single-bit module to show the proposed circuit can be extended to any larger size. The proposed circuit is implemented in the Qiskit simulation tool, and output results confirm the accuracy of our design functionality. The proposed full adder/ subtractor achieves an average of 64% and 43%, and the proposed ALU circuit achieves an average of 38% and 27% improvement in T-count and T-depth, respectively compared to their counterparts. The proposed reversible quantum-optimized fault tolerant adder/subtractor and ALU units can be applied as the basic part of DSP systems and quantum processor units in quantum computing devices.

IEEE Transactions on Emerging Topics in Computing•Apr 1, 2026•0 citations

Improved quantum circuits for division

Priyanka Mukhopadhyay, Alexandru Gheorghiu, Hari Krovi

Arithmetic operations are an important component of many quantum algorithms. Optimizing quantum circuits for these operations therefore leads to more efficient implementations of the corresponding algorithms. In this paper, we develop new fault-tolerant quantum circuits for various integer division algorithms (both reversible and non-reversible). These circuits, when implemented in the Clifford+T gate set, achieve improvements in the asymptotic T-count and CNOT-count from $O(n^2)$ to $O(nm)$, and in the asymptotic T-depth from $O(n^2)$ to $O(n \log m)$, where $n$ and $m$ are the bit lengths of the dividend and divisor, respectively. The qubit counts are significantly lower than those in previous works. We achieve this through careful modifications of the division algorithms and by expressing them in terms of a primitive we call COMP-N-SUB that compares two integers and conditionally subtracts them. We show that this primitive can be implemented at a cost, in terms of both Clifford and non-Clifford gates, comparable to that of one addition. By contrast, performing comparison and conditional subtraction separately would cost roughly as much as a controlled addition plus a regular addition.

quant-pharXiv:2603.18110•Mar 19, 2026•0 citations

Proof-Carrying Arithmetic for Quantum ECDLP: A Certificate Format for Public Reversible Blocks

Abdul Rahman

Quantum resource estimates for the elliptic-curve discrete logarithm problem (ECDLP) now shape cryptographic migration planning, blockchain security analysis, and fault-tolerant architecture design. Recent work has moved in two complementary directions: Babbush et al. give improved secp256k1 resource estimates supported by zero-knowledge attestation while withholding sensitive circuit details, whereas Luo et al. publish an explicit reversible modular-inversion construction based on the extended Euclidean algorithm, reducing the logical-qubit footprint of prime-field ECDLP and identifying gate count, depth, and architecture-aware implementation as natural optimization targets. This note proposes a third disclosure model: verifiable resource certificates for public reversible arithmetic blocks. A certificate records a circuit commitment, gate basis, resource counts, input-output specification, deterministic test generation, correctness transcript, and optional proof artifact. We specialize the framework to modular inversion blocks |x⟩|0⟩ → |x⟩|x−1 mod p⟩, for \(x\in\mathbb F_p^\times\), which are central to affine-coordinate quantum ECDLP implementations. We prove a basic soundness bound for hash-derived randomized testing and outline a prototype verifier. The goal is not a new quantum attack, but reproducible, comparable, and independently auditable quantum-ECDLP arithmetic claims.

•Jul 14, 2026•0 citations

Minimizing Quantum Overhead: A Fault-Tolerant ALU Design with Reduced T Metrics

Sarallah Keshavarz, Shekoofeh Moghimi, Mohammad Reza Reshadinezhad

Quantum Arithmetic Logic Units (ALUs) serve as critical components in quantum processors, enabling both arithmetic and logical operations on qubits. However, the fragile nature of quantum systems makes them susceptible to errors and decoherence, necessitating fault-tolerant designs. In this work, we propose a fault-tolerant quantum ALU architecture constructed using the Clifford+ T gate set, which is widely recognized for its compatibility with error-correcting codes. The proposed design minimizes quantum resource overhead while maintaining computational accuracy under fault-prone conditions. Notably, the architecture requires zero ancilla and generates a single garbage output, optimizing the qubit space. Performance evaluations demonstrate significant improvements, achieving a 31.8% reduction in T-count and a 33.3% reduction in T-depth compared to existing designs. These enhancements contribute to more efficient and reliable quantum computation, paving the way for scalable quantum processor development.

International Conference on Computer and Knowledge Engineering•Oct 28, 2025•0 citations
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=2n−cq=2^n-cq=2n−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 2n2n2n-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 ccc 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=10n=10n=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=20n=20n=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.
Due to the reversibility constraints of quantum circuits, the development of modular operations in quantum modular multiplication has been significantly limited. In this work, we propose an optimized modular operation scheme based on Barrett reduction and implement quantum circuits for three versions of Barrett reduction, including our optimized approach. The proposed quantum modular operation circuit can be integrated with quantum-quantum and quantum-classical multiplication circuits. Additionally, we analyze the quantum resource requirements of the proposed circuit and compare the results across the three versions. Our optimized folding Barrett reduction scheme demonstrates superior performance. Furthermore, general quantum modular reduction relies on recursive subtractors and controlled adders to avoid division operation, resulting in a T-depth of approximately [Formula: see text], where n is the bit length of the modulus. In contrast, our approach achieves a T-depth of only [Formula: see text] by utilizing the Barrett reduction.
Quantum computing has advanced rapidly in recent decades, driven by developments across the technology stack, including quantum error-correcting codes and efficient quantum algorithms. Among these, quantum arithmetic circuits serve as fundamental building blocks for various promising algorithms. Despite their crucial role, the design of quantum arithmetic circuits faces challenges arising from the no-cloning theorem, qubit limitations, and circuit depth constraints, which significantly impact the efficiency of large-scale quantum computing. We provide an overview of quantum arithmetic circuits in the context of public-key cryptanalysis, with particular emphasis on optimization strategies such as measurement-based uncomputation and conditionally clean ancilla. We review state-of-the-art designs for essential arithmetic operations in public-key cryptanalysis such as addition, multiplication, and modular exponentiation. We also present an overview of the techniques used for fault-tolerant runtime and resource estimation in quantum cryptanalysis. In brief, this chapter emphasizes strategies for designing resource-efficient quantum arithmetic circuits, providing a basis for realistic evaluations of quantum cryptanalytic capabilities.
Reversible logic is characterized by its feature of being a prominent application in low-power conventional computers and the most compatible logic in quantum computers. Quantum circuits executes quantum algorithms and are important in a new generation of advanced computing. However, they are highly error-prone and also subject to the use of limited and sensitive physical resources like qubits and quantum gates. This paper introduces a comprehensive fault tolerant quantum-based reversible circuit which can calculate a high variety number of arithmetic and logic operations. It uses both: parity preserving method for detecting one or an odd number of bit errors, and Clifford + T implementation for protecting circuits against decoherence faults. First, we propose a new fault-tolerant (parity preserving and Clifford + T) adder/subtractor and derive a quantum reversible Arithmetic and Logic Unit (ALU). These modules reach the most optimized extent of circuit line, ancilla inputs, and garbage outputs according to the logical analysis done in this work. This article focuses on reducing T-cost metrics in conjunction with enhancing the number of operations and quantum costs in proposed circuits compared to other counterparts. We propose 4-bit fault tolerant ALU derived from our proposed single-bit module to show the proposed circuit can be extended to any larger size. The proposed circuit is implemented in the Qiskit simulation tool, and output results confirm the accuracy of our design functionality. The proposed full adder/ subtractor achieves an average of 64% and 43%, and the proposed ALU circuit achieves an average of 38% and 27% improvement in T-count and T-depth, respectively compared to their counterparts. The proposed reversible quantum-optimized fault tolerant adder/subtractor and ALU units can be applied as the basic part of DSP systems and quantum processor units in quantum computing devices.
Arithmetic operations are an important component of many quantum algorithms. Optimizing quantum circuits for these operations therefore leads to more efficient implementations of the corresponding algorithms. In this paper, we develop new fault-tolerant quantum circuits for various integer division algorithms (both reversible and non-reversible). These circuits, when implemented in the Clifford+T gate set, achieve improvements in the asymptotic T-count and CNOT-count from O(n2)O(n^2)O(n2) to O(nm)O(nm)O(nm), and in the asymptotic T-depth from O(n2)O(n^2)O(n2) to O(nlog⁡m)O(n \log m)O(nlogm), where nnn and mmm are the bit lengths of the dividend and divisor, respectively. The qubit counts are significantly lower than those in previous works. We achieve this through careful modifications of the division algorithms and by expressing them in terms of a primitive we call COMP-N-SUB that compares two integers and conditionally subtracts them. We show that this primitive can be implemented at a cost, in terms of both Clifford and non-Clifford gates, comparable to that of one addition. By contrast, performing comparison and conditional subtraction separately would cost roughly as much as a controlled addition plus a regular addition.
Quantum resource estimates for the elliptic-curve discrete logarithm problem (ECDLP) now shape cryptographic migration planning, blockchain security analysis, and fault-tolerant architecture design. Recent work has moved in two complementary directions: Babbush et al. give improved secp256k1 resource estimates supported by zero-knowledge attestation while withholding sensitive circuit details, whereas Luo et al. publish an explicit reversible modular-inversion construction based on the extended Euclidean algorithm, reducing the logical-qubit footprint of prime-field ECDLP and identifying gate count, depth, and architecture-aware implementation as natural optimization targets. This note proposes a third disclosure model: verifiable resource certificates for public reversible arithmetic blocks. A certificate records a circuit commitment, gate basis, resource counts, input-output specification, deterministic test generation, correctness transcript, and optional proof artifact. We specialize the framework to modular inversion blocks |x⟩|0⟩ → |x⟩|x−1 mod p⟩, for x∈Fp×x\in\mathbb F_p^\timesx∈Fp×​, which are central to affine-coordinate quantum ECDLP implementations. We prove a basic soundness bound for hash-derived randomized testing and outline a prototype verifier. The goal is not a new quantum attack, but reproducible, comparable, and independently auditable quantum-ECDLP arithmetic claims.
Quantum Arithmetic Logic Units (ALUs) serve as critical components in quantum processors, enabling both arithmetic and logical operations on qubits. However, the fragile nature of quantum systems makes them susceptible to errors and decoherence, necessitating fault-tolerant designs. In this work, we propose a fault-tolerant quantum ALU architecture constructed using the Clifford+ T gate set, which is widely recognized for its compatibility with error-correcting codes. The proposed design minimizes quantum resource overhead while maintaining computational accuracy under fault-prone conditions. Notably, the architecture requires zero ancilla and generates a single garbage output, optimizing the qubit space. Performance evaluations demonstrate significant improvements, achieving a 31.8% reduction in T-count and a 33.3% reduction in T-depth compared to existing designs. These enhancements contribute to more efficient and reliable quantum computation, paving the way for scalable quantum processor development.