Complexity classification of the quantum minimum circuit size problems: NP-membership, hardness, and ancilla compression (Open Problems 1–2 of Chia–Chou–Zhang–Zhang)

The paper 'Quantum Meets the Minimum Circuit Size Problem' (ITCS 2022) introduced quantum analogs of the Minimum Circuit Size Problem (MCSP) for three objects — Boolean functions (MQCSP), unitaries (UMCSP), and quantum states (SMCSP) — and left their basic complexity classification open. The open questions are: are UMCSP, MQCSP, and SMCSP in NP; are they NP-hard, QCMA-hard, or C-hard for some class C between QCMA and SZK; and, as the paper's structural route to NP-membership, does the ancilla-compression containment $\mathsf{BQC}(s,t)\subseteq\mathsf{BQC}(\mathrm{poly}(s,t),O(n))$ hold for all $t\le s\le 2^{O(n)}$ ?

Background

The classical Minimum Circuit Size Problem (MCSP) asks, given the truth table of a Boolean function $f$ and a size bound $s$ in unary, whether $f$ has a Boolean circuit of size at most $s$ ; MCSP is trivially in NP (the circuit itself is a witness) but its hardness is a famous open problem. Chia, Chou, Jiayu Zhang, and Ruizhe Zhang (ITCS 2022) initiated the study of quantum analogs of MCSP for three kinds of objects. In all three, the witness is a quantum circuit over a universal gate set (a fixed finite set of gates from which any unitary can be approximated, with polylogarithmic overhead by the Solovay–Kitaev theorem): (i) MQCSP: given the truth table of a Boolean function $f$ and a size parameter $s$ , decide whether a quantum circuit of size at most $s$ , using at most $s$ ancilla qubits, computes $f$ correctly with high probability on every input; (ii) UMCSP: given the full description of a $2^n$ -dimensional unitary $U$ and a size parameter $s$ , decide whether some circuit of size at most $s$ with at most $s$ ancillas is close to $U$ on all inputs; (iii) SMCSP: given (copies or a classical description of) an $n$ -qubit state $|\psi\rangle$ and size parameters, decide whether some small circuit applied to $|0^n\rangle$ produces a state close to $|\psi\rangle$ in fidelity. Ancilla qubits are extra qubits initialized to $|0\rangle$ used as scratch registers; they are essential in quantum computation because gates are reversible, but a circuit need not return them to $|0\rangle$ . The paper proves the following baseline: MQCSP lies in QCMA (the classical-witness analog of QMA, the quantum version of NP with a quantum verifier), and UMCSP has QCMA protocols; when only linearly many ancilla qubits are allowed, MQCSP and UMCSP are in NP, because a classical verifier can simulate the witness circuit in time exponential in $n+O(n)$ ; multi-output MQCSP (with a gate set satisfying natural properties) is NP-hard under randomized reductions; a gap version of MQCSP reduces to UMCSP; and UMCSP/SMCSP admit search-to-decision reductions and SMCSP an approximate self-reduction, but only when no ancilla qubits are allowed. The classification gap has two sources. First, NP-membership breaks when the number of ancillas is superlinear: a classical verifier simulating the submitted circuit needs time exponential in $n+t$ , which is superpolynomial for $t\gg n$ , and the circuit may act non-trivially on the ancillas (implementing $U\otimes V$ with unknown $V$ ), so the witness cannot be efficiently checked nor the circuit be peeled off gate by gate. Second, apart from the paper's oracle-level inclusion $\mathsf{SZK}\subseteq\mathsf{BPP}^{\mathsf{MQCSP}}$ (SZK reduces to classical probabilistic computation with an MQCSP oracle; Theorem 3.13 of [1]), no reduction from any NP-hard, QCMA-hard, or SZK-intermediate problem to these variants is known; the paper's remaining results are consequences of efficient algorithms (e.g., MQCSP in BQP, the class of problems solvable efficiently by a quantum computer, would break quantum-secure one-way functions and put SZK in BQP). Here QCMA is the class of promise problems with classical witnesses verified by polynomial-time quantum computation, SZK is the class of problems with zero-knowledge interactive proofs, and $\mathsf{BQC}(s,t)$ denotes the class of promise problems (decision problems defined only on a promised subset of inputs) decided by quantum circuit families of size at most $s$ using at most $t$ ancilla qubits with bounded error. The paper identifies a sharp structural route to NP-membership: if large ancilla budgets could be compressed to $O(n)$ ancillas at only polynomial cost in size — the containment $\mathsf{BQC}(s,t)\subseteq\mathsf{BQC}(\mathrm{poly}(s,t),O(n))$ — then the classical simulation barrier for verifying witnesses would disappear. Bennett-style reversible uncomputation does not apply, precisely because a circuit deciding a promise problem need not clean its ancillas.

