O Exercício 4.29 de Computação Quântica e Informação Quântica de Nielsen e Chuang me deixou perplexo.

Encontre um circuito contendo $O(n^2)$ Toffoli, CNOT e portas de qubit único que implementam uma $C^n(X)$ portão (para $n > 3$), sem qubits de trabalho.

Eu descobri que isso não pode ser feito classicamente .

Eu descobri como fazer isso com $O(2^n)$ portões exponencialmente precisos (aninhe dentro de si a construção de controle duplo a partir de controles únicos e raiz quadrada de operação $n-2$ vezes).

Tentei generalizar a construção acima para acumular uma combinação linear de operações controladas. Por exemplo, se eu tiver 3 controles chamados A e B e C e criar um vetor dos vários casos [0, A, B, C, AB, BC, AC, ABC], então:

• A aplicação de uma operação adiciona incondicionalmente [1, 1, 1, 1, 1, 1, 1, 1]
• Controlar uma operação em A adiciona [0, 1, 0, 0, 1, 1, 0, 1]
• Xorar A em C e controlar uma operação em C (depois desfazer o xor) adicionaria [0, 1, 0, 1, 1, 1, 0, 0]
• Xoring (A e B) em C através de um portão de toffoli e, em seguida, controlar uma operação em C adicionaria [0, 0, 0, 1, 1, 1, 1, 0]

Então eu tentaria adicionar (aplicar uma raiz de X) e subtrair (aplicar raiz quadrada inversa) os vários vetores que posso criar até o resultado sair como [0, 0, 0, 0, 0, 0, 0, 0, N] .

Mas eu continuo batendo em várias paredes, como soluções que acabam com múltiplos grandes (ou seja, os portões que estou usando se tornam exponencialmente precisos, o que eu acho que é um não-não) ou simplesmente não sendo capaz de resolver o sistema devido à interação entre gerando elementos com AND / XOR e resolvendo com + / * como não padrão ou criando números exponenciais de portas.

Quais são algumas outras abordagens para tentar?

Acabei resolvendo isso para $O(n)$portões. Eu escrevi uma trilogia de postagens nele.

1. Construindo notas grandes controladas (classicamente, com uma ancilla)

2. Construindo grandes incrementos (classicamente, com uma ancilla)

3. Usando portões quânticos em vez de ancilla bits

É claro que seria péssimo se você descobrisse isso daqui a vinte anos e meu site estivesse fora do ar por muito tempo; portanto, as etapas básicas seguem uma forma de imagem descrita rapidamente.

1. Bootstrap um Bit Ancilla Emprestável

Use uma raiz quadrada e sua inversa para reduzir o número máximo de controles em um, criando um fio não envolvido para cada operação. Em seguida, remova iterativamente os controles das operações que não são Não e reorganize o cruft que resulta em grandes portões de incremento e portões de fase de qubit único.

2. Use um único bit Ancilla para cortar operações pela metade

Para cada operação grande, use o fio não envolvido como um bit auxiliar emprestado. Use-o para transformar o enorme incremento e os portões não controlados em operações menores, cada uma com aproximadamente metade dos fios não envolvidos. Repita duas vezes, se necessário, para a próxima etapa ter espaço de trabalho suficiente.

3. Use muitos bits Ancilla para concluir

Para cada operação ainda muito grande, pegue emprestados os muitos fios não envolvidos como bits ancilla. Use-os para descer até os portões de Toffoli ou menores.

Essas três etapas vão de um portão totalmente controlado - e não linearmente, a muitos Toffoli, CNOT e qubit único. Existem algumas partes implícitas, como mesclar um controle em um portão de incremento, mas são bem simples.

(Desculpe pelo estilo inconsistente dos diagramas.)