Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss
Authors: Hao Wang, Chenyi Zhang, Tongyang Li
ICLR 2024 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of N convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of O(Nϵ 5/3 + ϵ 8/3).1 On the other hand, we prove that quantum algorithms must take Ω(Nϵ 2/3) queries to a first order quantum oracle, showing that our dependence on N is optimal up to poly-logarithmic factors. |
| Researcher Affiliation | Academia | School of EECS Peking University Beijing, China Computer Science Department Stanford University Stanford, CA 94305, USA Center on Frontiers of Computing Studies School of Computer Science Peking University Beijing, China |
| Pseudocode | Yes | Algorithm 1: Quantum-Epoch-SGD-Proj on the exponentiated softmax Algorithm 2: Quantum sampling of the softmax distribution. |
| Open Source Code | No | The paper does not provide any links to open-source code for the described methodology or state that it is available. |
| Open Datasets | No | This paper is theoretical and does not involve experimental evaluation on datasets. Therefore, no information on training datasets is provided. |
| Dataset Splits | No | This paper is theoretical and does not involve experimental evaluation on datasets. Therefore, no information on validation splits or cross-validation is provided. |
| Hardware Specification | No | This paper is theoretical and focuses on algorithm design and lower bounds, not on empirical performance requiring specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | This paper is theoretical and presents algorithms and lower bounds, not an implementation. Therefore, no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | This paper is theoretical and does not involve empirical experiments with specific setups or hyperparameters. |