{
  "annotation_id": "c3df2975-65b9-4a18-b546-c29fea6d8cfb",
  "date_created": "2026-03-02T18:02:03.591000Z",
  "date_modified": "2026-03-02T18:02:03.591000Z",
  "file_hash": "173418f736e491a4dfea0335b2faf95fd9018f4516c13cf89d48482af86c78c5",
  "private": false,
  "record": {
    "abstract": "We propose an approach for quantifying a quantum circuit\u0027s quantumness as a\nmeans to understand the nature of quantum algorithmic speedups. Since quantum\ngates that do not preserve the computational basis are necessary for achieving\nquantum speedups, it appears natural to define the quantumness of a quantum\ncircuit using the number of such gates. Intuitively, a reduction in the\nquantumness requires an increase in the amount of classical computation, hence\ngiving a ``quantum and classical tradeoff\u0027\u0027.\n  In this paper we present two results on this direction. The first gives an\nasymptotic answer to the question: ``what is the minimum number of\nnon-basis-preserving gates required to generate a good approximation to a given\nstate\u0027\u0027. This question is the quantum analogy of the following classical\nquestion, ``how many fair coins are needed to generate a given probability\ndistribution\u0027\u0027, which was studied and resolved by Knuth and Yao in 1976. Our\nsecond result shows that any quantum algorithm that solves Grover\u0027s Problem of\nsize n using k queries and l levels of non-basis-preserving gates must have\nk*l=\\Omega(n).",
    "arxiv_id": "quant-ph/0312213",
    "authors": [
      "Yaoyun Shi"
    ],
    "categories": [
      "quant-ph"
    ],
    "doi": "10.1016/j.tcs.2005.03.053",
    "title": "Quantum and Classical Tradeoffs",
    "url": "https://arxiv.org/abs/quant-ph/0312213"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "7f5ed686-0cf4-4f89-b94f-0025429bcc6a",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}