Por que você precisa de correção de erros? Meu entendimento é que a correção de erros remove os erros do ruído, mas o ruído deve ter uma média própria. Para deixar claro o que estou perguntando, por que você não pode, em vez de envolver a correção de erros, simplesmente executar as operações, digamos, cem vezes e escolher a resposta média / mais comum?
Isso não escala bem. Após um cálculo moderadamente longo, você fica basicamente com o estado misto máximo ou em qualquer ponto fixo que seu ruído tenha. Para escalar para cálculos longos arbitrários, você precisa corrigir os erros antes que eles se tornem muito grandes.
Aqui está um breve cálculo para a intuição fornecida acima. Considere o modelo simples de ruído branco (ruído despolarizante),
ondeρé o estado ideal (anotação padrãose aplica). Se você concatenarntais processos ruidosos, o novo parâmetro de ruído seráε′=1-(1-ε)n, que aumenta exponencialmente o número de portas (ou outras fontes de erro). Se você repetir o experimentomvezes e assumir que o erro padrão é escalado como1
ρ′(ε)=(1−ε)ρ+εItrI,
ρnε′=1−(1−ε)nm você vê que o número de execuçõesmestaria exponencialmente no comprimento do seu cálculo!1m√m
Se a taxa de erro fosse baixa o suficiente, você poderia executar um cálculo cem vezes e obter a resposta mais comum. Por exemplo, isso funcionaria se a taxa de erro fosse baixa o suficiente para que o número esperado de erros por cálculo fosse algo muito pequeno - o que significa que o desempenho dessa estratégia dependeria de quanto tempo e complicado o cálculo você gostaria de fazer.
Depois que a taxa de erro ou a duração do seu cálculo se tornarem suficientemente altas, você não poderá mais ter certeza de que o resultado mais provável é que houve zero erro: em um determinado momento, torna-se mais provável que você tenha um ou dois, ou mais erros do que você tem zero. Nesse caso, não há nada para impedir que a maioria dos casos lhe dê uma resposta incorreta. O que então?
Essas questões não são especiais para a computação quântica: elas também se aplicam à computação clássica - acontece que quase toda a nossa tecnologia está em um estado de maturidade suficientemente avançado que essas questões não nos interessam na prática; que pode haver uma chance maior de o seu computador ser atingido por um meteorito no meio da computação (ou ficar sem bateria, ou você decidir desligá-lo) do que um erro de hardware. O que é (temporariamente) especial sobre a computação quântica é que a tecnologia ainda não está madura o suficiente para ficarmos tão relaxados com a possibilidade de erro.
Naqueles tempos em que a computação clássica temEstando em um estágio em que a correção de erros era prática e necessária, fomos capazes de fazer uso de certas técnicas matemáticas - a correção de erros - que permitiram suprimir a taxa de erro efetiva e, em princípio, reduzi-la ao nível desejado. Surpreendentemente, as mesmas técnicas podem ser usadas para a correção de erros quânticos - com um pouco de extensão, para acomodar a diferença entre informações quânticas e clássicas. A princípio, antes de meados da década de 90, pensava-se que a correção de erro quântico era impossível devido à continuidade do espaço dos estados quânticos. Mas, ao que parece, aplicando técnicas clássicas de correção de erros da maneira correta para as diferentes maneiras de medir um qubit (geralmente descrito como "bit" e "fase"), em princípio, você também pode suprimir muitos tipos de ruído em sistemas quânticos. Essas técnicas também não são especiais para os qubits: a mesma idéia pode ser usada para sistemas quânticos de qualquer dimensão finita (embora para modelos como a computação adiabática, ela possa atrapalhar a execução da computação que você deseja executar).
No momento em que escrevo isso, os qubits individuais são tão difíceis de construir e organizar que as pessoas esperam fazer cálculos de prova de princípio sem nenhuma correção de erro. Tudo bem, mas limitará o tempo que os cálculos podem demorar até que o número de erros acumulados seja grande o suficiente para que o cálculo deixe de ser significativo. Existem duas soluções: melhorar a eliminação de ruídos ou aplicar a correção de erros. Ambas são boas idéias, mas é possível que a correção de erros seja mais fácil de executar a médio e longo prazo do que suprimir fontes de ruído.
Como uma correção rápida, o hardware moderno sofre taxas de erro não desprezíveis e métodos de correção de erros são usados. Dito isto, é claro que seu argumento sobre os problemas serem muito piores nos atuais computadores quânticos é válido.
Nat
@ Nat: interessante. Estou vagamente ciente de que atualmente pode ser o caso de GPUs e (em um contexto que não envolve computação ativa) as matrizes RAID também são um exemplo óbvio. Mas você poderia descrever outras plataformas de hardware nas quais a computação clássica deve confiar na correção de erros durante uma computação?
Niel de Beaudrap 14/0318
Parece que os erros ocorrem com mais frequência nos contextos de rede, seguidos pelo armazenamento em disco e pela RAM. Protocolos e discos de rede implementam rotineiramente truques de correção de erros. RAM é um saco misto; a RAM do servidor / estação de trabalho tende a usar o código de correção de erros (ECC), embora a RAM do consumidor geralmente não o faça. Dentro das CPUs, eu imagino que elas tenham mais táticas específicas de implementação, mas essas provavelmente seriam segredos do fabricante. As taxas de erro em CPU e GPU se tornam relevantes em um nível observável em alguns casos, por exemplo, em decisões de overclocking e bloqueio de núcleo do fabricante.
Nat
Na verdade, estou meio curioso sobre a correção de erros do tipo CPU agora. Quero dizer, o cache parece propenso aos mesmos problemas que a RAM normal (a menos que seja de alguma forma armazenada em buffer com mais energia ou algo assim?), O que presumivelmente seria inaceitável no servidor / contextos de estação de trabalho. Mas no nível do registro? Isso seria algo interessante de se ler; não viu nada imediatamente no Google, embora eu suponha que essas informações provavelmente sejam um segredo comercial.
A principal razão pela qual a correção de erros é necessária para computadores quânticos é porque os qubits têm um continuum de estados (estou considerando computadores quânticos baseados em qubit apenas, no momento, por uma questão de simplicidade).
α | 0 ⟩ + β|1⟩α|0⟩+βeiϕ|1⟩α | 0 ⟩ + βei(ϕ+δ)|1⟩. The actual state is close to the correct state but still wrong. If we don't do something about this the small errors will build up over the course of time and eventually become a big error.
Moreover, quantum states are very delicate, and any interaction with the environment can cause decoherence and collapse of a state like α|0⟩+β|1⟩ to |0⟩ with probability |α|2 or |1⟩ with probability |β|2.
In a classical computer if say a bit's value is being replicated n-times as follows:
0→00000...n times
and
1→11111...n times
In case after the step something like 0001000100 is produced it can be corrected by the classical computer to give 0000000000 because majority of the bits were 0′s and most probably the intended aim of the initial operation was replicating the 0-bit 10 times.
But, for qubits such a error correction method won't work, because first of all duplicating qubits directly is not possible due to the No-Cloning theorem. And secondly, even if you could replicate |ψ⟩=α|0⟩+β|1⟩ 10-times it's highly probably that you'd end up with something like (α|0⟩+β|1⟩)⊗(αeiϵ|0⟩+βeiϵ′|1⟩)⊗(αeiϵ2|0⟩+βeiϵ′2|1⟩)⊗... i.e. with errors in the phases, where all the qubits would be in different states (due to the errors). That is, the situation is no-longer binary. A quantum computer, unlike a classical computer can no longer say that: "Since majority of the bits are in 0-state let me convert the rest to 0 !", to correct any error which occurred during the operation. That's because all the 10 states of the 10 different qubits might be different from each other, after the so-called "replication" operation. The number of such possible errors will keep increasing rapidly as more and more operations are performed on a system of qubits. M. Stern has indeed used the right terminology in their answer to your question i.e. "that doesn't scale well".
So, you need a different breed of error correcting techniques to deal with errors occurring during the operation of a quantum computer, which can deal not only with bit flip errors but also phase shift errors. Also, it has to be resistant against unintentional decoherence. One thing to keep in mind is that most quantum gates will not be "perfect", even though with right number of "universal quantum gates" you can get arbitrarily close to building any quantum gate which performs (in theory) an unitary transformation.
Niel de Beaudrap mentions that there are clever ways to apply classical error correction techniques in ways such that they can correct many of the errors which occur during quantum operations, which is indeed correct, and is exactly what current day quantum error correcting codes do. I'd like to add the following from Wikipedia, as it might give some clarity about how quantum error correcting codes deal with the problem described above:
Classical error correcting codes use a syndrome measurement to
diagnose which error corrupts an encoded state. We then reverse an
error by applying a corrective operation based on the syndrome.
Quantum error correction also employs syndrome measurements. We
perform a multi-qubit measurement that does not disturb the quantum
information in the encoded state but retrieves information about the
error. A syndrome measurement can determine whether a qubit has been
corrupted, and if so, which one. What is more, the outcome of this
operation (the syndrome) tells us not only which physical qubit was
affected, but also, in which of several possible ways it was affected.
The latter is counter-intuitive at first sight: Since noise is
arbitrary, how can the effect of noise be one of only few distinct
possibilities? In most codes, the effect is either a bit flip, or a
sign (of the phase) flip, or both (corresponding to the Pauli matrices
X, Z, and Y). The reason is that the measurement of the syndrome has
the projective effect of a quantum measurement. So even if the error
due to the noise was arbitrary, it can be expressed as a superposition
of basis operations—the error basis (which is here given by the Pauli
matrices and the identity). The syndrome measurement "forces" the
qubit to "decide" for a certain specific "Pauli error" to "have
happened", and the syndrome tells us which, so that we can let the
same Pauli operator act again on the corrupted qubit to revert the
effect of the error.
The syndrome measurement tells us as much as possible about the error
that has happened, but nothing at all about the value that is stored
in the logical qubit—as otherwise the measurement would destroy any
quantum superposition of this logical qubit with other qubits in the
quantum computer.
Note: I haven't given any example of actual quantum error correcting techniques. There are plenty of good textbooks out there which discuss this topic. However, I hope this answer will give the readers a basic idea of why we need error correcting codes in quantum computation.
I'm not sure the fact that there is a continuum of states plays any role. Classical computation with bits would also have the same problems if our technology were less mature, and indeed it did suffer meaningfully from noise at various times in its development. In both the classical and quantum case, noise doesn't conveniently average away under normal circumstances
Niel de Beaudrap
@NieldeBeaudrap It does play a big role. In classical computation you know that you'd have to deal only with two states, beforehand. Just consider an example: In classical computation if a signal of 5 mV represents "high" (or 1-state) while 0 mV theoretically represents the "low" (or 0-state), if your operation ended up with something like 0.5 mV it would be automatically be rounded off to 0 mV because it is much closer to 0 mV than 5 mV. But in case of qubits there are an infinite number of possible states and such rounding off doesn't work.
Sanchayan Dutta
Of course you're not wrong when you say that even classical computation suffered from the problem of noise. There's a well established theory of classical error correcting codes too! However, the situation is much more dire in case of quantum computation due to the possibility of infinite number of states of existence of a single qubit.
Sanchayan Dutta
1
The techniques used for quantum error correction does not involve the fact that the state-space is infinite in any way. The arguments you are making seem to be drawing an analogy between quantum computing and analog computing --- while there is a similarity, it would imply that quantum error correction would be impossible if it were a sound analogy. In contrast, the state-space of many qubits is also like a probability distribution on bit-strings, of which there is also a continuum; and yet just doing error correction on definite bit-strings suffices to suppress error.
Niel de Beaudrap
1
@glS I have removed the first sentence. You're right. I was interpreting computation in an unrelated way.
Sanchayan Dutta
2
Why do you need error correction? My understanding is that error correction removes errors from noise, but noise should average itself out.
If you built a house or a road and noise was a variance, a difference, with respect to straightness, to direction, it's not solely / simply: "How would it look", but "How would it be?" - a superposition of both efficiency and correctness.
If two people calculated the circumference of a golf ball given a diameter each would get a similar answer, subject to the accuracy of their calculations; if each used several places of decimal it would be 'good enough'.
If two people were provided with identical equipment and ingredients, and given the same recipe for a cake, should we expect identical results?
To make clear what I'm asking, why can't you, instead of involving error correction, simply run the operations, say, a hundred times, and pick the average/most common answer?
You're spoiling the weighing, tapping your finger on the scale.
If you're at a loud concert and try to communicate with the person next to you do they understand you the first time, everytime?
If you tell a story or spread a rumor, (and some people communicate verbatim, some add their own spin, and others forget parts), when it gets back to you does it average itself out and become essentially (but not identically) the same thing you said? - unlikely.
It like crinkling up a piece of paper and then flattening it out.
All those analogies were intended to offer simplicity over exactness, you can reread them a few times, average it out, and have the exact answer, or not. ;)
A more technical explanation of why quantum error correction is difficult but neccessary is explained on Wikipedia's webpage: "Quantum Error Correction":
"Quantum error correction (QEC) is used in quantum computing to protect quantum information from errors due to decoherence and other quantum noise. Quantum error correction is essential if one is to achieve fault-tolerant quantum computation that can deal not only with noise on stored quantum information, but also with faulty quantum gates, faulty quantum preparation, and faulty measurements.".
"Copying quantum information is not possible due to the no-cloning theorem. This theorem seems to present an obstacle to formulating a theory of quantum error correction. But it is possible to spread the information of one qubit onto a highly entangled state of several (physical) qubits. Peter Shor first discovered this method of formulating a quantum error correcting code by storing the information of one qubit onto a highly entangled state of nine qubits. A quantum error correcting code protects quantum information against errors of a limited form.".
Noise doesn't perfectly average itself out. That's the Gambler's Fallacy. Even though noise tends to meander back and forth, it still accumulates over time.
For example, if you generate N fair coin flips and sum them up, the expected magnitude of the difference from exactly N/2 heads grows like O(N−−√). That's quadratically better than the O(N) you expect from a biased coin, but certainly not 0.
Even worse, in the context of a computation over many qubits the noise doesn't cancel itself nearly as well, because the noise is no longer along a single dimension. In a quantum computer with Q qubits and single-qubit noise, there are 2Q dimensions at any given time for the noise to act on (one for each X/Z axis of each qubit). And as you compute with the qubits, these dimensions change to correspond to different subspaces of a 2Q dimensional space. This makes it unlikely for later noise to undo earlier noise, and as a result you're back to O(N) accumulation of noise.
run the operations, say, a hundred times, and pick the average/most common answer?
As computations get larger and longer, the chance of seeing no noise or of the noise perfectly cancelling out rapidly becomes so close to 0% that you can't expect see the correct answer even once even if you repeated the computation a trillion times.
Agora, acrescentando à resposta de M. Stern :
A principal razão pela qual a correção de erros é necessária para computadores quânticos é porque os qubits têm um continuum de estados (estou considerando computadores quânticos baseados em qubit apenas, no momento, por uma questão de simplicidade).
Moreover, quantum states are very delicate, and any interaction with the environment can cause decoherence and collapse of a state likeα|0⟩+β|1⟩ to |0⟩ with probability |α|2 or |1⟩ with probability |β|2 .
In a classical computer if say a bit's value is being replicated n-times as follows:
In case after the step something like0001000100 is produced it can be corrected by the classical computer to give 0000000000 because majority of the bits were 0′s and most probably the intended aim of the initial operation was replicating the 0 -bit 10 times.
But, for qubits such a error correction method won't work, because first of all duplicating qubits directly is not possible due to the No-Cloning theorem. And secondly, even if you could replicate|ψ⟩=α|0⟩+β|1⟩ 10-times it's highly probably that you'd end up with something like (α|0⟩+β|1⟩)⊗(αeiϵ|0⟩+βeiϵ′|1⟩)⊗(αeiϵ2|0⟩+βeiϵ′2|1⟩)⊗... i.e. with errors in the phases, where all the qubits would be in different states (due to the errors). That is, the situation is no-longer binary. A quantum computer, unlike a classical computer can no longer say that: "Since majority of the bits are in 0 -state let me convert the rest to 0 !", to correct any error which occurred during the operation. That's because all the 10 states of the 10 different qubits might be different from each other, after the so-called "replication" operation. The number of such possible errors will keep increasing rapidly as more and more operations are performed on a system of qubits. M. Stern has indeed used the right terminology in their answer to your question i.e. "that doesn't scale well".
So, you need a different breed of error correcting techniques to deal with errors occurring during the operation of a quantum computer, which can deal not only with bit flip errors but also phase shift errors. Also, it has to be resistant against unintentional decoherence. One thing to keep in mind is that most quantum gates will not be "perfect", even though with right number of "universal quantum gates" you can get arbitrarily close to building any quantum gate which performs (in theory) an unitary transformation.
Niel de Beaudrap mentions that there are clever ways to apply classical error correction techniques in ways such that they can correct many of the errors which occur during quantum operations, which is indeed correct, and is exactly what current day quantum error correcting codes do. I'd like to add the following from Wikipedia, as it might give some clarity about how quantum error correcting codes deal with the problem described above:
Note: I haven't given any example of actual quantum error correcting techniques. There are plenty of good textbooks out there which discuss this topic. However, I hope this answer will give the readers a basic idea of why we need error correcting codes in quantum computation.
Recommended Further Readings:
An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation - Daniel Gottesman
Scheme for reducing decoherence in quantum computer memory - Peter Shor
Recommended Video Lecture:
Mini Crash Course: Quantum Error Correction by Ben Reichardt, University of Southern California
fonte
If you built a house or a road and noise was a variance, a difference, with respect to straightness, to direction, it's not solely / simply: "How would it look", but "How would it be?" - a superposition of both efficiency and correctness.
If two people calculated the circumference of a golf ball given a diameter each would get a similar answer, subject to the accuracy of their calculations; if each used several places of decimal it would be 'good enough'.
If two people were provided with identical equipment and ingredients, and given the same recipe for a cake, should we expect identical results?
You're spoiling the weighing, tapping your finger on the scale.
If you're at a loud concert and try to communicate with the person next to you do they understand you the first time, everytime?
If you tell a story or spread a rumor, (and some people communicate verbatim, some add their own spin, and others forget parts), when it gets back to you does it average itself out and become essentially (but not identically) the same thing you said? - unlikely.
It like crinkling up a piece of paper and then flattening it out.
All those analogies were intended to offer simplicity over exactness, you can reread them a few times, average it out, and have the exact answer, or not. ;)
A more technical explanation of why quantum error correction is difficult but neccessary is explained on Wikipedia's webpage: "Quantum Error Correction":
fonte
Noise doesn't perfectly average itself out. That's the Gambler's Fallacy. Even though noise tends to meander back and forth, it still accumulates over time.
For example, if you generate N fair coin flips and sum them up, the expected magnitude of the difference from exactlyN/2 heads grows like O(N−−√) . That's quadratically better than the O(N) you expect from a biased coin, but certainly not 0.
Even worse, in the context of a computation over many qubits the noise doesn't cancel itself nearly as well, because the noise is no longer along a single dimension. In a quantum computer withQ qubits and single-qubit noise, there are 2Q dimensions at any given time for the noise to act on (one for each X/Z axis of each qubit). And as you compute with the qubits, these dimensions change to correspond to different subspaces of a 2Q dimensional space. This makes it unlikely for later noise to undo earlier noise, and as a result you're back to O(N) accumulation of noise.
As computations get larger and longer, the chance of seeing no noise or of the noise perfectly cancelling out rapidly becomes so close to 0% that you can't expect see the correct answer even once even if you repeated the computation a trillion times.
fonte