Quantum Carry-Save Arithmetic

In this paper, we propose an efficient quantum carry-lookahead adder based on the higher radix structure. For the addition of two $n$-bit numbers, our adder uses $O(n)-O(\frac{n}{r})$ qubits and $O(n)+O(\frac{n}{r})$ T gates to get the correct answer in T-depth $O(r)+O(\log{\frac{n}{r}})$, where $r$ is the radix. Quantum carry-lookahead adder has already attracted some attention because of its low T-depth. Our work further reduces the overall cost by introducing a higher ra...

We present a distributed implementation of Shor's quantum factoring algorithm on a distributed quantum network model. This model provides a means for small capacity quantum computers to work together in such a way as to simulate a large capacity quantum computer. In this paper, entanglement is used as a resource for implementing non-local operations between two or more quantum computers. These non-local operations are used to implement a distributed factoring circuit with pol...

We present a new linear-depth ripple-carry quantum addition circuit. Previous addition circuits required linearly many ancillary qubits; our new adder uses only a single ancillary qubit. Also, our circuit has lower depth and fewer gates than previous ripple-carry adders.

Reversible circuits for modular multiplication $Cx$%$M$ with $x<M$ arise as components of modular exponentiation in Shor's quantum number-factoring algorithm. However, existing generic constructions focus on asymptotic gate count and circuit depth rather than actual values, producing fairly large circuits not optimized for specific $C$ and $M$ values. In this work, we develop such optimizations in a bottom-up fashion, starting with most convenient $C$ values. When zero-initia...

Considering its relevance in the field of cryptography, integer factorization is a prominent application where Quantum computers are expected to have a substantial impact. Thanks to Shor's algorithm this peculiar problem can be solved in polynomial time. However, both the number of qubits and applied gates detrimentally affect the ability to run a particular quantum circuit on the near term Quantum hardware. In this work, we help addressing both these problems by introducing ...

Quantum modular adders are one of the most fundamental yet versatile quantum computation operations. They help implement functions of higher complexity, such as subtraction and multiplication, which are used in applications such as quantum cryptanalysis, quantum image processing, and securing communication. To the best of our knowledge, there is no existing design of quantum modulo $(2n+1)$ adder. In this work, we propose four quantum adders targeted specifically for modulo $...

We present the first exact quantum adder with sublinear depth and no ancilla qubits. Our construction is based on classical reversible logic only and employs low-depth implementations for the CNOT ladder operator and the Toffoli ladder operator, two key components to perform ripple-carry addition. Namely, we demonstrate that any ladder of $n$ CNOT gates can be replaced by a CNOT-circuit with $O(\log n)$ depth, while maintaining a linear number of gates. We then generalize thi...

In this work, we propose an adder for the 2D NTC architecture, designed to match the architectural constraints of many quantum computing technologies. The chosen architecture allows the layout of logical qubits in two dimensions and the concurrent execution of one- and two-qubit gates with nearest-neighbor interaction only. The proposed adder works in three phases. In the first phase, the first column generates the summation output and the other columns do the carry-lookahead...

In this work we define an universal arithmetical algorithm, by means of the standard quantum mechanical formalism, called universal qm-arithmetical algorithm. By universal qm-arithmetical algorithm any decidable arithmetical formula (operation) can be decided (realized, calculated. Arithmetic defined by universal qm-arithmetical algorithm called qm-arithmetic one-to-one corresponds to decidable part of the usual arithmetic. We prove that in the qm-arithmetic the undecidable a...

In this research, we create a scalable version of the quantum Fourier transform-based arithmetic circuit to perform addition and subtraction operations on N n-bit unsigned integers encoded in quantum registers, and it is compatible with d-level quantum sources, called qudits. We present qubit- and ququart-based multi-input QFT adders, and we compare and discuss potential benefits such as circuit simplicity and noise sensitivity. The results show that a ququart-based system si...