Complexity

Abstract: Quantum computing introduces many well-motivated problems rooted in physics, asking to compute information from input quantum states. Identifying the computational hardness of these problems yields potential applications with far-reaching impacts across both the realms of computer science and physics. However, these new problems do not neatly fit within the scope of existing complexity theory. The standard classes primarily cater to problems with classical inputs and outputs, leaving a gap to characterize problems involving quantum states as inputs. For instance, breaking new quantum cryptographic primitives involves solving problems with quantum inputs; this significantly changes Impagliazzo’s five-world while the complexity classes central to Pessiland, Heuristica, and Algorithmica are grounded in problems with classical inputs and outputs. To bridge these knowledge gaps, we explore the complexity theory for quantum promise problems and potential applications. Quantum promise problems are quantum-input decision problems asking to identify whether input quantum states satisfy specific properties. We begin by establishing structural results for several fundamental quantum complexity classes: p/mBQP, p/mQ(C)MA, p/mQSZKhv, p/mQIP, p/mBQP/qpoly, p/mBQP/poly, and p/mPSPACE. This includes identifying complete problems, as well as proving containment and separation results among these classes. Here, p/mC denotes the corresponding quantum promise complexity class with pure (p) or mixed (m) quantum input states for any classical complexity class C. Surprisingly, our findings uncover relationships that diverge from their classical analogues — specifically, we show unconditionally that p/mQIP \neq p/mPSPACE and p/mBQP/qpoly \neq p/mBQP/poly. This starkly contrasts the classical setting, where QIP=PSPACE and separations such as BQP/qpoly \neq BQP/poly are only known relative to oracles. This new framework has numerous applications in quantum cryptography, particularly in the contexts of Microcrypt and unconditional cryptography [Qia24, MNY24]. For Microcrypt, we provide a better characterization of its primitives; for example, we show that OWSG and PRS can be broken by a p/mQCMA oracle, leading to a natural quantum analogue of Impagliazzo’s five worlds by substituting the classical complexity classes in Pessiland, Heuristica, and Algorithmica with mBQP and mQCMA. Moreover, we establish the relativization barrier for proving the existence of EFI, noting that no such barrier currently exists within traditional complexity theory. For unconditional cryptography, our framework is the first to capture the notion of unconditional computational hardness, resolving the open problem in [Qia24,MNY24] by constructing an unconditionally secure auxiliary-input quantum commitment scheme with computational binding and statistical hiding. Our framework also has other applications in quantum property testing and unitary synthesis.

Abstract: We study the circuit width problem introduced by Montanaro in the polynomial representation of quantum circuits over the gate set ({H,Z,\mathrm{CZ},\mathrm{CCZ}}). In this framework, a circuit corresponds to a low‑degree polynomial over (\mathbb{F}_2), and the circuit width (w(f)) is the minimum number of qubits among circuits realizing a given polynomial (f). This parameter governs the precision with which a quantum computer can approximate the gap of (f), motivating the complexity of minimizing (w(f)). We prove that deciding whether (w(f)\le k) is NP‑complete, and that approximating (w(f)) within any factor better than (49/48-\epsilon) is NP‑hard. This inapproximability persists even for degree‑2 polynomials, showing that the hardness is gate‑set independent for common quadratic gate sets. On the algorithmic side, we give a nondeterministic polynomial‑time search algorithm with witness size (O(k\log(n/k))), yielding an XP algorithm by enumeration, and a fixed‑parameter tractable algorithm running in time (k^{O(k)}\cdot n). These results resolve Montanaro’s open question and place circuit width firmly within classical complexity theory while providing efficient algorithms for small width.

Abstract: We establish novel connections between magic in quantum circuits and communication complexity. In particular, we show that functions computable with low magic have low communication cost. Our first result shows that the $\Dsim$ (deterministic simultaneous message passing) cost of a Boolean function $f$ is at most the number of single-qubit magic gates in a quantum circuit computing $f$ with any quantum advice state. If we allow mid-circuit measurements and adaptive circuits, we obtain an upper bound on the two-way communication complexity of $f$ in terms of the magic + measurement cost of the circuit for $f$. As an application, we obtain magic-count lower bounds of $\Omega(n)$ for the $n$-qubit generalized Toffoli gate as well as the $n$-qubit quantum multiplexer. Our second result gives a general method to transform $\Qent$ protocols (simultaneous quantum messages with shared entanglement) into $\Rent$ protocols (simultaneous classical messages with shared entanglement) which incurs only a polynomial blowup in the communication and entanglement complexity, provided the referee's action in the $\Qent$ protocol is implementable in constant $T$-depth. The resulting $\Rent$ protocols satisfy strong privacy constraints and are $\PSM^*$ protocols (private simultaneous message passing with shared entanglement), where the referee learns almost nothing about the inputs other than the function value. As an application, we demonstrate $n$-bit partial Boolean functions whose $\Rent$ complexity is $\mathrm{polylog}(n)$ and whose $\R$ (interactive randomized) complexity is $n^{\Omega(1)}$, establishing the first exponential separations between $\Rent$ and $\R$ for Boolean functions.