Quantum schoolbook multiplication with fewer Toffoli gates
- URL: http://arxiv.org/abs/2410.00899v1
- Date: Tue, 1 Oct 2024 17:39:24 GMT
- Title: Quantum schoolbook multiplication with fewer Toffoli gates
- Authors: Daniel Litinski,
- Abstract summary: Controlled n-qubit add-subtract circuits perform an addition when the control qubit is one and a subtraction when it is zero.
Schoolbook multiplication yields the lowest Toffoli counts for small register sizes.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Scalable improvement of the generalized Toffoli gate realization using trapped-ion-based qutrits [32.33017977520031]
Direct realizations of the Toffoli gate require either a prohibitive growth of the number of two-qubit gates or using ancilla qubits.
Here we experimentally demonstrate a scalable improvement of the realization of the Toffoli gate using trapped-ion-based dual-type optic-microwave qutrits.
arXiv Detail & Related papers (2024-07-10T15:34:56Z) - Finding Transformer Circuits with Edge Pruning [71.12127707678961]
We propose Edge Pruning as an effective and scalable solution to automated circuit discovery.
Our method finds circuits in GPT-2 that use less than half the number of edges compared to circuits found by previous methods.
Thanks to its efficiency, we scale Edge Pruning to CodeLlama-13B, a model over 100x the scale that prior methods operate on.
arXiv Detail & Related papers (2024-06-24T16:40:54Z) - Linear decomposition of approximate multi-controlled single qubit gates [0.8520624117635328]
We provide a method for compiling approximate multi-controlled single qubit gates into quantum circuits without ancilla qubits.
The total number of elementary gates to decompose an n-qubit multi-controlled gate is proportional to 32n.
arXiv Detail & Related papers (2023-10-23T14:23:08Z) - Fast Flux-Activated Leakage Reduction for Superconducting Quantum
Circuits [84.60542868688235]
leakage out of the computational subspace arising from the multi-level structure of qubit implementations.
We present a resource-efficient universal leakage reduction unit for superconducting qubits using parametric flux modulation.
We demonstrate that using the leakage reduction unit in repeated weight-two stabilizer measurements reduces the total number of detected errors in a scalable fashion.
arXiv Detail & Related papers (2023-09-13T16:21:32Z) - Shallow unitary decompositions of quantum Fredkin and Toffoli gates for
connectivity-aware equivalent circuit averaging [0.0]
Controlled-SWAP and controlled-controlled-NOT gates are at the heart of the original proposal of reversible classical computation.
We provide several logically equivalent circuits for the Toffoli and Fredkin gates under all-to-all and linear qubit connectivity.
We also demonstrate the remarkable effectiveness of the obtained decompositions at mitigating coherent errors on near-term quantum computers.
arXiv Detail & Related papers (2023-05-29T14:46:19Z) - Quantum Fourier Addition, Simplified to Toffoli Addition [92.18777020401484]
We present the first systematic translation of the QFT-addition circuit into a Toffoli-based adder.
Instead of using approximate decompositions of the gates from the QFT circuit, it is more efficient to merge gates.
arXiv Detail & Related papers (2022-09-30T02:36:42Z) - Software mitigation of coherent two-qubit gate errors [55.878249096379804]
Two-qubit gates are important components of quantum computing.
But unwanted interactions between qubits (so-called parasitic gates) can degrade the performance of quantum applications.
We present two software methods to mitigate parasitic two-qubit gate errors.
arXiv Detail & Related papers (2021-11-08T17:37:27Z) - Halving the width of Toffoli based constant modular addition to n+3
qubits [69.43216268165402]
We present an arithmetic circuit performing constant modular addition having $mathcalO(n)$ depth of Toffoli gates.
This is an improvement by a factor of two compared to the width of the state-of-the-art Toffoli-based constant modular adder.
arXiv Detail & Related papers (2021-02-06T17:07:48Z) - On the realistic worst case analysis of quantum arithmetic circuits [69.43216268165402]
We show that commonly held intuitions when designing quantum circuits can be misleading.
We show that reducing the T-count can increase the total depth.
We illustrate our method on addition and multiplication circuits using ripple-carry.
arXiv Detail & Related papers (2021-01-12T21:36:16Z) - Dual Toffoli and Peres-reversible gates [0.35534933448684136]
The paper introduces dual Toffoli and Peres reversible gates, which operate under disjunctive control, and shows their functionality based on the Barenco et al. quantum model.
A Clifford+T realization of a dual Toffoli and a dual Peres gate is shown, which may be used when mapping reversible circuits to the IBM quantum computers.
arXiv Detail & Related papers (2020-11-01T21:28:10Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.