¿Algoritmo de Deutsch-Jozsa para funciones no balanceadas + no constantes?

Nota: me imagino que esta será una simple pregunta de sí/no para las personas mejor versadas en este tema que yo, pero sin embargo, proporcionaré un poco de información primero para la edificación de cualquiera que pueda encontrar esto más tarde. Como tal, es posible que desee pasar al final de la pregunta real.

Esencialmente, cualquier texto de introducción a la computación cuántica (por ejemplo, el libro clásico de Nielsen y Chuang ,$\S$1.4.4) incluirá una discusión sobre el algoritmo Deutsch-Jozsa , cuya idea es bastante sencilla. Es (siguiendo aproximadamente a Nielsen y Chuang por conveniencia) una solución al problema de Deutsch :

Problema de Deutsch: Bob tiene un circuito de oráculo (implementando una transformación unitaria)$U_f$que, dada alguna$(n+1)$-entrada de bits$|x\rangle|y\rangle$, da$|x\rangle|y\oplus f(x)\rangle$, con$|x\rangle\equiv|x_1\rangle\cdots|x_n\rangle$, como una salida para alguna función desconocida$\ f:\{0,1\}^n\longrightarrow \{0,1\}$. Esquemáticamente tenemos:

Ahora, supongamos que$f$es constante o balanceada (es decir, la salida es 0 la mitad del tiempo, 1 para la otra mitad). Entonces uno puede preguntar: si Alice vive muy, muy lejos de Bob y quiere enviar a Bob$n+1$bits, que luego los mete en su ingenioso oráculo y le envía los bits resultantes, entonces, ¿cuántas consultas de este tipo tiene que hacer Alice para identificar$f$como constante o balanceada?

En el caso de bit clásico, la respuesta es sencilla: Alice solo puede enviar un valor para$x$a la vez, por lo que necesita al menos$2^{n-1}-1$Consultas para saber qué tipo de$f$están tratando.

En el caso cuántico, podemos utilizar la interferencia y esta pregunta se puede responder utilizando el algoritmo Deutsch-Jozsa, como se mencionó anteriormente. Explícitamente:

Algoritmo de Deutsch-Jozsa: Alice toma$|0\rangle^{\otimes n}|1\rangle$, los mete en la transformación de Hadamard$H^{\otimes(n+1)}$(es decir, aplica una puerta de Hadamard a cada uno de los qubits que se tensan), envía eso a Bob y luego aplica$H^{\otimes n}\otimes \text{Id}$a lo que Bob envía de vuelta. Esquemáticamente se tiene:

Luego se queda con (después de un cálculo breve, vea el libro de N&C para más detalles):

$$|\psi\rangle=\sum_{x,z\in\{0,1\}^n}\frac{(-1)^{x\odot z+f(x)}}{2^n}|z\rangle\left(\frac{|0\rangle-|1\rangle}{\sqrt{2}}\right).$$

Finalmente, se observa que el coeficiente de$|0\rangle^{\otimes n}$estado en la suma anterior es

$$\sum_{x\in\{0,1\}^n}\frac{(-1)^{f(x)}}{2^n}=\left\{ \begin{array}{cr} \pm 1, & f \text{ is constant} \\ 0, & f \text{ is balanced} \end{array} \right.,$$

lo que significa que una medida todos los demás coeficientes son 0 si$f$es constante, y al menos uno de los otros coeficientes es distinto de cero si$f$es equilibrado; por lo tanto, una medida que da como resultado todos$0$Los medios le dicen a Alice que$f$es constante, y cualquier otro resultado significa que$f$está equilibrado. Por lo tanto, Alice solo necesita una única consulta para identificar qué tipo de función se esconde en el oráculo de Bob, ¡una mejora significativa en el caso clásico!

Con todo eso fuera del camino, finalmente podemos llegar a la pregunta:

Pregunta: Me parece que la mayoría de las funciones booleanas como$f$anteriores no son constantes ni equilibrados. El matemático que hay en mí no puede evitar preguntarse: ¿puede este algoritmo realmente permitirle distinguir también entre otras funciones booleanas? ¿Es esta una pregunta interesante para hacer?