The logical qubit and the correction of quantum errors

18 May 2022

Physical Qubit vs Logical Qubit

As discussed in the previous article, the unit of information processed by a quantum computer is generically called a qubit or quantum bit.

However, for a deeper understanding of the issues involved in building a quantum computer, it is necessary to introduce and distinguish between the concepts of physical qubit and logical qubit.

Within a quantum processor, each physical qubit corresponds one-to-one with the quantum state of a particle or, more generally, a microscopic phenomenon that encodes it. There are various types of physical qubits depending on the encoding technology. Some of the best known examples include superconducting, trapped ion, and photon physical qubits.
The physical qubit is an unstable entity. In fact, any attempt to guide the physical qubit to the desired computations through external actions can cause the quantum state to be altered, nullifying the quality of the encoded information. This tendency toward instability is called decoherence.

To mitigate this problem, multiple physical qubits are made to interact with the aim of maintaining a single quantum state stable over time, on which it is possible to act in a non-destructive manner. A set of physical qubits with this characteristic is called a logical qubit. The logical qubit is a theoretical entity corresponding to the actual unit of quantum information that a quantum processor is able to control, and the number of logical qubits identifies its actual associated computing power. To create the logical qubit, quantum error correction codes are applied, similar to what happens with classical bit transmission errors.

The physical-logical qubit dualism is still unclear at the current state of the art. The fundamental issue to be addressed is the precise estimation of the number of physical qubits needed to create a logical one. This estimate depends, first and foremost, on quantum technology, understood both as technological progress and as the technology used to encode physical qubits. At present, there is no reason to believe that any estimate would be valid for different technologies at the same time. On the contrary, it is reasonable to imagine that systems of different natures would behave very differently in this respect. For example, superconducting physical qubits are much more unstable than trapped ion qubits, although they offer other implementation advantages. Secondly, the complexity of the quantum circuit to be implemented also affects this estimate. The longer the circuit execution time, the longer the logical qubit must remain stable and, consequently, the more physical qubits will be needed for this purpose.

Below is a consideration that may be useful in giving concrete form to what has just been described. The estimate provided is not to be understood as absolute, given the previous observations, but it gives an idea of the orders of magnitude underlying the problem. Following the implementation of the quantum algorithm proposed by Shor proposed in [¹], 14238 logical qubits would be needed to break a 2048-bit RSA key[²]. It is suggested that each logical qubit corresponds to 1583 physical superconducting qubits, resulting in the breaking of RSA-2048 using approximately 20 million physical qubits. The following section discusses an example of Quantum Error Correction in a basic case in order to provide a meaningful idea of what happens in general. For the mathematical formalism relating to qubits and quantum please refer to the previous article in this section.

Quantum Error Correction

Error correction is also a fundamental technique in classical computing. Sometimes, information encoded in strings of binary variables (bits) becomes corrupted, usually due to alterations during transmission. One possible basic mitigation strategy is to encode each logical bit in sequences of three physical bits[⁴].

$\begin{align*} \bar{0} & \longleftrightarrow 000 \\ \bar{1} & \longleftrightarrow 111 \end{align*}$

Assuming that the simultaneous alteration of more than one physical bit is unlikely within a single sequence of three physical bits, correction is performed by monitoring their status, which in principle should remain identical. If an alteration is detected, the presumed correct value is restored by comparing the three physical bits and following a majority criterion. For example, if a sequence of physical bits $001$ is detected, it would be corrected to $000$ , as the occurrence of $0$ in $001$ is prevalent. This alteration, the only one possible in the classical case, is called a bit flip. In the quantum case, however, the properties of the qubit mean that the (qu)bit flip is not the only alteration to be defended against. To cite one example, consider phase errors, e.g., $|\psi\rangle\rightarrow e^{i\theta}|\psi\rangle$ . However, this article will only deal with the case of bit flip, as it is sufficient to give a meaningful idea of the general case.

An application entirely analogous to the classical error correction technique is not feasible in the quantum case. In quantum computing, classical monitoring of physical bits would result in a measurement of physical qubits, which by its very nature would disturb their state, nullifying any correction efforts. An alternative quantum computing strategy to measurement for bit flip correction is detailed below.

Given a logical qubit $|\psi\rangle$ , the first operation consists of encoding it in a sequence of three physical qubits, each represented by a row of the following circuit.

