El ejercicio 4.29 de Computación cuántica e información cuántica de Nielsen y Chuang me tiene perplejo.
Encuentre un circuito que contenga Toffoli, CNOT y compuertas qubit simples que implemente una compuerta (para ), sin utilizar qubits de trabajo.
He descubierto que esto no se puede hacer de manera clásica .
He descubierto cómo hacerlo con compuertas exponencialmente precisas (anidan la construcción de doble control desde controles simples y raíz de operación cuadrada dentro de sí mismo veces).
He intentado generalizar la construcción anterior para acumular una combinación lineal de operaciones controladas. Por ejemplo, si tengo 3 controles llamados A y B y C y hago un vector de los diversos casos [0, A, B, C, AB, BC, AC, ABC] entonces:
- La aplicación de una operación agrega incondicionalmente [1, 1, 1, 1, 1, 1, 1, 1]
- Controlar una operación en A agrega [0, 1, 0, 0, 1, 1, 0, 1]
- Xoring A en C y luego controlar una operación en C (luego deshacer el xor) agregaría [0, 1, 0, 1, 1, 1, 0, 0]
- Xoring (A y B) en C a través de una puerta toffoli y luego controlar una operación en C agregaría [0, 0, 0, 1, 1, 1, 1, 0]
Entonces trataría de sumar (aplicar una raíz de X) y restar (aplicar raíz cuadrada inversa) los diversos vectores que puedo hacer hasta que el resultado salga como [0, 0, 0, 0, 0, 0, 0, N] .
Pero sigo golpeando varios muros, como las soluciones que terminan con grandes múltiplos (es decir, las puertas que estoy usando se vuelven exponencialmente precisas, lo que creo que es un no-no) o simplemente no puedo resolver el sistema debido a la interacción entre generando elementos con AND / XOR y luego resolviendo con + / * siendo no estándar o creando números exponenciales de puertas.
¿Cuáles son algunos otros enfoques para probar?
fuente