Correção de ErrosError Correction

IntroduçãoIntroduction

Na computação clássica, se se quer proteger um pouco contra erros, muitas vezes pode ser suficiente para representar isso um pouco por um pouco lógico repetindo a parte dos dados.In classical computing, if one wants to protect a bit against errors, it can often suffice to represent that bit by a logical bit by repeating the data bit. Por exemplo, deixe $\overline {0} = 000$ ser a codificação do bit de dados 0, onde usamos a linha acima da etiqueta 0 para indicar que é uma codificação de um pouco no estado 0.For instance, let $\overline{0} = 000$ be the encoding of the data bit 0, where we use the a line above the label 0 to indicate that it is an encoding of a bit in the 0 state. Se também deixarmos $\overline {1} = 111$, então temos um simples código de repetição que protege contra qualquer erro de lançamento de um bit.If we similarly let $\overline{1} = 111$, then we have a simple repetition code that protects against any one bit flip error. Ou seja, se alguma das três partes for virada, então podemos recuperar o estado da parte lógica, votando por maioria.That is, if any of the three bits are flipped, then we can recover the state of the logical bit by taking a majority vote. Embora a correção clássica de erros seja um assunto muito mais rico que este exemplo em particular (recomendamos a introdução de Lint à teoria da codificação),o código de repetição acima já aponta para um possível problema na proteção da informação quântica.Though classical error correction is a much richer subject that this particular example (we recommend Lint's introduction to coding theory), the repetition code above already points to a possible problem in protecting quantum information. Ou seja, o teorema da não clonagem implica que, se medirmos cada qubit individual e tivermos uma votação maioritária por analogia ao código clássico acima, perdemos a informação precisa que estamos a tentar proteger.Namely, the no-cloning theorem implies that if we measure each individual qubit and take a majority vote by analogy to classical code above, then we have lost the precise information that we are trying to protect.

No cenário quântico, veremos que a medição é problemática.In the quantum setting, we will see that the measurement is problematic. Ainda podemos implementar a codificação acima.We can still implement the encoding above. É útil fazê-lo para ver como podemos generalizar a correção de erros no caso quântico.It is helpful to do so to see how we can generalize error correction to the quantum case. Assim, deixe $\ket{\overline {0} } = \ket {000} = \ket {0} \otimes \ket {0} \otimes \ket \ket {0} \ket $, e let $\ket{\overline {1} } = \ket {111} $.Thus, let $\ket{\overline{0}} = \ket{000} = \ket{0} \otimes \ket{0} \otimes \ket{0}$, and let $\ket{\overline{1}} = \ket{111}$. Então, por linearidade, definimos o nosso código de repetição para todas as entradas; por exemplo, $\ket{\overline{+}} = (\ket{\overline {0} } + \ket{\overline {1} }) / \sqrt {2} = {000} (\ket + \ket) {111} / \sqrt {2} $.Then, by linearity, we have defined our repetition code for all inputs; for instance, $\ket{\overline{+}} = (\ket{\overline{0}} + \ket{\overline{1}}) / \sqrt{2} = (\ket{000} + \ket{111}) / \sqrt{2}$. Em particular, deixando um erro de flip-flip $X_1$ agir no qubit médio, vemos que a correção necessária em ambos os ramos é precisamente $X_1$: $$ \start{align} X_1 \ket{\overline{+}} & = \frac {1} {\sqrt {2} } \X_1 \ket {000} + X_1 \ket {111} \ket \right) \ \ & = \frac {1} {sqrt {2} } \ket {010} {101}In particular, letting a bit-flip error $X_1$ act on the middle qubit, we see that the correction needed in both branches is precisely $X_1$: $$ \begin{align} X_1 \ket{\overline{+}} & = \frac{1}{\sqrt{2}} \left( X_1 \ket{000} + X_1 \ket{111} \right) \\ & = \frac{1}{\sqrt{2}} \left( \ket{010} + \ket{101} \right). \end{align} $$\end{align} $$

Para ver como podemos identificar que este é o caso sem medir o próprio estado que estamos a tentar proteger, é útil escrever o que cada erro de viragem de bits diferentes faz aos nossos estados lógicos:To see how we can identify that this is the case without measuring the very state we are trying to protect, it is helpful to write down what each different bit flip error does to our logical states:

