Shor’s Algorithm in Quantum Computing

Shor’s 3-Qubit Bit-Flop Code:

A bit-flip is the same as an X gate in the quantum computing context:

|0> → X |0>=|1>

|1> → X |1>=|0>

|Φ> =|0>+|1>→ X|Φ> =|1>+|0>

The concept of the classical 3-bit repetition code can be imitated to protect a qubit against bit-flip errors. Both encoding and error correction, however, it is done by quantum operations. Assume a qubit in some unknown state:

|Φ> = α|0> + β|1>

The embedding of this single qubit state, α|0> + β|1>, as three entangled qubits provides protection from bit-flip errors:

(α|0> + β|1>) ⊗ (α|0> + β|1>) ⊗ (α|0> + β|1>)

can’t be performed.

The 3-qubit code encodes a single logical qubit into three physical qubits with the property that it can correct a single-bit flip error. Assume the two logical states of the qubit are defined as –

|0>_L = |000> and |1>_L = |111>

Thus, an arbitrary single-qubit state Ψ = α|0> +β|1> can be mapped to

α|0> + β|1> → α|0>_L + β|1>_L
= α | 000> + β|111>
= Ψ_L

Shor’s 9-Qubit Code:

This code employs 9-qubits for each logical bit and can correct X bit-flip, Z phase-flip errors or a combination of both (Y = ZX) on a qubit. It is based on the concept of majority voting and assumes the presence of a single erroneous qubit bit-flip and phase-flip errors which can correct an arbitrary error on a single qubit.

Shor’s code is based on the 3-qubit repetition code and encodes a single logical qubit into three physical qubits.

|0>_L = |000> and |1>_L = |111>

It then uses two separate steps in the following order for encoding a physical qubit.

i. Employe phase encoding for the qubit state.

Ψ = α|0> + β|1>

to guard against phase-flip errors.

ii. Next, encode each of the resulting three qubits to protect each against bit-flip errors.