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.
The principle of superposition is a key ingredient for quantum mechanics. A recent work [Phys. Rev. Lett.116, 110403 (2016)10.1103/PhysRevLett.116.110403] has shown that a quantum adder that deterministically generates a superposition of two unknown states is forbidden. Here we consider the implementation of the probabilistic quantum adder in the 3D cavity-transmon system. Our implementation is based on a three-level superconducting transmon qubit dispersively coupled to two cavities. Numerical simulations show that high-fidelity generation of the superposition of two coherent states is feasible with current circuit QED technology. Our method also works for other physical systems such as two optical cavities coupled to a three-level atom or two nitrogen-vacancy center ensembles interacted with one three-level superconducting flux qubit.
The quantum adder is an essential attribute of a quantum computer, just as classical adder is needed for operation of a digital computer. We model the quantum full adder as a realistic complex algorithm on a large number of qubits in an Ising spin quantum computer. Our results are an important step toward effective modeling of the quantum modular adder which is needed for Shor's and other quantum algorithms. Our full adder has the following features. (i) The near-resonant transitions with small detunings are completely suppressed, which allows us to decrease errors by several orders of magnitude and to model a 1000-qubit full adder. (We add a 1000-bit number using 2001 spins.) (ii) We construct the full adder gates directly as sequences of radio-frequency pulses, rather than breaking them down into generalized logical gates, such as Control-Not and one qubit gates. This substantially reduces the number of pulses needed to implement the full adder. (The maximum number of pulses required to add one bit (F-gate) is 15.) (iii) Full adder is realized in a homogeneous spin chain. (iv) The phase error is minimized: the F-gates generate approximately the same phase for different states of the superposition. (v) Modeling of the full adder is performed using quantum maps instead of differential equations. This allows us to reduce the calculation time to a reasonable value.