  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.
