Códigos de repetição

Começaremos a aula com uma discussão sobre códigos de repetição. Os códigos de repetição não protegem informação quântica contra todo tipo de erro que pode ocorrer em qubits, mas formam a base para o código de Shor de 9 qubits, que veremos na próxima aula, e também são úteis para explicar os fundamentos da correção de erros.

Codificação e decodificação clássica

Os códigos de repetição são exemplos extremamente básicos de códigos de correção de erros. A ideia é que podemos proteger bits contra erros simplesmente repetindo cada bit um número fixo de vezes.

Em particular, vamos primeiro considerar o código de repetição de 3 bits, apenas no contexto de informação clássica para começar. Esse código codifica um bit em três repetindo o bit três vezes, então $0$ é codificado como $000$ e $1$ é codificado como $111.$

$$\begin{aligned} 0 & \mapsto 000\\ 1 & \mapsto 111 \end{aligned}$$

Se nada der errado, obviamente podemos distinguir as duas possibilidades para o bit original a partir de suas codificações. O ponto é que se houve um erro e um dos três bits foi invertido — ou seja, um 0 muda para 1 ou um 1 muda para 0 — ainda podemos descobrir qual era o bit original determinando qual dos dois valores binários aparece duas vezes. De forma equivalente, podemos decodificar computando o valor majoritário (ou seja, o valor binário que aparece com maior frequência).

$$a b c \mapsto \operatorname{majority}(a,b,c)$$

Claro, se 2 ou 3 bits da codificação forem invertidos, a decodificação não funcionará corretamente e o bit errado será recuperado, mas se no máximo 1 dos 3 bits for invertido, a decodificação estará correta. Esta é uma propriedade típica dos códigos de correção de erros em geral: eles podem permitir a correção de erros, mas somente se não houver erros em demasia.

Redução de ruído para o canal binário simétrico

Para um exemplo de situação em que as chances de cometer um erro podem ser reduzidas usando um código de repetição, suponha que nosso objetivo seja comunicar um único bit a um receptor hipotético, e que somos capazes de transmitir bits por um chamado canal binário simétrico, que inverte cada bit enviado por ele independentemente com alguma probabilidade $p.$ Ou seja, com probabilidade $1-p,$ o receptor recebe o bit que foi enviado pelo canal, mas com probabilidade $p,$ o bit é invertido e o receptor recebe o valor de bit oposto.

Então, se optarmos por não usar o código de repetição de 3 bits e simplesmente enviar o bit desejado pelo canal, o receptor receberá o bit errado com probabilidade $p.$ Por outro lado, se primeiro codificarmos o bit que queremos enviar usando o código de repetição de 3 bits e depois enviarmos cada um dos três bits da codificação pelo canal, então cada um deles é invertido independentemente com probabilidade $p.$ As chances de uma inversão de bit são agora maiores porque há três bits que podem ser invertidos em vez de um, mas se no máximo um dos bits for invertido, o receptor decodificará corretamente. Um erro persiste após a decodificação, portanto, apenas se dois ou mais bits forem invertidos durante a transmissão.

A probabilidade de dois bits serem invertidos durante a transmissão é $3p^2(1-p),$ que é $p^2(1-p)$ para cada uma das três escolhas para o bit que não é invertido, enquanto a probabilidade de que todos os três bits sejam invertidos é $p^3.$ A probabilidade total de duas ou três inversões de bits é, portanto,

$$3 p^2 (1 - p) + p^3 = 3 p^2 - 2 p^3.$$

Para valores de $p$ menores que um meio, isso resulta em uma diminuição na probabilidade de o receptor terminar com o bit errado. Ainda haverá uma chance de erro nesse caso, mas o código diminui a probabilidade. (Para valores de $p$ maiores que um meio, por outro lado, o código na verdade aumenta a probabilidade de o receptor receber o bit errado.)

Codificando qubits

O código de repetição de 3 bits é um código de correção de erros clássico, mas podemos considerar o que acontece se tentarmos usá-lo para proteger qubits contra erros. Como veremos, não é um código de correção de erros quântico muito impressionante, pois na verdade torna alguns erros mais prováveis. No entanto, é o primeiro passo em direção ao código de Shor e nos servirá bem do ponto de vista pedagógico.

Para ser claro, quando nos referimos ao código de repetição de 3 bits sendo usado para qubits, temos em mente uma codificação de um qubit onde os estados da base padrão são repetidos três vezes, de modo que um vetor de estado de qubit único é codificado da seguinte forma.

$$\alpha \vert 0\rangle + \beta \vert 1\rangle \mapsto \alpha \vert 000\rangle + \beta \vert 111\rangle$$

Essa codificação é facilmente implementada pelo seguinte Circuit quântico, que faz uso de dois qubits de espaço de trabalho inicializados e dois gates CNOT.

Observe, em particular, que essa codificação não é a mesma que repetir o estado quântico três vezes, como em um determinado vetor de estado de qubit sendo codificado como $\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle.$ Tal codificação não pode ser implementada para um estado quântico desconhecido $\vert\psi\rangle$ pelo teorema da não-clonagem.

