Evolving quantum circuits

Abstract

We develop genetic algorithms for searching quantum circuits, in particular stabilizer quantum error correction codes. Quantum codes equivalent to notable examples such as the 5-qubit perfect code, Shor’s code and the 7-qubit color code are evolved out of initially random quantum circuits. We anticipate evolution as a promising tool in the NISQ era, with applications such as the search for novel topological ordered states, quantum compiling and hardware optimization.

Appendices

Appendix A: Brief review of QECC stabilizer codes

The main objective of a QECC is to protect k data-qubit registers from a set of errors $\mathcal {E}$. By protection, it means that the code must be able to detect and correct any error in $\mathcal {E}$. Figure 16 summarizes the general structure of a [[n, k, d]] stabilizer error correction code. It is divided into three stages: encoding, syndrome extraction and correction. We now describe each stage in detail.

Fig. 16

Generic circuit of a [[n, k, d]] stabilizer error correction code. a A data register $\vert \psi \rangle _D$ is entangled with $n-k$ redundancy qubits via an EC to form the logical state $\vert \psi \rangle _L$. b After a potential error E occurs, ancilla qubits are attached to $\vert \psi \rangle _L$, and m syndrome measurements $P_i$ are performed. The result of the measurements produces the syndrome. c With the syndrome, one queries the syndrome table, and the appropriate correction R is appointed and applied. This process is represented by the Decoder gate. The double-line channels symbolize classical communication

On the encoding stage, Fig. 16a, a k-qubit data-state $\vert \psi \rangle _D$ is entangled with $m = n-k$ auxiliary qubits via an EC forming a n-qubit logical state $\vert \psi \rangle _L$. The EC defines the set of codewords $\mathcal {C} = \lbrace \vert c_i\rangle _L\rbrace _i$, which specify how the other stages of the code function. In general, $\vert \mathcal {C}\vert = 2^k$. For example, for $k = 2$, the encoding stage maps $\lbrace \vert 00\rangle ,\vert 01\rangle ,\vert 10\rangle ,\vert 11\rangle \rbrace$ into four mutually orthogonal codewords in an expanded Hilbert space.

During syndrome extraction, errors are detected by performing m syndrome measurements as shown in Fig. 16b. The codewords define a group of common stabilizers spanned by m generators [51]. Let $\mathcal {P} = \lbrace P_i \rbrace$ be a set of generators for the common stabilizer group of $\mathcal {C}$. We refer to the elements of $\mathcal {P}$ as syndrome operators. It follows that syndrome operators satisfy the following properties [123]:

• 1. $\mathcal {P} \subseteq \mathcal {G}_n$;

• 2. $P_i\vert \psi \rangle _{L,j} = +1\vert \psi \rangle _{L,j} \, \forall \, i,j$;

• 3. $[P_i,P_j] = 0 \, \forall \, i,j$,

where $\mathcal {G}_n$ is the general n-qubit Pauli group defined as the set composed of all tensor product combinations of the elements of $\mathcal {G}_1 = \lbrace \pm I,\pm iI, \pm X,\pm iX, \pm Y,\pm iY, \pm Z,\pm iZ \rbrace$. Property 2 ensures that the syndrome measurements do not further disturb the damaged logical state, and property 3 allows one to perform measurements in any order.

Let $E \in \mathcal {E}$ be an error that occurred between the encoding and syndrome extraction stages. The effect of each syndrome measurement is to map $E\vert \psi \rangle _L$ into the superposition

$$\begin{aligned} E&\vert \psi \rangle _L\vert 0\rangle _{A_i} \rightarrow \nonumber \\&\frac{1}{2}\left[ (I+P_i)E\vert \psi \rangle _L\vert 0\rangle _{A_i} + (I-P_i)E\vert \psi \rangle _L\vert 1\rangle _{A_i}\right] . \end{aligned}$$

(A1)

Note that E necessarily either commutes or anti-commutes with $S_i$ since $E,P_i \in \mathcal {G}_n$. If E and $P_i$ commutes (anti-commutes), the final state is unequivocally $E\vert \psi \rangle _L\vert 0\rangle _{A_i}$ ($E\vert \psi \rangle _L\vert 1\rangle _{A_i}$). Therefore, each syndrome measurement can be understood as a deterministic measurement of the state with the outcome revealing whether the error commutes or anti-commutes with the syndrome operator. At the end of the syndrome extraction stage, one is left with a binary syndrome string of length m whose i-th entry encodes whether $P_i$ and E commute or not.

Given $\mathcal {E}$ and $\mathcal {P}$, one builds the so-called syndrome table relating each error to the corresponding syndrome string it generates. As an illustration, Table 2 shows the syndrome table for the 3-qubit code with $\mathcal {P} = \lbrace Z_1Z_2,Z_2Z_3\rbrace$, and considering errors with weight one on three qubits. Note that the syndromes for $Z_i$ are composed only of zeros, which is the same syndrome for $E = I$ since the identity commutes with any operator. These errors are classified as undetectable [51] as they are not distinguishable from I.

