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.
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.
We study the practical performance of quantum-inspired algorithms for recommendation systems and linear systems of equations. These algorithms were shown to have an exponential asymptotic speedup compared to previously known classical methods for problems involving low-rank matrices, but with complexity bounds that exhibit a hefty polynomial overhead compared to quantum algorithms. This raised the question of whether these methods were actually useful in practice. We conduct a theoretical analysis aimed at identifying their computational bottlenecks, then implement and benchmark the algorithms on a variety of problems, including applications to portfolio optimization and movie recommendations. On the one hand, our analysis reveals that the performance of these algorithms is better than the theoretical complexity bounds would suggest. On the other hand, their performance as seen in our implementation degrades noticeably as the rank and condition number of the input matrix are increased. Overall, our results indicate that quantum-inspired algorithms can perform well in practice provided that stringent conditions are met: low rank, low condition number, and very large dimension of the input matrix. By contrast, practical datasets are often sparse and high-rank, precisely the type that can be handled by quantum algorithms.
As industrial models and designs grow increasingly complex, the demand for optimal control of large-scale dynamical systems has significantly increased. However, traditional methods for optimal control incur significant overhead as problem dimensions grow. In this paper, we introduce an end-to-end quantum algorithm for linear-quadratic control with provable speedups. Our algorithm, based on a policy gradient method, incorporates a novel quantum subroutine for solving the matrix Lyapunov equation. Specifically, we build a quantum-assisted differentiable simulator for efficient gradient estimation that is more accurate and robust than classical methods relying on stochastic approximation. Compared to the classical approaches, our method achieves a super-quadratic speedup. To the best of our knowledge, this is the first end-to-end quantum application to linear control problems with provable quantum advantage.
We study the computation of the Petz-Augustin mean of order α∈(0,1)∪(1,∞), defined as the minimizer of a weighted sum of n Petz-Rényi divergences of order α over the set of d-by-d quantum states, where the Petz-Rényi divergence is a quantum generalization of the classical Rényi divergence. We propose the first algorithm with a non-asymptotic convergence guarantee for solving this optimization problem. The iterates are guaranteed to converge to the Petz-Augustin mean at a linear rate of O(∣1−1/α∣T) with respect to the Thompson metric for α∈(1/2,1)∪(1,∞), where T denotes the number of iterations. The algorithm has an initialization time complexity of O(nd3) and a per-iteration time complexity of O(nd2+d3). Two applications follow. The first application concerns the Petz-Augustin capacity of order α∈(1/2,1), which generalizes the quantum channel capacity and characterizes the optimal error exponent in classical-quantum channel coding. To compute this quantity, we propose the first iterative method with a non-asymptotic convergence guarantee, which uses our algorithm for computing the Petz-Augustin mean as a subroutine. The second application concerns the equilibrium prices in Fisher markets with constant elasticity of substitution (CES) utilities. We establish that when all buyers have CES utilities of common elasticity, the equilibrium prices are equivalent to the Petz-Augustin mean when all quantum states commute. In this case, our proposed algorithm is a tâtonnement process à la Walras. We further extend the algorithm to inhomogeneous Fisher markets, where buyers have CES utilities with different elasticities, and prove a faster convergence rate than existing tâtonnement-type algorithms.
Quantum algorithms have been proposed for most computational tasks in trading, but the resulting literature is not a single body of work with a single standard of evidence. This survey partitions it into strands with distinct foundations and assesses each against the strongest available evidence. Pricing and market-risk computation rest on quantum amplitude estimation and carry a proven quadratic advantage in inverse precision; circuit-level resource estimates place the requirement at roughly 8000 logical qubits and a logical clock rate of tens of megahertz, several orders of magnitude beyond demonstrated hardware, with joint estimation of prices and sensitivities the main lever that lowers it. Combinatorial formulations of portfolio selection, multi-period trading trajectories and arbitrage detection map onto quadratic unconstrained binary optimization and have the field’s most mature hardware demonstrations, but an extensive benchmark on 250 real-stock instances finds classical mixed-integer programming and tailored heuristics dominant. Quantum machine learning for return prediction has been substantially dequantized, and a controlled evaluation on cross-sectional equity returns attributes reported advantages to evaluation protocol rather than to the model. A fourth strand exploits entanglement for decision coordination under latency constraints, where the advantage follows from Bell’s theorem rather than a complexity assumption. We identify the classical-quantum interface, superquadratic structure, resource-estimate methodology, nonlocal-game design and adversarial benchmarking as the productive open directions.
Abstract Quantum computing is increasingly discussed as a possible source of new computational methods for economics, but its relevance depends on whether economic bottlenecks match quantum algorithmic primitives. This critical review evaluates that match for computational economics. It synthesizes work on quantum amplitude estimation and quantum Monte Carlo for simulation and risk measurement; quadratic unconstrained binary optimization (QUBO), Ising formulations, quantum annealing, and the quantum approximate optimization algorithm for discrete optimization; and quantum linear-algebra and machine-learning primitives for econometrics and model solution. The review argues that there is no general-purpose quantum algorithm for economics analogous to Shor's algorithm for factoring. Credible claims are problem-class specific and depend on state preparation, output requirements, conditioning, hardware noise, embedding overhead, and comparison with strong classical and quantum-inspired baselines. The most mature economic applications are derivative pricing and financial risk, payment-system liquidity optimization, quantum Monte Carlo for stress testing, and early quantum-annealing formulations of dynamic programming. Transportation and infrastructure applications are relevant mainly as networked economic optimization problems. The article proposes an evidence ladder for quantum computational economics and a research agenda centered on reproducible benchmarks, economically meaningful objective functions, end-to-end resource accounting, and evaluation by economic value rather than hardware novelty. JEL Classification: C02; C15; C61; C63; C88; E37; G11; G17; R41
Gaussian process regression (GPR) is a nonparametric supervised learning method, widely valued for its ability to quantify uncertainty. Despite its advantages and broad applications, classical GPR implementations face significant scalability challenges, as they involve matrix operations with a cubic complexity in relation to the dataset size. This computational challenge is further compounded by the demand of optimizing the Gaussian Process (GP) model over its hyperparameters, rendering the total computational cost prohibitive for data intensive problems. To address this issue, we propose a quantum gradient descent algorithm to optimize the GP model. Taking advantage of recent advances in quantum algorithms for linear algebra, our algorithm achieves exponential speedup in computing the gradients of the log marginal likelihood. The entire gradient descent process is integrated into the quantum circuit. Through runtime analysis and error bounds, we demonstrate that our approach significantly improves the scalability of GPR model optimization, making it computationally feasible for large-scale applications.