Can we really deal with bit flip?

From a merely theoretical point of view, there is no doubt that quantum computers would have extraordinary power, but — concretely — we have to face the truth and fight against the existence of noise and errors. The challenge is to protect quantum information from them, and many tasks need to be accomplished to achieve this aim.
First of all, we should keep in mind that the quantum gates we have to apply to qubits to perform calculations, require an infinite precision to be exact. Since this level of precision is unreachable, small imperfections inevitably accumulate during the execution of the circuit, eventually leading, if no stratagems are put in place, to a serious failure in the computation.
Moreover, the success of quantum computation is jeopardized by interactions with the environment. Qubits' quantum states and superposition are very fragile, and one of the biggest problems plaguing physical implementations of quantum computers is qubits' very short “shelf-life”. We are used to classical technologies, in which classical bits may last unchanged for years, but the story for qubits in superpositions is completely different. They typically have lifespans of the order of microseconds before they get corrupted, and their state changes unintentionally, inevitably ruining the computation. Consequently, quantum systems must be very heavily isolated to avoid the decoherence and the decay of quantum information stored in the device since a single interaction with a stray particle or photon could put them into a completely different state. In decoherence, one of the worst consequences beyond quantum superposition destruction is bit-flip, a specific type of error where a qubit computational state flips from |0⟩ to |1⟩ or vice versa, as shown in Fig. 1(a). Needless to say, even if a mathematical description through X gates is useful, the bit-flip is not caused by wild extra gates randomly appearing in a circuit [1], such as a Pokèmon in our old Nintendo screen.

Fig. 1 — In (a) part of the figure, the effect of Bit Flip error on a qubit state is shown, and the state changes from |0⟩ to |1⟩; in (b), the effect of phase flip is depicted the state passes from |0⟩ to -|0⟩.

This kind of error has a direct classical counterpart: even though classically the states 0 and 1 for bits are so different that the probability for an unwanted flip to occur is negligible, things change when one tries to transmit a signal over large distances. In this situation, similar to what happens for quantum devices, classical information can be corrupted by noise. To protect the information stored in bits, error correction protocols are put in place using redundancy: the more bits carrying the same information, the lower the probability of losing part of it. The idea is very simple and indeed very effective: it is possible to encode each logical bit in a set of three or more physical bits, i.e.

|0⟩ → |0⟩ ≡ Logical 0 bit ≡ |0⟩|0⟩|0⟩ ≡ |000⟩,
|1⟩ → |1⟩ ≡ Logical 1 bit ≡ |1⟩|1⟩|1⟩ ≡ |111⟩.

The set of bit states is called codewords: if the bits in a codeword are not all in the same state, then the "majority rule" is used to perform a correction. It is based on the assumption that, if the values are no longer the same because some corruption occurred, the state appearing the greater number of times will represent the initial value. For example, |001⟩, |010⟩, |100⟩ would be corrected to |000⟩, while |110⟩, |101⟩, |110⟩ to |111⟩. It is easy to deduce that this protocol works properly only if no more than one bit is corrupted. In other words, the error rate must be small enough to assume that the probability that two or more bits are simultaneously corrupted can be neglected.
Extending this technique to fix unwanted flips to quantum bits (qubits) could seem straightforward. Still, several points must be raised to highlight the fundamental differences between the classical case and the quantum one [2]:

(i) error correction in quantum devices is essential to overcome the difficulties arising from outside interferences to build any large-scale quantum device, which is naturally prone to decoherence;

(ii) in the quantum case, checking for errors is indeed tricky: measurements destroy quantum superposition, and measuring a general quantum state to verify the occurrence of errors would imply the loss of any quantum advantage;

(iii) in quantum computing, other errors can occur, just as damaging as the bit-flip. They must be treated using different protocols combined with bit-flip ones. An example is the phase flip error, a phenomenon not having any classical counterpart, which causes an alteration of the state as shown in Fig. 1(b), e.g. α |0⟩ + β |1⟩ → α |0⟩ - β |1⟩;

