dorsal/arxiv
View SchemaDe-Quantising the Solution of Deutsch's Problem
| Authors | Cristian S. Calude |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0610220 |
| URL | https://arxiv.org/abs/quant-ph/0610220 |
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.
{
"annotation_id": "a1ae529c-e0d0-4da7-b4c4-b30683e7b793",
"date_created": "2026-03-02T18:02:31.241000Z",
"date_modified": "2026-03-02T18:02:31.241000Z",
"file_hash": "c08e65be93ad540f0c8c6367ed5b90d0e57dd2b6b56fdc20de98e57632aa3ad7",
"private": false,
"record": {
"abstract": "Probably the simplest and most frequently used way to illustrate the power of\nquantum computing is to solve the so-called {\\it Deutsch\u0027s problem}. Consider a\nBoolean function $f: \\{0,1\\} \\to \\{0,1\\}$ and suppose that we have a\n(classical) black box to compute it. The problem asks whether $f$ is constant\n(that is, $f(0) = f(1)$) or balanced ($f(0) \\not= f(1)$). Classically, to solve\nthe problem seems to require the computation of $f(0)$ and $ f(1)$, and then\nthe comparison of results. Is it possible to solve the problem with {\\em only\none} query on $f$? In a famous paper published in 1985, Deutsch posed the\nproblem and obtained a ``quantum\u0027\u0027 {\\em partial affirmative answer}. In 1998 a\ncomplete, probability-one solution was presented by Cleve, Ekert, Macchiavello,\nand Mosca. Here we will show that the quantum solution can be {\\it\nde-quantised} to a deterministic simpler solution which is as efficient as the\nquantum one. The use of ``superposition\u0027\u0027, a key ingredient of quantum\nalgorithm, is--in this specific case--classically available.",
"arxiv_id": "quant-ph/0610220",
"authors": [
"Cristian S. Calude"
],
"categories": [
"quant-ph"
],
"title": "De-Quantising the Solution of Deutsch\u0027s Problem",
"url": "https://arxiv.org/abs/quant-ph/0610220"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "47acc6d4-864a-40ab-8fc3-d24b18d104a5",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}