Problem Statement

Resolve the complexity classification of the quantum minimum circuit size problems introduced by Chia, Chou, Jiayu Zhang, and Ruizhe Zhang (2022) — MQCSP asks whether a small quantum circuit computes a given Boolean function, UMCSP whether a small circuit approximates a given unitary, and SMCSP whether a small circuit prepares a given quantum state — in their standard promise formulations permitting up to $s$ ancilla qubits, over any fixed universal gate set: (1) Are UMCSP, MQCSP, and SMCSP in NP? (2) Are any of them NP-hard, QCMA-hard, or C-hard for some complexity class $C$ with $\mathsf{QCMA}\subseteq C\subseteq\mathsf{SZK}$ ? As the structural sub-question identified by the paper as sufficient for part (1): (3) for all $n,s,t\in\mathbb{N}$ with $t\le s\le 2^{O(n)}$ , is $\mathsf{BQC}(s,t)\subseteq\mathsf{BQC}(\mathrm{poly}(s,t),O(n))$ — i.e., can every size- $s$ quantum circuit computation using $t$ ancilla qubits be simulated with only $O(n)$ ancilla qubits at polynomial overhead in circuit size? A complete answer determines, for each of the three variants, a containment in or hardness for one of these classes (including a proof or refutation of the ancilla-compression containment); partial answers resolving membership, hardness, or the containment for any variant would represent genuine progress on the classification, provided they address the standard (superlinear-ancilla-permitting) formulations rather than restricted variants.

References

Nai-Hui Chia, Chi-Ning Chou, Jiayu Zhang, Ruizhe Zhang. Quantum Meets the Minimum Circuit Size Problem. Innovations in Theoretical Computer Science (ITCS) 2022, DOI 10.4230/LIPIcs.ITCS.2022.47; arXiv:2108.03171. https://doi.org/10.4230/LIPIcs.ITCS.2022.47; https://arxiv.org/abs/2108.03171
Pei Yuan, Shengyu Zhang. Optimal (controlled) quantum state preparation and improved unitary synthesis by quantum circuits with any number of ancillary qubits. Quantum 7, 956 (2023), DOI 10.22331/q-2023-03-20-956; arXiv:2202.11302. https://arxiv.org/abs/2202.11302
Bruno P. Cavalar, Eli Goldin, Matthew Gray, Peter Hall. A Meta-Complexity Characterization of Quantum Cryptography. arXiv:2410.04984 (2024). https://arxiv.org/abs/2410.04984
Yanlin Chen, Yilei Chen, Rajendra Kumar, Subhasree Patro, Florian Speelman. Fine-Grained Complexity via Quantum Natural Proofs. arXiv:2504.10363 (2025). https://arxiv.org/abs/2504.10363
Lu Li, Kaifeng Bu, Dax Enshan Koh, Arthur Jaffe, Seth Lloyd. Wasserstein Complexity of Quantum Circuits. arXiv:2208.06306 (2022). https://arxiv.org/abs/2208.06306
Saugata Basu, Laxmi Parida. Quantum Analog of Shannon's Lower Bound Theorem. arXiv:2308.13091 (2023). https://arxiv.org/abs/2308.13091
Janani Gomathi, Alex Meiburg. Gradient descent reliably finds depth- and gate-optimal circuits for generic unitaries. arXiv:2601.03123 (2026). https://arxiv.org/abs/2601.03123