Quantum advantage for probabilistic one-time programs

Marie-Christine Roehsner, Joshua A. Kettlewell, Tiago B. Batalhão, Joseph F. Fitzsimons, Philip Walther

Published 2017-09-27Version 1

One-time programs, computer programs which self-destruct after being run only once, are a powerful building block in cryptography and would allow for new forms of secure software distribution. However, ideal one-time programs have been proved to be unachievable using either classical or quantum resources. Here we relax the definition of one-time programs to allow some probability of error in the output and show that quantum mechanics offers security advantages over purely classical resources. We introduce a scheme for encoding probabilistic one-time programs as quantum states with prescribed measurement settings, explore their security, and experimentally demonstrate various one-time programs using measurements on single-photon states. These include classical logic gates, computing the parity of a hidden set of bits, and a program to solve Yao's millionaires problem. By combining quantum and classical technology, we demonstrate the quantum techniques to enhance computing capabilities even before full-scale quantum computers are available.