(iv) the main difference between classical and quantum errors is that quantum ones are continuous errors, unlike classical ones, which are discrete. A classical bit could flip or not flip, while qubits errors grow continuously out of their uncorrupted state. To be concrete, this means that in the case of bit flip, the quantum state does not evolve from |0⟩ to |1⟩, but instead, the qubits gradually entangle with the environment causing its state to evolve from |0⟩ to (|0⟩ + ϵ|1⟩) according to the error rate ϵ [3].

These theoretical elements, plus the no-cloning theorem [4] —which states that it is impossible to make perfect copies of a qubit state —, could lead to the idea that a working quantum computer is impossible to get, but that is not the case. The turning point arrived in 1995 when Peter Shor [5] and Andrew Martin Steane [6] independently demonstrated the feasibility of Quantum Error Correction (QEC).
In order to explain the basics of this field and to highlight its differences concerning classical error correction, the easiest example of the quantum error correction approach will be discussed in what follows, being bit flip the only considered source of the noise.

Bit-Flip error correction protocol

Encoding Step
The easiest error correction approach to fight bit-flip noise consists in emulating the classical procedure explained above: the information of a qubit is encoded in three physical qubits, giving rise to a logical qubit. This first part, known as the encoding step [7], can be accomplished using two CNOT gates, as shown in Fig. 2. To give a clearer idea of how it works, let us suppose that the first qubit is in the |1⟩ (|0⟩) state: this means that both the CNOT gates will (not) act on the respective target qubits so that each of them will be in |1⟩ (|0⟩) state. These imply, of course, that any linear combination is transformed as we needed, i.e., α|0⟩ + β|1⟩ → α|000⟩ + β|111⟩. This technique is known as Error Correction Code and relies on preserving information by entangling one qubit with multiple spare qubits, so they are all in the same state. If any of the qubits is corrupted by its interaction with the environment, the error correction code can use the other qubits to “fix” it back into the proper state.

Fig. 2— A circuit encoding the generic qubit state |ψ⟩ into the 3-qubit code state, using two CNOT gates and two other qubits each initially in the state |0⟩. The original qubit is the first qubit in the diagram, and the two spares are the second and third.

One could think this encoding process would result in a violation of the no-cloning theorem, but this is not the case since a clone of the input state would mathematically correspond to (α|0⟩ + β|1⟩)⊗³, i.e.
α³|000⟩ + α²β(|001⟩ + |010⟩ + |100⟩) + αβ²(|110⟩ + |101⟩ + |011⟩) + β³|111⟩.

Syndrome measurement step
The next action is now to check if any of the qubits have been flipped. To do that, we need to have access to their parity, which means verifying whether or not they are in the same quantum state. This process is called the syndrome measurement step.

Fig. 3— Circuit to measure the parity of the three physical qubits. The encoded state may or may not have been corrupted by a single bit flipping. Two ancillary qubits (the last two in the figure) have been coupled to the codeword. After the CNOT gates have acted, each ancillary qubit is measured to collect information about the parity of physical qubits.

We, first of all, assume that no more than one qubit has been flipped, which is a reasonable approximation if the error rate ϵ is small (i.e. ϵ < 1/2). In this context, for a generic state α|000⟩ + β|111⟩, the possible outcome states one could have are: an uncorrupted (no bit-flip occurred) and three corrupted,

• α|000⟩ + β|111⟩ — uncorrupted;
• α|100⟩ + β|011⟩ — corrupted, qubit 1 flipped;
• α|010⟩ + β|101⟩ — corrupted, qubit 2 flipped;
• α|001⟩ + β|110⟩ — corrupted, qubit 3 flipped.

