Multiplication is a frequent computation in many algorithms, classical and quantum. This paper targets the im-plementation 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 mul-tiplier'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.
Multiplication is a frequent computation in many algorithms, classical and quantum. This paper targets the im-plementation 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 mul-tiplier'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.
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.
We present a quantum algorithm for multiplying two n-bit integers with overall circuit depth and T-depth both bounded by O(logn), while using O(n2) gates and ancillary qubits. Our construction generates partial products via indicator-controlled copying and adds them using a tree of reversible 3-to-2 adders followed by one quantum carry-lookahead adder. Building on the carry-save adders of Kim et al., we combine full input fanout, workspace reuse, and phase-corrected gate implementations to reduce T-depth. We provide explicit circuit constructions, proofs of correctness, and concrete closed-form resource bounds.
We present a novel set of reversible modular multipliers applicable to quantum computing, derived from three classical techniques: 1) traditional integer division, 2) Montgomery residue arithmetic, and 3) Barrett reduction. Each multiplier computes an exact result for all binary input values, while maintaining the asymptotic resource complexity of a single (non-modular) integer multiplier. We additionally conduct an empirical resource analysis of our designs in order to determine the total gate count and circuit depth of each fully constructed circuit, with inputs as large as 2048 bits. Our comparative analysis considers both circuit implementations which allow for arbitrary (controlled) rotation gates, as well as those restricted to a typical fault-tolerant gate set.
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 modular multipliers are a promising development in the field of quantum computing that aim to perform modular multiplication faster and more efficiently than classical algorithms. This is achieved by encoding the numbers being multiplied into quantum bits (qubits) and using quantum gates to manipulate them in a way that represents the calculation. Since quantum physics principles like superposition and entanglement dramatically speed up processing compared to conventional computing, many calculations may be run simultaneously. Quantum modular multipliers have the potential to have a significant impact in a range of fields, including cryptography and beyond, since they offer a faster and more efficient way to do modular multiplications. Several fields, including simulation, optimization, and cryptography, can benefit from the use of quantum computing.One of the crucial operations in many of these applications is modular multiplication, a sort of multiplication that requires obtaining the remainder of the product of two numbers when divided by a third number. In this paper, we provide a novel modular multiplication method based on a quantum algorithm. To examine its complexity and compare it to that of current adders, we employ a novel form of adder that is intended to not retain the final carry. This adder's decrease percentage in terms of gates and depth is roughly 70%. Our method takes advantage of the special qualities of qubits to complete the computation significantly more quickly than conventional algorithms. It is based on the fundamental ideas of quantum physics, such as superposition and entanglement.
Quantum multiplication is a fundamental operation in quantum computing. It is important to have a quantum multiplier with low complexity. In this paper, we propose the Quantum Multiplier Based on Exponent Adder (QMbead), a new approach that requires just log2(n) qubits to multiply two n-bit integer numbers, in addition to O(n) ancillary qubits used for quantum state preparation. The QMbead uses a so-called exponent encoding to respectively represent two multiplicands as two superposition states which are prepared by a quantum state preparation method, then employs a quantum adder to obtain the sum of these two superposition states, and subsequently measures the outputs of the quantum adder to calculate the product of the multiplicands. Different quantum adders can be used in the QMbead. The circuit depth and time complexity of the QMbead, using a logarithmic-depth quantum carry lookahead adder (QCLA) as adder, are O(logn) and O(nlogn), respectively. The gate complexity of the QMbead is O(n). The circuit depth and gate complexity of the QMbead is better than existing quantum multipliers such as the quantum Karatsuba multiplier and the QFT based multiplier. The time complexity of the QMbead is identical to that of the fastest classical multiplication algorithm, Harvey-Hoeven algorithm. Interestingly, the QMbead maintains an advantage over the Harvey-Hoeven algorithm, given that the latter is only suitable for excessively large numbers, whereas the QMbead is valid for both small and large numbers. The multiplicand can be either an integer or a decimal number. The QMbead has been implemented on quantum simulators to compute products with a bit length of up to 273 bits using only 17 qubits, excluding the ancillary qubits used for quantum state preparation. This establishes QMbead as an efficient solution for multiplying large integer or decimal numbers with many bits.