Erros de inversão de bit

Agora suponha que um erro ocorra após a codificação ter sido realizada. Especificamente, suponha que um gate $X$, ou seja, uma inversão de bit, ocorra em um dos qubits. Por exemplo, se o qubit do meio experimentar uma inversão de bit, o estado dos três qubits é transformado neste estado:

$$\alpha \vert 010\rangle + \beta \vert 101\rangle.$$

Claro, este não é o único tipo de erro que poderia ocorrer — e também é razoável questionar a suposição de que um erro assume a forma de uma operação unitária perfeita. Voltaremos a essas questões na última seção da aula, e por enquanto podemos ver um erro desta forma como sendo apenas um tipo possível de erro (embora fundamentalmente importante).

Podemos ver claramente a partir da expressão matemática para o estado acima que o bit do meio é o que é diferente dentro de cada ket. Mas suponha que tivéssemos os três qubits em nossa posse e não soubéssemos seu estado. Se suspeitarmos que uma inversão de bit pode ter ocorrido, uma opção para verificar que um bit foi invertido seria realizar uma medição na base padrão, que, no caso em questão, nos faria ver $010$ ou $101$ com probabilidades $\vert\alpha\vert^2$ e $\vert\beta\vert^2,$ respectivamente. Em qualquer caso, nossa conclusão seria que o bit do meio foi invertido — mas, infelizmente, perderíamos o estado quântico original $\alpha\vert 0\rangle + \beta \vert 1\rangle.$ Este é o estado que estamos tentando proteger, então medir na base padrão é uma opção insatisfatória.

O que podemos fazer em vez disso é usar o seguinte Circuit quântico, alimentando o estado codificado nos três qubits superiores. Este Circuit mede de forma não-destrutiva a paridade dos estados da base padrão dos dois qubits superiores, bem como dos dois qubits inferiores da codificação de três qubits.

Sob a suposição de que no máximo um bit foi invertido, pode-se deduzir facilmente dos resultados de medição a localização da inversão de bit (ou a ausência de uma). Em particular, como os quatro diagramas de circuito a seguir ilustram, o resultado de medição $00$ indica que nenhuma inversão de bit ocorreu, enquanto as outras três possibilidades indicam qual qubit experimentou uma inversão de bit.

Crucialmente, o estado dos três qubits superiores não colapsa em nenhum dos casos, o que nos permite corrigir um erro de inversão de bit se um tiver ocorrido — simplesmente aplicando a mesma inversão de bit novamente com um gate $X$. A tabela a seguir resume os estados que obtemos com no máximo uma inversão de bit, os resultados de medição (chamados de síndrome no contexto de correção de erros), e a correção necessária para voltar à codificação original.

Estado	Síndrome	Correção
$\alpha\vert 000\rangle + \beta \vert 111\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert 001\rangle + \beta \vert 110\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes X$
$\alpha\vert 010\rangle + \beta \vert 101\rangle$	$11$	$\mathbb{I}\otimes X\otimes\mathbb{I}$
$\alpha\vert 100\rangle + \beta \vert 011\rangle$	$10$	$X\otimes\mathbb{I}\otimes\mathbb{I}$

Mais uma vez, estamos considerando apenas a possibilidade de que no máximo uma inversão de bit ocorreu. Isso não funcionaria corretamente se duas ou três inversões de bit ocorressem, e também não consideramos outros erros possíveis além de inversões de bit.

Erros de inversão de fase

No contexto quântico, os erros de inversão de bit não são os únicos erros com os quais precisamos nos preocupar. Por exemplo, também precisamos nos preocupar com erros de inversão de fase, que são descritos por gates $Z$. Na mesma linha dos erros de inversão de bit, podemos pensar nos erros de inversão de fase como representando apenas outra possibilidade de erro que pode afetar um qubit.

No entanto, como veremos na última seção da aula, que trata da chamada discretização de erros para códigos de correção de erros quânticos, focar em erros de inversão de bit e erros de inversão de fase acaba sendo bem justificado. Especificamente, a capacidade de corrigir um erro de inversão de bit, um erro de inversão de fase, ou ambos simultaneamente implica automaticamente a capacidade de corrigir um erro quântico arbitrário em um único qubit.

Infelizmente, o código de repetição de 3 bits não protege contra inversões de fase de forma alguma. Por exemplo, suponha que um estado de qubit $\alpha\vert 0\rangle + \beta\vert 1\rangle$ tenha sido codificado usando o código de repetição de 3 bits, e um erro de inversão de fase ocorra no qubit do meio. Isso resulta no estado

$$(\mathbb{I} \otimes Z \otimes \mathbb{I}) ( \alpha \vert 000\rangle + \beta \vert 111\rangle) = \alpha \vert 000\rangle - \beta \vert 111\rangle,$$

