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.
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, 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, 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.
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.
Quantum computing is an emerging technology in which quantum mechanical properties are suitably utilized to perform certain compute-intensive operations faster than classical computers. Quantum algorithms are designed as a combination of quantum circuits that each require a large number of quantum gates, which is a challenge considering the limited number of qubit resources available in quantum computing systems. Our work proposes a technique to optimize quantum arithmetic algorithms by reducing the hardware resources and the number of qubits based on ZX calculus. We have utilized ZX calculus rewrite rules for the optimization of fault-tolerant quantum multiplier circuits where we are able to achieve a significant reduction in the number of ancilla bits and T-gates as compared to the originally required numbers to achieve fault-tolerance. Our work is the first step in the series of arithmetic circuit optimization using graphicalrewrite tools and it pavesthe way for advancing the optimization of various complex quantum circuits and establishing the potential for new applications of the same.
MD5 and SHA-1 are widely studied hash functions in cryptanalysis, owing to their well-structured round functions and historical significance in cryptography. This paper presents improved quantum circuit implementations of MD5 and SHA-1 specifically optimized for quantum cryptanalysis. We reduce the quantum implementation cost of auxiliary functions and eliminate the use of ancilla qubits, while reducing circuit depth (the number of sequential gate layers) by parallelizing multiple additions in the round operations of MD5 and SHA-1. Additionally, the quantum implementations of MD5 and SHA-1 are optimized by considering a fixed input size under the attack scenario. The proposed implementations achieve a 63% improvement in the depth - qubit count metric for MD5 and a 27% improvement for SHA-1 compared to previous works. By providing reduced quantum resources, this work establishes an improved baseline for the quantum cryptanalysis of MD5 and SHA-1. We analyze quantum attacks on MD5 and SHA-1, showing that the preimage attacks require a full depth of 279 and 296 for MD5 and SHA-1, respectively, while the collision attacks require a full depth of 254 and 264. For a realistic evaluation, we also estimate the quantum resources for fault-tolerant quantum computation, including the number of physical qubits and the runtime, to break MD5 and SHA-1.
Quantum algorithms are often represented in terms of quantum circuits operating on ideal (logical) qubits. However, the practical implementation of these algorithms poses significant challenges. Many quantum algorithms require a substantial number of logical qubits, and the inherent susceptibility to errors of quantum computers require quantum error correction. The integration of error correction introduces overhead in terms of both space (physical qubits required) and runtime (how long the algorithm needs to be run for). This paper addresses the complexity of comparing classical and quantum algorithms, primarily stemming from the additional quantum error correction overhead. We propose a comprehensive framework that facilitates a direct and meaningful comparison between classical and quantum algorithms. By acknowledging and addressing the challenges introduced by quantum error correction, our framework aims to provide a clearer understanding of the comparative performance of classical and quantum computing approaches. This work contributes to understanding the practical viability and potential advantages of quantum algorithms in real-world applications. We apply our framework to quantum cryptanalysis, since it is well known that quantum algorithms can break factoring and discrete logarithm based cryptography and weaken symmetric cryptography and hash functions. In order to estimate the real-world impact of these attacks, apart from tracking the development of fault-tolerant quantum computers it is important to have an estimate of the resources needed to implement these quantum attacks. This analysis provides state-of-the art snap-shot estimates of the realistic costs of implementing quantum attacks on these important cryptographic algorithms, assuming quantum fault-tolerance is achieved using surface code methods, and spanning a range of potential error rates. These estimates serve as a guide for gauging the realistic impact of these algorithms and for benchmarking the impact of future advances in quantum algorithms, circuit synthesis and optimization, fault-tolerance methods and physical error rates.