Quantumly controlled measurement, Hermitian conjugation and normalization in matrix-manipulation algorithms

Resumo Técnico: Medição Controlada Quanticamente, Conjugação Hermitiana e Normalização em Algoritmos de Manipulação de Matrizes

Definição do Problema
O artigo aborda três limitações críticas em algoritmos quânticos existentes para manipulação de matrizes (especificamente aqueles baseados na codificação de elementos de matriz nas amplitudes de probabilidade de um estado de superposição pura, como proposto nas Refs. [33–35]):

1. Ineficiência da Pós-Seleção: Os algoritmos atuais dependem da medição de um ancila de um único qubit para filtrar estados "lixo" (garbage states) e selecionar o resultado desejado. Este processo sofre de uma probabilidade de sucesso pequena que diminui polinomialmente ou exponencialmente com a dimensão da matriz. Consequentemente, o algoritmo requer múltiplas execuções para alcançar o resultado desejado, reduzindo severamente a eficiência.
2. Incapacidade de Lidar com a Conjugação Hermitiana: Embora esses algoritmos geralmente lidem com matrizes complexas, operações específicas como a conjugação hermitiana não podem ser realizadas dentro do framework de codificação padrão, restringindo a variedade de manipulações algébricas.
3. Restrições Estritas de Normalização: A codificação de elementos de matriz em um estado quântico puro impõe uma condição de normalização estrita ($\sum |a_{jk}|^2 = 1$). Isso limita o módulo dos elementos da matriz, exigindo um escalonamento específico que pode não ser ideal para todas as aplicações.

Metodologia
Os autores propõem três extensões distintas ao framework de manipulação de matrizes:

1. Medição Controlada Quanticamente (QCM - Quantumly Controlled Measurement):

   • Em vez de uma medição projetiva padrão em um único qubit ancila ($B_1$), os autores introduzem um sistema ancila de dois qubits ($B_1$ e $B_2$).
   • O estado do primeiro qubit ($B_1$) atua como um controle para um operador de medição aplicado ao segundo qubit ($B_2$).
   • Especificamente, se o sistema estiver em uma superposição onde o termo "útil" está emaranhado com $|1\rangle_{B_1}$ e o "lixo" com $|0\rangle_{B_1}$, uma porta C-NOT emaranha $B_1$ com $B_2$. Um operador de medição controlado $W^{(3)}_{B_1B_2} = |1\rangle_{B_1}\langle 1| \otimes M_{B_2} + |0\rangle_{B_1}\langle 0| \otimes I_{B_2}$ é então aplicado.
   • Este mecanismo garante que, se o componente útil existir ($\alpha \neq 0$), a medição em $B_2$ é disparada deterministicamente, colapsando o sistema para o estado desejado sem a falha probabilística associada à pós-seleção padrão.

2. Codificação Separada de Partes Reais e Imaginárias:

   • Para permitir a conjugação hermitiana, os autores propõem codificar as partes reais e imaginárias dos elementos complexos da matriz em dois subespaços ortogonais usando um subsistema adicional de um qubit ($M$).
   • O estado $|0\rangle_M$ rotula a parte real e o estado $|1\rangle_M$ rotula a parte imaginária.
   • A conjugação hermitiana é então realizada via uma operação SWAP nos registros de linha/coluna combinada com uma operação $\sigma_z$ no registro $M$, realizando efetivamente a transposição e a conjugação complexa.

3. Restrição de Normalização Suavizada:

   • Os autores introduzem um qubit auxiliar adicional ($K$) ao esquema de codificação.
   • O estado inicial é modificado para incluir um termo extra com amplitude $b$ associado ao estado $|0\rangle_K$, enquanto os elementos da matriz são associados ao estado $|1\rangle_K$.
   • Isso altera a condição de normalização de uma igualdade ($\sum |a_{jk}|^2 = 1$) para uma desigualdade ($\sum |a_{jk}|^2 \leq 1$), permitindo maior flexibilidade na magnitude dos elementos da matriz.

Principais Contribuições e Resultados

• Implementação em Multiplicação de Matrizes: Os autores integram a QCM e as duas extensões de codificação em um algoritmo de multiplicação de matrizes. Eles demonstram que o algoritmo pode realizar a multiplicação padrão, bem como operações envolvendo conjugados hermitianos (ex: $A^\dagger B$, $A B^\dagger$).
• Construção de Circuitos: Circuitos quânticos detalhados são apresentados para:
  • A sub-rotina QCM.
  • O operador de conjugação hermitiana.
  • O algoritmo de multiplicação de matrizes modificado incorporando as três extensões.
• Análise de Complexidade:
  • Espaço: As modificações requerem apenas um número constante de qubits adicionais (especificamente, quatro qubits adicionais para as extensões de codificação e um para o ancila da QCM no contexto de multiplicação). A complexidade de espaço permanece $O(n)$, onde $N=2^n$ é a dimensão da matriz.
  • Profundidade: A profundidade do circuito permanece $O(n)$. Os autores observam que, embora o tempo de execução total de algoritmos anteriores fosse efetivamente $O(2^n n)$ devido à necessidade de múltiplas execuções para superar baixas probabilidades de sucesso, o algoritmo baseado em QCM alcança o resultado em uma única execução, mantendo a característica de profundidade $O(n)$ do próprio circuito.
• Recuperação de Normalização: Os autores reconhecem que a QCM remove a informação probabilística sobre a constante de normalização $G$ (que anteriormente era derivada da probabilidade de sucesso da medição). Eles propõem um método para medir $G$ probabilisticamente, executando o algoritmo múltiplas vezes para medir a probabilidade do estado auxiliar $|0\rangle_K$, embora isso exija execuções separadas da geração de resultado de disparo único (single-shot).

Significância e Alegações
O artigo alega que a introdução da Medição Controlada Quanticamente (QCM) resolve fundamentalmente o "problema da pós-seleção" inerente aos algoritmos de matriz baseados em medição. Ao substituir a filtragem probabilística de estados lixo por um processo controlado quanticamente determinístico, o algoritmo elimina o overhead exponencial associado a múltiplas execuções.

Os autores enfatizam que a QCM não é meramente uma técnica de amplificação de amplitude (como o algoritmo de Grover), mas um operador distinto que combina controle quântico com medição clássica, oferecendo potencialmente um novo tipo de "controle quântico-clássico".

Além disso, as extensões relativas à conjugação hermitiana e às restrições de normalização relaxadas ampliam a aplicabilidade dos algoritmos de manipulação de matrizes para uma classe mais ampla de matrizes complexas e cenários de codificação de dados. Os autores afirmam que essas modificações podem ser aplicadas não apenas à multiplicação de matrizes, mas também a outros algoritmos discutidos nas Refs. [34, 35], incluindo adição de matrizes, cálculo de determinante, inversão e solucionadores de sistemas lineares, bem como outros algoritmos quânticos baseados em medição.