In recent decades, the field of quantum computing has experienced remarkable progress. This progress is marked by the superior performance of many quantum algorithms compared with their classical counterparts, with Shor's algorithm serving as a prominent illustration. Quantum arithmetic circuits, which are the fundamental building blocks in numerous quantum algorithms, have attracted much attention. Despite extensive exploration of various designs in the existing literature, researchers remain keen to develop novel designs and improve existing ones. In this review article, we aim to provide a systematically organized and easily comprehensible overview of the current state of the art in quantum arithmetic circuits. Specifically, this study covers fundamental operations such as addition, subtraction, multiplication, division and modular exponentiation. We delve into the detailed quantum implementations of these prominent designs and evaluate their efficiency considering various objectives. We also discuss potential applications of the presented arithmetic circuits and suggest future research directions.This article is part of the theme issue 'Emerging technologies for future secure computing platforms'.
In recent decades, the field of quantum computing has experienced remarkable progress. This progress is marked by the superior performance of many quantum algorithms compared with their classical counterparts, with Shor's algorithm serving as a prominent illustration. Quantum arithmetic circuits, which are the fundamental building blocks in numerous quantum algorithms, have attracted much attention. Despite extensive exploration of various designs in the existing literature, researchers remain keen to develop novel designs and improve existing ones. In this review article, we aim to provide a systematically organized and easily comprehensible overview of the current state of the art in quantum arithmetic circuits. Specifically, this study covers fundamental operations such as addition, subtraction, multiplication, division and modular exponentiation. We delve into the detailed quantum implementations of these prominent designs and evaluate their efficiency considering various objectives. We also discuss potential applications of the presented arithmetic circuits and suggest future research directions.This article is part of the theme issue 'Emerging technologies for future secure computing platforms'.
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.
In recent decades, quantum computing has witnessed remarkable progress, achieved through various advancements across the technology stack, such as quantum error-correcting codes and quantum algorithms. It is noteworthy that several promising algorithms incorporate quantum arithmetic circuits as fundamental building blocks. However, the inherent properties of quantum circuits challenge the efficiency of quantum arithmetic circuits, prompting creative solutions. While several quantum arithmetic circuits have been proposed, there is still a substantial gap in quantum arithmetic circuits optimization. For example, methods for integrating classical techniques such as high radix strategy into quantum designs still remain underexplored, highlighting a significant space for further advancement. This thesis aims to improve the performance of quantum arithmetic designs by integrating classical arithmetic circuit design techniques. Specifically, this thesis contains the following research: (1) The utilization of classical higher radix strategy to enhance quantum addition, reducing overall cost by lowering T-depth and T-count. The proposed design outperforms existing quantum carry-lookahead adders. (2) The application of Ling structure, achieving a reduced Toffoli-depth of 4log(n/2). (3) The exploration of the Kogge-Stone architecture, resulting in the lowest Toffoli-depth of log(n) for quantum adders. (4) The development of an efficient modular addition framework using carry-save architecture, demonstrating a 33.3% improvement in Toffoli depth compared to existing designs. (5) The design of an optimized quantum non-restoring divider framework. (6) A comprehensive overview of current advancements in quantum arithmetic designs, offering insights into potential research directions. These proposed designs are mapped to real-world quantum hardware architectures, including Noisy Intermediate-Scale Quantum systems, to validate their functionality and evaluate efficiency. Their applications in quantum machine learning and cryptography further underscore the broader impact of these improvements. Overall, this thesis makes significant advancements in reducing quantum circuit depth and improving resource efficiency, contributing to the development of scalable and efficient large-scale quantum circuits. By adapting classical design strategies to quantum circuits, it not only enhances various quantum circuit designs but also fosters further exploration at the intersection of classical and quantum computing.
The Quantum Fourier Transform (QFT) grants competitive advantages, especially in resource usage and circuit approximation, for performing arithmetic operations on quantum computers, and offers a potential route towards a numerical quantum-computational paradigm. In this paper, we utilize efficient techniques to implement QFT-based integer addition and multiplications. These operations are fundamental to various quantum applications including Shor's algorithm, weighted sum optimization problems in data processing and machine learning, and quantum algorithms requiring inner products. We carry out performance evaluations of these implementations based on IBM's superconducting qubit architecture using different compatible noise models. We isolate the sensitivity of the component quantum circuits on both one-/two-qubit gate error rates, and the number of the arithmetic operands' superposed integer states. We analyze performance, and identify the most effective approximation depths for quantum add and quantum multiply within the given context. We observe significant dependency of the optimal approximation depth on the degree of machine noise and the number of superposed states in certain performance regimes. Finally, we elaborate on the algorithmic challenges - relevant to signed, unsigned, modular and non-modular versions - that could also be applied to current implementations of QFT-based subtraction, division, exponentiation, and their potential tensor extensions. We analyze performance trends in our results and speculate on possible future development within this computational paradigm.
Quantum computing has been considered as an emerging approach in addressing problems which are not easily solvable using classical computers. In parallel to the physical implementation of quantum processors, quantum algorithms have been actively developed for real-life applications to show quantum advantages, many of which benefit from quantum arithmetic algorithms and their efficient implementations. As one of the most important operations, quantum addition has been adopted in Shor's algorithm and quantum linear algebra algorithms. Although various least-significant digit-first quantum adders have been introduced in previous work, interest in investigating the efficient implementation of most-significant digit-first addition is growing. In this work, we propose a novel design method for most-significant digit-first addition with several quantum circuit optimisations to reduce the number of quantum bits (i.e. qubits), quantum gates, and circuit depth. An open-source library of different arithmetic operators based on our proposed method is presented, where all circuits are implemented on IBM Qiskit SDK. Extensive experiments demonstrate that our proposed design, together with the optimisation techniques, reduces T-depth by up-to 4.0×, T-count by 3.5×, and qubit consumption by 1.2×.
Shor's factorization algorithm, as one of the most significant achievements in quantum computing, exhibits an exponential speedup compared to the corresponding classical algorithm. In Shor's factorization algorithm, modular exponentiation is one of the most computationally intensive components, which relies on the modular addition building block. This work aims to explore novel designs for enhancing the efficiency of quantum modular addition. In particular, we introduce a novel quantum modular addition framework based on carry-save architecture, which facilitates the conversion of multiple 2-addend quantum operations within modular addition into a single 3-addend operation, thereby reducing the computational depth. Compared to the most efficient existing quantum modular addition, our design has achieved an impressive result - a reduction in Toffoli Depth by up to 33.33%, while maintaining comparable Toffoli Count and Qubit Count. This research underscores the potential of carry-save architecture as a promising technique for accelerating quantum modular arithmetic as well as advancing the development of quantum computing in general.
A paradigm shift in computation is being brought about by quantum computing, which uses the concepts of quantum mechanics to tackle problems that even the most powerful conventional supercomputers cannot solve. This review provides an in-depth overview of the field, covering everything from basic concepts to the cutting edge. The three fundamental building blocks of quantum processing—the qubit, superposition, and entanglement—are first described.These ideas enable quantum computers to concurrently explore large computational domains. After that, the paper examines the various physical implementations, highlighting the advantages and disadvantages of the top hardware platforms, such as neutral atoms, trapped ions, photonic systems, and superconducting circuits, in terms of coherence and scalability. Shor's method for integer factorization and Grover's algorithm for unstructured search are two examples of groundbreaking quantum algorithms that are highlighted for their potential to achieve exponential and quadratic speedups over their classical counterparts. We also examine how programming languages that bridge the gap between abstract algorithms and physical hardware are being developed, as well as the new quantum software stack. The paper also explores how quantum computing can revolutionize a number of fields, such as machine learning, materials research, medication development, and cryptography. subsequently, we discuss two of the biggest challenges impeding the development of large-scale, fault-tolerant quantum computers: the requirement for robust quantum error correction and decoherence. In the end, a view of the current period of Noisy Intermediate-Scale Quantum (NISQ) and the path towards quantum advantage is presented. Researchers, students, and professionals looking for a comprehensive grasp of this quickly developing and revolutionary topic are expected to find this review to be an invaluable asset.