# QEncodeBench: Can Large Language Models Encode Classical Problems into Verified Quantum Oracles?

arXiv: https://arxiv.org/abs/2609.20319 · HTML: https://mlsanity.com/paper/2609.20319/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 25 of its 39 references that are in the map.
- First posted on arXiv 31 Jul 2026.

## Builds on (most cited first, 25 of 25)

- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Program Synthesis with Large Language Models](https://mlsanity.com/paper/2108.07732/) (2021)
- [Self-Refine: Iterative Refinement with Self-Feedback](https://mlsanity.com/paper/2303.17651/) (2023)
- [SWE-bench: Can Language Models Resolve Real-World GitHub Issues?](https://mlsanity.com/paper/2310.06770/) (2023)
- [LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code](https://mlsanity.com/paper/2403.07974/) (2024)
- [Competition-Level Code Generation with AlphaCode](https://mlsanity.com/paper/2203.07814/) (2022)
- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [Teaching Large Language Models to Self-Debug](https://mlsanity.com/paper/2304.05128/) (2023)
- [Decomposed Prompting: A Modular Approach for Solving Complex Tasks](https://mlsanity.com/paper/2210.02406/) (2022)
- [Logic-LM: Empowering Large Language Models with Symbolic Solvers for Faithful Logical Reasoning](https://mlsanity.com/paper/2305.12295/) (2023)
- [CodeT: Code Generation with Generated Tests](https://mlsanity.com/paper/2207.10397/) (2022)
- [LINC: A Neurosymbolic Approach for Logical Reasoning by Combining Language Models with First-Order Logic Provers](https://mlsanity.com/paper/2310.15164/) (2023)
- [SatLM: Satisfiability-Aided Language Models Using Declarative Prompting](https://mlsanity.com/paper/2305.09656/) (2023)
- [Qiskit HumanEval: An Evaluation Benchmark For Quantum Code Generative Models](https://mlsanity.com/paper/2406.14712/) (2024)
- [QCircuitBench: A Large-Scale Dataset for Benchmarking Quantum Algorithm Design](https://mlsanity.com/paper/2410.07961/) (2024)
- [QAgent: An LLM-based Multi-Agent System for Autonomous OpenQASM programming](https://mlsanity.com/paper/2508.20134/) (2025)
- [GroverGPT: A Large Language Model with 8 Billion Parameters for Quantum Searching](https://mlsanity.com/paper/2501.00135/) (2024)
- [The EPFL Logic Synthesis Libraries](https://mlsanity.com/paper/1805.05121/) (2018)
- [Quantum-Audit: Evaluating the Reasoning Limits of LLMs on Quantum Computing](https://mlsanity.com/paper/2602.10092/) (2026)
- [Formal Verification of Quantum Programs: Theory, Tools and Challenges](https://mlsanity.com/paper/2110.01320/) (2021)
- [A Survey on Testing and Analysis of Quantum Software](https://mlsanity.com/paper/2410.00650/) (2024)
- [A Black-box Testing Framework for Oracle Quantum Programs](https://mlsanity.com/paper/2505.07243/) (2025)
- [QuanBench+: A Unified Multi-Framework Benchmark for LLM-Based Quantum Code Generation](https://mlsanity.com/paper/2604.08570/) (2026)
- [Qiskit QuantumKatas: Adapting Microsoft's Quantum Computing exercises for LLM evaluation](https://mlsanity.com/paper/2605.27210/) (2026)

## Abstract (arXiv)

Grover search, amplitude amplification, and quantum counting all rely on the same reusable subroutine, a phase oracle, whose construction the algorithms literature takes as given: the classical predicate is assumed to be already encoded as a correct, resource-bounded circuit. We turn this assumption into a measured capability. QEncodeBench tasks large language models (LLMs) with encoding classical constraint problems as phase oracles and scores the generated circuits with an adversarially self-validated verifier that decides full solution-set equivalence up to a global phase, with ancillas restored and resource budgets enforced. Sampled basis-state tests, we show, systematically overestimate this ability. Measured this way, models separate sharply: code models without a reasoning mode solve essentially nothing, and enabling native reasoning on identical weights improves accuracy by an order of magnitude. The failures are overwhelmingly semantic rather than syntactic. Two architectures, a unit-verified constraint agent and a neuro-symbolic compilation pipeline, close most of the remaining gap by delegating correctness-critical composition to deterministic procedures. Ablations quantify the contribution of each component, and resource gating exposes an architecture-dependent trade-off between circuit width and depth. Finally, controlled difficulty escalation reveals architecture-specific responses to difficulty structure: different difficulty axes degrade different methods, while the neuro-symbolic pipeline passes every evaluated instance. Code and data are available at https://github.com/chexujun/QEncodeBench.