Posterior: Algoritmo de Deutsch-Jozsa Arriba: Nociones básicas de Computación Anterior: Compuertas cuánticas

Evaluación de funciones booleanas

Sea $V=\{0,1\}$ el conjunto de valores de verdad clásicos. Obviamente hay $2^{2^n}$ funciones booleanas $V^n\to V$ y hay $2^{n2^n}$ funciones $V^n\to V^n$. Cada una de las $2^n$ asignaciones $\mbox{\boldmath$\varepsilon$}=(\varepsilon_{n-1},\ldots,\varepsilon_{1},\varepsilon_{0})\in V^n$ se puede poner en correspondencia con el vector $\mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}}\in\mathbb{H}_n$ de la base ``canónica'' de $\mathbb{H}_n$. Sea $U$ una matriz permutación de orden $2^{n+1}\times 2^{n+1}$ tal que $U(\mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}}\otimes \mbox{\bf e}_{... ...arepsilon$}}\otimes \mbox{\bf e}_{f(\mbox{\scriptsize\boldmath$\varepsilon$})})$. $U$ es pues unitaria. Sea $A\subset V^n$ un conjunto no-vacío de asignaciones y sea $a=\mbox{card}(A)$ su cardinalidad. Al considerar el estado $\mbox{\bf u}_A=\frac{1}{\sqrt{a}}\sum_{\mbox{\scriptsize\boldmath$\varepsilon$}... ...scriptsize\boldmath$\varepsilon$}}\otimes \mbox{\bf e}_{\mbox{\scriptsize\bf0}}$ se tiene $U(\mbox{\bf u}_A)=\frac{1}{\sqrt{a}}\sum_{\mbox{\scriptsize\boldmath$\varepsilo... ...varepsilon$}}\otimes \mbox{\bf e}_{f(\mbox{\scriptsize\boldmath$\varepsilon$})}$ y así en un solo paso de cómputo se calcula a un promedio ponderado de la imagen de las asignaciones con índice en $A$. El proceso final de medición consiste en la selección de una pareja $\mbox{\bf e}_{\mbox{\scriptsize\boldmath$\varepsilon$}}\otimes \mbox{\bf e}_{f(\mbox{\scriptsize\boldmath$\varepsilon$})}$, $\mbox{\boldmath$\varepsilon$}\in A$, cada una con probabilidad $\frac{1}{a}$.