Efficient Evaluation of Exponential and Gaussian Functions on a Quantum Computer

• URL: http://arxiv.org/abs/2110.05653v1
• Date: Tue, 12 Oct 2021 00:06:51 GMT
• Title: Efficient Evaluation of Exponential and Gaussian Functions on a Quantum Computer
• Authors: Bill Poirier
• Abstract summary: We present algorithms for evaluating exponential and Gaussian functions efficiently on quantum computers. For a specific, realistic NISQ application, the Toffoli count of the exponential function is found to be reduced from 15,690 down to 912. Space requirements are also quite modest, to the extent that the aforementioned NISQ application can be implemented with as few as 71 logical qubits.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The exponential and Gaussian functions are among the most fundamental and important operations, appearing ubiquitously throughout all areas of science, engineering, and mathematics. Whereas formally, it is well-known that any function may in principle be realized on a quantum computer, in practice present-day algorithms tend to be very expensive. In this work, we present algorithms for evaluating exponential and Gaussian functions efficiently on quantum computers. The implementations require a (generally) small number of multiplications, which represent the overall computational bottleneck. For a specific, realistic NISQ application, the Toffoli count of the exponential function is found to be reduced from 15,690 down to 912, when compared against a state-of-the art competing method by H\"aner and coworkers [arXiv:1805.12445], under the most favorable conditions for each method. For the corresponding Gaussian function comparison, the Toffoli count is reduced from 19,090 down to 704. Space requirements are also quite modest, to the extent that the aforementioned NISQ application can be implemented with as few as 71 logical qubits. More generally, the methods presented here could also be equally well applied in a fault-tolerant context, using error-corrected multiplications, etc.

Related papers

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• AutoNumerics-Zero: Automated Discovery of State-of-the-Art Mathematical Functions [46.36204442052778]
  Computers operate on few limited precision types, such as the popular float32. We show that when aiming for limited precision, existing approximation methods can be outperformed by programs automatically discovered from scratch by a simple evolutionary algorithm.
  arXiv  Detail & Related papers  (2023-12-13T19:17:43Z)
• Approximative lookup-tables and arbitrary function rotations for facilitating NISQ-implementations of the HHL and beyond [6.1003703380200545]
  We propose a circuit approximation technique that enhances the arithmetic subroutines in the HHL. We show how these types of circuits can be reduced in depth by providing a simple and powerful approximation technique.
  arXiv  Detail & Related papers  (2023-06-08T08:22:41Z)
• Promises and Pitfalls of the Linearized Laplace in Bayesian Optimization [73.80101701431103]
  The linearized-Laplace approximation (LLA) has been shown to be effective and efficient in constructing Bayesian neural networks. We study the usefulness of the LLA in Bayesian optimization and highlight its strong performance and flexibility.
  arXiv  Detail & Related papers  (2023-04-17T14:23:43Z)
• Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
  We propose a provably efficient reinforcement learning algorithm (both computationally and statistically) with general value function approximations. Our algorithm achieves reasonable regret bounds when applied to both the linear setting and the sparse high-dimensional linear setting.
  arXiv  Detail & Related papers  (2023-02-22T20:21:25Z)
• A Q# Implementation of a Quantum Lookup Table for Quantum Arithmetic Functions [3.961270923919885]
  We present Q# implementations for arbitrary single-variabled fixed-point arithmetic operations for a gate-based quantum computer. We show examples of how to use the LUT to implement quantum arithmetic functions. The LUT implementation makes for a clear benchmark for evaluating the efficiency of bespoke quantum arithmetic circuits.
  arXiv  Detail & Related papers  (2022-10-21T07:40:24Z)
• 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)
• The vacuum provides quantum advantage to otherwise simulatable architectures [49.1574468325115]
  We consider a computational model composed of ideal Gottesman-Kitaev-Preskill stabilizer states. We provide an algorithm to calculate the probability density function of the measurement outcomes.
  arXiv  Detail & Related papers  (2022-05-19T18:03:17Z)
• Computational-Statistical Gaps in Reinforcement Learning [23.517741855454044]
  We show a reduction from Unique-Sat, where we convert a CNF formula into an MDP Hypothesis with deterministic transitions, constant number of actions and low dimensional linear optimal value functions. This result also exhibits the first computational-statistical gap in reinforcement learning with linear function approximation.
  arXiv  Detail & Related papers  (2022-02-11T04:48:35Z)
• Efficient Floating Point Arithmetic for Quantum Computers [1.189955933770711]
  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.
  arXiv  Detail & Related papers  (2021-12-20T14:00:36Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32: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.