Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > CHENGHUA LIU:
All reports by Author Chenghua Liu:

TR26-258 | 18th October 2026
Minbo Gao, Zhengfeng Ji, Chenghua Liu

A simplified proof of PARITY $\notin$ QAC$^0$

We give a simplified, self-contained proof of OpenAI's parity lower bound for constant-depth quantum circuits with arbitrary one-qubit gates, unbounded-arity Toffoli gates, and polynomially many ancillas. The proof establishes product-projection localization and uses it to bound the parity Fourier coefficient of the acceptance probability. We remove one circuit layer directly, ... more >>>


TR26-117 | 8th July 2026
Minbo Gao, Chenghua Liu, Guangxu Yang, Tianyi Zhang

Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy

We study one-way quantum communication lower bounds for search problems.Unlike decision problems, search problems can have many valid outputs, which pose a fundamental barrier to standard quantum lower-bound techniques. We overcome this by developing a novel method based on matrix discrepancy, which allows us to bound the output measurements of ... more >>>




ISSN 1433-8092 | Imprint