Rik Sengupta: Separating Quantum Circuits from Classical LLMs

Item: Rik Sengupta: Separating Quantum Circuits from Classical LLMs
Rating: 4
Author: PostSingularity Institute

Title history

Rik Sengupta: Separating Quantum Circuits from Classical LLMs — observed on 20261103-1921 UTC (YouTube)

by Rik Sengupta · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UYComputer science UYAMathematical theory of computation

🎙 Rik Sengupta 👥 3K 📅 November 3, 2026 ⏱ 46 min 👁 6 📄 original study 🧭 2026-11-03

Available in: English (current) Français

Keywords

iterated indexquantum circuitsLLMcomplexity separationtransformer width

Summary

The seminar talk by Rik Sengupta, from IBM Research, presents a theoretical result separating shallow quantum circuits from classical transformer models. The central contribution is an explicit function family called iterated multi-index, which can be computed by a small mostly quantum circuit of depth O(log log n) with a single unbounded fan-in AND gate, but requires transformers of large width for any fixed depth L. The talk situates the work within the broader goal of separating BPP from BQP, and discusses prior results such as QNC0 containing NC0 and AC0. The speaker carefully defines the models: transformers with standard softmax attention and parameters (depth L, heads H, embedding dimension D, precision P), and quantum circuits with standard gate sets. The iterated index function is a recursive generalization of the classical index function, where the output of one level is used as an index into subsequent tables. The quantum upper bound constructs a QNC0-like circuit exploiting the ability to test equality in constant depth, while the classical lower bound relies on communication complexity arguments resembling those for iterated index functions. The talk concludes with caveats about the non-uniform circuit model and the need for multiple copies of input, as well as open questions about removing the classical AND gate or improving the log log depth. The presentation is dense but well-structured, aimed at an audience familiar with computational complexity.

228 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk offers significant value by providing an explicit separation result between quantum circuits and transformer models, a step toward understanding the power of quantum computation over classical machine learning paradigms. The argumentation is rigorous: the speaker builds the separation from established concepts, clearly defining the function and outlining both upper and lower bounds. The use of a well-chosen iterated index function is elegant, and the arguments are presented with appropriate caveats, such as the need for multiple input copies in the quantum circuit. The connection to ongoing research on BPP vs BQP contextualizes the result, though the speaker honestly notes that this does not demonstrate practical quantum advantage. Overall, the value lies in deepening the theoretical understanding of what quantum circuits can achieve relative to classical attention-based models.

Scientific Rigor, Source Quality, Title Accuracy

The rigor is high: the speaker cites specific prior work, including Bravyi et al. for QNC0 containment and Li et al. for transformer width and iterated index lower bounds. The technical definitions are precise, and the talk adheres to established conventions in quantum complexity theory. The title is appropriate and does not overstate the findings; it accurately indicates a theoretical separation rather than a practical demonstration. The presentation is consistent with the seminar format and maintains a high level of technical accuracy. While no external links are provided in the description, the internal references are credible within the field.

243 words

Title / Content Match

The title accurately reflects the content: the speaker presents a theoretical separation between quantum circuit classes and transformer models, focusing on computational complexity.

Quality & Reliability

8/10

The talk presents original theoretical research from IBM Research, referencing established results and giving a clear technical exposition. While not peer-reviewed, the speaker demonstrates deep expertise and the content aligns with contemporary complexity theory.

Key Moments

Markers derived by PSI from the transcript: the creator did not define chapters.

Cited Sources

Bravyi et al. (2018), Quantum advantage with shallow circuits — Cited for the result that QNC0 strictly contains NC0.
Li et al., work on transformer width and iterated index lower bounds — Inspired the definition and hardness of the iterated index function.

Contribution & Novelties

The talk contributes a novel separation result between QNC0-like quantum circuits and transformer models, using an iterated multi-index function. It extends previous work on transformer width and builds on quantum complexity results, offering a concrete instance where quantum circuits with logarithmic-logarithmic depth outperform transformers with fixed depth but high width. The result is theoretical but relevant to understanding the fundamental limits of attention-based architectures.

Pour aller plus loin :

Quantum computing — Context for quantum circuits and their power.
BQP (complexity class) — The class of problems efficiently solvable on a quantum computer, central to the separation discussion.
Transformer (deep learning architecture) — The model class under consideration, with details on architecture.
Circuit complexity — Foundational topic for understanding QNC0 and related classes.

123 words

Radar Profile

The profile shows very high technical complexity and information density, with slightly lower scores for quality and reliability due to the presentation being a seminar talk without peer review. The balance indicates a rigorous but highly specialized content requiring expert audience.

Reliability 8/10