The advent of quantum computing has engendered a widespread proliferation of efforts utilizing qubits for optimizing classical computational algorithms. Number Theoretic Transform (NTT) is one such popular algorithm that accelerates polynomial multiplication significantly and is consequently, the core arithmetic operation in most homomorphic encryption algorithms. Hence, fast and efficient execution of NTT is highly imperative for practical implementation of homomorphic encryption schemes in different computing paradigms. In this paper, we, for the first time, propose an efficient and scalable Quantum Number Theoretic Transform (QNTT) circuit using quantum gates. We introduce a novel exponential unit for modular exponential operation, which furnishes an algorithmic complexity of O(n). Our proposed methodology performs further optimization and logic synthesis of QNTT, that is significantly fast and facilitates efficient implementations on IBM’s quantum computers. The optimized QNTT achieves a gate-level complexity reduction from power of two to one with respect to bit length. Our methodology utilizes 44.2% fewer gates, thereby minimizing the circuit depth and a corresponding reduction in overhead and error probability, for a 4-point QNTT compared to its unoptimized counterpart.
The advent of quantum computing has engendered a widespread proliferation of efforts utilizing qubits for optimizing classical computational algorithms. Number Theoretic Transform (NTT) is one such popular algorithm that accelerates polynomial multiplication significantly and is consequently, the core arithmetic operation in most homomorphic encryption algorithms. Hence, fast and efficient execution of NTT is highly imperative for practical implementation of homomorphic encryption schemes in different computing paradigms. In this paper, we, for the first time, propose an efficient and scalable Quantum Number Theoretic Transform (QNTT) circuit using quantum gates. We introduce a novel exponential unit for modular exponential operation, which furnishes an algorithmic complexity of O(n). Our proposed methodology performs further optimization and logic synthesis of QNTT, that is significantly fast and facilitates efficient implementations on IBM’s quantum computers. The optimized QNTT achieves a gate-level complexity reduction from power of two to one with respect to bit length. Our methodology utilizes 44.2% fewer gates, thereby minimizing the circuit depth and a corresponding reduction in overhead and error probability, for a 4-point QNTT compared to its unoptimized counterpart.
Quantum computing furnishes exponential speed up over classical computing in specific areas. For example, Shor’s algorithm can factor two numbers in a polynomial time complexity. Thus, many encryption algorithms that rely on large number factorization are potentially vulnerable to quantum computers. In order to address this, the National Institute of Standard and Test (NIST) has organized a competition to evaluate several post quantum cryptography (PQC) algorithms, that are secure from the attacks from quantum computers. Several of these lattice-based PQC encryption algorithms are based on Learning With Errors (LWE) computation. Conversely, LWE is the heaviest computation in a classical computer, which incurs significant portion of the latency overhead for the entire encryption algorithm. In this paper, we design an optimized quantum circuit for LWE computation. The proposed quantum circuit does not need any ancillary qubits and scales efficiently and easily if there are more qubits available on a higher qubit quantum computer.
Today's rapid progress in the physical implementation of quantum computers demands scalable synthesis methods to map practical logic designs to quantum architectures. There exist many quantum algorithms which use classical functions with superposition of states. Motivated by recent trends, in this paper, we show the design of quantum circuit to perform modular exponentiation functions using two different approaches. In the design phase, first we generate quantum circuit from a verilog implementation of exponentiation functions using synthesis tools and then apply two different Quantum Error Correction techniques. Finally the circuit is further optimized using the Linear Nearest Neighbor (LNN) Property. We demonstrate the effectiveness of our approach by generating a set of networks for the reversible modular exponentiation function for a set of input values. At the end of the work, we have summarized the obtained results, where a cost analysis over our developed approaches has been made. Experimental results show that depending on the choice of different QECC methods the performance figures can vary by up to 11%, 10%, 8% in T-count, number of qubits, number of gates respectively.
This research explores the use of superconductor electronics (SCE) for accelerating fully homomorphic encryption (FHE), focusing on the Number-Theoretic Transform (NTT), a key computational bottleneck in FHE schemes. We present SCE-NTT, a dedicated hardware accelerator based on superconductive single flux quantum (SFQ) logic and memory, targeting high performance and energy efficiency beyond the limits of conventional CMOS. To address SFQ constraints such as limited dense RAM and restricted fanin/fanout, we propose a deeply pipelined NTT-128 architecture using shift register memory (SRM). Designed for N=128 32-bit coefficients, NTT-128 comprises log2(N)=7 processing elements (PEs), each featuring a butterfly unit (BU), dual coefficient memories operating in ping-pong mode via FIFO-based SRM queues, and twiddle factor buffers. The BU integrates a Shoup modular multiplier optimized for a small area, leveraging precomputed twiddle factors. A new RSFQ cell library with over 50 parameterized cells, including compound logic units, was developed for implementation. Functional and timing correctness were validated using JoSIM analog simulations and Verilog models. A multiphase clocking scheme was employed to enhance robustness and reduce path-balancing overhead, improving circuit reliability. Fabricated results show the NTT-128 unit achieves 531 million NTT/sec at 34 GHz, over 100x faster than state-of-the-art CMOS equivalents. We also project that the architecture can scale to larger sizes, such as a 2^14-point NTT in approximately 482 ns. Key-switch throughput is estimated at 1.63 million operations/sec, significantly exceeding existing hardware. These results demonstrate the strong potential of SCE-based accelerators for scalable, energy-efficient secure computation in the post-quantum era, with further gains anticipated through advances in fabrication.
Abstract Efficient quantum comparators are a key building block in quantum algorithms, but their practical utilization during the Noisy Intermediate-Scale Quantum (NISQ) era is limited by high resource demands. In this paper, we present an automated and scalable approach focused on the synthesis of optimal n-bit quantum comparator circuits that significantly minimize key quantum parameters, namely quantum cost (QC), quantum delay (QD), and garbage outputs (GO). Our approach uses a dynamic algorithmic framework built with Python and Qiskit to adapt the circuit design based on the size of the input operands. This enables the automatic generation of resource-efficient, modular designs. Through systematic optimization of qubit assignment, gate ordering, and sub-circuit composition, our full circuit achieves substantial performance gains. Experimental validation using 4-bit comparators demonstrates 14.89% reduction in QC, 12.5% in QD, and 18.75% in GO over state-of-art designs, as validated through noise-free simulations under NISQ-era limitations. Although the algorithmic scalability of the produced circuits allows straightforward generalization to any n-bit operands without any loss in optimization quality. These findings confirm the effectiveness of our approach, suggesting that it may lead to further optimizations for related quantum circuits, including as Arithmetic Logic Units.
Quantum computing (Q-computing) is a revolutionary technology that applies quantum mechanics (QM) to implement calculations significantly quicker than traditional computers. Q-computing employs Q-bits (qubits) rather than classical bits, which can take on a superposition state, making it possible to represent both 0 and 1 at once. This distinctive property allows qubits to perform multiple calculations simultaneously, making Q computers exponentially more powerful as more qubits are added, compared to the linear scaling of classical computers. However, challenges such as qubit instability and error rates remain significant obstacles to fully realizing this potential. A vital aspect of this technology is the development of Q arithmetic circuits, which act as the foundational blocks for efficiently executing Q algorithms. Q half-adder and full-adder circuits are integral to performing fundamental arithmetic operations within Q computers. In contrast to classical adders, Q adders rely on Q gates such as Controlled NOT (CNOT) and Toffoli gates. These gates exploit Q phenomena like entanglement and superposition, allowing for more efficient computations. The Q half-adder consists of two qubits and adds two single bits, producing a carry and sum output. It utilizes the CNOT gate to compute the sum and the Toffoli gate (controlled-controlled-NOT [CCNOT]) to compute the carry. The Q full-adder builds on this, adding three qubits to produce a sum and a carry output, further increasing computational capacity. Through the entanglement of qubits, these circuits allow for more parallelism and speed compared to classical adders. Q carry-look-ahead adders (QCLAs) and Q ripple-carry adders (QRCAs) are used to perform more complex arithmetic operations based on these half-adder and full-adder structures. Q arithmetic circuits have broad applications, boosting secure key generation in cryptography, speeding up matrix operations for faster model training in machine learning, and enabling more precise, efficient image transformations in Q image processing, benefiting fields like medical imaging and computer vision.
The quantum Fourier transform and quantum wavelet transform have been cornerstones of quantum information processing. However, for non-stationary signals and anomaly detection, the Hilbert transform can be a more powerful tool, yet no prior work has provided efficient quantum implementations for the discrete Hilbert transform. This letter presents a novel construction for a quantum Hilbert transform in polylogarithmic size and logarithmic depth for a signal of length N, exponentially fewer operations than classical algorithms for the same mapping. We generalize this algorithm to create any d-dimensional Hilbert transform in depth O(dlogN). Simulations demonstrate effectiveness for tasks such as power systems control and image processing, with exact agreement with classical results.