Quantum Codes and Computation

Alan Bojić

Basic principles of quantum computer ensure more computing power than the principles of classical computers. Quantum computers use quantum mechanical effects such as entanglement and superposition to speed up computing processes compared to classical computers. If the quantum computers one day becomes a commercially available product, then it is very important to have a converter that will convert the source code of programming languages for classical computers into source code of programming languages for quantum computers because it will speed up the translation process and ensure that developers of classical computers can develop programs for quantum computer using programming languages for classical computers. In this paper, the basic approach to automatic conversion of the source code for classical computer into a source code of quantum computer is introduced.

Hao Chen

Abdelhamid Awad Aly Ahmed, Sala

It is conjectured that quantum computers are able to solve certain problems more \nquickly than any deterministic or probabilistic computer. For instance, Shor's algorithm \nis able to factor large integers in polynomial time on a quantum computer. \nA quantum computer exploits the rules of quantum mechanics to speed up computations. \nHowever, it is a formidable task to build a quantum computer, since the \nquantum mechanical systems storing the information unavoidably interact with their \nenvironment. Therefore, one has to mitigate the resulting noise and decoherence \neffects to avoid computational errors. \nIn this dissertation, I study various aspects of quantum error control codes - the key component of fault-tolerant quantum information processing. I present the \nfundamental theory and necessary background of quantum codes and construct many \nfamilies of quantum block and convolutional codes over finite fields, in addition to \nfamilies of subsystem codes. This dissertation is organized into three parts: \nQuantum Block Codes. After introducing the theory of quantum block codes, I \nestablish conditions when BCH codes are self-orthogonal (or dual-containing) \nwith respect to Euclidean and Hermitian inner products. In particular, I derive \ntwo families of nonbinary quantum BCH codes using the stabilizer formalism. I study duadic codes and establish the existence of families of degenerate quantum \ncodes, as well as families of quantum codes derived from projective geometries. \nSubsystem Codes. Subsystem codes form a new class of quantum codes in which \nthe underlying classical codes do not need to be self-orthogonal. I give an \nintroduction to subsystem codes and present several methods for subsystem \ncode constructions. I derive families of subsystem codes from classical BCH and \nRS codes and establish a family of optimal MDS subsystem codes. I establish \npropagation rules of subsystem codes and construct tables of upper and lower \nbounds on subsystem code parameters. \nQuantum Convolutional Codes. Quantum convolutional codes are particularly \nwell-suited for communication applications. I develop the theory of quantum \nconvolutional codes and give families of quantum convolutional codes based \non RS codes. Furthermore, I establish a bound on the code parameters of \nquantum convolutional codes - the generalized Singleton bound. I develop a \ngeneral framework for deriving convolutional codes from block codes and use it \nto derive families of non-catastrophic quantum convolutional codes from BCH \ncodes. \nThe dissertation concludes with a discussion of some open problems.

Isaac L. Chuang, Andrew W. Cross

Quantum computers have been shown to efficiently solve a class of problems for which no efficient solution is otherwise known. Physical systems can implement quantum computation, but devising realistic schemes is an extremely challenging problem largely due to the effect of noise. A quantum computer that is capable of correctly solving problems more rapidly than modern digital computers requires some use of so-called fault-tolerant components. Code-based fault-tolerance using quantum error-correcting codes is one of the most promising and versatile of the known routes for fault-tolerant quantum computation. This dissertation presents three main, new results about code-based fault-tolerant quantum computer architectures. The first result is a large new family of quantum codes that go beyond stabilizer codes, the most well-studied family of quantum codes. Our new family of codeword stabilized codes contains all known codes with optimal parameters. Furthermore, we show how to systematically find, construct, and understand such codes as a pair of codes: an additive quantum code and a classical (nonlinear) code. Second, we resolve an open question about universality of so-called transversal gates acting on stabilizer codes. Such gates are universal for classical fault-tolerant computation, but they were conjectured to be insufficient for universal fault-tolerant quantum computation. We show that transversal gates have a restricted form and prove that some important families of them cannot be quantum universal. This is strong evidence that so-called quantum software is necessary to achieve universality, and, therefore, fault-tolerant quantum computer architecture is fundamentally different from classical computer architecture. Finally, we partition the fault-tolerant design problem into levels of a hierarchy of concatenated codes and present methods, compatible with rigorous threshold theorems, for numerically evaluating these codes. The methods are applied to measure inner error-correcting code performance, as a first step toward elucidation of an effective fault-tolerant quantum computer architecture that uses no more than a physical, inner, and outer level of coding. Of the inner codes, the Golay code gives the highest pseudothreshold of 2 × 10-3. A comparison of logical error rate and overhead shows that the Bacon-Shor codes are competitive with Knill's C 4/C6 scheme at a base error rate of 10 -4. (Copies available exclusively from MIT Libraries, Rm. 14-0551, Cambridge, MA 02139-4307. Ph. 617-253-5668; Fax 617-253-1690.)