Quantum Circuit Design of Toom 3-Way Multiplication
| Autor: | Howon Kim, Janghyun Ji, Asep Muhamad Awaludin, Harashta Tatimma Larasati |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
Exact division
constant multiplication Technology Computer science QH301-705.5 QC1-999 Karatsuba algorithm Toffoli gate 02 engineering and technology 01 natural sciences complexity analysis integer division Toom–Cook multiplication Quantum circuit Computer Science::Hardware Architecture Computer Science::Emerging Technologies 0103 physical sciences Toom-3 0202 electrical engineering electronic engineering information engineering General Materials Science Arithmetic Biology (General) Instrumentation QD1-999 Quantum computer Fluid Flow and Transfer Processes Process Chemistry and Technology Physics 020208 electrical & electronic engineering General Engineering Division (mathematics) Engineering (General). Civil engineering (General) Computer Science Applications Chemistry Multiplication 010307 mathematical physics TA1-2040 quantum circuit |
| Zdroj: | Applied Sciences, Vol 11, Iss 3752, p 3752 (2021) Applied Sciences Volume 11 Issue 9 |
| ISSN: | 2076-3417 |
| Popis: | In classical computation, Toom–Cook is one of the multiplication methods for large numbers which offers faster execution time compared to other algorithms such as schoolbook and Karatsuba multiplication. For the use in quantum computation, prior work considered the Toom-2.5 variant rather than the classically faster and more prominent Toom-3, primarily to avoid the nontrivial division operations inherent in the latter circuit. In this paper, we investigate the quantum circuit for Toom-3 multiplication, which is expected to give an asymptotically lower depth than the Toom-2.5 circuit. In particular, we designed the corresponding quantum circuit and adopted the sequence proposed by Bodrato to yield a lower number of operations, especially in terms of nontrivial division, which is reduced to only one exact division by 3 circuit per iteration. Moreover, to further minimize the cost of the remaining division, we utilize the unique property of the particular division circuit, replacing it with a constant multiplication by reciprocal circuit and the corresponding swap operations. Our numerical analysis shows that the resulting circuit indeed gives a lower asymptotic complexity in terms of Toffoli depth and qubit count compared to Toom-2.5 but with a large number of Toffoli gates that mainly come from realizing the division operation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|