Qubit capacity is a common bottleneck in quantum computers, limiting the ability to run complex algorithms and slowing the advancements in quantum computing applications. Reusing qubits by resetting them after measuring and repurposing them for subsequent gate operations offers an effective strategy to reduce the overall qubit requirements. Based on Satisfiability Modulo Theories (SMT) and Integer Linear Programming (ILP), we present an optimal algorithm that maximizes qubit reuse while optionally constraining the circuit depth to a specified upper bound. Our approach considers all feasible circuit rearrangements to enhance optimality, including gate reordering and eager measurement. We further propose a divide-and-conquer approach to scale for large circuits by relaxing the optimality guarantee. Experimental results show that our exact method substantially decreases both the qubit count and the circuit depth compared to the current state of the art, while the divide-and-conquer approach effectively addresses scalability issues with maintained solution quality.
In this paper, we present Clifford+T gates based quantum circuit design of integer division having
n ancillary qubits. The proposed quantum circuit is based on restoring division algorithm. The proposed quantum circuit of integer division consists of (i) quantum circuitry of conditional addition operation, (ii) quantum circuitry of integer subtraction. To design ancillary and T-count optimized design of quantum integer division, the optimized quantum circuit design of integer conditional addition operation and integer subtraction are presented. The proposed quantum integer division circuitry has 50\% improvement in terms of ancillary qubits, and 90\% improvement in terms of T-count compared to the existing design of integer quantum division based on quantum fourier transform.
Abstract Quantum circuits for multiplication and division are necessary for scientific computing on quantum computers. Clifford + T circuits are widely used in fault-tolerant realizations. T gates are more expensive than other gates in Clifford + T circuits. But neglecting the cost of CNOT gates may lead to a significant underestimation. Moreover, the small number of qubits available in existing quantum devices is another constraint on quantum circuits. As a result, reducing T-count, T-depth, CNOT-count, CNOT-depth, and circuit width has become the important optimization goal. We use 3-bit Hermitian gates to design basic arithmetic operations. Then, we present a special multiplier and a divider using basic arithmetic operations, where 'special' means that one of the two operands of multiplication is non-zero. Next, we use new rules to optimize the Clifford + T circuits of the special multiplier and divider in terms of T-count, T-depth, CNOT-count, CNOT-depth, and circuit width. Comparative analysis shows that the proposed multiplier and divider have lower T-count, T-depth, CNOT-count, and CNOT-depth than the current works. For instance, the proposed 32-bit divider achieves improvement ratios of 40.41 percent, 31.64 percent, 45.27 percent, and 65.93 percent in terms of T-count, T-depth, CNOT-count, and CNOT-depth compared to the best current work. Further, the circuit widths of the proposed
n-bit multiplier and divider are
3n. I.e., our multiplier and divider reach the minimum width of multipliers and dividers, keeping an operand unchanged.