From Model Conjecture to Formal Proof: Verifying the Boundaries of Quantum Speedup

In recent years, artificial intelligence systems have continuously improved their capabilities in code generation, theorem proving, and mathematical reasoning. A recent, yet-to-be-independently-verified report claimed that a research team used an undisclosed internal model to process a long-standing complexity theory conjecture in a short period, translating the core arguments into a formal proof and submitting it to a proof checker. Once circulated, this news was interpreted as “AI has found the exponential advantage boundary of quantum computing over classical computing.”

While this narrative is highly compelling, it must be deconstructed into several distinct questions: What does the conjecture itself investigate? What step did the model actually complete? What does formal verification guarantee? Has it changed our understanding of the relationship between quantum and classical computing? Only by addressing these questions separately can we avoid equating “generating a seemingly complete proof” with “a mathematical conclusion is established.”

1. Why the Related Conjecture Matters

Such conjectures typically reside at the intersection of computational complexity theory, Boolean function analysis, and quantum query complexity. The core focus is not on a specific chip or algorithm, but on a more fundamental question:

For a certain class of computational problems, can quantum algorithms consistently achieve significant advantages in terms of query count, sample size, or computational resources that classical algorithms cannot replicate?

In complexity theory, researchers frequently use tools like polynomial representations of functions, Fourier spectra, variable influence, and query complexity to characterize problem structures. A function might possess a low-degree approximation or exhibit highly dispersed spectral features; these mathematical properties directly impact the achievable efficiency of randomized, deterministic, and quantum algorithms.

The conjecture has garnered long-term attention because it attempts to bridge several seemingly distinct concepts:

1. The relationship between low-complexity representations and variable influence;
2. Whether a function’s structure can be explained by a small number of key variables;
3. Whether the quantum query model can leverage global interference information that classical algorithms struggle to discover;
4. Whether quantum advantage is universal or only exists in a few carefully constructed problems.

If the conjecture holds, it may imply that certain functions, while difficult to process efficiently in classical models, still contain internal structures exploitable by quantum algorithms. If the conjecture is disproven, it might indicate that our current understanding of quantum speedup boundaries needs revision. However, it must be emphasized: solving a mathematical conjecture typically only affects specific theoretical propositions and cannot directly lead to the conclusion that “quantum computing has comprehensively surpassed classical computing.”

2. “Model Solved” is Not the Same as “Mathematical Theorem Established”

AI systems process mathematical problems across roughly four levels:

1. Finding Possible Proof Strategies

Models can extract patterns from vast arrays of known theorems, counterexamples, and proof templates to propose new lemmas, construct functions, or outline induction paths. This step is highly valuable, but the output remains a research hypothesis.

2. Generating Natural Language Proofs

A model might generate a structurally complete proof text, including definitions, lemmas, main theorems, and corollaries. However, natural language proofs are prone to implicit premises, quantifier scope errors, missing boundary conditions, and skipped steps justified as “obviously true.”

3. Translating to Formal Proofs

Researchers can deconstruct the proof into formal language definitions, propositions, and derivations, handing them over to a proof checker for step-by-step verification. The formalization process forces authors to explicitly state every type, variable scope, and dependency, significantly reducing the oversights common in traditional papers.

4. Independent Review and Community Consensus

Even if a formal proof passes checking, researchers must confirm that the formalized object corresponds exactly to the original conjecture, with no modeling errors, citation errors, or overly strong assumptions. Ultimately, independent teams need to reproduce the work, review the proof structure, and confirm the academic significance of the conclusion.

Therefore, “a proof checker accepting a formalized script” indicates that, given the specified axioms, definitions, and library environment, the script satisfies the checker’s rules of inference. It does not automatically guarantee the following:

• The formalized proposition is the original conjecture;
• All definitions align with standard domain definitions;
• The axiomatic system used matches community expectations;
• The proof hasn’t inadvertently proven a different proposition due to translation errors;
• The result explains the actual algorithmic speedup.

3. Why Formal Verification is a Key Advancement

Traditional mathematics papers rely on expert review, whereas complex proofs often contain massive amounts of intermediate steps. The advantage of formal proofs is that they transform “trusting the argument” into “checking the derivation.”

A typical workflow can be abstracted as follows:

Natural language conjecture
    ↓
Precise definition of objects and quantifiers
    ↓
Decomposition into several lemmas
    ↓
Translation into formalized propositions
    ↓
Generation of proof terms by proof search systems
    ↓
Verification by an independent checker
    ↓
Manual review of modeling and conclusions

The most critical aspect here is not whether the model can write the final answer in one go, but whether it can accomplish the following:

