Optimal Toffoli-Depth Quantum Adder

• URL: http://arxiv.org/abs/2405.02523v1
• Date: Fri, 3 May 2024 23:38:13 GMT
• Title: Optimal Toffoli-Depth Quantum Adder
• Authors: Siyi Wang, Suman Deb, Ankit Mondal, Anupam Chattopadhyay,
• Abstract summary: Efficient quantum arithmetic circuits are commonly found in numerous quantum algorithms of practical significance. In this work, 160 alternative compositions of the carry-propagation structure are explored to determine the optimal depth structure for a quantum adder.
• Score: 4.183952203508634
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Optimal T depth quantum circuits for implementing arbitrary Boolean functions [4.730360540444164]
  We present a generic construction to obtain an optimal T depth quantum circuit for any arbitrary $n$-input $m$-output Boolean function $f.<n>We achieve this by inspecting the Algebraic Normal Form (ANF) of a Boolean function.<n>The implications of our results are highlighted explaining the provable lower bounds on S-box and block cipher implementations.
  arXiv  Detail & Related papers  (2025-06-02T11:07:54Z)
• Quantum Fisher-Yates shuffle: Unifying methods for generating uniform superpositions of permutations [0.0]
  Uniform superpositions over permutations play a central role in quantum error correction, cryptography, and optimisation. We introduce a simple yet powerful quantisation of the classical Fisher-Yates shuffle, yielding a suite of efficient quantum algorithms. Our implementation in Qiskit is available as open-source code, supporting and future exploration of quantum permutation-based algorithms.
  arXiv  Detail & Related papers  (2025-04-24T22:24:39Z)
• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks. We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings. We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• Graphical Stabilizer Decompositions for Multi-Control Toffoli Gate Dense Quantum Circuits [0.0]
  We study concepts in quantum computing using graphical languages, specifically using the ZX-calculus. The first major focus is on the decomposition of non-stabilizer states created from star edges. The second major focus is on weighting algorithms, applied to the special class of multi-control Toffoli gate dense quantum circuits.
  arXiv  Detail & Related papers  (2025-03-05T16:07:21Z)
• Estimating quantum amplitudes can be exponentially improved [11.282486674587236]
  Estimating quantum amplitudes is a fundamental task in quantum computing. We present a novel framework for estimating quantum amplitudes by transforming pure states into their matrix forms. Our framework achieves the standard quantum limit $epsilon-2$ and the Heisenberg limit $epsilon-1$, respectively.
  arXiv  Detail & Related papers  (2024-08-25T04:35:53Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Implementing multi-controlled X gates using the quantum Fourier transform [0.0]
  We show how a quantum arithmetic-based approach can be efficiently used to implement many complex quantum gates. We show how the depth of the circuit can be significantly reduced using only a few ancilla qubits.
  arXiv  Detail & Related papers  (2024-07-25T13:22:00Z)
• Quantum querying based on multicontrolled Toffoli gates for causal Feynman loop configurations and directed acyclic graphs [0.0]
  We present a quantum algorithm for querying causality of multiloop Feynman diagrams. The construction of the quantum oracle is surprisingly based exclusively on multicontrolled Toffoli gates and XNOT gates. We explicitly analise several three-, four- and five-eloop topologies, which have not been previously explored.
  arXiv  Detail & Related papers  (2024-04-04T15:51:43Z)
• Taming Quantum Time Complexity [45.867051459785976]
  We show how to achieve both exactness and thriftiness in the setting of time complexity. We employ a novel approach to the design of quantum algorithms based on what we call transducers.
  arXiv  Detail & Related papers  (2023-11-27T14:45: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)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Gaussian initializations help deep variational quantum circuits escape from the barren plateau [87.04438831673063]
  Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years. However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number. This result leads to a general belief that deep quantum circuits will not be feasible for practical tasks.
  arXiv  Detail & Related papers  (2022-03-17T15:06:40Z)
• Estimating gate-set properties from random sequences [0.0]
  Current quantum devices are only capable of short unstructured gate sequences followed by native measurements. A single experiment - random sequence estimation - solves a wealth of estimation problems. We derive robust channel variants of shadow estimation with close-to-optimal performance guarantees.
  arXiv  Detail & Related papers  (2021-10-25T18:01:25Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• QUANTIFY: A framework for resource analysis and design verification of quantum circuits [69.43216268165402]
  QUANTIFY is an open-source framework for the quantitative analysis of quantum circuits. It is based on Google Cirq and is developed with Clifford+T circuits in mind. For benchmarking purposes QUANTIFY includes quantum memory and quantum arithmetic circuits.
  arXiv  Detail & Related papers  (2020-07-21T15:36:25Z)

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.