Additive Quantum Codes CS191 Project Gilho Lee Madhur Tulsiani email lghman postech ac kr Department of Chemistry Pohang University of Science Technology South Korea email madhurt cs berkeley edu Electrical Engineering Computer Science University of California Berkeley Abstract We study quantum error correction with emphasis on additive codes We present the uncorrelated error model and paradigm for construction of additive codes We also review constructions of non additive codes using additive codes I I NTRODUCTION Physicists and engineers are now learning and developing techniques to use properties of quantum systems into computational domains Quantum computers show exponential speedups over classical computational models However implementations of quantum systems are highly error prone The limitations on qubit sources and environmental decoherence make the development of efficient and robust quantum codes a necessity for realizing quantum computers In this project we study additive codes also called stabilizer codes which have been an important class of codes for most applications Section II presents the error model that we consider Section III gives an overview of the error correction model and information theoretic bounds on quantum error correcting codes Section IV describes the construction of additive codes and section V gives a method to construct non additive codes from additive ones II T HE Q UANTUM E RROR M ODEL A Origin of error The phenomenon of entanglement makes quantum computer different from ordinary classical computers The non locality which is a very odd concept in classical world is the source of the power of quantum computation That is a good side of entanglement but there are some undesirable effects also What we want to talk about from now on is how to overcome this defect The problem is that our quantum system is inevitably in contact with a much larger system which is its environment That means our system e g qubits can not be completely unentangled from environment e g external magnetic field Even if the universe which is composed with the system and its environment is well behaved which means the evolution of the universe is unitary because we are interested only in the system and we can see only the system it seems to behave unexpectedly which means the evolution of the system is non unitary In other words some unexpected noise may come to the system from environment because the environment is not controllable and predictable We call this phenomenon decoherence In the point of view of the information stored in the system qubits that information leaks out to the environment irrevocably Now we can say that the noise or leaking information is an error occurring in the system B Single qubit errors First we will give an example describing how the one qubit errors occur And then we will construct the general n qubit error model Let s say without loss of generality that the state of environment is 0 i Then most generally the unitary evolution U will act on the universe as U 0 i 0 ienv 0 i e00 ienv 1 i e01 ienv U 1 i 0 ienv 0 i e10 ienv 1 i e11 ienv Generally we have one qubit state as i 0 i 1 i U acts on this as U 0 i 1 i 0 i 0 i e00 i 1 i e01 i 0 i e10 i 1 i e11 i 1 0 i 1 i e00 i e11 i 2 1 0 i 1 i e00 i e11 i 2 1 1 i 0 i e01 i e10 i 2 1 1 i 0 i e01 i e10 i 2 I i eI i Z i eZ i X i eX i Y i eY i where we take Y XZ i Y We interpret I i as no error X i as a bit flip error Z i as a phase flip error and Y i as both bit and phase flips acting simultaneously However this classification should not be considered literally because eI i eX i eY i eZ i don t need to be mutually orthogonal and therefore these four alternatives may not be distinguishable But this classification is quite intuitive for constructing the error model In our error model we treat single qubit error as one of four pauli operators I X Yor Z C Uncorrelated errors We will now generalize our one qubit error model to n qubit error model We assume that errors on different qubits are independent of each other This means these are uncorrelated errors In other words the decoherence of each qubit is uncorrelated with the decoherence of any other qubit as all qubits interact with seperate reservoirs This is called Independent Qubit Decoherence IQD model In our discussion we shall stick to the IQD model Informally speaking there are no such errors like the C NOT gate which acts on two qubits and uncorrelated errors can be expressed by tensor product of one qubit gates Then the error of each qubit can be expressed by I X Y or Z Generally errors of n qubit can be described as Ea M1 M2 Mn where each Mi is one of the four Pauli operators We define weight t of Ea as the number of non identity Pauli operators such as X Y or Z And we also define the subset E Ea of errors which have weight up to t If we are able to correct the errors in the subset E we say that we can correct t errors D Correlated errors The IQD model can however be violated in some situations This model is valid when the spatial separation of qubits is larger than the correlation length of the reservoirs and validity of the IQD model depends on the physical realization models of quantum computer When this condition isn t met the error of each qubit is correlated For example 8 develop burst correcting quantum codes to correct spatially correlated qubit errors These codes are quantum analogs of classical burst correcting codes which correct spatially continuous errors III E RROR C ORRECTION M ODEL A The scheme for error correction Data Encoder h j Ea i i Ca ij Error Fig 1 Now we will find codewords which can store the information of original data and durable against the errors For example with the following quantum error correcting code we can correct one bit flip error In that error correcting code we encode 0 i to 000 i and 1 i to 111 i These 000 i and 111 i are codewords If we have one qubit state of data as i a 0 i b 1 i we encode it into three qubit state 0 i a 000 i b 111 i Suppose the second qubit is flipped The corrupted state will be 00 i a 010 i b 101 i When we measure Z1 Z2 I3 and I1 Z2 Z3 we will get eigenvalues as 1and 1 Then we can infer that the error was secondqubit bit flip and we can recover 00 i back into 0 i by acting second qubit bit flip I1 X2 I3 In this case we call the eigenvalues 1 of …