Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Jiayu Zhang:

TR21-116 | 10th August 2021
Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang

Quantum Meets the Minimum Circuit Size Problem

Revisions: 1

In this work, we initiate the study of the Minimum Circuit Size Problem (MCSP) in the quantum setting. MCSP is a problem to compute the circuit complexity of Boolean functions. It is a fascinating problem in complexity theory---its hardness is mysterious, and a better understanding of its hardness can have ... more >>>

ISSN 1433-8092 | Imprint