• Automatically discover missing intermediate lemmas;
• Conduct exhaustive enumeration and counterexample searches for finite cases;
• Break down complex proofs into verifiable small modules;
• Record the definitions and assumptions relied upon at each step;
• Quickly re-check the entire proof chain after modifying a proposition.

This approach is particularly suitable for long-standing unsolved problems, as it expands the research process from “relying on experience for inspiration” to a collaborative effort involving “machine search, formal verification, and human interpretation.”

4. Why We Cannot Rashly Announce “Quantum Computing is Proven to Crush Classical Computing”

“Exponential advantage” is a highly rigorous technical term that requires clarity regarding the objects being compared, input size, resource models, and success probability.

First, we must distinguish between query complexity, time complexity, space complexity, and communication complexity. A problem exhibiting exponential advantage in the quantum query model does not guarantee equivalent advantages on actual hardware. The query model often assumes unit-cost access to an idealized black box, whereas real systems incur costs for data loading, error correction, gate operations, measurement, and result readout.

Second, the limitations of classical algorithms must be clearly defined. If a result only rules out a specific class of classical algorithms, the conclusion cannot be extended to all classical computational models. It must also be clear whether the classical algorithm allows randomness, approximation errors, preprocessing, and non-uniform computational resources.

Third, there is a gap between mathematical existence results and engineering feasibility. A problem might possess theoretical quantum speedup, but the required quantum scale, error correction overhead, or input encoding costs might be so high that practical implementation is impossible in the short term.

Therefore, a more rigorous statement would be: A formalized result may advance our understanding of the quantum-classical complexity relationship within a specific family of problems, but whether it constitutes a universal exponential advantage requires evaluation based on the complete theorem, algorithmic construction, and resource analysis.

5. How to Audit an AI-Assisted Mathematical Breakthrough

When faced with similar claims, technical verification can be conducted using the following checklist:

Proposition Verification

Confirm whether public materials provide complete definitions, including the function domain, input size, error parameters, complexity model, and scope of application. “Solving a conjecture” in a headline sometimes refers to the original proposition, but might also just be an equivalent variant or a special case under附加 conditions.

Proof Verification

Check if the proof is public, includes all dependencies, and can be reconstructed in a clean environment. If there are only screenshots, summaries, or demo videos without auditable materials, it should not be considered a completed verification.

Formal Environment Verification

Confirm the formal system used, foundational axioms, math library versions, and custom axioms. Pay special attention to whether unproven assumptions were introduced or whether definitions inconsistent with the original problem were used.

Independent Review

Ideally, researchers not involved in the original work should re-run the checks and read the key lemmas. Machine checking can detect logical derivation errors but struggles to independently judge whether the proposition was translated correctly.

Result Interpretation

Finally, answer the following: Which known boundary did this proof alter? Does it provide a new algorithm? Does it establish a lower bound? Does it only solve a special case in an abstract model? Only by clarifying these points does the result possess communicable scientific value.

6. Practical Implications for Developers and Research Teams

Such events also offer valuable references for software engineering. For high-risk reasoning tasks, teams should not merely pursue model output speed, but should establish a “generation—checking—reproduction—auditing” closed loop.

In engineering implementations, the following strategies can be adopted:

1. Have the model output structured intermediate results rather than just the final conclusion;
2. Bind evidence to every key assertion, recording definitions, assumptions, and dependencies;
3. Delegate automatically checkable parts to verifiers to reduce manual repetitive labor;
4. Maintain complete version histories to locate where the model altered the argumentation;
5. Introduce independent review processes to prevent the generative model from acting as the sole judge;
6. Remain cautious of exceptionally strong conclusions, prioritizing the search for counterexamples, boundary conditions, and hidden assumptions.

Regardless of whether using local models, internal enterprise systems, or general AI services on Baidu AI Cloud, reliability should not be built on the premise that “the model looks smart,” but on reproducible, explainable, and verifiable workflows.

Conclusion

The true breakthrough of AI in mathematical research may not merely be “providing an answer in a few days,” but connecting conjecture search, proof construction, formal verification, and collaborative review into a new research pipeline. For long-standing unsolved problems, this capability promises to significantly reduce trial-and-error costs and help researchers discover structures previously difficult to track manually.

However, until formal papers, peer review, and independent replication are completed, any claim that “a model has solved a conjecture” should be treated as unverified information. A more reliable standard for judgment is not the speed of dissemination or the model’s name, but: whether the proposition is accurate, whether the proof is complete, whether the formalization matches, whether the result can be reproduced, and exactly which theoretical boundary it advances. Only when these conditions are met will AI-assisted mathematical discovery transition from a stunning demonstration into knowledge truly inheritable by the scientific community.