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.
In recent years, quantum computers have attracted extensive research interests due to their potential capability of solving problems which are not easily solvable using classical computers. In parallel to the constant research aiming at the physical implementation of quantum processors, there is another branch of research developing quantum algorithms for real-life applications, many of which need to perform arithmetic operations. As one of the most important operations, quantum addition has been adopted in Shor's algorithm, quantum linear algebra algorithms and various quantum machine learning applications. Since precision is always a non-trivial issue to determine during the computation, most-significant digit-first quantum addition can be a fundamental operation for variable precision computing. Therefore, this paper proposes the first quantum adder circuit that is able to compute from the most-significant digits, which demonstrates the advantages over the state-of-the-art quantum adders requiring carry propagation to produce results from least-significant digits. We first present a review of quantum addition circuits design, and then propose a novel method to implement quantum most-significant digit-first adders. Scalability and quantitative comparisons for different quantum full adder, quantum carry-ripple adder and quantum most-significant digit-first adder circuits have been investigated, where all circuits are implemented on IBM Qiskit SDK.
Nowadays, quantum computers are capturing the attention of researchers because of their potential capability to solve problems otherwise not solvable with classical computers. In parallel to the constant research aimed at solving problems related to the physical implementation of such computers, there is also another branch of research trying to develop quantum algorithms. Many of the existing algorithms today need to perform arithmetic operations. In this thesis, the development of a software library of quantum arithmetic circuits - capable of interfacing with the main languages related to the world of Quantum Computing, such as Qiskit, Cirq and T-ket - is presented. With the aim of implementing this software library, the basics of quantum computation were first studied and subsequently an extensive bibliographic research was carried out, aimed at identifying the best performing arithmetic circuits currently available. After determining the circuits to be implemented, the software development has begun using the Python language. During the development of the library, with the aim of making simpler future development, code's modularity - by organizing the general package in many subpackages - and readability - by respecting the guidelines proposed in the PEP8 style guide - were looked for. In addition to what has already been said, a detailed documentation has been produced using Sphinx. Once the development of the library was completed, the functionality of each circuit was tested with simulations on classical computers; moreover, some components were tested on real free-accessible quantum computers, in order to characterize their behavior. Even though the results obtained on real hardware proved that many of the circuits implemented in this library will be reliably executed by more sophisticated and performing quantum computers, this library can be currently employed in an effective way in the simulation of quantum circuits on classical computers.
Quantum computing, based on the fundamental principles of quantum mechanics, has become a breakthrough that has the potential to revolutionize computing. At the forefront of this quantum revolution are quantum algorithms that use the origin of qubits to solve computational problems much faster than classical algorithms. This article provides a review of quantum algorithms to introduce their principles, examine famous examples such as the Grover and Shor algorithms, and delve into their applications, including quantum machine learning. Exploring the fundamentals of quantum computing begins with an overview that highlights the unique features of quantum computing compared to classical computing. We then examine several different algorithmic paradigms to highlight the unique advantages that quantum parallelism and interference bring to computing. The best knowledge of quantum algorithms focuses on Grover's blind search, Shor's efficient factorization algorithm, and the quantum phase approach for solving quantum chemistry and eigenvalue problems. As well as celebrating the achievements of quantum algorithms, this research also looks at the challenges and limitations that hinder their widespread use. Topics such as decoherence, error correction, and finding errors in quantum computing are discussed in the context of overcoming obstacles to the use of practical quantum algorithms. In addition, the latest developments are clarified by showing the successes of the experiments and their implications for the future. As we stand at the forefront of a new era in computing, this article not only provides a snapshot of the current state of quantum algorithms but also speculates on future directions. The potential applications of quantum algorithms in many fields and the ongoing quest to overcome current limitations offer exciting opportunities for further research. This research aims to contribute to the ongoing debate about quantum algorithms, gaining a deeper understanding of their impact on the future of computing.
As quantum computing technology advances, the need for optimized arithmetic circuits continues to grow. This paper presents the implementation and resource estimation of a library of quantum arithmetic algorithms, including addition, multiplication, division, and modular exponentiation. Using the Azure Quantum Resource Estimator, we evaluate runtime, qubit usage, and space-time trade-offs and identify the best-performing algorithm for each arithmetic operation. We explore the design space for division, optimize windowed modular exponentiation, and identify the tipping point between multipliers, demonstrating effective applications of resource estimation in quantum research. Additionally, we highlight the impact of parallelization, reset operations, and uncomputation techniques on implementation and resource estimation. Our findings provide both a practical library and a valuable knowledge base for selecting and optimizing quantum arithmetic algorithms in real-world applications.