{
  "id": "2311.12618",
  "version": "v1",
  "published": "2023-11-21T14:03:29.000Z",
  "updated": "2023-11-21T14:03:29.000Z",
  "title": "Limitations of measure-first protocols in quantum machine learning",
  "authors": [
    "Casper Gyurik",
    "Riccardo Molteni",
    "Vedran Dunjko"
  ],
  "comment": "13 pages, 1 figure",
  "categories": [
    "quant-ph"
  ],
  "abstract": "In recent works, much progress has been made with regards to so-called randomized measurement strategies, which include the famous methods of classical shadows and shadow tomography. In such strategies, unknown quantum states are first measured (or ``learned''), to obtain classical data that can be used to later infer (or ``predict'') some desired properties of the quantum states. Even if the used measurement procedure is fixed, surprisingly, estimations of an exponential number of vastly different quantities can be obtained from a polynomial amount of measurement data. This raises the question of just how powerful ``measure-first'' strategies are, and in particular, if all quantum machine learning problems can be solved with a measure-first, analyze-later scheme. This paper explores the potential and limitations of these measure-first protocols in learning from quantum data. We study a natural supervised learning setting where quantum states constitute data points, and the labels stem from an unknown measurement. We examine two types of machine learning protocols: ``measure-first'' protocols, where all the quantum data is first measured using a fixed measurement strategy, and ``fully-quantum'' protocols where the measurements are adapted during the training process. Our main result is a proof of separation. We prove that there exist learning problems that can be efficiently learned by fully-quantum protocols but which require exponential resources for measure-first protocols. Moreover, we show that this separation persists even for quantum data that can be prepared by a polynomial-time quantum process, such as a polynomially-sized quantum circuit. Our proofs combine methods from one-way communication complexity and pseudorandom quantum states. Our result underscores the role of quantum data processing in machine learning and highlights scenarios where quantum advantages appear.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-11-21T14:03:29.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum machine learning",
      "measure-first protocols",
      "quantum data",
      "quantum states constitute data points",
      "limitations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}