Conditions for a quadratic quantum speedup in nonlinear transforms with applications to energy contract pricing
arXiv:2304.10385 · doi:10.1088/2058-9565/ada08c
Abstract
Computing nonlinear functions over multilinear forms is a general problem with applications in risk analysis. For instance in the domain of energy economics, accurate and timely risk management demands for efficient simulation of millions of scenarios, largely benefiting from computational speedups. We develop a novel hybrid quantum-classical algorithm based on polynomial approximation of nonlinear functions, computed through Quantum Hadamard Products, and we rigorously assess the conditions for its end-to-end speedup for different implementation variants against classical algorithms. In our setting, a quadratic quantum speedup, up to polylogarithmic factors, can be proven only when forms are bilinear and approximating polynomials have second degree, if efficient loading unitaries are available for the input data sets. We also enhance the bidirectional encoding, that allows tuning the balance between circuit depth and width, proposing an improved version that can be exploited for the calculation of inner products. Lastly, we exploit the dynamic circuit capabilities, recently introduced on IBM Quantum devices, to reduce the average depth of the Quantum Hadamard Product circuit. A proof of principle is implemented and validated on IBM Quantum systems.
References in corpus (26)
- Supervised learning with quantum enhanced feature spaces
- Quantum Convolutional Neural Networks
- An introduction to quantum machine learning
- Quantum fingerprinting
- Validating quantum computers using randomized model circuits
- Efficient Learning for Deep Quantum Neural Networks
- Synthesis of Quantum Logic Circuits
- The quest for a Quantum Neural Network
- Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
- Quantum-state preparation with universal gate decompositions
- Quantum speedup of Monte Carlo methods
- Variational quantum algorithms for nonlinear problems
- Architectures for a quantum random access memory
- Quantum Risk Analysis
- Option Pricing using Quantum Computers
- Iterative Quantum Amplitude Estimation
- On the advantages of using relative phase Toffolis with an application to multiple control Toffoli optimization
- A divide-and-conquer algorithm for quantum state preparation
- Applying quantum algorithms to constraint satisfaction problems
- Beyond the swap test: optimal estimation of quantum state overlap
- Singular value decomposition and matrix reorderings in quantum information theory
- Non-linear operations in quantum information theory
- Degree Correlations Amplify the Growth of Cascades in Networks
- Fast Pricing of Energy Derivatives with Mean-reverting Jump-diffusion Processes
- Guide to Mathematical Concepts of Quantum Theory
- Energy risk analysis with Dynamic Amplitude Estimation and Piecewise Approximate Quantum Compiling