In this paper, we present Q# implementations for arbitrary single-variabled fixed-point arithmetic op-erations for a gate-based quantum computer based on lookup tables (LUTs). In general, this is an inefficent way of implementing a function since the number of inputs can be large or even infinite. However, if the input domain can be bounded and there can be some error tolerance in the output (both of which are often the case in practical use-cases), the quantum LUT implementation of certain quantum arithmetic functions can be more efficient than their corresponding reversible arithmetic implementations. We discuss the implementation of the LUT using Q# and its approximation errors. We then show examples of how to use the LUT to implement quantum arithmetic functions and compare the resources required for the implementation with the current state-of-the-art bespoke implementations of some commonly used arithmetic functions. The implementation of the LUT is designed for use by practitioners to use when implementing end-to-end quantum algorithms. In addition, given its well-defined approximation errors, the LUT implementation makes for a clear benchmark for evaluating the efficiency of bespoke quantum arithmetic circuits.
In this paper, we present Q# implementations for arbitrary single-variabled fixed-point arithmetic op-erations for a gate-based quantum computer based on lookup tables (LUTs). In general, this is an inefficent way of implementing a function since the number of inputs can be large or even infinite. However, if the input domain can be bounded and there can be some error tolerance in the output (both of which are often the case in practical use-cases), the quantum LUT implementation of certain quantum arithmetic functions can be more efficient than their corresponding reversible arithmetic implementations. We discuss the implementation of the LUT using Q# and its approximation errors. We then show examples of how to use the LUT to implement quantum arithmetic functions and compare the resources required for the implementation with the current state-of-the-art bespoke implementations of some commonly used arithmetic functions. The implementation of the LUT is designed for use by practitioners to use when implementing end-to-end quantum algorithms. In addition, given its well-defined approximation errors, the LUT implementation makes for a clear benchmark for evaluating the efficiency of bespoke quantum arithmetic circuits.
Many promising applications of quantum computing with a provable speedup center around the HHL algorithm. Due to restrictions on the hardware and its significant demand on qubits and gates in known implementations, its execution is prohibitive on near-term quantum computers. Aiming to facilitate such NISQ-implementations, we propose a novel circuit approximation technique that enhances the arithmetic subrou-tines in the HHL, which resemble a particularly resource-demanding component in small-scale settings. For this, we provide a description of the algorithmic implementation of space-efficient rotations of polynomial functions that do not demand explicit arithmetic calculations inside the quantum circuit. We show how these types of circuits can be reduced in depth by providing a simple and powerful approximation technique. Moreover, we provide an algorithm that converts lookup-tables for arbitrary function rotations into a structure that allows an application of the approximation technique. This allows implementing approximate rotation circuits for many polynomial and non-polynomial functions. Experimental results obtained for realistic early-application dimensions show significant improve-ments compared to the state-of-the-art, yielding small circuits while achieving good approximations.
We present a synthesis framework to map logic networks into quantum circuits for quantum computing. The synthesis framework is based on lookup-table (LUT) networks, which play a key role in conventional logic synthesis. Establishing a connection between LUTs in an LUT network and reversible single-target gates in a reversible network allows us to bridge conventional logic synthesis with logic synthesis for quantum computing, despite several fundamental differences. We call our synthesis framework LUT-based hierarchical reversible logic synthesis (LHRS). Input to LHRS is a classical logic network representing an arbitrary Boolean combinational operation; output is a quantum network (realized in terms of Clifford+T gates). The framework allows one to account for qubit count requirements imposed by the overlying quantum algorithm or target quantum computing hardware. In a fast first step, an initial network is derived that only consists of single-target gates and already completely determines the number of qubits in the final quantum network. Different methods are then used to map each single-target gate into Clifford+T gates, while aiming at optimally using available resources. We demonstrate the versatility of our method by conducting a design space exploration using different parameters on a set of large combinational benchmarks. On the same benchmarks, we show that our approach can advance over the state-of-the-art hierarchical reversible logic synthesis algorithms.
This paper introduces a comprehensive quantum calculator using Qiskit that integrates quantum arithmetic and logic functions into a single calculator. The calculator relies on quantum Fourier transforms (QFT), controlled-phase gates, and quantum modular arithmetic to perform basic arithmetic operations such as addition, subtraction, and multiplication. These arithmetic techniques used quantum parallelism and interference to perform calculations more efficiently, particularly for tasks involving large numerical inputs. Numerical values are stored in qubit registers and processed using QFT-based circuits, which enable efficient and reversible mathematical computations. In addition to arithmetic operations, the calculator also implements quantum logic algorithms, including Grover’s Search and the Deutsch-Jozsa algorithm. Grover’s algorithm is an unstructured search algorithm that operates by constructing an oracle and iteratively amplifying the probability amplitude of the target solution. This amplitude amplification significantly increases the likelihood of measuring the desired outcome. Due to this property, Grover’s algorithm has practical relevance in applications such as database searching and solving combinatorial optimization problems. The Deutsch-Jozsa algorithm determines whether or not a certain Boolean function is constant or balanced and offers an exponential speed up compared to classical methods for this class of problem. A key fundamental function of the calculator is the ability to generate hybrid quantum circuits that support both arithmetic and logical functions. That allows the exploration of simple as well as complex problem-solving strategies that take advantage of both quantum arithmetic and decision-making algorithms. For instance, combining Grover’s amplification with function characterizations from the Deutsch-Jozsa algorithm provides not only interesting circuit configurations but also adds value to the possibilities of the algorithms. This research offers a modular idea and allows exploring the fundamental principles of quantum computing generally speaking and will be a valuable resource for educational as well as research purposes in the rapidly growing field of quantum algorithm development.
Windowed arithmetic [Gidney, 2019] is a technique for reducing the cost of quantum arithmetic circuits with space--time tradeoffs using memory queries to precomputed tables. It can reduce the asymptotic cost of modular exponentiation from O(n3) to O(n3/log2n) operations, resulting in the current state-of-the-art compilations of quantum attacks against modern cryptography. In this work we introduce four optimizations to windowed modular exponentiation. We (1) show how the cost of unlookups can be reduced by 66% asymptotically in the number of bits, (2) illustrate how certain addresses can be bypassed, reducing both circuit depth and the overall lookup cost, (3) demonstrate that multiple lookup--addition operations can be merged into a single, larger lookup at the start of the modular exponentiation circuit, and (4) reduce the depth of the unary conversion for unlookups. On a logical level, this leads to a 3% improvement in Toffoli count and Toffoli depth for modular exponentiation circuits relevant to cryptographic applications. This translates to some improvements on [Gidney and Ekerå, 2021]'s factoring algorithm: for a given number of physical qubits, our improvements show a reduction in the expected runtime from 2% to 6% for factoring RSA-2048 integers.
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 computers offer the potential to extend our abilities to tackle computational problems in fields such as number theory, encryption, search and scientific computation. Up to a superpolynomial speedup has been reported for quantum algorithms in these areas. Motivated by the promise of faster computations, the development of quantum machines has caught the attention of both academics and industry researchers. Quantum machines are now at sizes where implementations of quantum algorithms or their components are now becoming possible. In order to implement quantum algorithms on quantum machines, resource efficient circuits and functional blocks must be designed. In this work, we propose quantum circuits for Galois and integer arithmetic. These quantum circuits are necessary building blocks to realize quantum algorithms. The design of resource efficient quantum circuits requires the designer takes into account the gate cost, quantum bit (qubit) cost, depth and garbage outputs of a quantum circuit. Existing quantum machines do not have many qubits meaning that circuits with high qubit cost cannot be implemented. In addition, quantum circuits are more prone to errors and garbage output removal adds to overall cost. As more gates are used, a quantum circuit sees an increased rate of failure. Failures and error rates can be countered by using quantum error correcting codes and fault tolerant implementations of universal gate sets (such as Clifford+T gates). However, Clifford+T gates are costly to implement with the T gate being significantly more costly than the Clifford gates. As a result, designers working with Clifford+T gates seek to minimize the number of T gates (T-count) and the depth of T gates (T-depth). In this work, we propose quantum circuits for Galois and integer arithmetic with lower T-count, T-depth and qubit cost than existing work. This work presents novel quantum circuits for squaring and exponentiation over binary extension fields (Galois fields of form GF(2 m )). The proposed circuits are shown to have lower depth, qubit and gate cost to existing work. We also present quantum circuits for the core operations of multiplication and division which enjoy lower T-count, T-depth and qubit costs compared to existing work. This work also illustrates the design of a T-count and qubit cost efficient design for the square root. This work concludes with an illustration of how the arithmetic circuits can be combined into a functional block to implement quantum image processing algorithms.