Quantum Error Correction Joshua Kretchmer Gautam Wilkins Eric Zhou Error Correction Physical devices are imperfect Interactions with the environment Error must be controlled or compensated for One step has probability to succeed p t steps has probability to succeed pt Classical Error Correction Error Model Channels provide description of the type of error Encoding Extra bits added to protect logical bit String of bits codeword Redundancy Error Recovery Recovery operation Measure bits and re set all values to majority vote Classical 3 Bit Code Bit Flip Error Bit flip channel bit is flipped with prob p 1 2 Encoding b 0 0 Error Recovery b b b 000 000 1 p 3 001 p 1 p 2 010 p 1 p 2 100 p 1 p 2 011 p2 1 p 110 p2 1 p 101 p2 1 p 111 p3 Prob unrecoverable error 3p2 1 p p3 3p2 2p3 Problems with QEC No cloning theorem Can t copy an arbitrary quantum state Entanglement Measurement Cannot directly measure a qubit Error syndrome Quantum evolution is continuous Quantum 3 Bit Code Bit Flip Error a 0 b 1 0 0 Encoding Error Channel 0 0 M M Diagnose and Correct Encoding a 000 b 111 Error channel Noise acts on each qubit independently Probability noise does nothing 1 p Probability noise applies x p 1 2 X Decode Quantum 3 Bit Code Bit Flip Error After channel 8 possible results State a 000 b 111 a 100 b 011 a 010 b 101 a 001 b 110 a 110 b 001 a 101 b 010 a 011 b 100 a 111 b 000 Probability 1 p 3 p 1 p 2 p 1 p 2 p 1 p 2 p2 1 p p2 1 p p2 1 p p3 Quantum 3 Bit Code Bit Flip Error After CNOT s 4 possible results State a 000 b 111 00 a 100 b 011 10 a 010 b 101 01 a 001 b 110 11 a 110 b 001 01 a 101 b 010 10 a 011 b 100 11 a 111 b 000 00 Probability 1 p 3 p 1 p 2 p 1 p 2 p 1 p 2 p2 1 p p2 1 p p2 1 p p3 Quantum 3 Bit Code Bit Flip Error Measure 2 ancilla qubits error syndrome Measured syndrome action 00 do nothing 01 apply x to 3rd qubit 10 apply x to 2nd qubit 11 apply x to 1st qubit Designed to correct if there s an error in 1 or no qubits Error in 2 or 3 qubits is an uncontrollable error Quantum 3 Bit Code Bit Flip Error Failing probability pu 3p2 1 p p3 3p2 2p3 O p2 Fidelity success probability 1 pu 1 3p2 Without error correction pu O p Quantum 3 Bit Code Phase Error Random rotation of qubits about z axis Continuous error P ei 0 cos I isin z 0 e i fixed quantity stating typical size of rotation random angle Quantum 3 Bit Code Phase Error Apply H to each qubit at either end of the channel HIH HH I H zH x HPH cos I isin x Same result from bit flip code Fidelity 1 3p2 p sin2 2 2 3 for 1 General Quantum Error Errors occur due to interaction with environment 0 E 1 0 E1 2 1 E2 1 E 3 1 E3 4 0 E4 0 0 1 1 E 0 1 0 E1 0 2 1 E2 1 3 1 E3 1 4 0 E4 General Quantum Error 0 0 1 1 E 1 2 0 0 1 1 1 E1 3 E3 1 2 0 0 1 1 1 E1 3 E3 1 2 0 1 1 0 2 E2 4 E4 1 2 0 1 1 0 2 E1 4 E4 0 0 1 1 0 0 1 1 Z 0 1 1 0 X 0 1 1 0 XZ General Quantum Error 0 0 1 1 E 1 2 1 E1 3 E3 1 2 Z 1 E1 3 E3 1 2 X 2 E2 4 E4 1 2 XZ 2 E1 4 E4 Error basis I X Z XZ L e i L i e L general superposition of quantum codewords i error operator tensor product of pauli operators Correction of General Errors L e i L i e L orthonormal set of n qubit states To extract syndrome attach an n k qubit ancilla a to system perform operations to get syndrome si a 0 a i L i e si a i L i e Measure si to determine i 1 correct for error si a i L i e si a L i e Shor s Algorithm Each qubit is encoded as nine qubits 0 1 1 2 2 1 2 2 000 111 000 111 000 111 000 111 000 111 000 111 Shor s Algorithm Assume decoherence on first bit of first triple becomes 1 2 0 1 1 00 2 0 3 1 11 0 1 0 3 000 2 2 1 0 3 2 2 1 1 2 2 2 1 1 2 2 2 111 000 111 100 011 100 011 Shor s Algorithm Shor s Algorithm 1 0 0 1 1 00 2 0 2 1 0 3 000 111 2 2 1 0 3 000 111 2 2 1 1 2 100 011 2 2 1 1 2 100 011 2 2 3 1 11 No error Z error X error ZX Y error Shor s Algorithm Success Rate Works if only one qubit decoheres If probability of a qubit decohering is p Probability of 2 or more out of 9 decohering is1 1 8p 1 p 8 36p2 Therefore probability that 9 k qubits can be decoded is 1 36p2 k Shor s Algorithm More on decoherence Decoherence probability increases with time Use watchdog effect to periodically reset quantum state Unfortunately each reset introduces small amount of extra error Therefore cannot store indefinitely Steane s Algorithm Basis 1 is 0 1 Also called basis F or flip basis Basis 2 is 0 1 0 1 Also called basis P or phase basis Steane s Algorithm The word 000 0 consisting of all zeroes in basis 1 is equal to a superposition of all 2n possible words in basis 2 with equal coefficients If the jth bit of each word is complemented in basis 1 then all words in basis 2 in which the jth bit is a 1 change sign Hamming Distance The number of places two words of the same length differ Minimum Distance Smallest Hamming distance between any two code words in a code Steane s Algorithm A code of minimum distance d allows d 1 2 to be corrected If less than d 2 errors occur the correct original code word that gave rise of the erroneous word can be identified as the only code word at a distance of less than d 2 from the received word n k d is a linear set of 2k code words each of length n with minimum distance d Steane s Algorithm Parity Check Matrix …