Algorithms · Quantum linear algebra
Quantum algorithm for portfolio optimization
Given quantum access to a historical record of asset returns, determine the optimal risk-return tradeoff curve of a portfolio and provide a way to sample from the optimal portfolio.
Attested & literatureUpdated
- Record typeLiterature reference
- Reference implementationportfolio_optimization_hhl
- Reported costIn principle poly(log N), where N is the size of the historical return dataset — rendered from the abstract's inline TeX poly(log(N)) — against poly(N) for the direct classical algorithms the abstract compares it to. The abstract states this only as an order in N: it gives no constant, no dependence on any error or precision parameter, and no qubit or gate count, and it qualifies the comparison itself by pointing to recent work on efficient classical sampling approaches rather than treating the gap as settled.
- Papers1
Given quantum access to a historical record of asset returns, determine the optimal risk-return tradeoff curve of a portfolio and provide a way to sample from the optimal portfolio. Rebentrost and Lloyd present a quantum algorithm for portfolio optimization, addressing in turn the market-data input, the processing of that data by quantum operations, and the output of financially relevant results. Given quantum access to the historical record of returns, the algorithm determines the optimal risk-return tradeoff curve and allows one to sample from the optimal portfolio. The authors state that the algorithm can in principle attain a run time of poly(log N), where N is the size of the historical return dataset — rendered here from the abstract's own inline TeX — against poly(N) for the direct classical algorithms it compares to, which determine the risk-return curve and other properties of the optimal portfolio. They do not present this as an unqualified speedup: the abstract closes by discussing potential quantum speedups in light of recent works on efficient classical sampling approaches, flagging the comparison rather than asserting it outright. The abstract does not describe how the market-data input, the quantum operations that process it, or the output step are constructed; those mechanics are left to the paper.
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 →
Rebentrost and Lloyd present a quantum algorithm for portfolio optimization, addressing in turn the market-data input, the processing of that data by quantum operations, and the output of financially relevant results. Given quantum access to the historical record of returns, the algorithm determines the optimal risk-return tradeoff curve and allows one to sample from the optimal portfolio. The authors state that the algorithm can in principle attain a run time of poly(log N), where N is the size of the historical return dataset — rendered here from the abstract's own inline TeX — against poly(N) for the direct classical algorithms it compares to, which determine the risk-return curve and other properties of the optimal portfolio. They do not present this as an unqualified speedup: the abstract closes by discussing potential quantum speedups in light of recent works on efficient classical sampling approaches, flagging the comparison rather than asserting it outright. The abstract does not describe how the market-data input, the quantum operations that process it, or the output step are constructed; those mechanics are left to the paper. Reported cost: In principle poly(log N), where N is the size of the historical return dataset — rendered from the abstract's inline TeX poly(log(N)) — against poly(N) for the direct classical algorithms the abstract compares it to. The abstract states this only as an order in N: it gives no constant, no dependence on any error or precision parameter, and no qubit or gate count, and it qualifies the comparison itself by pointing to recent work on efficient classical sampling approaches rather than treating the gap as settled..
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
- portfolio_optimization_hhl
- Reported cost
- In principle poly(log N), where N is the size of the historical return dataset — rendered from the abstract's inline TeX poly(log(N)) — against poly(N) for the direct classical algorithms the abstract compares it to. The abstract states this only as an order in N: it gives no constant, no dependence on any error or precision parameter, and no qubit or gate count, and it qualifies the comparison itself by pointing to recent work on efficient classical sampling approaches rather than treating the gap as settled.
- Complexity basis
- The abstract of arXiv:1811.03975, the only source read for this record, opens by stating the contribution — "We present a quantum algorithm for portfolio optimization" — and the setting: "Given quantum access to the historical record of returns, the algorithm determines the optimal risk-return tradeoff curve and allows one to sample from the optimal portfolio." Its complexity claim is: "The algorithm can in principle attain a run time of ${\rm poly}(\log(N))$, where $N$ is the size of the historical return dataset." (TeX rendered into Unicode/plain notation for the reader: ${\rm poly}(\log(N))$ is poly(log N).) It compares this to "Direct classical algorithms for determining the risk-return curve and other properties of the optimal portfolio take time ${\rm poly}(N)$" (rendered poly(N)) and immediately qualifies the comparison: "we discuss potential quantum speedups in light of the recent works on efficient classical sampling approaches." The demonstration this record covers states no complexity bound of its own. Beyond the two run-time orders quoted above, the abstract carries no constant, no big-O for any other step, and no dependence on error or precision, which is why none appears above.
- Circuit
- Not supplied
This record is not a concrete circuit.
Quantum vs classical
Classical baseline
Compare Quantum linear algebra 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: Quantum algorithm for portfolio optimization
PROBLEM: Given quantum access to a historical record of asset returns, determine the optimal risk-return tradeoff curve of a portfolio and provide a way to sample from the optimal portfolio.
IDEA: Rebentrost and Lloyd present a quantum algorithm for portfolio optimization, addressing in turn the market-data input, the processing of that data by quantum operations, and the output of financially relevant results. Given quantum access to the historical record of returns, the algorithm determines the optimal risk-return tradeoff curve and allows one to sample from the optimal portfolio. The authors state that the algorithm can in principle attain a run time of poly(log N), where N is the size of the historical return dataset — rendered here from the abstract's own inline TeX — against poly(N) for the direct classical algorithms it compares to, which determine the risk-return curve and other properties of the optimal portfolio. They do not present this as an unqualified speedup: the abstract closes by discussing potential quantum speedups in light of recent works on efficient classical sampling approaches, flagging the comparison rather than asserting it outright. The abstract does not describe how the market-data input, the quantum operations that process it, or the output step are constructed; those mechanics are left to the paper.
REPORTED COST: In principle poly(log N), where N is the size of the historical return dataset — rendered from the abstract's inline TeX poly(log(N)) — against poly(N) for the direct classical algorithms the abstract compares it to. The abstract states this only as an order in N: it gives no constant, no dependence on any error or precision parameter, and no qubit or gate count, and it qualifies the comparison itself by pointing to recent work on efficient classical sampling approaches rather than treating the gap as settled.
BASIS: The abstract of arXiv:1811.03975, the only source read for this record, opens by stating the contribution — "We present a quantum algorithm for portfolio optimization" — and the setting: "Given quantum access to the historical record of returns, the algorithm determines the optimal risk-return tradeoff curve and allows one to sample from the optimal portfolio." Its complexity claim is: "The algorithm can in principle attain a run time of ${\rm poly}(\log(N))$, where $N$ is the size of the historical return dataset." (TeX rendered into Unicode/plain notation for the reader: ${\rm poly}(\log(N))$ is poly(log N).) It compares this to "Direct classical algorithms for determining the risk-return curve and other properties of the optimal portfolio take time ${\rm poly}(N)$" (rendered poly(N)) and immediately qualifies the comparison: "we discuss potential quantum speedups in light of the recent works on efficient classical sampling approaches." The demonstration this record covers states no complexity bound of its own. Beyond the two run-time orders quoted above, the abstract carries no constant, no big-O for any other step, and no dependence on error or precision, which is why none appears above.
PRIMARY SOURCE: Patrick Rebentrost, Seth Lloyd (2018), Quantum computational finance: quantum algorithm for portfolio optimization — https://arxiv.org/abs/1811.03975
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
- HHL linear-systems reference
Algorithms
- Quantum phase estimation
Algorithms
- Option pricing by amplitude estimation
Algorithms
- Quantum amplitude estimation
Algorithms
References
- Quantum computational finance: quantum algorithm for portfolio optimization
Patrick Rebentrost, Seth Lloyd · 2018
Primary source: it presents the quantum algorithm for portfolio optimization, states the poly(log N) run time it can in principle attain against poly(N) for the direct classical algorithms it compares to, and gives the input assumption of quantum access to the historical record of returns. Consult it for how the market-data input, the quantum processing, and the output step are actually constructed, for any constant factors or error dependence, and for the classical sampling works the abstract's discussion of potential speedups refers to — none of which the abstract itself states.