# Presentation: 035260

## Codeword stabilized quantum codes

- 11111

- arXiv:0708.1021

- (CWS codes for short)

- Graeme Smith

- IBM TJ Watson Research Center

- Joint with:	  Andrew Cross
- 			  John Smolin
- 			  Bei Zeng

- See also: arXiv:0803.3232

## Venn Diagram

- All codes

- CWS

- stabilizer

- classical

## Outline

- Quantum Codes
- CWS Codes (Graph+Classical Code = Quantum Code)
- Error Correction Conditions
- Some Examples
- Encoding Circuits

## Definition:  A Quantum Error Correcting Code is a	
			  		subspace of                .  “n qubits”

Messages are vectors in 	    dimensional space.

						dimensions.

Corrects t errors if can recover original state after noise acts on t of the qubits.

Goal:  Large K, large t, small n.

- Definition:  A Quantum Error Correcting Code is a
- 			  		subspace of                .  “n qubits”
- Messages are vectors in 	    dimensional space.
- 						dimensions.
- Corrects t errors if can recover original state after noise acts on t of the qubits.
- Goal:  Large K, large t, small n.

- Quantum Codes

## The Pauli Group

- Pauli group on n qubits:

- Weight = # of nonidentity factors

- These form a basis for the set of quantum errors.

## Distance of a Code

- Might as well just worry about the Paulis
- Minimum distance d: Lowest weight Pauli that (nontrivially) maps the code to itself.
- ((n,K,d))
- Can detect d-1 errors
- Can correct 						errors.

## Stabilizer/Additive Codes

- Let S be an abelian subgroup of n-bit Paulis
- |S| =
- Let
- Gives an ((n,     ,d)) code
- We call it [n,k,d]

## Stabilizer Codes are...

- Easy to find (cf GF(4))
- Easy to encode
- Like classical linear codes
- Easy to think about
- Suboptimal --- ((5,6,2))  circa. ‘97

## Nonadditive Codes

- Rains, Hardin, Shor, Sloane ‘97--- ((5,6,2))
- Rains  
- Smolin, S., Wehner ’07
- 
- Embarrassing to only have distance 2.

## ((9,12,3))‏

- Our work was inspired by the ((9,12,3)) code of
- Yu, Chen, Lai and Oh quant-ph/0704.2122.
- This was the first nonadditive quantum code with
- distance > 2 that outperforms any known additive
- code (and even any *possible *additive code).

## Codeword Stabilized Codes

- Ingredient 1:  A graph state
- Ingredient 2: A Classical Code

## What is a Graph State?

- A graph state is the +1 eigenvector of a maximal abelian subgroup of the Paulis.
- Generators: each has a single X and Z's on the nodes to which it’s connected.

- 1

- 2

- 3

- 4

- 5

*XIIII*

*IXZZI*

*IZZXZ*

*IZXZZ*

*IIZZX*

## Codeword Stabilized Codes

- Ingredient 1: Graph state
- Ingredient 2:  Classical code
- Basis for our Code:
-  with

## X-Z rule (lemma)‏

- On a graph state X errors are equivalent to (possibly multiple) Z errors.
- We call these the *induced errors*.

*S**i* has only one *X* on bit *i*  so the *X*'s cancel
- This defines Cl(E)

## X-Z rule

## Error detection conditions 

- Since all induced errors are *Z's, *things are essentially classical

- (degeneracy)‏

## Example: [5,1,3] Stabilizer

*XZZXI*
*IXZZX*
*XIXZZ*
*ZXIXZ*

*XXXXX   *logical X
*ZZZZZ   *logical Z

- Generators of the stabilizer

- Can be made into a CWS code by adding in
- XXXXX to the stabilizer, and using 00000 and
- ZZZZZ as the codeword operators

## On a cycle

- To correct single errors, need to detect double errors

- If the codewords are
- 00000 and 11111 a
- nondetectable error would
- have to be weight 5

- The X-Z rule tells us all single errors on
- the ring are weight 1, 2, or 3

- We need one weight 3 and one weight 2

- But the only weight 2 errors are nonadjacent

*Z*

*Z*

*Z*

*Z*

*Z*

- these cancel

## Example: ((5,6,2)) Rains, Hardin, Shor, Sloane code

- “The symmetries discussed above generate a group of order 640.  There is
- an additional symmetry which can be described as follows:
- First, permute the columns as k->k^3, that is exchange qubits 2 and 3.
- Next, for each qubit negate one of the Pauli matrices and exchange
- the other two, where the Pauli matrices negated are Z, Y, X, X, Y, respectively.
- This increases the size of the symmetry group to 3840.  This group acts
- as the permutation group S5 on the qubits.  This is the full group of symmetries
- of the code.  That is, the full subgroup of the semidirect product of S5 and
- PSU25 that preserves the code [10].”
- 						!?

## ((5,6,2)) code

- 00000
- 11010
- 01101
- 10110
- 01011
- 10101

- Since weight 3 induced errors are adjacent, the weight can't change by 3
- so none of these can be transformed into 00000.
- Since weight 2 errors are non-adjacent, they can't be transformed amongst
- each other.

## ((9,12,3))‏

- 9-cycle

## ((10,18,3))‏

- 10-cycle

- Linear programming bound is ((10,24,3))‏

- If cycles are so great,
- why not a bigger one?

## ((10,20,3))‏

- Linear programming bound is ((10,24,3))‏

- If one cycle is good,
- two must be better

## Big search problem

- For all graphs of size n, search for best classical
- code of a given distance.

- Super-exponential

- Turns out to be quite doable for n up to 10 or maybe 11

- ((10,24,3)) code meeting linar programming bound:
-                                   Yu, Chen and Oh, 0709.1780

## ((10,24,3))‏

- ((10,24,3)) code is unique and
- meets linear programming bound

## Example: Quantum Goethals-Preparata Codes

- Grassl and Rotteler found a systematic family of CWS codes in arXiv:0801.2150
**Idea 1**: Impose large amount of linear structure on the classical code.
- Do this by translating whole stabilizer *codes* rather than stabilizer states.
**Idea 2**:  Construct the code from the (linear part of) the Goethals and Preparata codes.
- The Goethals and Preparata codes are famous nonlinear classical binary codes.
**Result**: ((2^m, 2^(2^m-5m+1), 8))  for m ≥ 6--- three extra qubits.
- (for 64 bit, 35 vs. 32 encoded bits)

## Encoding Circuits

- H

- H

- H

- H

- H

- C

## Encoding Circuits

- H

- H

- H

- H

- H

- C

- {

- }

- Classical

- Encodes Graph State

## Encoding Circuits: [5,1,3]

- H

- H

- H

- H

- H

## Future Work

- Find more codes!
-          Particularly of higher distance
- Generalize to higher dimensions
-           Looi, Yu, Gheorghiu and Griffiths 0712.1979
- Understand strange classical error models
- What are the transversal gates?