Quantum-Classical Equivalence for AND functions by Sreejato Bhattacharya

Quantum-Classical Equivalence for AND functions by Sreejato Bhattacharya

by Sreejato Bhattacharya · View the channel on PSI

Formal & Physical Sciences Computing & Cybersecurity UYComputer scienceUYXNatural computing
🎙 Sreejato Bhattacharya 👥 74K 📅 September 28, 2026 ⏱ 41 min 👁 1 📄 original study 🧭 2026-09-28
Available in: English (current) Français

Keywords

communication complexityquantumAND functionsapproximate ranklog rank conjecture

Summary

The speaker presents a new result in communication complexity: for AND-lifted Boolean functions, deterministic communication complexity is polynomially bounded by quantum communication complexity, thereby proving the log equivalence conjecture for this class. The key technical contribution is showing that the approximate rank of such functions is closely related to the sparsity of the base function. The proof uses Fourier analysis, restriction and averaging operators, and builds on prior work by Razborov, Burman-Wolf, and others. The talk outlines the main argument: assuming a large gap between sparsity and approximate rank leads to a Boolean function with a large gap between its exact degree and approximate degree, contradicting known upper bounds. The result closes an open problem from 2002.

117 words

Critical Evaluation

Value of the Information & Strength of the Argument

The talk provides a well-structured argumentation, clearly motivating the problem and the approach. The speaker explains the relevance of AND functions and the connection to open conjectures such as the log rank and log equivalence conjectures. The proof sketch is coherent and detailed enough to convey the main ideas, highlighting the role of Fourier analysis and the careful construction of a distribution over restrictions. The presentation is rigorous and demonstrates a deep understanding of the subject.

Scientific Rigor, Source Quality, Title Accuracy

The talk references several prior works (Razborov, Burman-Wolf, Lovett et al.) and the program page is linked. The title is faithful to the content. No comments are available to analyze public reception.

123 words

Title / Content Match

The title accurately describes the content: the talk proves an equivalence between quantum and classical communication complexity for AND functions.

Quality & Reliability

8/10

The talk is a research seminar presenting new results, with a detailed proof sketch from a reputable institute. The content is technical and appears rigorous, but the claims are not independently verified in this setting.

Key Moments

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

Cited Sources

Contribution & Novelties

The main original contribution is proving the log approximate rank conjecture for AND-lifted functions, which implies the quantum-classical equivalence for this class. This resolves an open problem by Razborov (2002) and advances the understanding of the connection between sparsity, approximate rank, and communication complexity.

Pour aller plus loin :

  • Communication complexity — For background on the model and key results.
  • Quantum complexity theory — For quantum models of computation, including communication.
  • Fourier analysis on the Boolean cube — To understand the Fourier tools used in the proof.

87 words

Radar Profile

The radar profile is highly skewed toward technical depth (9/10) and moderate-to-high on quantity and quality of information (8/8). The reliability score is slightly lower (7/10), reflecting that the claims are presented without external verification but are consistent with established literature.

Reliability 7/10