OpenAI’s AI-Generated Proof To Challenge Quantum Advantage
OpenAI has invited external researchers to examine an AI-generated proof that, according to the company, challenges a long-held assumption about the inherent difficulty of certain computing problems. This work directly addresses the Exponential Time Hypothesis (ETH). A team from UC San Diego and MIT will be responsible for verifying and explaining the findings. The implications could extend to quantum computing, as some arguments for quantum advantage depend on assumptions about the limitations of classical machines.
Details of the Review
OpenAI’s press release identifies three scientific advancements currently under review. The primary computational claim centers on the Exponential Time Hypothesis (ETH), which describes the exponential increase in difficulty for certain logic problems as their size grows. A proof purporting to disprove ETH has been verified using Lean, a system for checking mathematical reasoning, and has been made publicly available for inspection.
The external review group includes individuals who were instrumental in formulating the hypothesis:
- Russell Impagliazzo and Ramamohan Paturi of UC San Diego, both original formulators of ETH.
- Ryan Williams of MIT, who will help verify and explain the results.
- A separate collaboration led by physicist David Gross, which is examining claimed existence proofs for quantum field theories, including quantum chromodynamics.
OpenAI is holding back the AI-produced materials related to the physics work until Gross’s group completes its account. One specific detail clarifies the second claim: the announcement mentions the existence of pure Yang-Mills theory, which constitutes only a portion of the Clay Mathematics Institute’s Millennium Prize problem. That problem also requires establishing a mass gap, so an existence claim alone doesn’t solve it.
Why Quantum Researchers Will Be Attentive
Disproving ETH wouldn’t automatically make large problems easy. A method could run in “subexponential” time and still be too slow for practical use. OpenAI’s own example illustrates this: a calculation requiring two raised to the square root of the number of variables would involve approximately a trillion steps for a problem with 1,600 variables. Furthermore, the claim doesn’t resolve the P versus NP problem.
The quantum aspect is more nuanced than the headline might suggest. Some arguments regarding the difficulty of simulating quantum circuits rely on the Strong Exponential Time Hypothesis (SETH), a related assumption. A 2018 study found classical limits on simulating quantum circuit amplitudes, with part of its conclusion resting on SETH. If this assumption is invalidated, those specific parts would require a new foundation, while results not dependent on it would remain valid.
The loss of an argument that something must be difficult does not automatically provide a faster method to achieve it. The task now for the research community is to determine which quantum comparisons depend on challenged assumptions and which are based on measured performance. For more information on how researchers evaluate these claims, refer to QNews coverage of quantum algorithm benchmarks.