In a quantum circuit, the bit flip error can be modeled by the presence of an extraneous NOT gate, denoted by $X$ .

Formally, to denote that we are considering at most a bit flip, we have:

$i_j\in\{0,1\}\,\forall j,\qquad \sum_{j=1}^{3}i_j \leq 1.$

Consequently, the qubit $|\bar{\psi}\rangle$ may be altered into one of the following states:

$\begin{align*} |\bar{\psi}_1\rangle & :=\alpha|001\rangle+\beta|110\rangle, \\ |\bar{\psi}_2\rangle & :=\alpha|010\rangle+\beta|101\rangle, \\ |\bar{\psi}_3\rangle & :=\alpha|100\rangle+\beta|011\rangle. \end{align*}$

These issues can be corrected by introducing two auxiliary physical qubits. The idea is to “record the error” on these two qubits, measure them, and act accordingly. The resulting circuit is as follows, where the first two lines correspond to the two auxiliary qubits initialized to $|0\rangle$ .

In order for the circuit to be correct, the action of the NOT gates placed at step $3$ , depending on the result of the measurement in $2$ , must cancel out the alteration modeled at step $1$ , so we must obtain

$\begin{align*} i_1 & =x\cdot|y-1|;\\ i_2 & =x\cdot y;\\ i_3 & =|x-1|\cdot y. \end{align*}$

Consider the case where $|\bar{\psi}\rangle$ is altered to $|\bar{\psi_1}\rangle$ , i.e., $i_3=1,i_1=i_2=0$ . The treatment of the other instances is entirely analogous. Verifying that $x=0, y=1$ , all the above required equalities follow. In fact, the action of the four CNOTs on the state $|00\rangle|\bar{\psi_1}\rangle$ is as follows, from which the conclusion is immediate.

$\begin{align*} \text{I CNOT } && |00\rangle|\bar{\psi_1}\rangle & \longmapsto \alpha|00001\rangle+\beta|10110\rangle\\ \text{II CNOT } && & \longmapsto \alpha|00001\rangle+\beta|00110\rangle\\ \text{III CNOT } && & \longmapsto \alpha|00001\rangle+\beta|01110\rangle\\ \text{IV CNOT } && & \longmapsto \alpha|01001\rangle+\beta|01110\rangle=|01\rangle|\bar{\psi_1}\rangle\implies x=0, y=1 \end{align*}$

A generic 1-qubit alteration can be viewed as a combination of bit flip and phase error, formally:

$|\psi\rangle\longmapsto(\alpha \mathbf{1} + \beta X + \gamma Z + \delta ZX)|\psi\rangle$

However, in order to cover all possible cases, it is also necessary to take into account errors modeled by gates that act by correlating multiple physical qubits with each other. Furthermore, the assumption that the probability of having more than one error in a sequence of three physical qubits is negligible is not realistic given the current state of technology. These reasons underlie the estimate of the number of physical qubits per logical qubit reported in the previous section.

[ 1 ] Gidney, Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits , 2019.

[ 2 ] This is not an optimal solution from this point of view. For example, in [3], the algorithm presented would rely on 4099 logical qubits, but this is a trade-off to mitigate the overall computational cost of the algorithm in terms of quantum gates.

[ 3 ] Beauregard S., Circuit for Shor’s algorithm using 2n+3 qubits, Quantum Information and Computation , Vol. 3, No. 2, 175-185, 2003.

[ 4 ] The physical bit-logical bit dualism is analogous to what was discussed earlier for qubits.

This article is part of a series of contributions by the Telsy Cryptography Research Group dedicated to quantum computing and its implications for cryptography. For other articles, please refer to the index of the section.

For other articles related to quantum and cryptography, please refer to the relevant categories in the blog.

The authors

Edoardo Signorini, graduated in Mathematics with a curriculum in cryptography at the University of Trento, in 2020 carried out the Master’s thesis in the field of Post-Quantum Cryptography (PQC) at Telsy. He currently holds the role of cryptographer within the Telsy research group and carries out an industrial research doctorate in Pure and Applied Mathematics at the Politecnico di Torino. His activity focuses on PQC research and on the analysis and development of cryptographic protocols.

Francesco Stocco, a master’s degree in Mathematics at the University of Padua and the Université de Bordeaux attending the course of study “Algebra Geometry And Number Theory” (ALGANT), joined the Telsy research group in Cryptography at end of 2020 focusing in particular on issues related to quantum technologies.