it may be possible to check twice as many cities in half the time using a quantum computer.
Table 4.2. Church–Turing computability thesis.
| Church–Turing thesis | Problem answered |
| Church–Turing (original) | Is the problem computable? (ignoring time) |
| Church–Turing (extended) | Is the problem efficiently computable in time? |
4.4Quantum Error Correction
4.4.1 Practical concerns and status
One of the biggest challenges to the potential instantiation of universal quantum computers is quantum error correction. Qubits are more fragile than classical bits and need to be error-corrected if they become damaged. It is too early in the development of quantum computing to estimate exactly which hardware approaches will require error correction and at what point (with certain numbers of qubits). However, since qubits are affected by both state decay and environmental noise, some kind of error correction is likely to be required. Methods for error correction are largely a research effort at present, and more clarity may arrive with implementation.
The two kinds of commercially available systems (as of June 2019) use superconducting circuits, but in different architectures. There is the standard gate model (with 30–70 qubits) and the quantum annealing model (with 2048 qubits). The trade-off is that the gate model aims to be more of a universal quantum computer, whereas the quantum annealing model can only accommodate certain classes of optimization problems. On the one hand, annealing machines harness the natural evolution of quantum systems over time to settle into the lowest-energy state (a minimum). The intermediate operation of the quantum process cannot be controlled. On the other hand, gate model machines seek to control and manipulate the evolution of the quantum system at each moment in time, which suggests that they can be used to solve a much larger and more general set of problems. For error correction, the benefit is that with less manipulation, less errors arise, and the annealing machine does not require the same kinds of error correction that the gate model machine does, at least at the current number of qubits.
Table 4.3. Quantum computing systems and error correction.
Other approaches to quantum information systems claim that error correction is not an immediate concern (Table 4.3), although the path to scaling up the number of qubits is perhaps less clear than with superconducting circuits. These other methods, although still in the research phase, are designed such that error-correction requirements may be greatly reduced. These systems include ion trapping, fermion braiding, and photonic quantum computing. In particular, the fermion braiding approach is robust to noise since changes in geometry do not have an effect, only changes in topology, and the errors can be corrected in hardware instead of software.
4.4.2 Quantum state decoherence
Quantum information has different properties than classical information and is much more sensitive to being damaged by the computing environment. Whereas in a classical system, the idea is to pack in as many bits as possible, in a quantum system, the aim is to have only as many high-fidelity qubits as can be effectively controlled, and scale up with that level of integrity. It is difficult to isolate systems from the environment well enough for them to have useful quantum behavior. The quantum states can decohere (decay) quickly and become damaged by the noisy (imperfect) environment. It is likely that some kinds of error correction will always be necessary in quantum systems. Even if a perfect computing environment without any noise were to be obtained, there is still the natural property of qubits to decay that must be addressed. The excited state of qubits ultimately decays to the ground state due to being coupled to the vacuum fluctuation (the vacuum fluctuations of electromagnetic fields are unavoidable). Therefore, it is necessary to encode the quantum states to be protected in such a way that they can be error-corrected to remain robust. These requirements introduce the notions of qubit lifecycle and qubit management in quantum information systems.
4.4.3 Entanglement property of qubits
Unlike classical information, which can be examined arbitrarily many times to determine if it has changed, quantum information cannot be measured directly because it will change or destroy the information. However, quantum information has the interesting property of entanglement. The entanglement property refers to quantum particles being entangled with one another. Quantum particles are not isolated and discrete, but rather correlated, both with each other, and the history of the system. Particles and previous states are correlated as part of the fuller information landscape of the quantum system. Hence, quantum error correction is performed by taking advantage of the entanglement property of qubits. The insight is that due to entanglement, it is possible to measure relationships between qubits without measuring the values stored by the qubits themselves.
4.4.3.1Error-correction codes
Quantum error correction uses the entanglement property to smear out the information of 1 qubit onto 9 entangled qubits (in the basic case). The idea is that the information of 1 qubit can be stored on a highly entangled state of several qubits. A local point, 1 qubit, can be smeared out, and represented with a larger number of qubits. The auxiliary qubits are called an ancilla (ancillary qubits). Quantum error correction is typically performed by introducing an ancilla in the form of additional qubits with which the qubit of interest is entangled. Entangling the qubit of interest with ancillary qubits allows the qubit to be protected by smearing out its information over a larger system. The qubit of interest can be error-checked since its information can be examined indirectly through the entangled qubits (through parity measurements). In this way, quantum error correction is used to test the integrity of quantum information without damaging it. Quantum error correction makes quantum computing feasible, in that a quantum computer can tolerate some degree of noise in the environment by correcting errors. Many different kinds of quantum error-correction codes (encoding schemes) have been proposed. Shor’s code uses a 9-qubit smear, and others require fewer qubits (a 7-qubit code and a 5-qubit code, for example) (Shor, 1995).
4.4.3.2Classical error correction
In general, all forms of computing systems use error correction to check for data integrity. An error-correcting process seeks to determine whether information has been damaged or destroyed and restores its initial state. Error correction is well-understood in classical logic. For example, there could be a memory chip storing bits that is hit by a cosmic ray. If one bit in a 32-bit word is flipped, there are many known ways of recovery. One frequently used method is having many copies of the data. With redundancy, having several copies of the information means that a mechanistic majority-voting mechanism can be used to confirm the intact version of the data. With quantum logic, however, error correction based on making redundant copies of the same information cannot work. It is not possible to copy quantum information due to the no-cloning theorem, which states that it is impossible to create an identical copy of an arbitrary unknown quantum state. Therefore, quantum error-correction methods such as those based on entanglement are needed.
4.4.3.3Shor’s code
It is not by accident that Shor’s code, the first quantum error-correction code discovered, is 9 qubits. Nine qubits is the smallest ancilla that can be used to confirm that the original qubit was not flipped (changed or damaged), by checking various pairwise sequences of possible flipping along the X, Y, and Z axes of the qubit. A simple error-correcting code could instantiate a single logical qubit of data as three physical qubits for each scenario of the three axes. With pair-wise evaluation, it is possible to determine whether the first and second qubits have the same value, and whether the second and third qubits have the same value, without determining what that value is. If one of the qubits turns out to disagree with the other two, it can be reset to their value. Further, the pair-wise evaluations might be performed in both time and space suggesting quantum information processing architectures with time speed-ups.
Shor’s