Efficient Floating Point Arithmetic for Quantum Computers

• URL: http://arxiv.org/abs/2112.10537v1
• Date: Mon, 20 Dec 2021 14:00:36 GMT
• Title: Efficient Floating Point Arithmetic for Quantum Computers
• Authors: Raphael Seidel, Nikolay Tcholtchev, Sebastian Bock, Colin Kai-Uwe Becker and Manfred Hauswirth
• Abstract summary: One of the major promises of quantum computing is the realization of SIMD (single instruction - multiple data) operations using the phenomenon of superposition. We introduce the formalism of encoding so called semi-booleans, which allows convenient generation of unsigned integer arithmetic quantum circuits. We extend this type of evaluation with additional features, such as ancilla-free in-place multiplication and integer coefficient evaluation.
• Score: 1.189955933770711
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: One of the major promises of quantum computing is the realization of SIMD (single instruction - multiple data) operations using the phenomenon of superposition. Since the dimension of the state space grows exponentially with the number of qubits, we can easily reach situations where we pay less than a single quantum gate per data point for data-processing instructions which would be rather expensive in classical computing. Formulating such instructions in terms of quantum gates, however, still remains a challenging task. Laying out the foundational functions for more advanced data-processing is therefore a subject of paramount importance for advancing the realm of quantum computing. In this paper, we introduce the formalism of encoding so called-semi-boolean polynomials. As it turns out, arithmetic $\mathbb{Z}/2^n\mathbb{Z}$ ring operations can be formulated as semi-boolean polynomial evaluations, which allows convenient generation of unsigned integer arithmetic quantum circuits. For arithmetic evaluations, the resulting algorithm has been known as Fourier-arithmetic. We extend this type of algorithm with additional features, such as ancilla-free in-place multiplication and integer coefficient polynomial evaluation. Furthermore, we introduce a tailor-made method for encoding signed integers succeeded by an encoding for arbitrary floating-point numbers. This representation of floating-point numbers and their processing can be applied to any quantum algorithm that performs unsigned modular integer arithmetic. We discuss some further performance enhancements of the semi boolean polynomial encoder and finally supply a complexity estimation. The application of our methods to a 32-bit unsigned integer multiplication demonstrated a 90\% circuit depth reduction compared to carry-ripple approaches.

Related papers

• Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
  We develop AlphaTensor-Quantum, a method to minimize the number of T gates that are needed to implement a given circuit. Unlike existing methods for T-count optimization, AlphaTensor-Quantum can incorporate domain-specific knowledge about quantum computation and leverage gadgets. Remarkably, it discovers an efficient algorithm akin to Karatsuba's method for multiplication in finite fields.
  arXiv  Detail & Related papers  (2024-02-22T09:20:54Z)
• Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck [55.22418739014892]
  We generalize the quantum Arimoto-Blahut algorithm by Ramakrishnan et al. We apply our algorithm to the quantum information bottleneck with three quantum systems. Our numerical analysis shows that our algorithm is better than their algorithm.
  arXiv  Detail & Related papers  (2023-11-19T00:06:11Z)
• Automated Quantum Oracle Synthesis with a Minimal Number of Qubits [0.6299766708197883]
  We present two methods for automatic quantum oracle synthesis. One method uses a minimal number of qubits, while the other preserves the function domain values while also minimizing the overall required number of qubits.
  arXiv  Detail & Related papers  (2023-04-07T20:12:13Z)
• Calculating the many-body density of states on a digital quantum computer [58.720142291102135]
  We implement a quantum algorithm to perform an estimation of the density of states on a digital quantum computer. We use our algorithm to estimate the density of states of a non-integrable Hamiltonian on the Quantinuum H1-1 trapped ion chip for a controlled register of 18bits.
  arXiv  Detail & Related papers  (2023-03-23T17:46:28Z)
• Factoring integers with sublinear resources on a superconducting quantum processor [11.96383198580683]
  Shor's algorithm has seriously challenged information security based on public key cryptosystems. To break the widely used RSA-2048 scheme, one needs millions of physical qubits, which is far beyond current technical capabilities. We report a universal quantum algorithm for integer factorization by combining the classical lattice reduction with a quantum approximate optimization algorithm.
  arXiv  Detail & Related papers  (2022-12-23T14:45:02Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Quantum Sparse Coding [5.130440339897477]
  We develop a quantum-inspired algorithm for sparse coding. The emergence of quantum computers and Ising machines can potentially lead to more accurate estimations. We conduct numerical experiments with simulated data on Lightr's quantum-inspired digital platform.
  arXiv  Detail & Related papers  (2022-09-08T13:00:30Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• An Efficient Summation Algorithm for the Accuracy, Convergence and Reproducibility of Parallel Numerical Methods [0.0]
  We have introduced a new parallel algorithm for summing a sequence of floating-point numbers. This algorithm which scales up easily with the number of processors, adds numbers of the same exponents first. In this article, our main contribution is an extensive analysis of its efficiency with respect to several properties.
  arXiv  Detail & Related papers  (2022-05-11T08:31:48Z)
• Resource Optimisation of Coherently Controlled Quantum Computations with the PBS-calculus [55.2480439325792]
  Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. We refine the PBS-calculus, a graphical language for coherent control inspired by quantum optics.
  arXiv  Detail & Related papers  (2022-02-10T18:59:52Z)
• CNOT-count optimized quantum circuit of the Shor's algorithm [8.88308897530269]
  We present improved quantum circuit for modular exponentiation of a constant, which is the most expensive operation in Shor's algorithm for integer factorization. According to the number of CNOT gates, we analyze the running time and feasibility of Shor's algorithm on a ion trap quantum computer.
  arXiv  Detail & Related papers  (2021-12-21T16:56:22Z)

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.