Erro $E$Error $E$ $E\ket{\overline {0} }$$E\ket{\overline{0}}$ $E\ket{\overline {1} }$$E\ket{\overline{1}}$
$\boldone$$\boldone$ $\ket {000} $$\ket{000}$ $\ket {111} $$\ket{111}$
$X_0$$X_0$ $\ket {100} $$\ket{100}$ $\ket {011} $$\ket{011}$
$X_1$$X_1$ $\ket {010} $$\ket{010}$ $\ket {101} $$\ket{101}$
$X_2$$X_2$ $\ket {001} $$\ket{001}$ $\ket {110} $$\ket{110}$

Para proteger o estado que estamos codificando, precisamos ser capazes de distinguir os três erros uns dos outros e da identidade $\boldone$ sem distinguir entre $\ket\overline {0} }$ e $\ket{\overline {1} }$.In order to protect the state that we're encoding, we need to be able to distinguish the three errors from each other and from the identity $\boldone$ without distinguishing between $\ket{\overline{0}}$ and $\ket{\overline{1}}$. Por exemplo, se medirmos $Z_0$, obtemos um resultado diferente por $\ket{\overline {0} }$ e $\ket{\overline {1} }$ na caixa sem erro, de modo que colapsa o estado codificado.For example, if we measure $Z_0$, we get a different result for $\ket{\overline{0}}$ and $\ket{\overline{1}}$ in the no-error case, so that collapses the encoded state. Por outro lado, considere medir $Z_0 Z_1$, a paridade dos dois primeiros bits em cada estado de base computacional.On the other hand, consider measuring $Z_0 Z_1$, the parity of the first two bits in each computational basis state. Lembre-se que cada medição de um operador Pauli verifica qual o valor do estado que está a ser medido corresponde, de modo que para cada estado $\ket{\psi}$ na tabela acima, podemos calcular $Z_0 Z_1 \ket{\psi}$ para ver se recebemos $\pm\ket\psi}$.Recall that each measurement of a Pauli operator checks which eigenvalue the state being measured corresponds to, so for each state $\ket{\psi}$ in the table above, we can compute $Z_0 Z_1 \ket{\psi}$ to see if we get $\pm\ket{\psi}$. Note que $Z_0 Z_1 {000} \ket = \ket {000} $ e que $Z_0 Z_1 \ket {111} = \ket {111} $, de modo a concluir que esta medição faz o mesmo a ambos os estados codificados.Note that $Z_0 Z_1 \ket{000} = \ket{000}$ and that $Z_0 Z_1 \ket{111} = \ket{111}$, so that we conclude that this measurement does the same thing to both encoded states. Por outro lado, $Z_0 Z_1 \ket {100} = - \ket {100} $ e $Z_0 Z_1 \ket {011} = -\ket {011} $, pelo que o resultado da medição de $Z_0 Z_1$ revela informações úteis sobre que erro ocorreu.On the other hand, $Z_0 Z_1 \ket{100} = - \ket{100}$ and $Z_0 Z_1 \ket{011} = -\ket{011}$, so the result of measuring $Z_0 Z_1$ reveals useful information about which error occurred.

Para enfatizar isto, repetimos a tabela acima, mas adicionamos os resultados da medição $Z_0 Z_1$ e $Z_1 Z_2$ em cada linha.To emphasize this, we repeat the table above, but add the results of measuring $Z_0 Z_1$ and $Z_1 Z_2$ on each row. Denotamos os resultados de cada medição pelo sinal do valor eigen que é observado, ou $+$ ou $-$, correspondente aos Q# Result valores de Zero One e, respectivamente.We denote the results of each measurement by the sign of the eigenvalue that is observed, either $+$ or $-$, corresponding to the Q# Result values of Zero and One, respectively.

Erro $E$Error $E$ $E\ket{\overline {0} }$$E\ket{\overline{0}}$ $E\ket{\overline {1} }$$E\ket{\overline{1}}$ Resultado de $Z_0 Z_1$Result of $Z_0 Z_1$ Resultado de $Z_1 Z_2$Result of $Z_1 Z_2$
$\boldone$$\boldone$ $\ket {000} $$\ket{000}$ $\ket {111} $$\ket{111}$ $+$ $+$
$X_0$$X_0$ $\ket {100} $$\ket{100}$ $\ket {011} $$\ket{011}$ $-$ $+$
$X_1$$X_1$ $\ket {010} $$\ket{010}$ $\ket {101} $$\ket{101}$ $-$ $-$
$X_2$$X_2$ $\ket {001} $$\ket{001}$ $\ket {110} $$\ket{110}$ $+$ $-$

