Identification of a given Boolean function with a mixed-state NMR quantum computer (Mathematical Study of Quantum Dynamical Systems and Its Application to Quantum Computer)
Hiroshi Ozawa · Institutional Repositories DataBase (IRDB) · 2004
\prime \mathrm{J}\backslash \grave{\grave{;}}\ovalbox{\tt\small REJECT} \mu_{\mathrm{A}} \ovalbox{\tt\small REJECT}\overline{7\backslash },\star^{\mathrm{R}^{\backslash }}- eq'\ovalbox{\tt\small REJECT}\Phi\ovalbox{\tt\small REJECT}\Phi^{\tau}\mathrm{k}\backslash \vee earrow$ 5 Any given Boolean function $f(x)\in$ {0, 1}, x $=1,$ \ldots , $2^{n}$ -1, is identifified with n queries to the oracle which evaluates f with an n-spin mixed-state nuclear magnetic resonance (NMR) quantum computer.This means that the database searching problem to fifind x for which $f(x)=1$ is solved with an exponential speedup, compared to classical methods.The procedure is a physical imple- mentation of the probabilistic ensemble computer model, where the uniformly random input is realized by the mixed state of superpositions, to which function f is efficiently applied using quantum parallelism, and the exact probability of the output is certified by the ensemble averaging.