que é exatamente o estado que teríamos obtido ao codificar o estado de qubit $\alpha\vert 0\rangle - \beta\vert 1\rangle.$ De fato, um erro de inversão de fase em qualquer um dos três qubits da codificação tem o mesmo efeito, que é equivalente a um erro de inversão de fase ocorrendo no qubit original antes da codificação. Sob a suposição de que o estado quântico original é um estado desconhecido, portanto não há como detectar que um erro ocorreu, porque o estado resultante é uma codificação perfeitamente válida de um estado de qubit diferente. Em particular, executar o Circuit de detecção de erros anterior no estado $\alpha \vert 000\rangle - \beta \vert 111\rangle$ certamente resultará na síndrome $00,$ que equivocadamente sugere que nenhum erro ocorreu.

Enquanto isso, agora há três qubits em vez de um que poderiam potencialmente experimentar erros de inversão de fase. Então, em uma situação em que erros de inversão de fase ocorrem independentemente em cada qubit com alguma probabilidade não nula $p$ (semelhante a um canal binário simétrico, exceto para inversões de fase em vez de inversões de bit), esse código na verdade aumenta a probabilidade de um erro de inversão de fase após a decodificação para valores pequenos de $p.$ Para ser mais preciso, obteremos um erro de inversão de fase no qubit original após a decodificação sempre que houver um número ímpar de erros de inversão de fase nos três qubits da codificação, o que acontece com probabilidade

$$3 p (1 - p)^2 + p^3.$$

Este valor é maior que $p$ quando $0<p<1/2,$ portanto o código aumenta a probabilidade de um erro de inversão de fase para valores de $p$ nesse intervalo.

Código de repetição modificado para erros de inversão de fase

Observamos que o código de repetição de 3 bits é completamente alheio a erros de inversão de fase, portanto não parece ser muito útil para lidar com esse tipo de erro. Podemos, no entanto, modificar o código de repetição de 3 bits de uma maneira simples para que ele detecte erros de inversão de fase. Essa modificação tornará o código alheio a erros de inversão de bit — mas, como veremos na próxima seção, podemos combinar o código de repetição de 3 bits com essa versão modificada para obter o código de Shor, que pode corrigir tanto erros de inversão de bit quanto de fase.

Aqui está a versão modificada do Circuit de codificação acima, que agora será capaz de detectar erros de inversão de fase. A modificação é muito simples: simplesmente aplicamos um gate de Hadamard a cada qubit após realizar os dois gates CNOT.

Um gate de Hadamard transforma um estado $\vert 0\rangle$ em um estado $\vert + \rangle$, e um estado $\vert 1\rangle$ em um estado $\vert - \rangle$, de modo que o efeito líquido é que o estado de qubit único $\alpha\vert 0\rangle + \beta \vert 1\rangle$ é codificado como

$$\alpha \vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-} \rangle$$

onde $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ e $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle.$

Um erro de inversão de fase, ou equivalentemente um gate $Z$, inverte entre os estados $\vert + \rangle$ e $\vert - \rangle$, portanto essa codificação será útil para detectar (e corrigir) erros de inversão de fase. Especificamente, o Circuit de detecção de erros anterior pode ser modificado da seguinte forma.

Em palavras, pegamos o Circuit anterior e simplesmente colocamos gates de Hadamard nos três qubits superiores tanto no início quanto no final. A ideia é que os primeiros três gates de Hadamard transformam os estados $\vert + \rangle$ e $\vert - \rangle$ de volta em estados $\vert 0\rangle$ e $\vert 1\rangle$, as mesmas verificações de paridade de antes ocorrem, e então a segunda camada de gates de Hadamard transforma o estado de volta para os estados $\vert + \rangle$ e $\vert - \rangle$ para que recuperemos nossa codificação. Para referência futura, observemos que esse Circuit de detecção de inversão de fase pode ser simplificado da seguinte forma.

Os quatro diagramas de circuito a seguir descrevem como nossa versão modificada do código de repetição de 3 bits, incluindo a etapa de codificação e a etapa de detecção de erros, funciona quando no máximo um erro de inversão de fase ocorre. O comportamento é semelhante ao código de repetição ordinário de 3 bits para inversões de bit.

Aqui está uma tabela análoga à acima, desta vez considerando a possibilidade de no máximo um erro de inversão de fase.

Estado	Síndrome	Correção
$\alpha\vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-}\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert {+}\,{+}\,{-}\rangle + \beta \vert {-}\,{-}\,{+}\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes Z$
$\alpha\vert {+}\,{-}\,{+}\rangle + \beta \vert {-}\,{+}\,{-}\rangle$	$11$	$\mathbb{I}\otimes Z\otimes\mathbb{I}$
$\alpha\vert {-}\,{+}\,{+} \rangle + \beta \vert {+}\,{-}\,{-}\rangle$	$10$	$Z\otimes\mathbb{I}\otimes\mathbb{I}$

Infelizmente, essa versão modificada do código de repetição de 3 bits não consegue mais corrigir erros de inversão de bit. Porém, nem tudo está perdido. Como sugerido anteriormente, seremos capazes de combinar os dois códigos que acabamos de ver em um único código — o código de Shor de 9 qubits — que pode corrigir tanto erros de inversão de bit quanto de fase, e de fato qualquer erro em um único qubit.