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 myste
rious, and a better understanding of its hardness can have surprising implications to many fields in computer science. We first define and investigate the basic complexity-theoretic properties of minimum quantum circuit size problems for three natural objects: Boolean functions, unitaries, and quantum states. We show that these problems are not trivially in NP but in QCMA (or have QCMA protocols). Next, we explore the relations between the three quantum MCSPs and their variants. We discover that some reductions that are not known for classical MCSP exist for quantum MCSPs for unitaries and states, e.g., search-to-decision reduction and self-reduction. Finally, we systematically generalize results known for classical MCSP to the quantum setting (including quantum cryptography, quantum learning theory, quantum circuit lower bounds, and quantum fine-grained complexity) and also find new connections to tomography and quantum gravity. Due to the fundamental differences between classical and quantum circuits, most of our results require extra care and reveal properties and phenomena unique to the quantum setting. Our findings could be of interest for future studies, and we post several open problems for further exploration along this direction.
With the increasing popularity of the Internet of Things(IoT) devices, the demand for fast and convenient battery charging services grows rapidly. Wireless charging is a promising technology for such a purpose and its usage has become ubiquitous. How
ever, the close distance between the charger and the device being charged not only makes proximity-based and near field communication attacks possible, but also introduces a new type of vulnerabilities. In this paper, we propose to create fingerprints for wireless chargers based on the intrinsic non-linear distortion effects of the underlying charging circuit. Using such fingerprints, we design the WirelessID system to detect potential short-range malicious wireless charging attacks. WirelessID collects signals in the standby state of the charging process and sends them to a trusted server, which can extract the fingerprint and then identify the charger.
Covert communication prevents legitimate transmission from being detected by a warden while maintaining certain covert rate at the intended user. Prior works have considered the design of covert communication over conventional low-frequency bands, bu
t few works so far have explored the higher-frequency millimeter-wave (mmWave) spectrum. The directional nature of mmWave communication makes it attractive for covert transmission. However, how to establish such directional link in a covert manner in the first place remains as a significant challenge. In this paper, we consider a covert mmWave communication system, where legitimate parties Alice and Bob adopt beam training approach for directional link establishment. Accounting for the training overhead, we develop a new design framework that jointly optimizes beam training duration, training power and data transmission power to maximize the effective throughput of Alice-Bob link while ensuring the covertness constraint at warden Willie is met. We further propose a dual-decomposition successive convex approximation algorithm to solve the problem efficiently. Numerical studies demonstrate interesting tradeoff among the key design parameters considered and also the necessity of joint design of beam training and data transmission for covert mmWave communication.
In the universal blind quantum computation problem, a client wants to make use of a single quantum server to evaluate $C|0rangle$ where $C$ is an arbitrary quantum circuit while keeping $C$ secret. The clients goal is to use as few resources as possi
ble. This problem, first raised by Broadbent, Fitzsimons and Kashefi [FOCS09, arXiv:0807.4154], has become fundamental to the study of quantum cryptography, not only because of its own importance, but also because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification). Known protocols on this problem are mainly either information-theoretically (IT) secure or based on trapdoor assumptions (public key encryptions). In this paper we study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of universal blind quantum computation. We give a new universal blind quantum computation protocol. Similar to previous works on IT-secure protocols (for example, BFK [FOCS09, arXiv:0807.4154]), our protocol can be divided into two phases. In the first phase the client prepares some quantum gadgets with relatively simple quantum gates and sends them to the server, and in the second phase the client is entirely classical -- it does not even need quantum storage. Crucially, the protocols first phase is succinct, that is, its complexity is independent of the circuit size. Given the security parameter $kappa$, its complexity is only a fixed polynomial of $kappa$, and can be used to evaluate any circuit (or several circuits) of size up to a subexponential of $kappa$. In contrast, known schemes either require the client to perform quantum computations that scale with the size of the circuit [FOCS09, arXiv:0807.4154], or require trapdoor assumptions [Mahadev, FOCS18, arXiv:1708.02130].
