Quantum Programming Implementation: Quantum Error Correction
Feb 17, 2022
Quantum Programming, by Outline Implementation: quantum error correction; 100 minutes; Feb 17, 2022
Copyright By PowCoder代写 加微信 powcoder
Hook: Quantum computers are noisy and their results are unreliable. Can we correct the errors that happen due to noise? While the hardware people are busy making more reliable qubits, the algorithms people are busy making better algorithms for error correction.
Purpose: Persuade you that we can correct errors at the cost of adding many qubits.
1. We will define two particular kinds of errors.
2. We will give three reasons why quantum error correction is hard.
3. We will define three schemes for error correction, culminating with the Shor code.
Transition to Body: Now let us talk about errors.
Main Point 1: We will define two particular kinds of errors. [Bit flip errors]
[Phase flip errors] [Arbitrary quantum errors]
Transition to MP2: In classical computing, we handle errors by adding redundancy.
Main Point 2: We will list three reasons why quantum error correction is hard. [We cannot clone a qubit]
[Errors are continuous] [Measurement destroys quantumness]
Transition to MP3: So, what can we do about it?
Main Point 3: We will define three schemes for error correction, culminating with the Shor code. [The three qubit bit flip code and the three qubit phase flip code]
[The Shor code]
[The Threshold Theorem]
Transition to Close: So there you have it.
Review: Quantum error correction is harder than classical error correction due to quantum
limitations such as no-cloning. We can correct many errors but at the cost of adding many qubits.
Strong finish: More reliable quantum computing can be achieved by better hardware, better algorithms for error correction, or both. Given the huge reliability gap between classical computing and quantum computing, we need both.
Call to action: Now is a great time to do research on quantum error correction.
Detailed presentation
Hook: Quantum computers are noisy and their results are unreliable. In particular, they are much more unreliable than classical computers. Can we correct the errors that happen due to noise? While the hardware people are busy making more reliable qubits, the algorithms people are busy making better algorithms for error correction. Today I will explain quantum error correction in a way that ties together the No-Cloning theorem, the World’s most reliable qubits from UCLA Physics, and the number 1 .
Purpose: Persuade you that we can correct errors at the cost of adding many qubits.
1. We will define two particular kinds of errors.
2. We will give three reasons why quantum error correction is hard.
3. We will define three schemes for error correction, culminating with the Shor code.
Transition to Body: Now let us talk about errors.
Main Point 1: We will define two particular kinds of errors.
[Bit flip errors]
In classical computing, a bit flip error maps 0 to 1, and 1 to 0.
In quantum computing, a bit flip error maps |ψ⟩ to X|ψ⟩, that is, a|0⟩ + b|1⟩ to a|1⟩ + b|0⟩.
[Phase flip errors]
In quantum computing, a phase flip error maps |ψ⟩ to Z|ψ⟩, that is, a|0⟩ + b|1⟩ to a|0⟩ − b|1⟩.
In classical computing, we have nothing like a phase flip error.
[Arbitrary quantum errors]
We can consider an arbitrary error on a single qubit. Such an arbitrary error can be anything from a tiny change to the phase to removing the qubit entirely and replacing it with garbage.
Transition to MP2: In classical computing, we handle errors by adding redundancy. Main Point 2: We will list three reasons why quantum error correction is hard.
[We cannot clone a qubit]
In classical computing we handle noise via encoding and decoding. For example, we can encode a bit as three copies of itself and then decode by majority vote. If at most one bit has flipped, we will get the right result. Notice that when errors are rare, one error is more likely than two.
In quantum computing, we cannot clone a qubit so the idea of three copies of a qubit won’t work. Specifically, the no-cloning theorem says that we cannot copy an unknown quantum state.
[Errors are continuous]
In classical computing, data is discrete: 0 and 1; and errors are discrete: 0 to 1, or 1 to 0.
In quantum computing, qubits are made up of complex numbers; and errors can be continuous and modify those complex numbers. So, we have a continuum of errors rather than just bit flips.
[Measurement destroys quantumness]
The basis for doing a majority vote is that we can observe the things we are voting on. In quantum computing, we can measure the qubits but measurement destroys superposition in a quantum state so we cannot recover the qubits we measured. So, we cannot examine every part of a codeword and then determine how to correct an error.
Transition to MP3: So, what can we do about it?
Main Point 3: We will define three schemes for error correction, culminating with the Shor code.
[The three qubit bit flip code and the three qubit phase flip code]
The field of quantum error correction overcomes all the three challenges listed above. We begin by solving the problem for bit flip errors.
If we have a bit flip error, then we can handle it with the bit flip code: map a|0⟩ + b|1⟩ to a|000⟩ + b|111⟩. The first two gates in the following diagram does the mapping.
Now let us assume that at most one bit gets flipped and that no other error occurs. In the following diagram, the gate Ebit models a bit flip error on any of the three qubits. The three gates that follow Ebit recover the quantum state.
Let us check that these steps work in the case of flipping the second bit, that is, Ebit delivers a|010⟩ + b|101⟩. Now we can do the steps after Ebit:
CX(1, 2) :
CX(1, 3) : CCX(3, 2, 1) :
a|010⟩ + b|101⟩ a|010⟩ + b|111⟩ a|010⟩ + b|110⟩ a|010⟩ + b|110⟩
The end result is correct: the first qubit is a|0⟩ + b|1⟩.
One downside of the above circuit is that it leaves the two helper qubits in a state that depends
on the error. We prefer to leave helper qubits in a well-defined state, like |0⟩, such that we can use them again easily.
Another downside of the above circuit is that the last gate is a Toffoli gate that on today’s quantum computers will be implemented using 2-qubit gates. Theoretically, five 2-qubit gates are sufficient, but if CNOTs are the only 2-qubit gates available, we need 6 CNOTs plus 9 1-qubit gates.
How is this related to parity checks? The following diagram shows how to implement the bit flip code using parity checks.
First we do error detection and correction by computing and measuring two additional helper qubits. The outcome of the measurement of the two helper qubits is known as the error syndrome. The first measured bit says whether the first and second bits of the encoded state are different (1) or the same (0). The second measured bit says whether the second and third bits of the encoded
state are different (1) or the same (0).
If we are sending an encoding of the qubit a|0⟩ + b|1⟩, then the error syndrome does not depend
on a, b. Thus, we can learn about errors without learning about a, b, and thereby we preserve the superposition of a|0⟩ + b|1⟩.
Given that at most one bit gets flipped, we will get one of the following four measurements and a corrective action to take:
Measurement corrective action 00 do nothing
10 flip the first qubit
11 flip the second qubit
01 flip the third qubit
Second we bring the two additional qubits back to their original state using decode in the diagram above.
Let us check that these steps work in the case of flipping the second bit, that is, the channel delivers a|010⟩ + b|101⟩. After introducing the two additional helper bits, the state is a|01000⟩ + b|10100⟩. Now we can do the steps of detect and correct:
CX(1, 4) : CX(2, 4) : CX(2, 5) : CX(3, 5) :
measure the two helper qubits : flip the second qubit by applying X :
a|01000⟩ + b|10100⟩ a|01000⟩ + b|10110⟩ a|01010⟩ + b|10110⟩ a|01011⟩ + b|10110⟩ a|01011⟩ + b|10111⟩ 11
a|00011⟩ + b|11111⟩
Finally, decode brings the two additional qubits back to their original state |00⟩. The end result is correct: the first qubit is a|0⟩ + b|1⟩. Notice that the final state of the helper qubits depends on the error.
If we have a phase flip error, then we can handle it with the phase flip code, which, intuitively, uses Hadamard to map the problem to the bit flip problem. In practice, we are changing the base from |0⟩, |1⟩ to |+⟩, |−⟩. We begin with a straightforward modification of the first circuit above.
Let us check that these steps work in the case of flipping the phase on the third qubit. Reminder: Z|+⟩ = |−⟩ and Z|−⟩ = |+⟩. We map a|0⟩+b|1⟩ to a|+++⟩+b|−−−⟩, and then the channel delivers a|+ + −⟩ + b|− − +⟩. Now we can do the steps after Ebit:
a|+ + −⟩ + b|− − +⟩ a|001⟩ + b|110⟩ a|001⟩ + b|100⟩ a|001⟩ + b|101⟩ a|001⟩ + b|101⟩
CX(1, 3) CCX(3, 2, 1)
The end result is correct: the first qubit is a|0⟩ + b|1⟩. We can also do this with parity checks.
Let us check that these steps work in the case of flipping the phase on the third qubit, that is, the channel delivers a|+ + −⟩ + b|− − +⟩. After introducing the two additional helper bits, the
state is a|+ + − 00⟩ + b|− − + 00⟩. Now we can do H⊗H⊗H
CX(1, 4) CX(2, 4) CX(2, 5) CX(3, 5)
measure the two helper qubits flip the third qubit by applying X
the steps of detect and correct:
Finally, decode brings the two additional qubits back correct: the first qubit is a|0⟩ + b|1⟩.
: : : : : : :
a|++− 00⟩+b|−−+ 00⟩ a|00100⟩ + b|11000⟩ a|00100⟩ + b|11010⟩ a|00100⟩ + b|11000⟩ a|00100⟩ + b|11000⟩ a|00101⟩ + b|11001⟩
a|00001⟩ + b|11101⟩
to their original state |00⟩. The end result is
[The Shor code]
The Shor code corrects an arbitrary error on a single qubit. The idea is to first encode a qubit using the phase flip code and then encode each of the three qubits using the bit flip code. Thus, the encoding is given by the following circuit:
The idea of using one code after the other is known as concatenation.
Intuitively, the Shor code can correct both a bit flip and a phase flip on any qubit. But the Shor code can do much more than that. First, the Shor code can correct the combination of a bit flip and phase flip on any qubit. Second, and more impressively, the Shor code can correct an arbitrary error on a single qubit. Thus, we are correcting a continuum of errors by correcting a discrete subset of those errors. This discretization of the errors is central to why quantum error-correction works.
[The Threshold Theorem]
Can we use error correction to create highly reliable quantum computation? The error correction will run on noisy quantum hardware so who will correct errors in the error correction? Can this work out, or will we have “turtles all the way down”?
The Threshold Theorem says that if the noise in the quantum gates is below a known threshold, then we can fix errors faster than they happen, at arbitrarily large scale. This means that noise won’t stop us from doing reliable large-scale quantum computation. The stack of turtles is finite.
The idea of the proof is to concatenate codes. Each level of concatenation decreases the error rate. After k levels of concatenation, the error rate is vanishingly small. Specifically, for a compu- tation of length T , we need log(log T ) levels of concatenation and thus polylog(T ) extra qubits for high reliability.
So, the underlying concept of the Threshold Theorem is that by nesting error correction codes a sufficient number of times, we can make the logical error rate arbitrarily small.
How do we determine the threshold value? One can try a theoretical approach, which will tend to give a low threshold. One can try an experimental approach, possibly via simulation, which will tend to give a high threshold. In either case, one can make assumptions that will simplify the task but also give more approximate answers.
Some theoretical papers have reported a threshold value of 10−5, while some simulation-based papers have reported a threshold value of 10−3.
We know that the World’s most reliable qubits from UCLA Physics have a State Preparation and Measurement (SPAM) error of (1 − 99.97)%, which is about 10−4, so that is good.
Here, we will do a back-of-the-envelope calculation. Let us apply the idea of the Threshold Theorem to the case where the code state has two errors. In many cases, the two errors will result in a logical error, like when both qubits 1 and 2 have bit-flip errors. We can solve this using the idea of the Threshold Theorem, if we make a big assumption: all errors occur independently with small probability p. Note: experiments have shown that this assumption is sometimes wrong, but the following ideas can be adapted to cases beyond the big assumption.
Let us assume that p is the error rate of the qubits and let us assume that (1 − p) ≈ 1. Now we can calculate:
Prob(two errors occurring in the Shor code) = (9 choose 2) × p2 × (1 − p)7 ≈ 36p2
So, if p < 1 , then Prob(two errors occurring in the Shor code) < p. In other words, if p < 1 , then
the two-error rate for the encoding is less than the one-error rate for the original qubits. Notice that the assumption that p < 1 is true on today’s quantum computers.
We can improve further by adding another level of the Shor code and thereby get a logical error
rate of 36 ∗ (36 ∗ p2)2, which is smaller than 36p2. Thus, two levels of Shor code is better than
one level of Shor code, though now we are up to 9 × 9 = 81 helper qubits for each logical qubit.
So, if we pick the threshold value to be 1 , then we can nest the encoding for as many layers as 36
we like, and make the logical error rate arbitrarily small. This nesting is the key to do quantum computation with faulty qubits and arbitrarily high accuracy.
So, is 1 the threshold that we are looking for? No! Aside from the approximations above, we 36
have a hidden and unrealistic assumption that the measurement of error syndromes can be done perfectly.
We also need to think about how to perform logical gates on the encoded qubits. So far, the best schemes are highly complicated, require a lot of additional qubits, and depend on a tiny threshold. For example, from Google and ̊a from Sweden had an impressive paper in 2019. In that paper they showed how to factor 2,048 bit RSA integers in 8 hours on a model of a quantum computer with 20 million qubits and a gate error of 10−3.
Overall, we need both the hardware people to make more reliable qubits and the algorithms people to make better algorithms for error correction. But the Threshold Theorem says that the stack of turtles has an end to it.
O! Wanderers in the shadowed land despair not! For though dark they stand, all woods there be must end at last, and see the open sun go past.
Who said that? Frodo, in Lord of the Rings, in the Old Forest.
Transition to Close: So there you have it.
Review: Quantum error correction is harder than classical error correction due to quantum limitations such as no-cloning. We can correct many errors but at the cost of adding many qubits.
Strong finish: More reliable quantum computing can be achieved by better hardware, better algorithms for error correction, or both. Given the huge reliability gap between classical computing and quantum computing, we need both.
Call to action: Now is a great time to do research on quantum error correction.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com