As explained in the introductory part, in the case of classical bits, to determine if one of the bits is flipped, we have to look at them; on the contrary, quantum-mechanically, a measurement would lead to a collapse of the wave function, destroying the coherent superposition completely. This obstacle could again lead to the wrong conclusion that quantum error correction is unfeasible. The secret final ingredient for this quantum error correction recipe to work is the addition of two ancillary qubits: coupling those with the codeword qubits and measuring only the ancillary ones would give us enough information to determine which syndrome the state is in, without destroying the coherent superposition (Fig. 3). This is the key to the indirect detection of errors preserving the potential to achieve quantum advantage. Indeed, the two ancillary qubits, having two CNOT gates each, will not be entangled with any part of the logical qubit. In particular, if the first (second) ancillary qubit is in a |0⟩ state, the first and second (first and third) qubits are in the same state; otherwise, they are in a different state. Using this information and assuming that only one physical qubit could have been corrupted, using Table 1, we can easily deduce which qubit must be corrected.

Table 1 — Results of measurement of the ancillary qubits states for the different syndromes of the codeword.

It is worth noticing that other parity measurements could be used to achieve the same result. For example, it would be equivalent to measure first-second and second-third qubits parity, keeping in mind that a new table of truth must be built.

Correction step
Once the parity measurements have been obtained, one can perform the third part of the bit-flip code: the correction step. It is now time to interpret the syndrome measurement results to uniquely determine if any physical qubit flipped and which of them did. In Table 1 it is shown how to deduce which qubit has been corrupted and needs to be fixed, combining the result of the two parity measurements. This can be translated in the correction circuit shown in Fig. 4.

Fig. 4— Multi-controlled NOT gates are applied to the codeword. If the ancillary qubits were both found in a |1⟩ (|0⟩) state, the first (third) codeword qubit is flipped, if the first were found in |1⟩ while the second were found in |0⟩ the second codeword qubit is flipped.

Up to now, we have assumed for simplicity that the system's state has had a qubit flipped with probability one. However, this is not true: as previously pointed out, errors in quantum circuits can arise continuously from zero, and we are instead concerned with the situation where the error rate is small (otherwise, we cannot error correct). This means that our initial state |ψ⟩ changes as |ψ⟩→ [1+ϵ₁X₁+ϵ₂X₂+ϵ₃X₃]|ψ⟩.
Being the error rate ϵₖ small, the probability that a corrupted state is detected is also small, so the most likely situation is that no correction is needed. Nevertheless, there is still a non-zero probability that the projection occurs on one of the corrupted syndromes. This might seem to pose a problem, but this is not the case since the corrupted state is precisely known and can be effectively corrected by returning it to the uncorrupted state. This means that quantum error correction is feasible, even though quantum errors have a continuous nature, thanks to the fact that corrupted states are projected on one of a discrete set of states, which can be corrected if necessary.

Other more complex error correction protocols exist, involving more codeword qubits and allowing to fight phase flips, such as Steane’s Error Correction Code [8] or Shor’s nine qubits code [9]. Anyway, we decided to keep these out of this discussion having this article the aim of giving some basic elements about QEC and, in particular, bit-flip.

At ColibrITD

At ColibrITD, we believe that applying quantum error correction protocols can bring the quantum-advantage era significantly closer. Therefore, we strongly believe that developing algorithms to solve everyday-life use cases is a priority to be ready for the upcoming quantum revolution.

References
[1] N. D. Mermin, Quantum Computer Science: An Introduction (Cambridge University Press, 2007).
[2] P. Young, Quantum error Correction notes (2020).
[3] Quantum Error Correction slides.
[4] Wikipedia contributors, No-cloning theorem, In Wikipedia, The Free Encyclopedia (2022).
[5] P. Shor, Scheme for reducing decoherence in quantum computer memory, Phys. Rev. A 52, 2493 (1995).
[6] A. M. Steane, Error correcting codes in quantum theory, Phys. Rev. Lett. 77, 793 (1996).
[7] Intro to Quantum Software Development, Bit-Flip code.
[8] Intro to Quantum Software Development, Steane’s Error Correction Code.
[9] Quantum Error Correction: Shor's code in Qiskit.