An official website of the United States government
This paper proposes a new and improved implementation of a quantum integer multiplier. Performing arithmetic computations is sometimes a necessary step in the implementation of quantum algorithms. In this work, Quantum Fourier Transform is used in order to perform scalable arithmetic in a generic bit-width quantum system. In the phase domain, addition can be implemented through accumulated controlled rotations on the qubits’ state. Leveraging this, and inspired by the classical implementation of an array multiplier, a new integer multiplier is fully designed and tested in a quantum environment. The depth of a quantum circuit is the number of computational steps necessary to completion, and it is a key parameter that reflects on the performance of the design. The new design reduces the quantum depth of the design from the exponential order of the previously proposed designs to polynomial order.
more »
« less
Approximate Quantum Array Multiplier
Multiplication is a frequent computation in many algorithms, classical and quantum. This paper targets the implementation of quantum integer multiplication. Quantum array multipliers take inspiration from classical array multipliers, with the result of reduced circuit depth. They take advantage of the quantum phase domain, through rotations controlled by the multiplier’s qubits. This work further explores this implementation by applying approximate rotations. Although this approach can have an impact on the accuracy of the result, the reduction in depth can result in better outcomes when noise is involved.
more »
« less
- Award ID(s):
- 2300476
- PAR ID:
- 10593441
- Publisher / Repository:
- IEEE
- Date Published:
- ISBN:
- 979-8-3315-4137-8
- Page Range / eLocation ID:
- 58 to 66
- Subject(s) / Keyword(s):
- Quantum Multiplication Quantum Phase Estimation Approximate Quantum Computing
- Format(s):
- Medium: X
- Location:
- Montreal, QC, Canada
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The rapid advancement in quantum technology has initiated a new round of post-quantum cryptography (PQC) related exploration. The key encapsulation mechanism (KEM) Saber is an important module lattice-based PQC, which has been selected as one of the PQC finalists in the ongoing National Institute of Standards and Technology (NIST) standardization process. On the other hand, however, efficient hardware implementation of KEM Saber has not been well covered in the literature. In this paper, therefore, we propose a novel cyclic-row oriented processing (CROP) strategy for efficient implementation of the key arithmetic operation of KEM Saber, i.e., the polynomial multiplication. The proposed work consists of three layers of interdependent efforts: (i) first of all, we have formulated the main operation of KEM Saber into desired mathematical forms to be further developed into CROP based algorithms, i.e., the basic version and the advanced higher-speed version; (ii) then, we have followed the proposed CROP strategy to innovatively transfer the derived two algorithms into desired polynomial multiplication structures with the help of a series of algorithm-architecture co-implementation techniques; (iii) finally, detailed complexity analysis and implementation results have shown that the proposed polynomial multiplication structures have better area-time complexities than the state-of-the-art solutions. Specifically, the field-programmable gate array (FPGA) implementation results show that the proposed design, e.g., the basic version has at least less 11.2% area-delay product (ADP) than the best competing one (Cyclone V device). The proposed high-performance polynomial multipliers offer not only efficient operation for output results delivery but also possess low-complexity feature brought by CROP strategy. The outcome of this work is expected to provide useful references for further development and standardization process of KEM Saber.more » « less
-
Recent advances in quantum computing have initiated a new round of cryptosystem innovation as the existing public-key cryptosystems are proven to be vulnerable to quantum attacks. Several types of cryptographic algorithms have been proposed for possible post-quantum cryptography (PQC) candidates and the lattice-based key encapsulation mechanism (KEM) Saber is one of the most promising algorithms. Noticing that the polynomial multiplication over ring is the key arithmetic operation of KEM Saber, in this paper, we propose a novel strategy for efficient implementation of polynomial multiplication on the hardware platform. First of all, we present the proposed mathematical derivation process for polynomial multiplication. Then, the proposed hardware structure is provided. Finally, field-programmable gate array (FPGA) based implementation results are obtained, and it is shown that the proposed design has better performance than the existing ones. The proposed polynomial multiplication can be further deployed to construct efficient hardware cryptoprocessors for KEM Saber.more » « less
-
Shor's factoring algorithm, believed to provide an exponential speedup over classical computation, relies on finding the period of an exactly periodic quantum modular multiplication operator. This exact periodicity is the hallmark of an integrable system, which is paradoxical from the viewpoint of quantum chaos, given that the classical limit of the modular multiplication operator is a highly chaotic system that occupies the “maximally random” Bernoulli level of the classical ergodic hierarchy. In this work, we approach this apparent paradox from a quantum dynamical systems viewpoint, and consider whether signatures of ergodicity and chaos may indeed be encoded in such an “integrable” quantization of a chaotic system. We show that Shor's modular multiplication operator, in specific cases, can be written as a superposition of quantized -baker's maps exhibiting more typical signatures of quantum chaos and ergodicity. This work suggests that the integrability of Shor's modular multiplication operator may stem from the interference of other “chaotic” quantizations of the same family of maps, and paves the way for deeper studies on the interplay of integrability, ergodicity, and chaos in and via quantum algorithms. Published by the American Physical Society2024more » « less
-
Residue Number Systems (RNS) demonstrate the fascinating potential to serve integer addition/multiplication-intensive applications. The complexity of Artificial Intelligence (AI) models has grown enormously in recent years. From a computer system’s perspective, ensuring the training of these large-scale AI models within an adequate time and energy consumption has become a big concern. Matrix multiplication is a dominant subroutine in many prevailing AI models, with an addition/multiplication-intensive attribute. However, the data type of matrix multiplication within machine learning training typically requires real numbers, which indicates that RNS benefits for integer applications cannot be directly gained by AI training. The state-of-the-art RNS real number encodings, including floating-point and fixed-point, have defects and can be further enhanced. To transform default RNS benefits to the efficiency of large-scale AI training, we propose a low-cost and high-accuracy RNS fixed-point representation: Single RNS Logical Partition (S-RNS-Logic-P) representation with Scaling Down Postprocessing Multiplication (SD-Post-Mul). Moreover, we extend the implementation details of the other two RNS fixed-point methods: Double RNS Concatenation (D-RNS-Concat) and Single RNS Logical Partition (S-RNS-Logic-P) representation with Scaling Down Preprocessing Multiplication (SD-Pre-Mul). We also design the architectures of these three fixed-point multipliers. In empirical experiments, our S-RNS-Logic-P representation with SD-Post-Mul method achieves less latency and energy overhead while maintaining good accuracy. Furthermore, this method can easily extend to the Redundant Residue Number System (RRNS) to raise the efficiency of error-tolerant domains, such as improving the error correction efficiency of quantum computing.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/QCE60285.2024.00017
