De-Quantising the Solution of Deutsch's Problem
| dc.creator | Calude, Cristian S. | |
| dc.date | 2006-10-26 | |
| dc.date.accessioned | 2026-07-07T07:34:02Z | |
| dc.date.available | 2026-07-07T07:34:02Z | |
| dc.description | 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. | |
| dc.description | 8 pages | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0610220 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0610220 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/119671 | |
| dc.subject | Quantum Physics | |
| dc.title | De-Quantising the Solution of Deutsch's Problem | |
| dc.type | text |