Table 2 3-qubit code syndrome table for single-qubit errors

Finally, in the correction stage, one prescribes an operator R for which

$$\begin{aligned} RE\vert \psi \rangle _L = \vert \psi \rangle _L. \end{aligned}$$

(A2)

Since Pauli operators square to the identity, R is, in principle, identical to the appointed error guided by the syndrome table. The decoder gate of Fig. 16c is a crosscheck, performed in a classical computer, between the extracted syndrome and its related error on the syndrome table. This scheme functions perfectly for non-degenerate codes, where a one-to-one correspondence between errors and syndromes exists. On the other hand, for degenerate codes, multiple errors can produce the same syndrome. For a successful correction, all two-on-two combinations of errors with the same syndrome must stabilize all codewords. Consider an arbitrary correction code with codewords $\lbrace \vert c_i\rangle _L\rbrace$, and let $\lbrace E_i \rbrace$ be a set of errors with the same syndrome. One requires

$$\begin{aligned} E_iE_j\vert c_k\rangle _L = +\vert c_k\rangle _L \, \forall i,j,k \end{aligned}$$

(A3)

for $\lbrace E_i \rbrace$ to be correctable. If the above condition is met, applying any element of $\lbrace E_i \rbrace$ will restore the logical state even though it is impossible to single out which error actually took place. If for some pairing $E_iE_j$ Equation (A3) is not satisfied, the set $\lbrace E_i \rbrace$ is classified as uncorrectable, since it is impossible to decide the proper correction operation.

Appendix B: Generating sets of codewords

Given an EC, applying it to the $\vert 0\rangle ^{\otimes n}$ state generates a first possible codeword $\vert c_0\rangle$. Recollecting that codewords form a set of mutually orthogonal states, we create a method to build $2^{n}-1$ mutually orthogonal states to $\vert c_0\rangle$ which will give us a set of $2^n$ potential codewords (since we work with qubits, a n-dimensional Hilbert space is spawned by $2^n$ states) $\lbrace \vert c_i\rangle \rbrace$. In possession of $\lbrace \vert c_i\rangle \rbrace$, it remains to evaluate the corrigibility degree $\mathcal {C}$ of subsets. To generate states orthogonal to $\vert c_0\rangle$, we find a set of logical $\mathcal {X} \equiv \lbrace \bar{X}_i\rbrace$ operators such that

$$\begin{aligned} \bar{X}_i\vert c_0\rangle&= \vert c_i\rangle \end{aligned}$$

(B1)

$$\begin{aligned} \langle c_i\vert \vert c_j\rangle&= \delta _{ij} \end{aligned}$$

(B2)

$\forall i \in \lbrace 1,\dots ,2^{n-1}\rbrace$.

There is a systematic method to build a particular (non-unique) set $\mathcal {X}$ that satisfies the above equations starting from the computational basis. Consider the n-qubit computational basis. Starting from $\vert \psi _{0,I}\rangle = \vert 0\rangle ^{\otimes n}\,$ (the first subscript 0 refers to $\vert 0\rangle ^{\otimes n}$ and the I subscript stands for the identity), it is straightforward to verify that the logical $\lbrace \bar{X}_{i,I}\rbrace$ operators that take $\vert \psi _{0,I}\rangle$ to the other states of the basis $\vert \psi _{i,I}\rangle$—which are mutually orthogonal by definition—are all the $2^n-1$ tensor product combinations of Pauli letters X and I possessing at least one X. Define $[\bar{X}_I]$ as a $2^n-1 \times n$ matrix whose rows are $\lbrace \bar{X}_{i,I}\rbrace$:

$$\begin{aligned}{}[\bar{X}_I] = \begin{bmatrix} X &{} I &{} I &{}\dots &{} I &{} I\\ I &{} X &{} I &{}\dots &{} I &{} I\\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ I &{} I &{} I &{}\dots &{} I &{} X\\ X &{} X &{} I &{}\dots &{} I &{} I\\ \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots &{} \vdots \\ X &{} X &{} X &{}\dots &{} X &{} X \end{bmatrix}. \end{aligned}$$

(B3)

Notice that $\lbrace \bar{X}_{i,I}\rbrace$ satisfies Eqs. (B1) and (B2). Let $\vert \psi _{0,U}\rangle = U\vert \psi _{0,I}\rangle$, where U is some unitary computation. The operator U transforms each $\bar{X}_{i,I}$ into $\bar{X}_{i,U} \equiv U\bar{X}_{i,I}U^\dagger$ such that

