{
  "id": "quant-ph/0610220",
  "version": "v1",
  "published": "2006-10-26T08:42:13.000Z",
  "updated": "2006-10-26T08:42:13.000Z",
  "title": "De-Quantising the Solution of Deutsch's Problem",
  "authors": [
    "Cristian S. Calude"
  ],
  "comment": "8 pages",
  "categories": [
    "quant-ph"
  ],
  "abstract": "Probably the simplest and most frequently used way to illustrate the power of quantum computing is to solve the so-called {\\it Deutsch's problem}. Consider a Boolean function $f: \\{0,1\\} \\to \\{0,1\\}$ and suppose that we have a (classical) black box to compute it. The problem asks whether $f$ is constant (that is, $f(0) = f(1)$) or balanced ($f(0) \\not= f(1)$). Classically, to solve the problem seems to require the computation of $f(0)$ and $ f(1)$, and then the comparison of results. Is it possible to solve the problem with {\\em only one} query on $f$? In a famous paper published in 1985, Deutsch posed the problem and obtained a ``quantum'' {\\em partial affirmative answer}. In 1998 a complete, probability-one solution was presented by Cleve, Ekert, Macchiavello, and Mosca. Here we will show that the quantum solution can be {\\it de-quantised} to a deterministic simpler solution which is as efficient as the quantum one. The use of ``superposition'', a key ingredient of quantum algorithm, is--in this specific case--classically available.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2006-10-26T08:42:13.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "deutschs problem",
      "deterministic simpler solution",
      "de-quantising",
      "quantum algorithm",
      "quantum solution"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2006quant.ph.10220C"
    }
  }
}