Quantum algorithm for large-scale market equilibrium computation
Authors: Po-Wei Huang, Patrick Rebentrost
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Numerical simulations of a system with 16384 buyers and goods support our theoretical results that our quantum algorithm provides a significant speedup. |
| Researcher Affiliation | Academia | 1Centre for Quantum Technologies, National University of Singapore, Singapore 117543 2Department of Computer Science, National University of Singapore, Singapore 117417 |
| Pseudocode | Yes | The full algorithm is shown in Algorithm 1, and the algorithmic guarantee is shown in Theorem 5. |
| Open Source Code | Yes | The codebase can be found at https://github.com/georgepwhuang/q-market-equilibrium. |
| Open Datasets | No | For our experiments, we generate the input data v where the value v is sampled from a uniform distribution with range (0, 1] and a normal distribution N(0.5, 0.25), where we resample values that fall outside the range of (0, 1]. The paper generates its own data and does not provide access to a publicly available dataset, nor does it refer to an established benchmark dataset. |
| Dataset Splits | No | The paper discusses algorithmic iterations and convergence but does not provide specific training, validation, or test dataset splits in terms of percentages or sample counts for data partitioning. |
| Hardware Specification | Yes | Our experiments are conducted on a single NVIDIA P100 GPU and written with the Py Torch library [99]. |
| Software Dependencies | No | Our experiments are conducted on a single NVIDIA P100 GPU and written with the Py Torch library [99]. While PyTorch is mentioned, a specific version number for it or any other software dependency is not provided in the text. |
| Experiment Setup | Yes | For QAE, we run for p T n = 512 iterations and set M O( p T n). We compensate for the loss in accuracy of the estimation by employing the median-ofmeans estimator [60], where we take the median of 3 estimators constructed from the mean of 7 samples from the QAE subroutine. For the PR dynamics, we iterate for T = 16 iterations. We rerun our quantum algorithm over 15 times. |