Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2405.13788 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911354119520256 |
|---|---|
| author | Huang, Po-Wei Rebentrost, Patrick |
| author_facet | Huang, Po-Wei Rebentrost, Patrick |
| contents | Classical algorithms for market equilibrium computation such as proportional response dynamics face scalability issues with Internet-based applications such as auctions, recommender systems, and fair division, despite having an almost linear runtime in terms of the product of buyers and goods. In this work, we provide the first quantum algorithm for market equilibrium computation with sub-linear performance. Our algorithm provides a polynomial runtime speedup in terms of the product of the number of buyers and goods while reaching the same optimization objective value as the classical algorithm. Numerical simulations of a system with 16384 buyers and goods support our theoretical results that our quantum algorithm provides a significant speedup. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13788 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Quantum algorithm for large-scale market equilibrium computation Huang, Po-Wei Rebentrost, Patrick Quantum Physics Computer Science and Game Theory Classical algorithms for market equilibrium computation such as proportional response dynamics face scalability issues with Internet-based applications such as auctions, recommender systems, and fair division, despite having an almost linear runtime in terms of the product of buyers and goods. In this work, we provide the first quantum algorithm for market equilibrium computation with sub-linear performance. Our algorithm provides a polynomial runtime speedup in terms of the product of the number of buyers and goods while reaching the same optimization objective value as the classical algorithm. Numerical simulations of a system with 16384 buyers and goods support our theoretical results that our quantum algorithm provides a significant speedup. |
| title | Quantum algorithm for large-scale market equilibrium computation |
| topic | Quantum Physics Computer Science and Game Theory |
| url | https://arxiv.org/abs/2405.13788 |