Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NAI-HUI CHIA:
All reports by Author Nai-Hui Chia:

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