Quantum algorithm for large-scale market equilibrium computation
- URL: http://arxiv.org/abs/2405.13788v1
- Date: Wed, 22 May 2024 16:12:45 GMT
- Title: Quantum algorithm for large-scale market equilibrium computation
- Authors: Po-Wei Huang, Patrick Rebentrost,
- Abstract summary: We provide the first quantum runtime algorithm for market equilibrium computation with sub-linear performance.
Our algorithm provides the same runtime speedup in terms of the product of the number of buyers and goods while reaching the objective optimization value as the classical algorithm.
- Score: 0.9208007322096533
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- A Quadratic Speedup in Finding Nash Equilibria of Quantum Zero-Sum Games [102.46640028830441]
We introduce the Optimistic Matrix Multiplicative Weights Update (OMMWU) algorithm and establish its average-iterate convergence complexity as $mathcalO(d/epsilon)$ to $epsilon$-Nash equilibria.
This quadratic speed-up sets a new benchmark for computing $epsilon$-Nash equilibria in quantum zero-sum games.
arXiv Detail & Related papers (2023-11-17T20:38:38Z) - Quantum speedup for combinatorial optimization with flat energy
landscapes [0.0]
We develop a theoretical framework to analyze the relative performance of the optimized quantum adiabatic algorithm and a broad class of classical Markov chain Monte Carlo algorithms.
arXiv Detail & Related papers (2023-06-22T18:00:00Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
We design, implement, and evaluate three hybrid quantum k-Means algorithms.
We exploit quantum phenomena to speed up the computation of distances.
We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
arXiv Detail & Related papers (2022-12-13T16:04:16Z) - Quantum algorithm for stochastic optimal stopping problems with
applications in finance [60.54699116238087]
The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory.
We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
arXiv Detail & Related papers (2021-11-30T12:21:41Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator.
variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware.
We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
arXiv Detail & Related papers (2021-08-09T18:00:05Z) - An optimal quantum sampling regression algorithm for variational
eigensolving in the low qubit number regime [0.0]
We introduce Quantum Sampling Regression (QSR), an alternative hybrid quantum-classical algorithm.
We analyze some of its use cases based on time complexity in the low qubit number regime.
We demonstrate the efficacy of our algorithm for a benchmark problem.
arXiv Detail & Related papers (2020-12-04T00:01:15Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z) - Towards quantum advantage via topological data analysis [0.0]
We study the quantum-algorithmic methods behind the algorithm for topological data analysis of Lloyd, Garnerone and Zanardi.
We provide a number of new quantum algorithms for problems such as rank estimation and complex network analysis.
arXiv Detail & Related papers (2020-05-06T06:31:24Z) - Approximating the quantum approximate optimization algorithm with
digital-analog interactions [0.0]
We show that the digital-analog paradigm is suited to the variational quantum approximate optimisation algorithm.
We observe regimes of single-qubit operation speed in which the considered variational algorithm provides a significant improvement over non-variational counterparts.
arXiv Detail & Related papers (2020-02-27T16:01:40Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.