Research map / Learning theory and algorithms / Submodular and game algorithms
Quantum algorithm for large-scale market equilibrium computation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a quantum algorithm for Fisher market equilibrium based on a faulty proportional response dynamics, using quantum norm and inner-product estimation to get sublinear-in-mn runtime, validated by simulations at n=m=16384.
Problem
Computing Fisher market equilibrium (EG convex program) via proportional response dynamics scales linearly in the product of buyers and goods, which is costly for large Internet-scale markets.
Approach
Introduces faulty proportional response (FPR) dynamics whose price and utility computations are estimates, and implements them quantumly by computing bids on the fly from QRAM-stored products of prices and utility estimates, using quantum amplitude estimation for l1 norms and inner products to obtain a quadratic speedup in the smaller dimension.
Key results
- Theoretical runtime of the quantum algorithm is O~(T^2 sqrt(mn max(m,n)) log(1/delta)) versus O(mn/eps) per classical PR run, a polynomial speedup in the product of buyers and goods.
- Simulated quantum algorithm (QAE emulated classically) converges much faster than PR dynamics per query on 16384x16384 markets, per the authors' plots.
- PR-based methods (classical and quantum) outperform projected gradient descent in the mid-accuracy, low-iteration regime.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use quantum norm and inner-product estimation in faulty proportional response updates instead of computing the updates classically | Fisher market equilibrium computation · Numerical simulations with 16384 buyers and 16384 goods | objective convergence at equal query budget | Helped |
| Use PR-dynamics-related updates instead of projected gradient descent | Fisher market equilibrium computation · Mid-accuracy regime | objective convergence | Helped |
| Replace classical PR updates with quantum FPR updates | Fisher market equilibrium computation · Fisher markets | runtime: $\tilde{\mathcal O} \Big(\dfrac{mn}{\varepsilon}\Big)$ -> $ \tilde{\mathcal O} \bigg(\dfrac{\sqrt{mn\max(m,n)}}{\varepsi | Helped |
| Use quantum rather than classical computation for the iterations | Fisher market equilibrium computation · Mid-accuracy regime | objective convergence | Helped |
Surprising findings
- Quantum speedup is reported with the number of iterations increasing by T, so the total speedup comes from the logarithmic dependence of T on m.
- Frank-Wolfe style alternatives may have O(n) iteration dependence, making them worse for quantum speedups.
Limitations
- Speedup depends on QRAM and quantum query access to inputs; QAE requires fault-tolerant hardware.
- Simulation emulates QAE classically and does not run on quantum hardware; QAE iterations scaled down by a factor of 16.
- No speedup when number of buyers is constant (addressed only in a discussion extension).
Experimental setup
Datasets: synthetic market data (values uniform on (0,1] and normal N(0.5,0.25); budgets sampled or equal)
Benchmarks: synthetic Fisher markets with n=m=16384
Metrics: EG objective gap versus number of queries
Baselines: proportional response dynamics projected gradient descent
Builds on: proportional response dynamics quantum amplitude estimation Eisenberg-Gale convex program Shmyrev convex program
Closest papers by meaning
- Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games (NeurIPS 2025 · similarity 0.84)
- Learning Bayesian Nash Equilibrium in Auction Games via Approximate Best Response (ICML 2025 · similarity 0.82)
- Quantum Algorithms for Finite-horizon Markov Decision Processes (ICML 2025 · similarity 0.82)
- Winning Lottery Tickets in Neural Networks via a Quantum-Inspired Classical Algorithm (NeurIPS 2026 · similarity 0.81)
- Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling (ICLR 2025 · similarity 0.81)
- Quantum speedup of non-linear Monte Carlo problems (NeurIPS 2025 · similarity 0.81)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.