Creating superpositions that correspond to efficiently integrable probability distributions

By Lov K. Grover, Terry Rudolph. 2002

535 citations recorded by the source corpus.

We give a simple and efficient process for generating a quantum superposition of states which form a discrete approximation of any efficiently integrable (such as log concave) probability density functions.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/07f4621702954efa955f8877f338c3dfe58c7bae

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Circuit-centric quantum classifiers (2018, background): “When more structure in the data can be exploited, preparation routines with polylogarithmic dependence on the number of features might be applicable [25, 26].”
On lattices, learning with errors, random linear codes, and cryptography (2005, methodology): “This state can be created efficiently using a technique by Grover and Rudolph [ 18 ] who show that in order to create such a state, it suffices to be able to compute for any a;b 2 fi p nr;:::; p nrg the sum Pb”
Simulating chemistry using quantum computers. (2010, background): “Zalka’s original paper (138) contained a very general state-preparation scheme, later rediscovered (48, 64, 71) and improved (114).”
High-order quantum algorithm for solving linear differential equations (2010, methodology): “The Euler method is A-stable, but it is not possible to construct arbitrary order A-stable multistep methods.”
Quantum risk analysis (2018, methodology): “, log-concave distributions.(29) Approximating E1⁄2X using AE requires the operator F corresponding to f(x)= x/(N− 1), defined in Eq.”
Quantum Computing for Finance: State-of-the-Art and Future Prospects (2020, background): “This is feasible, e.g. for eﬃciently integrable probability distributions such as log-concave distributions for which the loading operator can be built from controlled rotations [31].”
Quantum Generative Adversarial Networks for learning and loading random distributions (2019, background): “As proven in [31], a normal distribution can be efficiently loaded into a quantum state.”
Adiabatic quantum state generation and statistical zero knowledge (2003, background): “We note that some of these states (perhaps all) can be generated using standard techniques which exploit the self reducibility of the problem (see [30]).”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, background): “Indeed, the discrete-time quantum walk can be carried out efficiently provided only that the Hamiltonian is efficiently index-computable, and that the weights appearing in the states (4) are integrable in the sense of [29].”
Quantum walks: a comprehensive review (2012, methodology): “[107] have proposed a general method, based on [179,427], for realizing a quantum walk operator corresponding to an arbitrary sparse classical random walk.”
Option Pricing using Quantum Computers (2019, background): “In [30], the authors show that log-concave probability distributions (such as the log-normal distribution of the BSM model) can be efficiently loaded in a gatebased quantum computer.”
Quantum algorithm for linear systems of equations. (2008, background): “We make no further assumption about B; it may represent another part of a larger algorithm, or a standard state-preparation procedure such as [14].”
Polynomial-time quantum algorithm for the simulation of chemical dynamics (2008, background): “It is known that superpositions corresponding to efficiently integrable functions can be prepared on a quantum computer in polynomial time (15, 30).”
Quantum machine learning: a classical perspective (2017, methodology): “For example, a technique developed by Grover & Rudolph [54] allows one to generate a”
On lattices, learning with errors, random linear codes, and cryptography (2009, methodology): “Lemma 3.12 There exists an efﬁcient quantum algorithm that, given an n -dimensional lattice L ⊆ Z n and r > 2 2 n λ n ( L ) , outputs a state that is within ℓ 2 distance 2 − Ω( n ) of the normalized state corresponding to Proof: We start by creating the ‘one-dimensional Gaussian state’ This state ca”
Quantum algorithms for supervised and unsupervised machine learning (2013, background): “Constructing the log2N qubit quantum state |v〉 = |~v|−1/2~v then takes O(log2N) steps as long as the sub-norms nl = ∑l i=1 |vi|(2) can be estimated efficiently [20-22].”