$$\begin{aligned} \langle \psi _{0,U}\vert \bar{X}_{i,U}\vert \psi _{0,U}\rangle&= \langle \psi _{0,I}\vert U^\dagger U\bar{X}_{i,I}U^\dagger U\vert \psi _{0,I}\rangle \nonumber \\&= \langle \psi _{0,I}\vert \bar{X}_{i,I}\vert \psi _{0,I}\rangle \nonumber \\&= 0 \end{aligned}$$

(B4)

$\forall i$. Each $\bar{X}_{i,U}$ is distinct since if $\bar{X}_{i,U} = \bar{X}_{j,U}$ for some i, j, then

$$\begin{aligned} U\left( \bar{X}_{i,I}-\bar{X}_{j,I}\right) U^\dagger = 0. \end{aligned}$$

(B5)

Since $U \ne 0$ and $\lbrace \bar{X}_{i,I}\rbrace$ are different by construction, then forcibly $i = j$. We conclude that $\lbrace \bar{X}_{i,U}\rbrace$ forms a set of logical operators whose elements take $\vert \psi _{0,U}\rangle$ into $2^n-1$ unique mutually orthogonal states $\vert \psi _{i,U}\rangle$. Taking the particular case of U as an EC, $\mathcal {X} = \lbrace \bar{X}_{i,\textrm{EC}}\rbrace$ is the set we seek.

There is a significant computational cost in evaluating the corrigibility degree $\mathcal {C}$ for each subset of $\lbrace \vert c_i\rangle \rbrace$ due to the large number of subsets. To overcome this, we simplify our approach by considering a limited number of subsets. First, we limited ourselves to evolving QECCs with two-dimensional code spaces, which leads to an $O\left( 2^{2n-1}\right)$ number of subsets to consider for each tentative EC (a significant but not sufficient reduction). Second, by appealing to symmetry, we make the heuristic argument that we can fix one of the codewords, as $\vert c_0\rangle$ without loss, and only consider subsets of the form $\lbrace \vert c_0\rangle , \vert c_i\rangle \rbrace$ for $i = 1,\dots ,2^{n}-1$.

Appendix C: Qubit overhead

Let n be the Hilbert space dimension of a QECC. Considering errors as a product of Pauli operators, we express a general error by assigning a Pauli letter for each vector entry of the form $\varvec{E} = (a_1,a_2,\dots ,a_n)$. Define $n_e(n,t)$ as the number of errors with weight t. For $t = 1$, each possible error can be constructed by choosing one of the n entries of $\varvec{E}$ and assigning one of three Pauli letters $\lbrace X,Y,Z\rbrace$. Therefore,

$$\begin{aligned} n_e(n,1) = {n \atopwithdelims ()1} \times 3. \end{aligned}$$

(C1)

For $t = 2$, the reasoning is similar: we choose two entries in n to allocate the errors and, for each entry, we choose one of three Pauli letters. Thus,

$$\begin{aligned} n_e(n,2) = {n \atopwithdelims ()2} \times 3^2. \end{aligned}$$

(C2)

This reasoning holds true for any $t \le n$. Therefore, the general formula for $n_e(n,t)$ is given by

$$\begin{aligned} n_e(n,t) = {n \atopwithdelims ()t} \times 3^t. \end{aligned}$$

(C3)

For error correction, we are interested in detecting and correcting errors with weight up to t. Let s(n, t) denote all possible errors up to weight t, i.e., the number of errors with weight less or equal to t. It follows that

$$\begin{aligned} s(n,t) = \sum _{i=1}^t n_e(n,i) = \sum _{i=1}^t {n \atopwithdelims ()i} \times 3^i. \end{aligned}$$

(C4)

With s(n, t), we can derive the minimum number of qubits necessary for constructing a non-degenerate quantum error correction code capable of handling errors up to a weight t.

The argument goes as follows: if the codewords are made by n qubits, then at most $n-1$ auxiliary ancilla qubits are employed in the syndrome measurement stage. Therefore, the syndrome is a vector with at most $n-1$ binary entries. Since there exist $2^{n-1}$ binary vectors with $n-1$ entries and at least one distinct vector must be assigned to each particular error, there must exist at least as many binary vectors as the number of possible errors for a non-degenerate error correction code to be able to correct all errors up to weight t:

$$\begin{aligned} s(n,t) + 1 \le 2^{n-1} \end{aligned}$$

(C5)

To account for the case in which no errors occurred, 1 is added to the LHS of Equation (C5).

For $t = 1$, it follows

$$\begin{aligned} {n \atopwithdelims ()1} \times 3 + 1 = 3n + 1\le 2^{n-1}. \end{aligned}$$

(C6)

Note that $n = 5$ saturates the inequality (C6), therefore it is of no use to try to build a QECC with less then 5 qubits; non-degenerate 5-qubits codes that correct single-qubit errors are called perfect codes [51, 55] since they have the property of using every available syndrome for 5 qubits.