Complex problems in optimization and encryption that now tie up supercomputers for years will one day be solved in seconds, some have predicted, by quantum computers.
But this will not come to pass, says Tiffany Jing Li, without quantum error-correction (QEC) codes that let quantum devices compute reliably in the fragile quantum world. Li, an associate professor of electrical and computer engineering, has invented several new classes of QEC codes with support from NSF.
Conventional computers encode information as bits. Quantum computers encode data in electrons, photons, nuclei and other quantum states as quantum bits, or qubits. A bit can exist in two different states – 1 or 0. A qubit can be 1, 0, or a “superposition” of one over the other. Additional states are enabled by entanglements between qubits.
But in the quantum world of atoms and subatomic particles, the slightest noise degrades signal and data quality and undermines the ambiguity and entanglements that give quantum computing its potential. This frustrates efforts to achieve fault-tolerant quantum computing using conventional error-correction codes, says Li.
In conventional computers, says Li, errors that occur during transmission can be corrected by encoding data to introduce redundancy. When transmission is completed, the original data is retrieved through decoding.
The “no cloning theorem” of quantum mechanics, however, does not allow replication of a quantum state, because that which is arbitrary and unknown cannot be copied. Another rule postulates that observation and measurement change the quantum state and make restoration impossible.
This would seem to preclude the possibility of QEC coding. If a decoder cannot accurately observe a possibly corrupted qubit value, it cannot develop an appropriate decoding procedure.
In 1995, three researchers overcame these obstacles by showing that the information in one qubit could be spread onto an entanglement of qubits. Their CSS stabilizer code is the basis of most QEC codes yet developed.
“The vast majority of existing quantum codes is restricted to this special formalism,” says Li. “Unrestricted forms offer richer coding choices and better error-correction performances, but formal methods are lacking to construct them.”
Two years ago, Li and her group invented the first class of unrestricted (non-CSS) stabilizer LDPC (low-density parity-check) codes based on classical binary codes. In contrast to previously reported design methods, many of which resulted in only a single code with a fixed rate and length, the new design developed by Li’s group revealed a rich family of codes with a wide range of rates and lengths.
More recently, Li and her group have invented systematic ways of constructing unrestricted and restricted stabilizer codes. They have designed the first feasible quantum decoding algorithm for unrestricted stabilizer convolutional error-correcting codes, and they have successfully simulated and demonstrated the codes’ error-correction performance.