Statistical Zero Knowledge Problems Inspire Novel Classification Tasks for the Quantum Kernel Support Vector Machine

In a seminal result, Liu et al. recently showed that the Quantum Kernel Estimation Support Vector Machine (QKE-SVM) provably outperforms all classical models on a classification task that reduces to the famous discrete logarithm problem [1]. This raises a question: are there other such learning problems? To this end, we present a new classification task reducible to order-finding that is able to be efficiently learned by the QKE-SVM. We additionally outline the conditions under which learning this task would be classically intractable. Our approach relies on a three-part framework that is centered on the class of Statistical Zero Knowledge (SZK) promise problems whose instances have the curious property of being separable by a hyperplane within some quantum Hilbert space. We show that if a quantum computer can efficiently map into this space for a given SZK-based classification task, then that task is efficiently learnable by the QKE-SVM. Such an efficient mapping typically requires efficiently uncomputing the index of a one-way function in a procedure known as index erasure. Notably, our order-finding classification task is able to bypass the requirement for index erasure as it belongs to a version of SZK in which the verifier has access to a quantum computer.

[1] Y. Liu, S. Arunachalam, and K. Temme, A rigorous and robust quantum speed-up in supervised machine learning, Nature Physics 17, 1013 (2021).