{
  "id": "1709.09724",
  "version": "v1",
  "published": "2017-09-27T20:21:37.000Z",
  "updated": "2017-09-27T20:21:37.000Z",
  "title": "Quantum advantage for probabilistic one-time programs",
  "authors": [
    "Marie-Christine Roehsner",
    "Joshua A. Kettlewell",
    "Tiago B. Batalhão",
    "Joseph F. Fitzsimons",
    "Philip Walther"
  ],
  "categories": [
    "quant-ph"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-09-27T20:21:37.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum advantage",
      "quantum mechanics offers security advantages",
      "full-scale quantum computers",
      "yaos millionaires problem",
      "encoding probabilistic one-time programs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}