Quantum computers will be able solve important problems with significant polynomial and exponential speedups over their classical counterparts, for instance in option pricing in finance, and in real-space molecular chemistry simulations. However, key applications can only achieve their potential speedup if their inputs are prepared efficiently. We effectively solve the important problem of efficiently preparing quantum states following arbitrary continuous (as well as more general) functions with complexity logarithmic in the desired resolution, and with rigorous error bounds. This is enabled by the development of a fundamental subroutine based off of the simulation of rank-1 projectors. Combined with diverse techniques from quantum information processing, this subroutine enables us to present a broad set of tools for solving practical tasks, such as state preparation, numerical integration of Lipschitz continuous functions, and superior sampling from probability density functions. As a result, our work has significant implications in a wide range of applications, for instance in financial forecasting, and in quantum simulation.
Quantum computers will be able solve important problems with significant polynomial and exponential speedups over their classical counterparts, for instance in option pricing in finance, and in real-space molecular chemistry simulations. However, key applications can only achieve their potential speedup if their inputs are prepared efficiently. We effectively solve the important problem of efficiently preparing quantum states following arbitrary continuous (as well as more general) functions with complexity logarithmic in the desired resolution, and with rigorous error bounds. This is enabled by the development of a fundamental subroutine based off of the simulation of rank-1 projectors. Combined with diverse techniques from quantum information processing, this subroutine enables us to present a broad set of tools for solving practical tasks, such as state preparation, numerical integration of Lipschitz continuous functions, and superior sampling from probability density functions. As a result, our work has significant implications in a wide range of applications, for instance in financial forecasting, and in quantum simulation.
Quantum algorithms manipulate the amplitudes of quantum states to find solutions to computational problems. In this work, we present a framework for applying a general class of non-linear functions to the amplitudes of quantum states, with up-to an exponential improvement over the previous work. Our framework accepts a state preparation unitary (or block-encoding), specified as a quantum circuit, defining an N-dimensional quantum state. We then construct a diagonal block-encoding of the amplitudes of the quantum state, building on and simplifying previous work. Techniques from the QSVT literature are then used to process this block-encoding. The source of our exponential speedup comes from the quantum analog of importance sampling. We then derive new error-bounds relevant for end-to-end applications, giving the error in terms of ℓ2-norm error. We demonstrate the power of this framework with four key applications. First, our algorithm can apply the important function tanh(x) to the amplitudes of an arbitrary quantum state with at most an ℓ2-norm error of ε, with worst-case query complexity of O(log(N/ε)), in comparison to the O(Nlog(N/ε)) of prior work. Second, we present an algorithm solving a new formulation of maximum finding in the unitary input model. Third, we prove efficient end-to-end complexities in applying a number of common non-linear functions to arbitrary quantum states. Finally, we generalize and unify existing quantum arithmetic-free state-preparation techniques. Our work provides an important and efficient algorithmic building block with potentially numerous applications in areas such as optimization, state preparation, quantum chemistry, and machine learning.
Quantum amplitude estimation (QAE) can achieve a quadratic speedup for applications classically solved by Monte Carlo simulation. A key requirement to realize this advantage is efficient state preparation. If state preparation is too expensive, it can diminish the quantum advantage. Preparing arbitrary quantum states has exponential complexity with respect to the number of qubits, and thus, is not applicable. Currently known efficient techniques require problems based on log-concave probability distributions, involve learning an unknown distribution from empirical data, or fully rely on quantum arithmetic. In this paper, we introduce an approach to simplify state preparation, together with a circuit optimization technique, both of which can help reduce the circuit complexity for QAE state preparation significantly. We demonstrate the introduced techniques for a numerical integration example on real quantum hardware, as well as for option pricing under the Heston model, i.e., based on a stochastic volatility process, using simulation.
Modeling stochastic phenomena in continuous time is an essential yet challenging problem. Analytic solutions are often unavailable, and numerical methods can be prohibitively time-consuming and computationally expensive. To address this issue, we propose an algorithmic framework tailored for quantum continuous time stochastic processes. This framework consists of two key procedures: data preparation and information extraction. The data preparation procedure is specifically designed to encode and compress information, resulting in a significant reduction in both space and time complexities. This reduction is exponential with respect to a crucial feature parameter of the stochastic process. Additionally, it can serve as a submodule for other quantum algorithms, mitigating the common data input bottleneck. The information extraction procedure is designed to decode and process compressed information with quadratic acceleration, extending the quantum-enhanced Monte Carlo method. The framework demonstrates versatility and flexibility, finding applications in statistics, physics, time series analysis and finance. Illustrative examples include option pricing in the Merton Jump Diffusion Model and ruin probability computing in the Collective Risk Model, showcasing the framework’s ability to capture extreme market events and incorporate history-dependent information. Overall, this quantum algorithmic framework provides a powerful tool for accurate analysis and enhanced understanding of stochastic phenomena.
Quantum computers were first proposed to perform simulation -- in particular, quantum simulation. The premise is that such computers can simulate quantum dynamics exponentially faster than a classical computer. Some of the early proposals of practical applications of quantum computers come from quantum chemistry. Algorithms for more general systems, described by ordinary and partial differential equations, emerged later on. This thesis grounds on an extensive amount of prior research and proposes a set of improvements as well as new algorithms or algorithmic tools, focusing on applications from quantum chemistry and differential equations.First, we propose a technique relating to finding ground-states for electronic systems via the variational quantum eigensolver. The presented method enables solving the problem on early quantum hardware by a partitioning of the computational problem into smaller problems, using only classical resources to perform the partitioning. Next, the thesis considers simulation problems from chemistry in a more general sense. Following the idea that dynamical simulation of many chemical systems is efficient, whereas preparing ground-states is a `hard' problem, our computational framework leverages simulation routines to prepare molecular states as an input to a computation, relying only on `hard' input states for small problem instances. The preparation relies on dynamical scattering of initial fragments supported by a trap potential, allowing to estimate the success probability for certain bonds. A weak measurement scheme enables preparation of molecular states. Furthermore, this dissertation investigates quantum algorithms for differential equations. More specifically, the the Carleman linearization approach is considered to solve nonlinear differential equations. This entails bounding the Carleman truncation error, re-scaling of the solution to avoid an exponentially vanishing success probability, and discussing higher-order discretization. Moreover, this thesis introduced a penalty-based method to enforce constraints on the solution of differential equations, with inspiration from complex absorbing potentials and the quantum Zeno effect. We bound the approximation errors and embed the penalty method into an efficient quantum algorithm, with computational overhead only logarithmic in the penalty's strength. Efficiency is enabled by an interaction-picture approach with fast-forwardable constraint projections.
Quantum state preparation is a task to prepare a state with a specific function encoded in the amplitude, which is an essential subroutine in many quantum algorithms. In this paper, we focus on multivariate state preparation, as it is an important extension for many application areas. Specifically in finance, multivariate state preparation is required for multivariate Monte Carlo simulation, which is used for important numerical tasks such as risk aggregation and multi-asset derivative pricing. Using existing methods, multivariate quantum state preparation requires the number of gates exponential in the number of variables D. For this task, we propose a quantum algorithm that only requires the number of gates linear in D. Our algorithm utilizes multivariable quantum signal processing (M-QSP), a technique to perform the multivariate polynomial transformation of matrix elements. Using easily prepared block-encodings corresponding to each variable, we apply the M-QSP to construct the target function. In this way, our algorithm prepares the target state efficiently for functions achievable with M-QSP.
The simulation of many industrially relevant physical processes can be executed up to exponentially faster using quantum algorithms. However, this speedup can only be leveraged if the data input and output of the simulation can be implemented efficiently. While we show that recent advancements for optimal state preparation can effectively solve the problem of data input at a moderate cost of ancillary qubits in many cases, the output problem can provably not be solved efficiently in general. By acknowledging that many simulation problems arise only as a subproblem of a larger optimization problem in many practical applications however, we identify and define a class of practically relevant problems that does not suffer from the output problem: Quantum Simulation-based Optimization (QuSO). QuSO represents optimization problems whose objective function and/or constraints depend on summary statistic information on the result of a simulation, i.e., information that can be efficiently extracted from a quantum state vector. In this article, we focus on the LinQuSO subclass of QuSO, which is characterized by the linearity of the simulation problem, i.e., the simulation problem can be formulated as a system of linear equations. By cleverly combining the quantum singular value transformation (QSVT) with the quantum approximate optimization algorithm (QAOA), we prove that a large subgroup of LinQuSO problems can be solved with up to exponential quantum speedups with regards to their simulation component. Finally, we present two practically relevant use cases that fall within this subgroup of QuSO problems.