The power of constant-depth quantum circuits of unbounded size

Resumo Técnico: O Poder de Circuitos Quânticos de Profundidade Constante de Tamanho Ilimitado

Enunciado do Problema
O artigo investiga o poder computacional de circuitos quânticos quando as restrições sobre o tamanho do circuito e o espaço ancilar são removidas. Na complexidade clássica, a classe $AC^0$ (circuitos de profundidade constante com portas AND/OR de fan-in ilimitado) não consegue computar paridade. No entanto, se a restrição de tamanho polinomial for levantada, toda função booleana pode ser computada em profundidade constante via construções de Forma Normal Disjuntiva (DNF). Os autores questionam se um fenômeno semelhante ocorre para circuitos quânticos construídos a partir de portas de um único qubit arbitrárias e portas Toffoli generalizadas ($QAC^0$). Especificamente, pode toda operação unitária ser implementada exatamente em profundidade constante se o tamanho do circuito e o número de qubits ancilares forem irrestritos?

Os autores formulam esta investigação através de quatro tarefas progressivamente mais gerais:

1. Computar a pertinência em qualquer conjunto $L \subseteq \{0, 1\}^n$.
2. Implementar qualquer permutação de estados da base computacional.
3. Preparar qualquer estado puro.
4. Implementar qualquer unitária arbitrária em cada estado de entrada.

Metodologia
Os autores empregam uma combinação de construções de circuitos clássicos reversíveis, técnicas clássicas probabilísticas adaptadas ao domínio quântico e protocolos de teletransporte quântico.

• Construções Clássicas Reversíveis: Os autores estabelecem primeiro que permutações arbitrárias de strings de bits podem ser implementadas em profundidade constante usando portas Toffoli e fanout. Isso é alcançado via um esquema de "codificação de indicador": a entrada é mapeada para um vetor indicador de dimensão $2^n$ (onde exatamente uma entrada é 1), manipulado, e então decodificado de volta para a string original. Isso permite a avaliação paralela de todas as possíveis strings de entrada.
• Adaptação Probabilística para o Quântico: Para preparar distribuições de probabilidade arbitrárias e estados puros, os autores adaptam uma construção clássica probabilística. Isso envolve amostrar bits independentemente para codificar uma distribuição baseada na posição do primeiro '1'. No cenário quântico, isso é tornado coerente aplicando rotações inversas aos qubits seguindo o primeiro '1' para retornar ao estado $|0\rangle$ sem destruir a superposição.
• Extensões do Conjunto de Portas: Embora o conjunto de portas primário inclua portas de um único qubit e portas Toffoli generalizadas, os autores utilizam portas fanout como uma ferramenta conceitual. Eles citam resultados de Grier, Morris e Wu [GMW26] e Rosenthal [Ros20] para mostrar que o fanout pode ser implementado exatamente em profundidade constante usando apenas o conjunto de portas primário, embora com um potencial aumento no tamanho do circuito para limites duplamente exponenciais.
• Reduções para Unitárias: Para a implementação de unitárias arbitrárias, os autores não fornecem uma construção direta. Em vez disso, oferecem várias formulações equivalentes e reduções. Estas incluem reduzir a implementação de unitárias para:
  • Clonar vetores de uma base ortonormal especificada.
  • Permutar listas de vetores de base.
  • Decodificar rótulos de base.
  • Implementar unitárias com somas de linha e coluna unitárias (via a forma normal de Idel-Wolf).
  • Implementar involuções unitárias traço-nulas (usando um qubit limpo adicional).
• Teletransporte Baseado em Portas (PBT): Para se aproximar da implementação de unitárias arbitrárias sem correções unitárias dependentes da porta específica, os autores utilizam o Teletransporte Baseado em Portas (PBT). Eles constroem um circuito unitário que realiza PBT usando estados maximamente emaranhados (ou estados de Choi da unitária alvo) e uma medição conjunta, seguido pela seleção de porta.

Contribuições Principais e Resultados

