Quantum computing is an emerging field recognized for the significant speedup it offers over classical computing through quantum algorithms. However, designing and implementing quantum algorithms pose challenges due to the complex nature of quantum mechanics and the necessity for precise control over quantum states. Despite the significant advancements in AI, there has been a lack of datasets specifically tailored for this purpose. In this work, we introduce QCircuitBench, the first benchmark dataset designed to evaluate AI's capability in designing and implementing quantum algorithms in the form of quantum circuit codes. Unlike using AI for writing traditional codes, this task is fundamentally more complicated due to highly flexible design space. Our key contributions include: 1. A general framework which formulates the key features of quantum algorithm design task for Large Language Models.2. Implementation for quantum algorithms from basic primitives to advanced applications, spanning 3 task suites, 25 algorithms, and 120,290 data points.3. Automatic validation and verification functions, allowing for iterative and interactive evaluation without human inspection.4. Promising potential as a training dataset through primitive fine-tuning results.We observed several interesting experimental phenomena: fine-tuning does not always outperform few-shot learning, and LLMs tend to exhibit consistent error patterns. QCircuitBench provides a comprehensive benchmark for AI-driven quantum algorithm design, while also revealing some limitations of LLMs in this domain.

Detecting out-of-distribution (OOD) instances is crucial for NLP models in practical applications.Although numerous OOD detection methods exist, most of them are empirical.Backed by theoretical analysis, this paper advocates for the measurement of the "OOD-ness" of a test case x through the likelihood ratio between out-distribution P out and in-distribution P in .We argue that the state-of-the-art (SOTA) feature-based OOD detection methods, such as Maha (Lee et al., 2018) and KNN (Sun et al., 2022), are suboptimal since they only estimate in-distribution density p in (x).To address this issue, we propose FLatS, a principled solution for OOD detection based on likelihood ratio.Moreover, we demonstrate that FLatS can serve as a general framework capable of enhancing other OOD detection methods by incorporating out-distribution density p out (x) estimation.Experiments show that FLatS establishes a new SOTA on popular benchmarks. 1

Recent studies have discovered that Chain-of-Thought prompting (CoT) can dramatically improve the performance of Large Language Models (LLMs), particularly when dealing with complex tasks involving mathematics or reasoning. Despite the enormous empirical success, the underlying mechanisms behind CoT and how it unlocks the potential of LLMs remain elusive. In this paper, we take a first step towards theoretically answering these questions. Specifically, we examine the expressivity of LLMs with CoT in solving fundamental mathematical and decision-making problems. By using circuit complexity theory, we first give impossibility results showing that bounded-depth Transformers are unable to directly produce correct answers for basic arithmetic/equation tasks unless the model size grows super-polynomially with respect to the input length. In contrast, we then prove by construction that autoregressive Transformers of constant size suffice to solve both tasks by generating CoT derivations using a commonly used math language format. Moreover, we show LLMs with CoT can handle a general class of decision-making problems known as Dynamic Programming, thus justifying their power in tackling complex real-world tasks. Finally, an extensive set of experiments show that, while Transformers always fail to directly predict the answers, they can consistently learn to generate correct solutions step-by-step given sufficient CoT demonstrations.