Quantum schoolbook multiplication with fewer Toffoli gates
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916419135864832 |
|---|---|
| author | Litinski, Daniel |
| author_facet | Litinski, Daniel |
| contents | This paper presents a method for constructing quantum circuits for schoolbook multiplication using controlled add-subtract circuits, asymptotically halving the Toffoli count compared to traditional controlled-adder-based constructions. Controlled n-qubit add-subtract circuits, which perform an addition when the control qubit is one and a subtraction when it is zero, require only n-1 Toffoli gates, instead of the 2n-1 needed for controlled adders. Despite the existence of multiplication circuits with better asymptotic scaling, schoolbook multiplication yields the lowest Toffoli counts for small register sizes, making it advantageous in practical applications. For example, the presented approach reduces the Toffoli count by up to around 30% in circuits for breaking 256-bit elliptic curve keys compared to circuits with standard schoolbook multipliers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_00899 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum schoolbook multiplication with fewer Toffoli gates Litinski, Daniel Quantum Physics This paper presents a method for constructing quantum circuits for schoolbook multiplication using controlled add-subtract circuits, asymptotically halving the Toffoli count compared to traditional controlled-adder-based constructions. Controlled n-qubit add-subtract circuits, which perform an addition when the control qubit is one and a subtraction when it is zero, require only n-1 Toffoli gates, instead of the 2n-1 needed for controlled adders. Despite the existence of multiplication circuits with better asymptotic scaling, schoolbook multiplication yields the lowest Toffoli counts for small register sizes, making it advantageous in practical applications. For example, the presented approach reduces the Toffoli count by up to around 30% in circuits for breaking 256-bit elliptic curve keys compared to circuits with standard schoolbook multipliers. |
| title | Quantum schoolbook multiplication with fewer Toffoli gates |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2410.00899 |