Paper 2020/639

Indistinguishability obfuscation for quantum circuits of low T-count

Anne Broadbent and Raza Ali Kazmi

Abstract

An indistinguishability obfuscator is a probabilistic polynomial-time algorithm that takes a circuit as input and outputs a new circuit that has the same functionality as the input circuit, such that for any two circuits of the same size that compute the same function, the outputs of the indistinguishability obfuscator are computationally indistinguishable. Here, we study schemes for indistinguishability obfuscation for quantum circuits ($qi\mathcal{O}$), which consists in a procedure that takes as input a quantum circuit and outputs a quantum state, together with a quantum circuit, which together can be used to evaluate the original quantum circuit on any quantum input; the security guarantee being that for two quantum circuits of the same size that have the same input-output behaviour, the outputs of the obfuscator are computationally indistinguishable. Our main result provides a construction for $qi\mathcal{O}$, where the size of the output of the obfuscator is exponential in the number of non-Clifford (T gates), which means that the construction is efficient as long as the number of T gates is logarithmic in the circuit size.