01351nas a2200193 4500008004100000245011700041210006900158260001400227300000800241490000600249520075900255100001301014700001701027700001801044700002201062700002001084700001601104856003701120 2021 eng d00aQuantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance0 aQuantumaccelerated multilevel Monte Carlo methods for stochastic c6/22/2021 a4810 v53 a
Inspired by recent progress in quantum algorithms for ordinary and partial differential equations, we study quantum algorithms for stochastic differential equations (SDEs). Firstly we provide a quantum algorithm that gives a quadratic speed-up for multilevel Monte Carlo methods in a general setting. As applications, we apply it to compute expection values determined by classical solutions of SDEs, with improved dependence on precision. We demonstrate the use of this algorithm in a variety of applications arising in mathematical finance, such as the Black-Scholes and Local Volatility models, and Greeks. We also provide a quantum algorithm based on sublinear binomial sampling for the binomial option pricing model with the same improvement.
1 aAn, Dong1 aLinden, Noah1 aLiu, Jin-Peng1 aMontanaro, Ashley1 aShao, Changpeng1 aWang, Jiasu uhttps://arxiv.org/abs/2012.0628302412nas a2200145 4500008004100000245006200041210006100103260001500164300001400179520194800193100002102141700002402162700002202186856005802208 2017 eng d00aSequential measurements, disturbance and property testing0 aSequential measurements disturbance and property testing c2017/01/01 a1598-16113 aWe describe two procedures which, given access to one copy of a quantum state and a sequence of two-outcome measurements, can distinguish between the case that at least one of the measurements accepts the state with high probability, and the case that all of the measurements have low probability of acceptance. The measurements cannot simply be tried in sequence, because early measurements may disturb the state being tested. One procedure is based on a variant of Marriott-Watrous amplification. The other procedure is based on the use of a test for this disturbance, which is applied with low probability. We find a number of applications. First, quantum query complexity separations in the property testing model for testing isomorphism of functions under group actions. We give quantum algorithms for testing isomorphism, linear isomorphism and affine isomorphism of boolean functions which use exponentially fewer queries than is possible classically, and a quantum algorithm for testing graph isomorphism which uses polynomially fewer queries than the best algorithm known. Second, testing properties of quantum states and operations. We show that any finite property of quantum states can be tested using a number of copies of the state which is logarithmic in the size of the property, and give a test for genuine multipartite entanglement of states of n qubits that uses O(n) copies of the state. Third, correcting an error in a result of Aaronson on de-Merlinizing quantum protocols. This result claimed that, in any one-way quantum communication protocol where two parties are assisted by an all-powerful but untrusted third party, the third party can be removed with only a modest increase in the communication cost. We give a corrected proof of a key technical lemma required for Aaronson's result.
1 aHarrow, Aram, W.1 aLin, Cedric, Yen-Yu1 aMontanaro, Ashley uhttp://epubs.siam.org/doi/10.1137/1.9781611974782.105