Algorithms · Amplitude estimation
Asian option pricing via the Karhunen-Loève expansion
Price discretely monitored Asian options over T monitoring points, where the underlying asset is modeled by a geometric Brownian motion.
Attested & literatureUpdated
A small worked example, computed in your browser. It is not a result from this record's papers.
Canonical amplitude estimation
3 counting qubits estimating a = sin²(θ) for the one-qubit state A|0⟩ = RY(π/4)|0⟩, θ = π/8.
Step 1 of 4 · RY(π/4)
Probability of each outcome after this step
- 000085%
- 100015%
Prepares the target qubit as A|0⟩ = cos(θ)|0⟩ + sin(θ)|1⟩; the quantity being estimated is a = sin²(θ), the probability that measuring this qubit alone would give |1⟩.
Probability spreads from 1 outcome to 2.
Spreads the 3 counting qubits into an equal superposition of all 8 values.
Probability spreads from 2 outcomes to 16.
Applies controlled powers of the Grover operator Q = A Z A⁻¹ Z, one power per counting qubit: phase estimation of Q, using A|0⟩ in place of a single eigenstate.
Probability moves between the same 16 outcomes. Down: 0110 10.7% → 1.8%, 0010 10.7% → 1.8%. This is the step that entangles the qubits: from here on no single qubit has a state of its own, only the register as a whole does.
An inverse QFT on the counting register reads the phase into a 3-bit estimate.
Probability gathers from 16 outcomes onto 4. 0001 goes from 1.8% to 25.0%.
Readout The counting register reads 001 or 111, each equally likely: these are θ/π = 1/8 and its mirror 1 − 1/8 = 7/8, both exact in 3 bits by construction. Either one gives a = sin²(π/8) = (2 − √2) / 4 exactly, the standard amplitude-estimation formula a = sin²(πλ) applied to the smaller of the two readings.
Open in Studio- Record typeLiterature reference
- Reference implementationbrownian_chebyshev_polynomials
- Reported costPoly-logarithmic in T and polynomial in 1/ε for both quantum algorithms given, where T is the number of monitoring points and ε is the additive approximation error; the better of the two reaches Õ(1/ε³), with the tilde suppressing factors that are poly-logarithmic in T and 1/ε. One algorithm is built from an O(log T)-qubit semi-digital quantum encoding of the Brownian motion. The abstract states no further constant, no explicit qubit or gate count for the Monte-Carlo-derived algorithm, and no total circuit-resource count for either.
- Papers1
Price discretely monitored Asian options over T monitoring points, where the underlying asset is modeled by a geometric Brownian motion. Prakash, Sun, Chakrabarti, Che, Dandapani, Herman, Kumar, Sureshbabu, Wood, Kerenidis and Pistoia consider the problem of pricing discretely monitored Asian options over T monitoring points, with the underlying asset modeled by a geometric Brownian motion, and give two quantum algorithms for it. Both achieve complexity poly-logarithmic in T and polynomial in 1/ε, where ε is the additive approximation error. One is obtained from an O(log T)-qubit semi-digital quantum encoding of the Brownian motion that allows exponentiation of the stochastic process; the other from analyzing classical Monte Carlo algorithms inspired by that same semi-digital encoding. The better of the two, the abstract states, reaches complexity Õ(1/ε³), where the tilde suppresses factors that are only poly-logarithmic in T and 1/ε. The authors state that their methods generalize to pricing options where the underlying asset price is a smooth function of a sub-Gaussian process and the payoff depends on the weighted time-average of that price. The abstract's title refers to the Karhunen-Loève expansion; it does not use the term Chebyshev polynomials anywhere, so this record makes no claim connecting the two algorithms it describes to any Chebyshev-polynomial construction.
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
Prakash, Sun, Chakrabarti, Che, Dandapani, Herman, Kumar, Sureshbabu, Wood, Kerenidis and Pistoia consider the problem of pricing discretely monitored Asian options over T monitoring points, with the underlying asset modeled by a geometric Brownian motion, and give two quantum algorithms for it. Both achieve complexity poly-logarithmic in T and polynomial in 1/ε, where ε is the additive approximation error. One is obtained from an O(log T)-qubit semi-digital quantum encoding of the Brownian motion that allows exponentiation of the stochastic process; the other from analyzing classical Monte Carlo algorithms inspired by that same semi-digital encoding. The better of the two, the abstract states, reaches complexity Õ(1/ε³), where the tilde suppresses factors that are only poly-logarithmic in T and 1/ε. The authors state that their methods generalize to pricing options where the underlying asset price is a smooth function of a sub-Gaussian process and the payoff depends on the weighted time-average of that price. The abstract's title refers to the Karhunen-Loève expansion; it does not use the term Chebyshev polynomials anywhere, so this record makes no claim connecting the two algorithms it describes to any Chebyshev-polynomial construction. Reported cost: Poly-logarithmic in T and polynomial in 1/ε for both quantum algorithms given, where T is the number of monitoring points and ε is the additive approximation error; the better of the two reaches Õ(1/ε³), with the tilde suppressing factors that are poly-logarithmic in T and 1/ε. One algorithm is built from an O(log T)-qubit semi-digital quantum encoding of the Brownian motion. The abstract states no further constant, no explicit qubit or gate count for the Monte-Carlo-derived algorithm, and no total circuit-resource count for either..
TakesNothingWhat joins here
No input port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
ReturnsNothingWhat joins here
No output port at this edge: the record publishes no gate sequence and no register, so there is nothing here to read one off — and unlike a declared hole, nothing has been recorded about what belongs here.
Nothing in the Atlas meets this end.
This record publishes no gate sequence and no register, so there is nothing here to read an interface off. Absent rather than empty. See all 152 →
- Record type
- Literature reference
- Reference implementation
- brownian_chebyshev_polynomials
- Reported cost
- Poly-logarithmic in T and polynomial in 1/ε for both quantum algorithms given, where T is the number of monitoring points and ε is the additive approximation error; the better of the two reaches Õ(1/ε³), with the tilde suppressing factors that are poly-logarithmic in T and 1/ε. One algorithm is built from an O(log T)-qubit semi-digital quantum encoding of the Brownian motion. The abstract states no further constant, no explicit qubit or gate count for the Monte-Carlo-derived algorithm, and no total circuit-resource count for either.
- Complexity basis
- The abstract of arXiv:2402.10132, the only source read for this record, sets up the task — "We consider the problem of pricing discretely monitored Asian options over $T$ monitoring points where the underlying asset is modeled by a geometric Brownian motion" — and states the headline bound: "We provide two quantum algorithms with complexity poly-logarithmic in $T$ and polynomial in $1/\epsilon$, where $\epsilon$ is the additive approximation error." (TeX rendered into Unicode/plain notation for the reader: $T$ is T and $1/\epsilon$ is 1/ε.) One algorithm comes from "an $O(\log T)$-qubit semi-digital quantum encoding of the Brownian motion that allows for exponentiation of the stochastic process" (rendered O(log T)-qubit), the other "by analyzing classical Monte Carlo algorithms inspired by the semi-digital encodings." The abstract names the better of the two: "The best quantum algorithm obtained using this approach has complexity $\widetilde{O}(1/\epsilon^{3})$ where the $\widetilde{O}$ suppresses factors poly-logarithmic in $T$ and $1/\epsilon$" (rendered Õ(1/ε³), the tilde marking exactly the suppression the abstract states). Beyond these expressions the abstract gives no further constant, no total qubit or gate count for either algorithm, and no cost figure for the Monte-Carlo-derived one beyond its complexity order. The demonstration this record covers states no complexity bound of its own; its name refers to Chebyshev polynomials, a term this abstract never uses, so this field carries no claim about any Chebyshev-polynomial construction.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Amplitude estimation with the strongest classical method for the same instance, input budget, and output metric.
Quantum claim
This reference exposes a quantum circuit pattern; it does not imply an application-level speedup without a matched benchmark.
How to compare
Report input loading, circuit depth, repetitions, classical preprocessing, post-processing, and wall-clock time together.
Nobody has reviewed this record for gaps yet.
ALGORITHM: Asian option pricing via the Karhunen-Loève expansion
PROBLEM: Price discretely monitored Asian options over T monitoring points, where the underlying asset is modeled by a geometric Brownian motion.
IDEA: Prakash, Sun, Chakrabarti, Che, Dandapani, Herman, Kumar, Sureshbabu, Wood, Kerenidis and Pistoia consider the problem of pricing discretely monitored Asian options over T monitoring points, with the underlying asset modeled by a geometric Brownian motion, and give two quantum algorithms for it. Both achieve complexity poly-logarithmic in T and polynomial in 1/ε, where ε is the additive approximation error. One is obtained from an O(log T)-qubit semi-digital quantum encoding of the Brownian motion that allows exponentiation of the stochastic process; the other from analyzing classical Monte Carlo algorithms inspired by that same semi-digital encoding. The better of the two, the abstract states, reaches complexity Õ(1/ε³), where the tilde suppresses factors that are only poly-logarithmic in T and 1/ε. The authors state that their methods generalize to pricing options where the underlying asset price is a smooth function of a sub-Gaussian process and the payoff depends on the weighted time-average of that price. The abstract's title refers to the Karhunen-Loève expansion; it does not use the term Chebyshev polynomials anywhere, so this record makes no claim connecting the two algorithms it describes to any Chebyshev-polynomial construction.
REPORTED COST: Poly-logarithmic in T and polynomial in 1/ε for both quantum algorithms given, where T is the number of monitoring points and ε is the additive approximation error; the better of the two reaches Õ(1/ε³), with the tilde suppressing factors that are poly-logarithmic in T and 1/ε. One algorithm is built from an O(log T)-qubit semi-digital quantum encoding of the Brownian motion. The abstract states no further constant, no explicit qubit or gate count for the Monte-Carlo-derived algorithm, and no total circuit-resource count for either.
BASIS: The abstract of arXiv:2402.10132, the only source read for this record, sets up the task — "We consider the problem of pricing discretely monitored Asian options over $T$ monitoring points where the underlying asset is modeled by a geometric Brownian motion" — and states the headline bound: "We provide two quantum algorithms with complexity poly-logarithmic in $T$ and polynomial in $1/\epsilon$, where $\epsilon$ is the additive approximation error." (TeX rendered into Unicode/plain notation for the reader: $T$ is T and $1/\epsilon$ is 1/ε.) One algorithm comes from "an $O(\log T)$-qubit semi-digital quantum encoding of the Brownian motion that allows for exponentiation of the stochastic process" (rendered O(log T)-qubit), the other "by analyzing classical Monte Carlo algorithms inspired by the semi-digital encodings." The abstract names the better of the two: "The best quantum algorithm obtained using this approach has complexity $\widetilde{O}(1/\epsilon^{3})$ where the $\widetilde{O}$ suppresses factors poly-logarithmic in $T$ and $1/\epsilon$" (rendered Õ(1/ε³), the tilde marking exactly the suppression the abstract states). Beyond these expressions the abstract gives no further constant, no total qubit or gate count for either algorithm, and no cost figure for the Monte-Carlo-derived one beyond its complexity order. The demonstration this record covers states no complexity bound of its own; its name refers to Chebyshev polynomials, a term this abstract never uses, so this field carries no claim about any Chebyshev-polynomial construction.
PRIMARY SOURCE: Anupam Prakash, Yue Sun, Shouvanik Chakrabarti, Charlie Che, Aditi Dandapani, Dylan Herman, Niraj Kumar, Shree Hari Sureshbabu, Ben Wood, Iordanis Kerenidis, Marco Pistoia (2024), Quantum option pricing via the Karhunen-Loève expansion — https://arxiv.org/abs/2402.10132
This is a literature reference record, not an executable circuit.A reference record, not runnable source. Leona cannot execute it, so it cannot be saved to your Library as a circuit.
Related entries
- Quantum amplitude estimation
Algorithms
- Option pricing by amplitude estimation
Algorithms
- Quantum phase estimation
Algorithms
- Iterative phase estimation
Algorithms
References
- Quantum option pricing via the Karhunen-Loève expansion
Anupam Prakash, Yue Sun, Shouvanik Chakrabarti, Charlie Che, Aditi Dandapani, Dylan Herman, Niraj Kumar, Shree Hari Sureshbabu, Ben Wood, Iordanis Kerenidis, Marco Pistoia · 2024
Primary source: it states the poly-logarithmic-in-T, polynomial-in-1/ε bound for both quantum algorithms, the O(log T)-qubit semi-digital encoding behind one of them, the Õ(1/ε³) complexity of the better algorithm, and the claimed generalization to sub-Gaussian processes with weighted time-average payoffs. Consult it for the Karhunen-Loève expansion the title refers to, for how the semi-digital encoding and the Monte Carlo algorithm it inspires are actually built, for any constant factors, and for whether a Chebyshev-polynomial construction, named in this record's own directory name but not in this abstract, appears anywhere in the paper.