1. Construções de Profundidade Constante Exatas para Tarefas Específicas:

   • Permutações: Permutações arbitrárias de strings de bits podem ser implementadas em profundidade constante (profundidade $\le 20$) usando $O(n2^n)$ portas e qubits ancilares.
   • Unitárias Diagonais: Unitárias diagonais arbitrárias podem ser implementadas em profundidade constante (profundidade 7) computando indicadores, aplicando fases em paralelo e descomputando.
   • Preparação de Estado: Estados puros arbitrários podem ser preparados em profundidade constante (profundidade $\le 37$) usando $O(4^n)$ qubits e $O(n2^n)$ portas. Todos os qubits ancilares são retornados a zero.
   • Implementação de Fanout: O fanout pode ser implementado exatamente em profundidade constante usando apenas portas de um único qubit e portas Toffoli generalizadas, embora isso possa exigir um tamanho duplamente exponencial.

2. Reduções para Unitárias Arbitrárias:
   O artigo demonstra que implementar unitárias arbitrárias em profundidade constante é equivalente a implementar qualquer uma de várias operações específicas (por exemplo, clonar vetores de base, decodificar rótulos ou implementar involuções traço-nulas). Isso recontextualiza o problema aberto da implementação de unitárias arbitrárias em um conjunto de desafios estruturais equivalentes.

3. Medições Adaptativas e Teletransporte de Portas:
   Os autores mostram que, se medições intermediárias adaptativas forem permitidas, qualquer porta no nível $\ell$ da hierarquia de Clifford pode ser implementada com profundidade $O(\ell)$. Além disso, a implementação de uma unitária arbitrária reduz-se à implementação de involuções unitárias traço-nulas neste modelo adaptativo.

4. Aproximação por Teletransporte Baseado em Portas (PBT):
   Os autores constroem um circuito unitário para o Teletransporte Baseado em Portas (PBT) para uma dimensão de entrada $d$ e $M \ge d^2 - 1$ portas.

   • Profundidade: O circuito tem profundidade $O(\sqrt{d})$, que é independente do número de portas $M$.
   • Fidelidade: A fidelidade de emaranhamento é limitada por $F_e \ge (1 - \frac{d^2-1}{2M})^2$.
   • Precisão vs. Profundidade: Para qualquer dimensão de entrada $d$ fixa, a aproximação pode ser tornada arbitrariamente precisa aumentando $M$ sem aumentar a profundidade do circuito. No entanto, a dependência da dimensão de entrada $d$ permanece; se um limite de profundidade independente de $d$ pode ser alcançado continua sendo uma questão aberta.
   • Implementação: O circuito utiliza apenas portas de um único qubit e portas Toffoli generalizadas e não requer medições intermediárias.

Significância e Alegações
O artigo estabelece que remover as restrições de tamanho e espaço ancilar permite que circuitos quânticos de profundidade constante realizem tarefas que são geralmente impossíveis em modelos de tamanho polinomial de profundidade constante, como preparação de estado arbitrária e permutação de estados de base. Isso conecta a preparação de estado quântico diretamente à computação clássica reversível e à preparação de distribuições de probabilidade.

No entanto, o artigo mantém uma postura modesta em relação à implementação de unitárias arbitrárias. Embora forneça construções exatas de profundidade constante para permutações, unitárias diagonais e preparação de estado, a implementação de unitárias gerais permanece um problema aberto. Os autores fornecem caracterizações equivalentes deste problema, mas não o resolvem.

A principal contribuição em relação às unitárias gerais é a construção de PBT. Os autores demonstram que, para qualquer dimensão de entrada fixa, unitárias arbitrárias podem ser aproximadas com precisão arbitrária sem aumentar a profundidade do circuito ao aumentar o número de portas. Contudo, a profundidade desta construção escala como $O(\sqrt{d})$ com a dimensão de entrada $d$. Os autores explicitamente afirmam que se essa dependência de $d$ pode ser removida (ou seja, alcançar um limite de profundidade independente de $d$) permanece uma questão aberta. O trabalho destaca que a dificuldade fundamental na implementação de unitárias em profundidade constante não reside em produzir um resultado arbitrário a partir de uma entrada fixa, mas em prescrever a ação sobre cada estado de entrada simultaneamente, preservando a unitariedade.