Interest in quantum computing has grown rapidly following the discovery by Peter Shor in 1994 of a polynomial-time algorithm for integer factorisation on a quantum computer. In a classical computer a sequence of N binary digits defines one specific configuration among the 2N possible values. However, in a quantum computer a collection of N “qubits” has a state function (in ‘ket’ notation) ket(ψ) in a Hilbert space, which can be in a superposition of all 2N possible values:
A basic theorem in quantum information theory states that it is impossible to clone a quantum state. Since this implies that it is not possible to copy quantum information, it was initially believed that error-correction would be impossible on a quantum computer. However, in 1995 Shor showed that it was possible to encode quantum information in such a way that errors can be corrected, assuming an error model in which errors occur independently in distinct qubits. Following this discovery, a class of quantum error-correcting codes known as stabiliser codes were developed. In 1996, Calderbank, Rains, Shor, and Sloane showed that stabiliser codes can be represented in terms of additive codes over finite fields. This remarkable result reduces the problem of constructing fault-tolerant encodings on a continuous Hilbert space to that of constructing certain discrete codes, allowing the use of many of the tools developed in classical coding theory.
The current Magma package for quantum codes deals exclusively with finite field representations of stabiliser codes. It is important to keep in mind that, although a quantum code is represented by a code over a finite field, an actual quantum code is in fact a totally different object. The reduction of the problem of continuous errors on a Hilbert space to a problem employing a discrete finite field representation is achieved by confining attention to a finite error group. An element of the error group, acting on the N qubits, is expressed as a combination of bit flip errors, designated by the operator X, and phase shift errors, designated by the operator Z (as well as an overall phase factor that will be ignored here):
The Magma package also supports non-binary quantum codes, which are obtained by generalising from the binary case in a natural way. For quantum codes based on qubits over GF(q), the compact format in GF(q2) will be w = a + λb, where λ is a fixed element of GF(q2) which defines the GF(q2) representation for quantum codes over GF(q).
A symplectic inner product is defined on the group of errors in its representation as a set of GF(q)-vectors. For vectors in extended format this is defined by
A quantum stabiliser code is defined by an abelian subgroup of the error group. In the context of its finite field representation this translates to a self-orthogonal additive code under the symplectic inner product. So a quantum stabiliser code Q is defined by a symplectic self-orthogonal additive code S, which is (with some redundancy) termed the stabiliser code of Q. The error-correcting capability of a code is determined by the set of errors which cannot be detected. For classical linear codes these undetectable errors are precisely the non-zero codewords of the code, while for a quantum code the undetectable errors are given by the set S⊥ \ S, where S⊥ is the symplectic dual of S.
The most important measure of the ability of a quantum code to correct errors is its minimum weight; that is, the minimum of the weights of the words of S⊥ \ S. An exception to this definition occurs in the case of quantum codes having dimension zero, which are defined by symplectic self-dual stabiliser codes. These are termed “self-dual quantum codes” and are defined to have a minimum weight equal to the (classical) minimum weight of their stabiliser code.
A quantum code of length n over GF(q) is defined in terms of a symplectic self-orthogonal stabiliser code, which is given either as a length n additive code over GF(q2) (compact format) or as a length 2n additive code over GF(q) (extended format). If Q is a quantum code with generator matrix G1 in compact format, and generator matrix G2 = (A | B) in extended format, then
An [n,k] symplectic self-orthogonal linear code over GF(q2) will generate an [[n,n/2 – k]] quantum stabiliser code. A (compact format) additive symplectic self-orthogonal code C over GF(q2) will give a quantum code of the same length and “dimension” logq(N), where N is the number of code words in C.
The basic construction takes an additive code S which is self-orthogonal with respect to the symplectic inner product and returns the quantum code defined by S. The usual constructions for producing new codes by modifying an existing code are provided: direct sum, extension, puncture, shorten. Given linear binary codes C1 and C2 such that C2 is a subcode of C1, the construction due to Calderbank, Shor, and Steane may be used to construct a quantum code.
Cyclic quantum codes are those having cyclic stabiliser codes. The conditions which generating polynomials must satisfy in order to yield symplectic self-orthogonal stabiliser codes have been published by Calderbank, Rains, Shor, and Sloane. A number of functions are provided to construct both cyclic quantum codes and quasicyclic quantum codes.
Given a quantum code, functions are provided to return the stabiliser group and various versions of the quantum error group. The error group is an extraspecial p-group and so is returned in the form of a pc-group. The stabiliser group and normaliser matrix can also be accessed.
An [[n,k]] quantum stabiliser code Q is said to be a best known [[n,k]] quantum code (BKQC) if C has the highest minimum weight among all known [[n,k]] quantum codes. Magma currently has a database of binary quantum codes, though it should be noted that these codes are considered to be over the alphabet GF(4), not GF(2). The database for codes over GF(4) currently contains constructions of all best known quantum codes of length 35, including self-dual quantum codes up to length 35. Quantum codes of length up to 12 are optimal, in the sense that their minimum weights meet the upper bound. Thus, the user has access to 665 best-known binary quantum codes. The database was compiled by M. Grassl (Karlsruhe).
The weight distribution of a quantum code Q consists of three separate distributions:
For a quantum code Q with stabiliser code S, the weights of the undetectable errors are the weights of the codewords in S⊥ \ S. The weight distribution function for a quantum code returns each of these distributions as a separate value. The value returned by the minimum weight function is the minimum weight of the codewords in S⊥ \ S. The default algorithm is based on the minimum weight algorithm for classical linear codes.
Automorphisms acting on a quantum code are a slight generalisation of those which act on the underlying additive stabiliser code. Thus, automorphisms comprise a permutation action on the columns of a stabiliser code, combined with a monomial action on the individual columns which permute the values. The automorphism group of a length n additive stabiliser code over GF(4) is a subgroup of Z3 ≀ Sym(n) of order 3×n!. However, the automorphism group of the quantum code it generates is a subgroup of Sym(3) ≀ Sym(n) of order 3!×n! because of the more general action on the values in the columns. At present the computation of the automorphism group is restricted to binary quantum codes.
The QECC machinery includes code that allow the construction and analysis of quantum Hilbert spaces. Such a space is constructed from a complex field and an integer giving the number of qubits which the space is to model. A set of basic operators allow new states to be constructed from existing states. A set of functions are provided that allow the user to determine probabilities of quantum states. For example, given a binary vector v of length equal to the number of qubits in the quantum state e, a function returns the probability of the basis state corresponding to v being returned as the result of a measurement on e. A further function returns the probability distribution of a given quantum state. A small set of unitary transformations on quantum states are available. These include bit flip, phase flip, controlled not, and the Hadamard transformation.
A number of groups working in the field of Quantum Information Theory make heavy use Magma in their work. A very incomplete list includes:
Some relevant publications up to 2010 that cite Magma may be found at