Equivalence of non-local computation tasks beyond Clifford operations

Resumo Técnico: Equivalência de Tarefas de Computação Não Local Além de Operações de Clifford

Declaração do Problema
A computação quântica não local (NLQC) investiga como duas partes espacialmente separadas, Alice e Bob, podem implementar um canal quântico conjunto em sistemas distribuídos usando apenas uma única rodada simultânea de comunicação quântica e emaranhamento compartilhado. Embora se saiba que qualquer canal quântico pode ser implementado via NLQC, o custo de recursos — especificamente a quantidade de emaranhamento pré-compartilhado necessária — varia significativamente entre diferentes tarefas.

Uma motivação primária para o estudo da NLQC é sua aplicação em Verificação de Posição Quântica (QPV). Na QPV, um provador tenta convencer verificadores de sua localização física. Um provador trapaceiro, localizado em outro lugar, deve simular as operações locais do provador honesto usando NLQC. A segurança de um esquema de QPV depende da dificuldade da tarefa de NLQC: se um provador trapaceiro exigir uma quantidade exponencialmente grande de emaranhamento para simular a tarefa, o esquema é considerado seguro.

O problema central abordado neste trabalho é a falta de uma compreensão unificada da dificuldade relativa de diferentes tarefas de NLQC. Especificamente, embora a tarefa de "f-routing" (roteamento de um sistema quântico controlado classicamente) tenha sido extensivamente estudada, não está claro se outras protocolos de QPV plausíveis — particularmente aqueles envolvendo medições quânticas controladas ou unitárias além do simples roteamento — oferecem segurança melhorada. Os autores visam determinar se essas tarefas aparentemente distintas são redutíveis umas às outras, estabelecendo assim se elas compartilham o mesmo custo assintótico de emaranhamento.

Metodologia
Os autores empregam um framework de reduções entre famílias de tarefas de NLQC, análogas a reduções na teoria da complexidade computacional. Eles definem dois tipos de reduções:

1. Redução de Estado de Recurso: Uma tarefa $G$ reduz-se a uma tarefa $F$ se $G$ puder ser implementada usando um pequeno número de cópias do estado de recurso necessário para $F$.
2. Redução de Oráculo: Uma tarefa $G$ reduz-se a uma tarefa $F$ se $G$ puder ser implementada usando um pequeno número de chamadas a um oráculo de caixa-preta que implementa $F$, além de operações locais e uma pequena quantidade de recursos compartilhados adicionais.

O artigo foca em tarefas de 2→2 controladas por $f$, onde a operação realizada depende do valor de uma função booleana $f(x, y)$ dada a Alice ($x$) e Bob ($y$). Os sistemas de entrada são tipicamente de tamanho constante ($O(1)$ qubits), enquanto as entradas clássicas podem ser grandes ($n$ bits).

A abordagem técnica envolve:

• Teletransporte de Portão e Computação Quântica Baseada em Medição (MBQC): Os autores utilizam gadgets inspirados em teletransporte de portão e MBQC não adaptativo para construir protocolos que transformam uma tarefa de NLQC em outra.
• Caracterização e Manipulação de Ângulos: Para medições de um único qubit, os autores caracterizam as tarefas por ângulos de rotação na esfera de Bloch. Eles desenvolvem técnicas para adicionar, dividir e aproximar esses ângulos usando combinações de protocolos mais simples (por exemplo, combinando protocolos de $f$-medição com ângulos $\theta_1$ e $\theta_2$ para simular $\theta_1 + \theta_2$).
• Teletransporte Baseado em Portas (Port-Based Teleportation): Utilizado nos apêndices para demonstrar que a distribuição espacial dos inputs quânticos (seja do lado de Alice, do lado de Bob ou dividida) não altera significativamente a dificuldade da tarefa, desde que o tamanho da entrada seja constante.

Principais Contribções e Resultados