Assim, os resultados das duas medições determinam exclusivamente qual o erro bit-flip ocorrido, mas sem revelar qualquer informação sobre o estado que codificamos.Thus, the results of the two measurements uniquely determines which bit-flip error occurred, but without revealing any information about which state we encoded. Chamamos a estes resultados uma síndrome, e referimo-nos ao processo de mapear uma síndrome de volta ao erro que a causou como recuperação .We call these results a syndrome , and refer to the process of mapping a syndrome back to the error that caused it as recovery . Em particular, salientamos que a recuperação é um procedimento de inferência clássica que toma como entrada a síndrome que ocorreu, e devolve uma receita para como corrigir quaisquer erros que possam ter ocorrido.In particular, we emphasize that recovery is a classical inference procedure which takes as its input the syndrome which occurred, and returns a prescription for how to fix any errors that may have occurred.

Nota

O código bit-flip acima só pode corrigir contra erros simples de bit-flip; isto é, uma X operação agindo num único qubit.The bit-flip code above can only correct against single bit-flip errors; that is, an X operation acting on a single qubit. XAplicar-se a mais de um qubit irá mapear $\ket{\overline {0} }$ para $\ket{\overline {1} }$ após a recuperação.Applying X to more than one qubit will map $\ket{\overline{0}}$ to $\ket{\overline{1}}$ following recovery. Da mesma forma, a aplicação de uma operação de lançamento de fase Z irá mapear $\ket{\overline {1} }$ para $-\ket{\overline {1} }$, e, portanto, mapeará $\ket{\overline{+}} para $\ket{\overline {-} }$.Similarly, applying a phase flip operation Z will map $\ket{\overline{1}}$ to $-\ket{\overline{1}}$, and hence will map $\ket{\overline{+}}$ to $\ket{\overline{-}}$. De uma forma mais geral, podem ser criados códigos para lidar com um maior número de erros e para lidar com erros de $Z$, bem como $X$ erros.More generally, codes can be created to handle larger number of errors, and to handle $Z$ errors as well as $X$ errors.

A perceção de que podemos descrever medições na correção de erros quânticos que atuam da mesma forma em todos os estados de código, é a essência do formalismo estabilizador.The insight that we can describe measurements in quantum error correction that act the same way on all code states, is the essence of the stabilizer formalism . O Q# cânone fornece um quadro para descrever a codificação e descodificamento dos códigos estabilizadores, e para descrever como se recupera de erros.The Q# canon provides a framework for describing encoding into and decoding from stabilizer codes, and for describing how one recovers from errors. Nesta secção, descrevemos este quadro e a sua aplicação a alguns simples códigos de correção de erros quânticos.In this section, we describe this framework and its application to a few simple quantum error-correcting codes.

Dica

Uma introdução completa ao formalismo estabilizador está fora do âmbito desta secção.A full introduction to the stabilizer formalism is beyond the scope of this section. Referimos leitores interessados em aprender mais com Gottesman 2009.We refer readers interested in learning more to Gottesman 2009.

Representando códigos de correção de erros em Q#Representing Error Correcting Codes in Q#

