Optimal Toffoli-Depth Quantum Adder
<|reference_start|>Optimal Toffoli-Depth Quantum Adder: Efficient quantum arithmetic circuits are commonly found in numerous quantum algorithms of practical significance. Till date, the logarithmic-depth quantum adders includes a constant coefficient k >= 2 while achieving the Toffoli-Depth of klog n + O(1). In this work, 160 alternative compositions of the carry-propagation structure are comprehensively explored to determine the optimal depth structure for a quantum adder. By extensively studying these structures, it is shown that an exact Toffoli-Depth of log n + O(1) is achievable. This presents a reduction of Toffoli-Depth by almost 50% compared to the best known quantum adder circuits presented till date. We demonstrate a further possible design by incorporating a different expansion of propagate and generate forms, as well as an extension of the modular framework. Our paper elaborates on these designs, supported by detailed theoretical analyses and simulation-based studies, firmly substantiating our claims of optimality. The results also mirror similar improvements, recently reported in classical adder circuit complexity.<|reference_end|>
@article{wang2024optimal,
    title={Optimal Toffoli-Depth Quantum Adder},
    author={Siyi Wang, Suman Deb, Ankit Mondal, Anupam Chattopadhyay},
    journal={arXiv preprint arXiv:2405.02523},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.02523},
    primaryClass={quant-ph cs.ET}
}