1. Equivalência de Protocolos de $f$-Medição de Um Único Qubit:
   Os autores provam que todos os protocolos de $f$-medição de um único qubit não triviais (onde a base de medição é escolhida entre duas bases arbitrárias $U$ e $V$ baseadas em $f(x,y)$) são equivalentes sob reduções de oráculo $O(1)$.

   • Especificamente, qualquer $f$-medida($U, V$) pode ser reduzida ao caso canônico $f$-medida($I, H$) (medição nas bases computacional ou Hadamard).
   • Isso implica que nenhum protocolo de medição projetiva de um único qubit oferece vantagem de segurança sobre o caso mais simples, pois todos herdam os mesmos limites superiores de emaranhamento subexponenciais conhecidos para $f$-routing.

2. Redução de Unitárias de Clifford Controladas:
   O artigo demonstra que unitárias de Clifford controladas por $f$ e medições em bases relacionadas a Clifford podem ser reduzidas a $f$-medida($I, H$).

   • Ao estabelecer uma equivalência entre $f$-medida($I, H$) e $f$-medida de Bell (medição na base de Bell), os autores mostram que operações de Clifford controladas podem ser implementadas via estratégias de teletransporte de portão usando oráculos de $f$-Bell.
   • Isso estende a classe de tarefas redutíveis ao $f$-routing, confirmando que mesmo operações de Clifford de múltiplos qubits não exigem inerentemente mais emaranhamento do que a tarefa básica de roteamento.

3. Extensão para Unitárias Diagonais Controladas:
   Um resultado significativo é a redução de unitárias controladas por $f$ da forma $U = C_1 D C_0$, onde $C_0, C_1$ são circuitos de Clifford e $D$ é uma unitária diagonal arbitrária.

   • Os autores mostram que $f$-unitária($I, U$) pode ser reduzida por oráculo a $f$-medida($I, H$) com overhead de $O(n_Q)$ (onde $n_Q$ é o número de qubits).
   • Isso é surpreendente porque $D$ pode ter uma profundidade T alta, tornando $U$ altamente não-Clifford. No entanto, o custo de implementação permanece vinculado à tarefa de $f$-medida baseada em Clifford mais simples.
   • A construção baseia-se em "gadgets de injeção de rotação-Z" que relacionam rotações-X controladas de um único qubit (implementáveis via $f$-medida) a rotações-Z de múltiplos qubits via portas CZ.

Significância e Alegações
O artigo alega que o panorama de protocolos de QPV viáveis é mais restrito do que se pensava anteriormente. Ao estabelecer uma rica estrutura de reduções, os autores demonstram que:

• Limitações de Segurança: Muitos esquemas de QPV propostos envolvendo medições controladas de um único qubit, operações de Clifford e até certas unitárias diagonais não-Clifford não oferecem segurança melhorada sobre a tarefa básica de $f$-routing. Todos compartilham a mesma escala assintótica para o custo de emaranhamento (subexponencial em relação ao tamanho da entrada clássica).
• Dificuldade Unificada: A dificuldade relativa dessas tarefas é unificada; se um ataque subexponencial existe para $f$-routing, ele se estende a essas classes mais amplas de tarefas através das reduções estabelecidas.
• Avanço de Técnica: O trabalho introduz novas estratégias para NLQC, como gadgets específicos de teletransporte de portão e técnicas de divisão de ângulos, que podem ser de interesse independente para a construção de limites superiores de custos de emaranhamento para outras tarefas de NLQC.

Os autores permanecem modestos quanto ao escopo desses resultados, observando que, embora cubram uma ampla classe de protocolos "viáveis" (grande entrada clássica, pequena entrada quântica), permanece uma questão em aberto se duas camadas de portas diagonais ou outras estruturas unitárias mais complexas poderiam fornecer níveis de segurança mais altos que evitem essas reduções. Os resultados não pretendem provar limites inferiores superlineares, mas sim esclarecer que muitas extensões intuitivas de $f$-routing não escapam dos limites superiores conhecidos.