Para ajudar a especificar códigos de correção de erros, o Q# cânone fornece vários tipos distintos definidos pelo utilizador:To help specify error correcting codes, the Q# canon provides several distinct user-defined types:

  • LogicalRegister user defined type= Qubit[]: Denota que um registo de qubits deve ser interpretado como o bloco de código de um código de correção de erros.LogicalRegister user defined type = Qubit[]: Denotes that a register of qubits should be interpreted as the code block of an error-correcting code.
  • Syndrome user defined type= Result[]: Denota que uma série de resultados de medição deve ser interpretada como a síndrome medida num bloco de código.Syndrome user defined type = Result[]: Denotes that an array of measurement results should be interpreted as the syndrome measured on a code block.
  • RecoveryFn user defined type= (Syndrome -> Pauli[]): Denota que uma função clássica deve ser usada para interpretar uma síndrome e devolver uma correção que deve ser aplicada.RecoveryFn user defined type = (Syndrome -> Pauli[]): Denotes that a classical function should be used to interpret a syndrome and return a correction that should be applied.
  • EncodeOp user defined type= ((Qubit[], Qubit[]) => LogicalRegister): Denota que uma operação requer qubits que representam dados juntamente com novos qubits de ancilla, a fim de produzir um bloco de código de um código de correção de erros.EncodeOp user defined type = ((Qubit[], Qubit[]) => LogicalRegister): Denotes that an operation takes qubits representing data along with fresh ancilla qubits in order to produce a code block of an error-correcting code.
  • DecodeOp user defined type= (LogicalRegister => (Qubit[], Qubit[])): Denota que uma operação decompõe um bloco de código de um código de correção de erros nos qubits de dados e nos qubits de ancilla utilizados para representar informações de síndrome.DecodeOp user defined type = (LogicalRegister => (Qubit[], Qubit[])): Denotes than an operation decomposes a code block of an error correcting code into the data qubits and the ancilla qubits used to represent syndrome information.
  • SyndromeMeasOp user defined type= (LogicalRegister => Syndrome): Denota uma operação que deve ser utilizada para extrair informações de síndrome de um bloco de código, sem perturbar o estado protegido pelo código.SyndromeMeasOp user defined type = (LogicalRegister => Syndrome): Denotes an operation that should be used to extract syndrome information from a code block, without disturbing the state protected by the code.

Finalmente, o cânone fornece o QECC user defined type tipo de recolha dos outros tipos necessários para definir um código de correção de erros quânticos.Finally, the canon provides the QECC user defined type type to collect the other types required to define a quantum error-correcting code. Associado a cada código quântico estabilizador está o comprimento do código $n$, o número $k$ de qubits lógicos, e a distância mínima $d$, muitas vezes convenientemente agrupados na notação ⟦$n$, $k$, $d$⟧.Associated with each stabilizer quantum code is the code length $n$, the number $k$ of logical qubits, and the minimum distance $d$, often conveniently grouped together in the notation ⟦$n$, $k$, $d$⟧. Por exemplo, a BitFlipCode function função define o código flip ⟦3, 1, 1⟧ bit:For example, the BitFlipCode function function defines the ⟦3, 1, 1⟧ bit flip code:

let encodeOp = EncodeOp(BitFlipEncoder);
let decodeOp = DecodeOp(BitFlipDecoder);
let syndMeasOp = SyndromeMeasOp(MeasureStabilizerGenerators([
    [PauliZ, PauliZ, PauliI],
    [PauliI, PauliZ, PauliZ]
], _, MeasureWithScratch));
let code = QECC(encodeOp, decodeOp, syndMeasOp);

Note que o QECC tipo não inclui uma função de recuperação.Notice that the QECC type does not include a recovery function. Isto permite-nos alterar a função de recuperação que é utilizada na correção de erros sem alterar a definição do próprio código; esta capacidade é particularmente útil ao incorporar feedback das medições de caracterização no modelo assumido pela recuperação.This allows us to change the recovery function that is used in correcting errors without changing the definition of the code itself; this ability is in particular useful when incorporating feedback from characterization measurements into the model assumed by recovery.

Uma vez que um código é definido desta forma, podemos usar a Recover operation operação para recuperar de erros:Once a code is defined in this way, we can use the Recover operation operation to recover from errors:

let code = BitFlipCode();
let fn = BitFlipRecoveryFn();
let X0 = ApplyPauli([PauliX, PauliI, PauliI], _);
using (scratch = Qubit[nScratch]) {
    let logicalRegister = encode(data, scratch);
    // Cause an error.
    X0(logicalRegister);
    Recover(code, fn, logicalRegister);
    let (decodedData, decodedScratch) = decode(logicalRegister);
    ApplyToEach(Reset, decodedScratch);
}

Exploramos isto mais detalhadamente na amostra de código bit flip.We explore this in more detail in the bit flip code sample.

Além do código bit-flip, o Q# cânone é fornecido com implementações do código perfeito de cinco qubits, e o código de sete qubits, ambos podem corrigir um erro arbitar de um único qubit.Aside from the bit-flip code, the Q# canon is provided with implementations of the five-qubit perfect code, and the seven-qubit code, both of which can correct an arbitrary single-qubit error.