On the Complexity of Finding Decoherence Free Subspaces

Resumo Técnico: Sobre a Complexidade de Encontrar Subespaços Livres de Decoerência

Enunciado do Problema
Este artigo investiga a complexidade computacional de determinar se um dado sistema quântico aberto, governado por uma equação mestre de Lindblad independente do tempo, admite um subespaço livre de decoerência (DFS - Decoherence-Free Subspace). Um DFS é definido como um subespaço de estados quânticos puros que permanece estável sob a dinâmica do sistema, preservando não apenas os estados em si, mas também as coerências quânticas entre eles. O autor formaliza esta investigação em problemas de decisão, focando especificamente no problema k-Local Lindbladian Pure Steady-State, que pergunta se um dissipador lindbladiano $k$-local admite um DFS de 1 dimensão (um estado estacionário puro). Eles também introduzem o problema k-Local Lindbladian, que trata da dificuldade de computar taxas de decaimento de pureza sob dinâmicas lindbladianas.

Metodologia
O autor utiliza técnicas de teoria da complexidade quântica, especificamente a classe Quantum Merlin Arthur (QMA), para analisar estes problemas. Sua metodologia envolve vários componentes técnicos fundamentais:

1. Reduções e Definições de Problemas:

   • Eles definem o problema k-Local Lindbladian Pure Steady-State e o problema k-Local Lindbladian.
   • Introduzem uma variante chamada Symmetric Separable k-Local Hamiltonian*, uma modificação do problema Separable k-Local Hamiltonian, para estabelecer a ponte entre os estados estacionários de sistemas abertos e os estados fundamentais de sistemas fechados.
   • Estabelecem reduções entre estes problemas, mostrando que o problema k-Local Lindbladian reduz-se ao Symmetric Separable k-Local Hamiltonian*, colocando o primeiro dentro da classe QMA.

2. Construção de Hardness (Generalização do Relógio de Kitaev):

   • Para provar a QMA-Hardness, o autor generaliza a construção do Hamiltoniano de relógio de Kitaev para o cenário de sistemas quânticos abertos.
   • Eles codificam a execução de um circuito quântico (especificamente, o problema Quantum Circuit-SAT) no subespaço de estado estacionário de um Lindbladian construído.
   • Ao contrário de construções anteriores que resultavam apenas em estados de história mistos, seu mapeamento inovador conduz o sistema para um subespaço estacionário contendo tanto estados de história mistos quanto puros. Isso permite a interpolação entre ambos e é crucial para analisar o decaimento de estados puros.
   • Eles constroem um "Dissipador de Propagação" usando operadores de salto derivados dos termos hamiltonianos da construção de Kitaev. Este dissipador verifica a propagação correta das portas do circuito.
   • Dissipadores adicionais são projetados para verificar a inicialização de qubits ancilares e a saída do circuito. O dissipador de saída é desenhado para misturar o subespaço estacionário se o circuito rejeitar (caso de rejeição) e preservar o subespaço se o circuito aceitar (caso de aceitação).

3. Ferramentas Técnicas:

   • Correspondência Operador-Vetor: Utilizam o isomorfismo entre o espaço de operadores $B(H)$ e o espaço de Hilbert duplicado $H \otimes H$ para mapear o problema de encontrar um estado puro com uma taxa de decaimento específica para o problema de encontrar um estado produto com uma "energia" específica em um espaço duplicado.
   • Lema de Projeção de Decaimento de Estado Puro: Uma generalização do lema de projeção de Kempe et al., adaptada para limitar a taxa de decaimento de estados puros sob dinâmicas de Lindblad. Esta ferramenta permite que o autor projete sua análise em subespaços específicos (como o subespaço do estado de história) enquanto limita o erro introduzido pelo vazamento (leakage).
   • Codificação Unária: Para alcançar localidade constante ($k \ge 5$), eles codificam o registro do relógio do circuito em unário, em vez de binário. Isso requer um novo dissipador Lindbladiano k-Local Hermitiano que estabiliza estados de relógio válidos enquanto garante a hermiticidade em relação ao produto interno de Hilbert-Schmidt.

Principais Contribuições

1. Classificação de Complexidade:

   • O problema k-Local Lindbladian Pure Steady-State é mostrado como sendo QMA1-Hard para $k \ge 5$ constante.
   • O problema k-Local Lindbladian é mostrado como sendo QMA-Complete para $k \ge 5$ constante.
   • O problema Symmetric Separable k-Local Hamiltonian* é mostrado como sendo QMA-Complete para $k \ge 5$ constante.

2. Novos Mapeamentos e Construções:

   • Um mapeamento inovador de circuitos quânticos para dissipadores lindbladianos que admite um subespaço estacionário de estados de história tanto mistos quanto puros.
   • Um novo dissipador Lindbladiano Hermitiano usando codificação unária para estabilizar estados de relógio válidos, garantindo simultaneamente a hermiticidade em relação ao produto interno de Hilbert-Schmidt.
   • Um "Lema de Projeção de Decaimento de Estado Puro" adaptado para sistemas quânticos abertos para analisar taxas de decaimento em subespaços específicos.

Resultos
O artigo demonstra que decidir se um sistema quântico de Markov genérico admite um subespaço livre de decoerência é computacionalmente intratável, mesmo para computadores quânticos, sob a suposição de que $\text{BQP} \neq \text{QMA}$. Especificamente:

• Para $k \ge 5$, determinar a existência de um estado estacionário puro (e, portanto, um DFS de 1 dimensão) é QMA1-Hard.
• Determinar a taxa de decaimento de pureza (o problema k-Local Lindbladian) é QMA-Complete.
• A dificuldade (hardness) mantém-se mesmo quando o Lindbladian é gerado por operadores de salto Hermitianos.

Significância
O autor afirma que seus resultados sugerem que encontrar subespaços livres de decoerência é intratável para a computação quântica. Isso implica que, diferentemente da estrutura de estado fundamental de sistemas fechados, onde podem existir algoritmos eficientes ou aproximações para certas classes, a estrutura de estado estacionário de sistemas abertos apresenta uma barreira computacional fundamental. O artigo destaca que mesmo o problema relaxado de encontrar estados puros de decaimento lento (computar taxas de decaimento de pureza de primeira ordem) permanece intratável.

O trabalho estende o campo da complexidade de Hamiltoniano para sistemas quânticos abertos, estabelecendo uma conexão rigorosa entre a estrutura de estado estacionário de Lindbladianos e a estrutura de estado fundamental de Hamiltonianos locais. O autor observa que, embora seus resultados estabeleçam a dificuldade para $k \ge 5$, a complexidade para localidades menores (ex: $k=2$) permanece uma questão aberta, semelhante ao status do problema do Hamiltoniano 2-Local. Eles concluem que estes resultados de intratabilidade motivam a busca por condições identificáveis de forma mais eficiente que garantam a presença ou ausência de subespaços livres de decoerência em sistemas fisicamente relevantes.